属性文法的左递归移除对语义自动迁移的影响

理论计算机科学电子笔记110（2004）133-148www.elsevier.com/locate/entcs属性文法中左递归移除时语义规则的语义保持迁移我是洛夫冈·罗曼 GuênterRiede wal d a MarkusStoy a罗斯托克大学计算机科学系18051 Rostock，德国摘要有几个源代码到源代码转换的工具是基于自顶向下的解析器的。这限制了用户使用没有左递归的语法。移除给定语法的左递归通常会使其不可读，从而阻止用户专注于原始语法。此外，问题出现了，如果工具是基于与原始语言定义不同的语法实现的，那么它是否实现了原始语言的语义。此外，现有的原始语法的语义实现不能直接重用。本文有助于该领域的自动迁移的软件（这里的语义规则）引起的语法变化。它修改了删除左递归的语法适应的上下文中，并证明，而在删除左递归的同时，语义规则可以自动迁移。因此，程序员可以继续使用左递归语法的语义规则。这个问题得到了解释和公正。关键词：文法工程，文法调适，属性文法，语意规则迁移，转换，剖析1介绍本文考虑左递归删除对与文法规则相关的语义的影响。我们的出发点是在已经为语法编写了语义规则之后，需要进行语法工程。我们将证明，在自动左递归删除属性语法语义规则可以自动迁移。语法工程在软件开发和维护中都存在语法工作。语法用于描述1571-0661 © 2004 Elsevier B. V.根据CC BY-NC-ND许可证开放访问。doi：10.1016/j.entcs.2004.06.006134W. Lohmann等人理论计算机科学电子笔记110（2004）133数据，以获得用于操纵这些数据的工具，或用作开发人员之间的参考，例如，语言的定义。与其他软件工件一样，语法也会发生变化，例如，使其可用于解析器生成的适应性、语法的演变（语法校正、语言的变化和扩展）、从现有工具或文档中恢复语法以及语法的重构（使其更具可读性，部分更好地可重用，例如用于适于几种语言方言的工具）。移除语法中的左递归是对语法的一种修改，以适应技术需求。许多句法结构都是用递归来自然表达的，通常是左递归和右递归。然而，有一些工具，如ANTLR，JavaCC，TXL，基于Prolog的工具，以某种方式处理递归下降解析器生成，以便于与语义结合[21]，这将落入无限递归。左递归的移除在编译器构造中已经有40多年的历史了，并且大多被认为是wrt。上下文无关语法或编译器的开发。然而，左递归移除的必要性不仅出现在编译器构造中，而且出现在语言开发、原型设计和软件维护中，特别是对于已经使用和测试过的语法的适应。技术挑战第一个问题是移除左递归会导致语法可读性很差。更精细的语义规则是必要的。然而，如果可能的话，用户希望使用最容易理解的语法，甚至是参考语法。通常使用EBNF重写语法，其中左递归变为迭代，这可能导致循环中的语义问题。其次，语言定义由语法和语义定义组成。如果由于技术需求而修改语法，这将导致语义的改变。语言结构的意义是不变的吗？最后，如果已经有了左递归语法的语义规则（例如，作为逻辑语言给出），那么它们是如何被改变所影响的？它们可以被重新使用还是全部丢弃？结果和好处我们认为，与原始语法的语法符号相关联的语义仍然可以在自动左递归去除后重建这将被证明是S属性语法。我们将讨论，如何的方法可以推广到多通道属性gram- mars。程序员从我们的方法中受益，因为他们现在可以处理类似于引用语法的语法，即可能包含左递归的语法。 语法和语义规则的适应可以 可以自动完成，并且可以作为预处理器实现，如图1所示。该方法可以与上述工具（例如ANTLR，基于Prolog的工具）相结合。W. Lohmann等人理论计算机科学电子笔记110（2004）133135pppKFig. 1. 使用该方法文件的其余部分第2节回顾属性文法的概念。第三节用算术表达式的小例子来说明第四节中语义规则转换的基本思想。第5节给出了一个解释。第6节讨论了其他类型的属性文法。第7节报告了迄今为止的实际经验。第8节指出了一些相关的工作，然后在第9节中总结了论文。2属性文法本节回顾属性语法（AG）的定义。下面的形式定义与[1]类似。语义条件，可以限制生成的上下文无关文法的语言被省略，而不失我们的方法的一般性。在[1]中给出了语义。关于属性语法的起源，读者可以参考Irons [6]和Knuth[9]。没有语义条件的属性文法是四元组AG=（G，SD，AD，R），其中(i) G=（VN，VT，P，S）是上下文无关文法的基础。VN和VT是非终结符和终结符的集合，V = VN<$VT和VN<$VT=<$。P是产生式规则的有限集合，S∈VN表示起始符号，p∈P会写成p：Xp→X... X，其中np≥ 0，X∈VN且0对1 ≤k≤ np，X p ∈ V.1np0(ii) SD=（TY PES，FUNCS）表示语义域。 TY PES是一个136W. Lohmann等人理论计算机科学电子笔记110（2004）133Kp∈∅01npKK00KK00KKKkaKKipp有限集和FUNCS一个有限集的总功能与类型1×... ×类型n→类型0，n≥0，类型i∈TY PES（0≤i≤n）。(iii) AD=（AI，AS，TY PE）表示属性。 每个符号X∈V得到有限个合成和继承的相关属性集，AI（X）和AS（X）。 A（X）=AI（X）<$AS（X）和AI（X）<$AS（X）=A=<$X∈VA（X）（对于AI和AS类似）。如果有必要区分的话，某个符号X的属性a可以写成X. a对于a∈A TY PE（a）∈TY PES是a的值的集合（TY PE=a∈ATY PE（a））。(iv) R=p∈PR（p）表示与一个语义规则相关联的语义规则的有限集合生产p∈P。 生产p：Xp→Xp... Xp有一个属性出现次数Xp.a，如果a∈A（Xp）。 的所有属性出现的集合生产p被写为AO（p）。它可以分为两个不相交的定义的出现DO（P）和使用的出现UO（p）的子集，其定义如下：DO（p）={Xp.s|s∈AS（Xp）}<${Xp.i|i∈AI（Xp）<$1 ≤k≤ np}，UO（p）={Xp.i|i∈AI（Xp）}<${Xp.s|s∈AS（Xp）<$1 ≤k≤ np}.R（p）的语义规则定义了DO（p）中属性出现的值如何作为AO（p）中其他属性出现的函数来计算。属性出现Xp.a的定义规则的形式为：Xp.a：= fp（Xp.a1，. ，Xp.am）k ka k1km其中Xp.a∈DO（p），fp：TY PE（a1）×. ×TY PE（am）→TY PE（a），ka∈FUNCS和Xki ∈AO（p），其中1 ≤i≤m。 的发生Xp.a依赖于Xp.ai（1 ≤ i ≤ m）。一个AG是在正常的形式，如果每个语义规则另外保持：Xki.aiUO（p）。每一个AG都可以转化为标准形式。在不失一般性的情况下，我们假设语法必须是正常的形式。AG有几个子类，包括S-属性文法（S-AG）和I-属性文法（I-AG）。对于S-AG，AI=Δ I，计算自下而上进行，即根节点的属性包含节目的确定含义。类似地，对于I-AG是AS=，并且计算是自顶向下的。意义就在叶子里。3示例AG我们使用以下常见的简单示例来演示基本思想：算术表达式的左递归定义。文法的上下文无关部分实现算术运算符的优先级。图2给出了上下文无关文法的左递归移除的一般算法（参见例如[18]）。该算法必须扩展以处理语义规则，FW. Lohmann等人理论计算机科学电子笔记110（2004）133137E0→E1+T{E0.v：=E1.v+T.v}|E1− T{E0.v：=E1.v−T.v}|T{E0.v：=T.v}T0→T1<$F{T0.v：=T1.v<$F.v}|T1/F{T0.v：=T1.v/F.v}|F{T0.v：=F.v}F→N{F.v：=N.v}|（E）{F.v：=E.v}E→ TE′{？个文件夹E′→ +TE′{？个文件夹|-TE'{？个文件夹|{\fn黑体\fs22\bord1\shad0\3aHBE\4aH00\fscx67\fsc输入：G=（VN，VT，P，S），无G-产生式和循环;不失一般性，令V--1NN输出：GJ=（VNJ，VT， PJ， S），带左反射对于i：= 1到N，A，. A}对于j：= 1到i−1，（间接左递归）替换模式A→A β的生成I j由A i→α1β|......这是什么？ | αkβ,端其中A j→α1|......这是什么？| αk are the currentproductions of A j替换模式A i→A i α1的产生式|......这是什么？ |β1|......你好。|..。 | βm{移除直接左递归}其中没有βk以Ai其中Ai'是新引入的非终结符端由A i→β1A i'|......这是什么？|......这是什么？|... |G|G图二、上下文无关文法的左递归移除图三. 简单表达式定义（左），删除左递归（右）因此，在我们的示例中，表达式被正确计算。表达式的左递归属性语法在图3的左侧给出。右边显示了去掉了左递归的上下文无关文法。乍一看，语义规则如何被修改以描述相同的含义并不明显。 为了了解语义规则如何 我们来研究一下表达式1+2*3的计算。 图4描述了构造的抽象语法树以及计算使用原始语法（左）和转换后的语法（右），从转换后的语法可以看出，原始树已被拉伸。给出的转换树的评价给出了基本思想：合成属性的计算被重定向到新引入的非终结符的继承属性（i）。 从树叶中，138W. Lohmann等人理论计算机科学电子笔记110（2004）133E→TE′{E′.i：=T.v，E.v：=E′.v}E0′ →+TE1′{E1′. i：=E0′。i+T。v，E0′. v：=E1′。v}|−TE1′{E1′. i：=E0′。i−T。v，E0′. v：=E1′。v}|{E′.v：= E′.i}T→FT′{T′.i：=F.v，T.v：=T′.v}T0′→ΔF T1′{T1′. i：=T0′。iF。v，T0′. v：=T1′。v}|/FT1′{T1′. i：=T0′。i/F。v，T0′. v：=T1′。v}|{T′.v：=T′.i}F→N{F.v：=N.v}|（E）{F.v：=E.v}E7E7E1+T6T1第一季第T1T2*F3F1 1T' 1+T6第七季第F1F231F22T'6122 *F36T'63图四、1+2*3的属性语法树（左）和无左递归（右）使用合成属性复制结果。因此，中间结果被保留并仅以不同的位置组合到最终值。图5给出了实现这种行为的新语义规则。图五. 移除左递归并迁移语义规则4S-AG变换的一般算法给出了S-属性图的左递归消除算法迁移语义规则的方法保证转换后的语法树的根包含与原始树中的根相同的属性值。下一节将给出一个解释W. Lohmann等人理论计算机科学电子笔记110（2004）1331391na一11na一其中Xp.a=0我我一一见图6。S属性文法的转换，* 表示非终结符的继承（左侧）和合成（右侧）属性左递归移除的算法将被扩展如下（参见：图6）：(i)对于在变换期间新引入的每个非终结符AJ，AS（AJ）=AS（A）(1)AI（AJ）={aJ|a ∈ AS（A）}，其中 TY PE（aJ）= TY PE（a）AJ获取A的所有属性，此外还为A的每个合成属性获取一个具有相同类型的继承属性。(ii) 在产品p：A0→A1α到PJ：Aj0→αAJ1的R（p）={A0.a：= fa（Xp.a1，.，Xp.an）的方式|a ∈ AS（A）}=R（pJ）={AJ.aJ：= fa（XpJ.a1，.，XpJ.an）|aJ∈AI（AJ）}<$(2){AJ0.a：= AJ1.a|a∈ AS（A）}JAJ. aJ，如果X p=A1我我我Xp.ai，否则实际的计算被重定向到继承的属性。对于合成属性，添加了新的复制规则。(iii) 对于产生式p：Ap→β到pJ的平移：ApJ→βAJR（p）={Ap.a：= fa（X1.a1，.，Xn.an）|a ∈ AS（A）}=（三）R（pJ）={AJ.aJ：= fa（X1.a1，.，Xna.ana）|aJ∈AI（A）}<${ApJ.a：= AJ.a|a∈ AS（A）}类似，但没有替换语义规则的参数。(iv) 添加一个新的生产p：AJ→B需要(4)R（p）={AJ.a：= AJ.aJ|a ∈AS（AJ）}.复制规则从每个继承的属性添加到对应（一）（二）（三）（四）（五）Y*A0*A*X*AGA*A1** A'0*A** A'*Y*AG'* A'**A'1* A'*140W. Lohmann等人理论计算机科学电子笔记110（2004）133一我›→›→→|∈∗我一01na一一1na一其中XpJ.afq（. 。 。），如果X p=X⎩a我我综合属性(v) 在生产p：Y→Xβ到pJ：Y→αβ的过渡期间，通过部署q：X→α，R（q）={Xq.a：=fq（.。）的方式|a∈ AS（X）}R（p）={Yp.a：=fp（Xp.a1，.，Xp.an）|a∈ AS（Y）} =R（pJ）={YpJ.a：=fp（XpJ.a1，.，XpJ.an）|a ∈AS（Y）}我我Xp.ai，否则部署上下文无关规则的右侧，语义规则的对应右侧被并行部署因此，YpJ.a是由嵌套函数应用程序计算的，该函数应用程序不符合在第2节中给出的形式。(The嵌套的函数应用程序可以被折叠到语义规则中，以便适当的属性将其删除总而言之，该算法描述了S-属性文法AG=（G，SD，AD，R）的AG AGJ到AGJ=（GJ，SD，ADJ，RJ）的变换，其中G<$→GJ根据左递归去除的一般算法AD<$→ADJ（1）和R<$→RJ（2-5）。5计算属性值命题：对于每个变换AG AGJ，下面的第4节成立：对于可从AG和AG '的上下文无关语法导出的每个词，相同的价值观。此外，在直接左递归移除的情况下，中间结果被保留，尽管在树中的不同位置比在原始树中的位置不同。一般来说，左递归规则的形式A→Aα1|......这是什么？|β1|......这是什么？|... | βm. αi和βj的选择对于论证无关紧要，因此我们假设AAαβ（含α，β）（五）。可以看出，每个这样的规则生成以下形式的符号序列：βαn（cf.例如，[18]），类似于相应的变换规则A→βAJ和AJ→αAJ|-是的图7示出了用于推导βαn的语法树。 αi表示从α可能的不同推导（而不是规则的不同选择）。 注意，通常αi和β可以包含子树通过应用左递归规则创建。 因此，他们需要转化为αT和βT。我们表示α最高层的根节点（森林的所有根）通过Rα，Rα.a表示在这些节点之一处的属性出现。 的T去-（五）=W. Lohmann等人理论计算机科学电子笔记110（2004）133141我我我不An*A0T *An-1**第一名*An-2*...A1** 阿'2*...*一号*A0**恩*卢恩*A'n+1*海恩-111海恩-1卢恩见图7。 βαn的求导树注意到非终结符A位于转换后的产生式的派生树的根处。前提条件（在树上使用结构归纳法）是（6）α∈AS（Rαi）：Rαi.a=RαT.a，α∈AS（Rβ）：Rβ.a=RβT.a基本情况是没有左递归子树的最大左递归(6) 因为αi= αT，β = βT。 因此，我们将不区分αi和αT以及β和βT。为了去除直接左递归，归纳步骤是为了表明，对于图7中描绘的变换，(7)A∈AS（A）：An.a=A0.a因此，我们需要等式(8)i∈ {0，.，n}∈AS（A）：Ai.a = AJi+1.AJ为了证明它是有效的，我们使用推导树深度n上的归纳：基本情况（n=0）：A0.a = f（Rβ.a1，.，Rβ.ana）cf. Def.AJ1.AJ= f（Rβ.a1，... ，Rβ.ana） cf. （三）<$→ A0.a=AJ1.aJ<$a∈AS（A）142W. Lohmann等人理论计算机科学电子笔记110（2004）133诱导步骤（n›→n+1）：An+1.a = f（An.a1，.，An.ana，Rαn+1.a1，. ，Rαn+1.am） cf. Def.AJn+2。aJ=f（AJn+1. aJ1， . . 。 ，AJn+1。aJna，Rαn+1. a1， . . 。 ，Rαn+1. am）cf. （二）Ai. aj=AJi+1。aJj∈{1， . . 。，na}ind. a ssp.<$→ An+1.a=AJn+2. aj<$a∈AS（A）因此，（8）对所有n都成立，我们可以说，计算的中间结果在计算变换树中其他定义良好的节点的继承属性时被保留下来。现在有：i，j∈ {1，.，n +1}： AJi.a= AJj.由（2）得出的结论AT.a = AJ.acf. （三）0 1<$→AT.a=AJ.a0n +1=AJn+1.aJcf. （四）=An.acf. （八）从（5）我们可以得出结论，根中的属性值不会改变通过部署规则的右手边，同时去除间接的左递归。6非S属性文法I-AGs几乎可以类似地处理。属性是自上而下计算和复制的。直观地说，这个过程是颠倒的，即实际的计算是在新添加的合成属性上完成的，并使用现有的继承属性向下复制。在简单的多通道AG中，每个属性可以在特定通道期间计算。我们可以假设每一遍都由一个S-AG或一个I-AG定义。因此，我们的方法可以可以推广到简单的多通道AG。因为多通道AG可以被转换成等效的简单多通道AG，所以也可以处理这样的AG7实践经验原型给出的方法已实现为多通道属性语法的概念证明原型也就是说，它演示了简单的例子的算法，但还没有准备好实际应用。选择TXL [2]进行实施。在实验中，我们使用语法作为W. Lohmann等人理论计算机科学电子笔记110（2004）133143e（V）：-e（E），@"+"，t（T），V是E+T。e（V）：-e（E），@"-"，t（T），V是E-T。e（V）：-t（T），V是T。t（V）：-t（T），@"*"，f（F），V是T*F。t（V）：-t（T），@"/"，f（F），V是T/F。t（V）：-f（F），V是F。f（V）：-num（N），V是N。f（V）：-@"（“，e（E），@”）"，V是E。TXL v10.3（8.3.03）（c）1988-2003皇后大学编译股份公司.Txl.解析示例/exp.ag. 转化...e1（V，V3）：-@"+"，t（T），e1（V，E2），E2是 V3+T。e1（V，V4）：-@"-"，t（T），e1（V，E3），E3是V4-T。e（V）：- t（T），e1（V，V2），V2是T。t1（V，V7）：-@"*"，f（F），t1（V，T2），T2是 V7*F。t1（V，V8）：-@"/"，f（F），t1（V，T3），T3是 V8/F。t（V）：- f（F），t1（V，V6），V6是F。f（V）：-num（N），V是N。f（V）：-@"（“，e（E），@”）"，V是E。e1（V，V）.t1（V，V）.见图8。 原型的输入（左）和输出（右）用的是Laptob [14]。语法在Prolog中被表示为逻辑规则。Pred- icates表示非终结符，@将字符串解释为终结符，而变量是按位置寻址的属性。在图8中，给出了原型的输入（左）和输出（右）。原型正在Prolog中重新实现，以便与Laptob更顺利地集成一个更大的场景我们开始将这种方法应用于一个15年来不断发展的YACC规范1，该规范描述了LPC，一种用于多用户环境中解释脚本的语言2。该语法目前拥有99条规则，共有310种选择，将来可能会发生变化。我们在语法和代码上没有什么特别之处，因为这是一个内核发行版的一部分，一年多以来，对类库进行了复杂的现代化改造。因此，区号有1000个变化。工具支持是可取的，其中每个必要的更改都根据已知的语法用语义规则指定。出于几个原因，选择了基于LL（k）语法的工具。 图9显示了表达式定义的上下文无关语法的摘录。即使没有移除左递归，真正成熟的语法规则也很难阅读。语法规则可以从YACC规范中自动提取，并转换为用于该工具的语法符号。然后，语法的上下文无关部分被重用，通过给出适当的语义规则来指定源到源的转换。然后，可以使用上述方法将转换转换为适合于所使用的工具的形式，如图10所示。有几个技术问题尚待解决。例如，逆-产生式违反了将算法应用于左递归移除的条件。第1http://www.ldmud.de2http：//www.e vermore. 奥尔格144W. Lohmann等人理论计算机科学电子笔记110（2004）133实验0：(some（34个备选方案）左值L_ASSIGN expr %prec L_ASSIGN|exp0 '？' expr0 '：'expr0%prec'？'| expr 0 L_LOR %prec L_LORexpr 0|出口|'expr0|decl_cast expr 0% prec“~”|铸造expr 0% prec '~'|pre_inc_dec expr4 index_expr %prec '['|pre_inc_dec expr4 '['expr0'，'expr0']'%prec'['|L_NOT exp0 |'-'expr0%prec'~'|expr4...expr4：（29个备选方案中的|内联函数|抓住|L_关闭|L_符号|L_FLOAT|'（'note_startcomma_expr'）'|“（"{”note_startexpr_list“}"”）“| L_QUOTED_AGGREGATEnote_startexpr_list’}’|'（''[''：'expr0']''）'|“（"[”m_expr_list“]”“）”|“<（">"）”|'<（' identifier '>' note_start opt_struct_init '）'| expr4 L_ARROW结构成员名称|expr4 index_range| '&'L_| '&'（' expr4 L_ARROW struct_member_name '）'|"&"（“expr4index_expr”）“|'&'（'expr4'['expr0'，'expr0']''）'|"&"（“expr4index_range”）“| expr4 index_expr|expr4 '[' expr0 '，' expr0 ']'|L_...见图9。从yacc规范中提取上下文无关的表达式定义见图10。 重用原始语法进行小型维护转换8相关工作有几种方法可以去除左递归，所有这些方法都只处理上下文无关语法，而不关心属性。左递归删除的一般算法在许多编译器书籍中给出，作为代表，参见Louden [18]。他还演示了左递归如何W. Lohmann等人理论计算机科学电子笔记110（2004）133145避免使用EBNF符号，并使用迭代实现。Rechenbe rg/M？ossenbo？ck[21]使用grammar到syn-tax图的翻译左递归通过将其转换为迭代来处理，同时保留已接受的语言。我们提到了自顶向下工具的使用，因为它们易于使用。Pepper [20]统一了LR（k）-和LL（k）-解析的范式，用公式LR（k）= 3 NF + LL（k）表示。主要目标是一个易于理解的推导方法，易于适应，提供LR解析的功能，同时提供LALR解析的效率。语法被空的非终结符丰富了，这些非终结符不改变语言，但可以携带语义动作，或者可以充当指导归约的断言。语法转换过程中不考虑语义规则。Schmeiser/Barnard [22]修改了自底向上解析的标准表驱动算法，使程序员在使用自底向上解析器时能够使用自顶向下的解析顺序。除了状态之外，规则列表也存储在堆栈中。当规则被减少时，规则列表以适当的顺序连接。我们讨论了语法不仅仅是为了实现编译器而改变的[8]强调了语法软件工程学科的必要性。在[15]中，作者提出了一种为现有语言构建语法的方法。该方法的主要特点是语法标记不是从头开始构建的，而是通过从语言引用、编译器和其他工件中提取它们来恢复的。它们提供了一个结构化的过程来恢复语法，包括原始提取语法的自动转换和解析器的推导。语法工程工具支持的例子是语法部署工具包（GDK）[7]和SDFT转换的框架（FST）[16]。GDK在将语法规范转换为工作解析器的过程中提供了支持。FST支持基于语法定义形式主义SDF的语法调整，例如，EBNF模式被删除（YACCi化）或引入（deYACCi化）。Cordy et al.基于问题特定语法[3，4]实现敏捷解析是语法工程的示例，也是Wile [23]从具体语法导出抽象的转换的示例关于一般语法适应的理论工作可以在[11]中找到。 一组运算符与属性一起定义。操作符可用于描述语法适应。我叫我叫他。 [12，13，10]所有工作都在rammarevolution上进行。[10]中提出了一个元编程的通用框架和一个操作符套件，其中操作符对程序转换、合成和组合的模式进行了建模例如折叠和展开操作，146W. Lohmann等人理论计算机科学电子笔记110（2004）133说明性程序的框架，即属性语法，逻辑程序。通过折叠元素分析和传播参数还有一个与重构的关系[5，19]，它可以应用于语法和转换规则。实际上，左递归的移除可以被认为是语法的复合重构。与本文相关的是一篇关于语法扩展后转换规则自动迁移的论文[17]。该方法可用于在语法扩展之后重用转换规则，以便它们不会与新语法的代码中断。给出了如何使重写规则能够在重写模式中存储布局信息的问题。在重写器的层面上，这些信息是不可见的，因此该方法有助于降低用户重写模式的复杂性9总结发言总结-本文有助于语法适应的工作，并集中在语法生产相关的语义规则。该方法试图为新的语法重用现有的语义规则。此外，它还为程序转换的程序员提供了一个机会，可以在更接近语法规范的语法上指定语义规则，而语法和语义规则可以适应技术需求，这里只剩下递归删除。因此，我们为重写器提供了比工具所需的更简单的语法标记。文中给出了该文法的必要转换步骤，并对该方法进行了论证。该方法的缺点是属性数加倍，并引入了额外的复制规则。虽然增加的复杂性是隐藏的，但问题可能是它增加了工具构造过程的时间开销。每次从规则和语法构建工具时，都必须调整使用原始语法的语义规则。在解释性使用环境的情况下，例如在Prolog设置中，这对于较大的语法来说可能会变得令人讨厌。未来的工作我们将使这种方法在现实生活中可用，目前的状态仍然是一个薄弱的原型。仍然存在重复生产的问题。该算法可以通过使用惰性评估策略来改进。该方法将仅在S-AG中实现，所有其他变体都自动支持。也可以构造术语而不是应用操作，然后在根属性中解释术语。将来，我们将在维护过程中寻找进一步的语法调整，并调查是否以及如何可能对语法使用的软件和相关的语义规则W. Lohmann等人理论计算机科学电子笔记110（2004）133147语法的问题我们将研究如何将这种组合的语法/转换规则适应连接到更复杂的操作。确认我们要感谢匿名审稿人的建议，感谢Anke Dittmar对论文早期草稿的评论。我们很高兴与RalfLa？melon共同完成语法工程和元编程。Anke Dittmar提出了通过使用惰性评估策略来改进算法的想法。Jim Cordy帮助我们解决了有关TXL的问题。引用[1] 阿尔韦托， H、 属性文法简介， in：H. Alcohol和B. Melichar，编辑，Attribute Grammars，Applications and Systems（SAGA 1991），LNCS545（1991），pp. 1-15。[2] Cordy ， J. ， T. Dean ， A. Malton 和 K. Schneider ， Source Transformation in SoftwareEngineering using the TXL T transformation System ， Journal of Information andSoftware Technology44（2002），pp.827-837[3] 迪恩，T.，J. Cordy，A. Malton和K. Schneider，Grammar Programming in TXL，in：Proc.Source Code Analysis and Manipulation（SCAM[4] 迪 恩 ， T. ， J. Cordy ， A.Malton 和 K.Schneider ， Agile Parsing in TXL ， Journal ofAutomated Software Engineering10（2003），pp.311-336[5] Fowler，M.，K. Beck，J.Brant，W.Opdyke和D.Roberts，[6] Irons，E.T.，A syntax-directed compiler for ALGOL 60，Communications of the ACM4（1961），pp.51比55[7] Ja n Kort and dRalfLaémmelandChr isVerh oef，TheGramarDeploymentKit，in：M. G. 诉D.布拉恩德河。李文，等.电子计算机技术与应用.北京：科学出版社，2002.[8] Klint，P. 、R. Lémmel和C. Verhoef，Towardsaneneine rr ama rar einedis in e d i s i ned i n e disi s ine r ama ra r a r are（2003），32页，提交期刊出版。[9] Knuth，D.E、上下文无关语言的语义学，数学系统理论2（1968），pp。127比145[10] 拉梅尔河，论文，罗斯托克大学计算机科学系（1999年）。[11] 莱梅尔河，GrammarAdaptation，in：Proc. F或M方法欧洲（FME）2001，LNCS2021（2001），pp. 550-570[12] 莱 梅 尔 河 ， EvolutionofRule-BasedPrograms ， JornalofLogicandAlgebra icProgramming（2004），Special Issue on Structural Operational Semantics;待出现。[13] 拉梅尔河 和G. 李文，属性文法及其应用研究，北京：北京大学出版社，1999年。37-56，INRIA，ISBN 2- 7261-1138-6。148W. Lohmann等人理论计算机科学电子笔记110（2004）133[14] 拉梅尔河 和G. Riedewald，PrologicalLanguageProc eessing，in：M. G. 诉D. BrandandD. Parigot，editors，Proceedings of the First Workshop on Language Descriptions，Toolsand Applications （ LDTA '01 ） ， Genova ， Italy ， April 7 ， 2001 ， Satellite event ofETAPS'2001，ENTCS 44（2001）. 网址http://www.elsevier.com/locate/entcs/volume44.html[15] 拉梅尔河 和DC。 Verhoef，Semmi-autom atic GramarRecovery，S oftware-Practice&Experience 31（2001），pp. 公元1395-1438年。[16] L ？ m mel 河 和 G. Wachsmuth ， TransformationofSDFsyntaxdefinitiontheASF+SDF Meta-Environment ， in ： M.van den Brand 和 D. Parigot ， editors ， Proceedings of the FirstWorkshop on Language Descriptions，Tools and Applications（LDTA[17] Lohmann ， W. 和 G. Riedewald ， Towards automatical migration of transformation rulesafter grammar extension ， in ： Proc.第 七 届欧 洲 软 件 维 护 和 再 工 程 会 议 （ CSMR'03 ）（2003），第10页。30比39[18] Louden，K. C.的方法，“Compiler construction: principles and practice,” International ThomsonPublishing,[19] Opdyke ， W. F. 和 R. J. Johnson ， Refactoring ： An Aid in Designing ApplicationFrameworks ， in ： Proceedings of the Symposium on Object-Oriented Programmingemphasizing Practical Applications，ACM-SIGPLAN，1990，pp. 145-160[20] Pepper，P.，LR解析=语法转换+LL解析，技术报告CS-99- 05，柏林工业大学（1999）。[21] Rechenberg，P. 和H。 Müossenbüock，“Ei n Compile r -Gene ne ra to or r fur？r Mikr o c o m put e r，“C a rl Hanser Verlag ，1985 ，德文。[22] Schmeiser，J.P. 和D.T. Barnard，Producing a top-down parse order with bottom-upparsing，Information Processing Letters 54（1995），pp. 323-326[23] 怀 尔 ， D. ， 抽 象 语 法 从 具 体 语 法 ， 在 ： Proc.International Conference on SoftwareEngineering（ICSE'97）（1997），pp. 472-480