参数化LR解析：理论与实现

理论计算机科学电子笔记110（2004）115-132www.elsevier.com/locate/entcs参数化LR分析Peter Thiemann and Matthias Neubauer彼得·蒂曼和马蒂亚斯·诺伊鲍尔1，2InstitutfurInforrmatikUniversit？aFreiburgGeorges-K？ohler-Allee079D-79110 Freiburg，Germany摘要常见的LR解析器生成器缺乏用于定义生成的重复模式的抽象设施。虽然有生成器能够在产品的右侧支持正则表达式，但没有生成器支持语法中的用户定义模式参数化LR解析扩展了标准LR解析技术，允许使用参数化非终结符的语法。生成器可以通过两种方式实现这样的语法，通过扩展或直接。我们开发了直接实现所需的理论，并表明它会导致显着更小的解析表，它具有更少的解析约束比扩展的语法。如果与非终结符相关的语义函数关于参数是多态的，则参数化非终结符的属性求值可以以与之前相同的方式进行。我们已经实现了参数化LR解析的本质，部分评估为基础的LR解析器生成器的方案的上下文中。关键词：LR分析器生成器，产生式，属性求值，多态性，部分求值。1介绍LR解析[11]是语言设计者工具箱中的一个强大工具。它提供了一种解析算法，可以在线性时间内工作，上下文无关的语法。LR解析的理论已经在许多著作中进行了探索，它已经成为编译器构造讲座和教科书的标准部分[1]。它也构成了整个系列的基础1电子邮件地址：thiemann@informatik.uni-freiburg.de2电子邮件地址：neubauer@informatik.uni-freiburg.de1571-0661 © 2004 Elsevier B. V.根据CC BY-NC-ND许可证开放访问。doi：10.1016/j.entcs.2004.06.007116P. Thiemann，M. Neubauer / Electronic Notes in Theoretical Computer Science 110（2004）115-132从yacc/bison [10，5]开始的解析器生成工具，其思想几乎适用于任何编程语言。虽然工具在解析操作的模块化和解析与扫描规范的集成方面有了一些发展，但实际的原始内容，即语法，在解析器规范中仍然保持其原始形式。由于大型文法很可能会产生数百个结果，因此文法维护可能成为一项乏味的任务。因此，令人惊讶的是，没有一个解析器生成器具有在语法规则上引入抽象的功能。在LR文法中引入某些缩写机制的主要尝试是考虑规则的正则右侧[3]。然而，只有少数LR解析器生成器（例如，，[7]）直接支持常规的右手边或扩展的BNF。因此，LR解析器生成器的典型语法下面是一些随机选取的语法中该模式的使用次数的例子。• 带分隔符的列表（七次）DelimTypeSchemes：/*empty*/|NEDelimTypeSchemes;NEDelimTypeSchemes：TypeScheme| NEDelimTypeSchemes ’,’ TypeScheme;• 普通列表（五次加上两个非空列表）TypeVars：/*空*/| NETypeVars;NETypeVars：TypeVar|NETypeVarsTypeVar;• 可选项目（两次）Imports：/* empty*/| 进口类型;通常，甚至语义动作也是一致的，或者可以很容易地使其一致。我们的建议几乎直接来自这些意见。在语法规则的右侧，我们不再依赖于一组固定的（常规）运算符，而是以可参数化的非终结符的形式提供了一组任意的、用户可定义的运算符。这些非终结符像函数一样使用。它们可以通过产品右侧的实际参数调用。必须注意适当地限制实际参数，例如，仅限制为一个非终结符或一个形式参数。在不限制实际参数的情况下，我们将获得宏文法的概念，它严格地比上下文无关文法更强大[4]。通过我们提出的扩展，语法作者可以一次性地编写与上面展示的模式相对应的参数化产生式。P. Thiemann，M. Neubauer / Electronic Notes in Theoretical Computer Science 110（2004）115117参数化的非终结符集可以在模块中收集，并在语法之间重用。下面的示例显示了上述语法模式的参数化规则SepList（Sep，Item）：/* 空 */| NESepList（Sep，Item）;NESepList（Sep，Item）：Item| NESepList（Sep，Item）Sep Item;List（Item）：/*空*/| return（）;NEList（项目）：项目| NEList（Item）项目;Option（Item）：/*empty*/| 项目;对于上面的例子，定义通用的语义动作也是有意义的。唯一的要求是这些动作在参数的语义值方面是多态的。因此，SepList（Sep，Item）和List（Item）都可能返回ListItem类型的值，Option（Item）可能返回Maybe Item类型的值。 当从用实际非终结符实例化的参数化非终结符返回时，应该发生类型特定的语义操作实现参数化LR解析的一种方式是通过相对于实际上单独实例化为参数的所有非终结符来单独地指定参数化非终结符。由于我们对实际参数的限制，这种特殊化很容易终止。然而，事实证明，直接为参数化语法开发理论会产生更小的解析表（因为参数化部分可以共享），并且有时避免解析冲突。我们已经扩展了LR（k）解析器生成器Essence [17]来生成参数化的LR（k）解析器。执行工作的初步试验令人鼓舞。概述在发展参数化LR分析理论之前，我们在第2节中对形式语言理论进行了一次例外，向读者介绍了宏语法和宏语言。在定义了一个适当限制的宏语法概念之后，第3节介绍了参数化LR解析的基本定义。第4节定义解析算法，从非确定性规范开始，然后定义冲突的概念以获得确定性解析器。第5节专门讨论属性评估。 它定义了一个类型系统，将多态类型分配给参数化的非终结符。第6节描述了我们在118P. Thiemann，M. Neubauer / Electronic Notes in Theoretical Computer Science 110（2004）115-→{·}⇒⇒Essence的上下文，Scheme的解析器生成器最后，第7节考虑了相关的工作，第8节总结并概述了一些未来的工作。2宏语法为了正确地定义宏文法，我们需要从泛代数中得到一些标准的定义。一个签名是一个有限集合N和一个元函数a的对Γ =（N，a）：NN，非负整数的集合。具有变量X的Γ-项的集合TΓ（X）（与N不相交的集合）归纳地定义为：• X<$TΓ（X）• （n ∈ N，t1. t n∈ TΓ（X），A ∈ N）a（A）= n <$A（t1，. ，tn）∈TΓ（X）.定义2.1宏文法是一个四元组（Γ， N，P，S），其中Γ =（N，a）是一个签名，N是非终结符，N是一个有限的集合，终止符号，P<$N×TΓJ（T<$N）是宏产生式的有限集合，S∈N，a（S）= 0是起始符号. 签名ΓJ将Γ扩展为 一个二元运算符·（连接）和一个常数ε（空字符串）。生产受到以下限制。 若A→w∈P当a（A）= n时，则w∈TΓJ（n ∈ {0，.，n-1}）。宏语法使用以下关于TrJ（k）的导出关系k• 若A → w ∈ P，则a（A）= n，t1... t n∈ TΓJ（n），则A（t1，.，t n）tw [0] →t1，.，n-1 <$→t n]，以及• 若f ∈ Γ J，a（f）= n，t1. t n∈ TΓJ（n），t i∈ tJi，将n f（t1， . . . 我. . . . ，tn）n=f（t1， . . . ，tJI， . . . ，tn）。也就是说，该关系包括所有项对，并且在compat下是封闭伊比利河很平常，关系。表示导子的自反传递闭包一个词在语言中是由语法决定的，w∈T·，ε（ε），它可作为上述两种情形中的一个基本元素。通常，推导关系被限制为由内而外（IO）或由外而内（OI）的替代非终端。IO减少A（t1，.，t n）n =10w [0] →t1，.，n−1<$→t n]仅当t1，.，tn∈T·，ε（ε）（ydot o ntOI归约OI的归约规则与for相同，但compat-ε仅限于f，ε（归约不进行到参数位置）。P. Thiemann，M. Neubauer / Electronic Notes in Theoretical Computer Science 110（2004）115119这两种语言分别称为IO宏语言和OI宏语言。他们已被详细调查[6]，我们回顾他们的一些属性如下。3(i) 一般来说，在IO归约下从文法生成的语言不同于在OI归约下生成的语言。(One对应于按值调用，另一个对应于按名称调用。）(ii) IO宏语言和OI宏语言的类是不可比较的。(iii) IO宏语言和OI宏语言是介于上下文无关语言和上下文敏感语言之间的严格的语言层次结构[4]。我们在这里介绍的宏语法只对应于上面提到的层次结构的第一层。然而，在他们的全面一般来说，它们可以描述不是上下文无关的语言例如，前一个缓冲区放大器会将数据集{anbncn|n∈N}：S→F（ε，ε，ε）F（A，B，C）→ABCF（A，B，C）→F（aA，bB，cC）在这里，我们冒昧地命名了F的参数，而不是使用定义中的编号方案。由于我们只对帮助定义上下文无关语言的抽象感兴趣，因此我们需要限制一般定义。定义2.2限制宏文法是一个宏文法（Γ，r，P，S），其中每个产生式具有形式A → t1···t m（对于m ∈ N），使得对于每个1 ≤i≤m，或者ti∈ r，或者ti= B（s0，.，s l−1）其中l = a（B），对于每个0 ≤j 0，则写为[A→t1···ti···tm，v]，如果i= 0，则写为[A→·t1···tm，v]标准理论定义了一个非确定性有限自动机，它具有ε转换，LR项的集合作为状态。在参数存在的情况下，自动机构造需要被推广到与有限自动机相比具有额外类型的弧的转换图。这个图的构造需要--和标准情况一样--计算规则右侧的k但是，由于右侧现在可以包含参数，因此此计算必须相对于参数实例进行。122P. Thiemann，M. Neubauer / Electronic Notes in Theoretical Computer Science 110（2004）115-KKKK1111定义3.2一个参数实例是一个空非终结符的元组C=（C0，. ，Cm−1）.参数实例化（对于C）是元组s =（s0，.，s l−1）的空非终结符或参数引用（即，，0.. m− 1）。参数实例化s对参数实例的应用s（CC产生新的参数实例s（C）= D =（D0，. ，D l−1）其中，如果s i是零值非终结符，则D i = s i，如果s i = j，则D i= C j，参数引用。著名的构造产生式右边的第一个-k集合需要相对于实例进行参数化。定义3.3关于实例C的右侧项的k-前缀的集合（关于M）定义为：第一个C（ε）={ε}第一个C（α·β）={prefix（vw）|v∈firstC（α），w∈ firstC（β）}k k k k第一个C（a）={a}f tC（i）={f t（）（δ）|C i→δ∈P}KKF tC（B（s））={F ts（C）（δ）|B→δ∈P}其中prefixk（a1. a m）= a1.其中l = min（k，m）。例3.4在例2.4中，非终结符N和L出现在两种情况（C，A）和（C，E）中。分别是，第一（C，A）（N）={c}第一（C，A）（L）={ε，c}第一（C，E）（N）={c，{，[}第一（C，E）（L）={ε，c，{，[}定义3.5PLR（k）转换图的节点是PLR（k）项和弧，标记有终结符、非终结符、参数或参数实例。首先，我们需要两个辅助概念。路径X0... X n在X j−1和X j之间有一条标记为lj的弧，它有关于B的参数实例C，如果• n= 0，C=B• n>0，或者l n=（s），X0. Xn-1具有关于B的参数实例D，并且C=s（D），或·ln不是实例化，并且X0. X n−1有关于B的参数实例C。一个节点X有参数实例C，如果有一个空的非终结符B，·P. Thiemann，M. Neubauer / Electronic Notes in Theoretical Computer Science 110（2004）115123（C（C（C（C（C，A）（C，A）→ ∈ →·BK−→KG.S −>。EES −>E。（（E −>。“c”CE（）E −>。{”L（C，A）“}E −>。[”L（C，E）“][C −>。“、”、（E −>“{”。L（C，A）“}”E −>“[”。L（C，E）“]”LC−>“，”。L−>。L −>。N（0，1）E −>“[”L（C，E）.“]”A −>。“c”“：“ECNN −>。1（C，A）（C，E）1N −>。N（0，1）0 1N]E −>“[”L（C，E）A −>“c”。“：“E：（C，A）（C，E）N −> 1。N −> N（0，1）。0 1 L −> N（0，1）。A −>“c”“：“。0N −> N（0，1）0。11N −> N（0，1）0 1.EA −>“c”“：“E.Fig. 1. 例文法产生式B δ P，终端串v，以及从节点[Bδ，v]到X的路径，该路径具有关于（）的参数实例C转移图被定义为满足以下条件的最小图G• [S→·α，ε]是G的一个结点，如果S→α∈P（S是起始符号）.• 如果X=[A→β·aγ，v]是G的一个结点，则Y=[A→β·aγ，v]是G的一个结点，X−→Y是G中的一条标号弧。• 如果X = [A→β·B（s1，.，sk）γ，v]是G的一个结点e（k≥ 0），B→δ∈P，X有参数实例C，且VJ∈第一个C（γv），则Y = [B→·δ，VJ]是G的一个结点且X（s1，.，sk）Y是G中的一条标号弧。• 如果X = [A→β·B（s1，.，sk）γ，v]是G的一个节点（k≥ 0），则Y = [A →βB（s1，. ，s k）·γ，v]是G的一个节点，X −→ Y是G中的一条标号弧，• 若X=[A→β·iγ，v]是G的一个结点，则Y=[A→βi·γ，v]是G的一个结点G和X−→iY都是G中的一个环。• 若X= [A→β·iγ，v]是G的一个结点，则X有参数实例C=（C0，.，Cl−1），Ci→δ∈P，且vJ∈firstC（γv），则Y = [Ci →·δ，vJ]是a节点G.124P. Thiemann，M. Neubauer / Electronic Notes in Theoretical Computer Science 110（2004）115-.∈.、、例3.6图1是先行k= 0时的示例语法的转换图。在图中，端子符号用双引号表示。项的前看部分被省略（因为它总是空的）。C→·的包含是由实例（C，A）中的N→N（0， 1）·0 1或（C，E）。 A→·c：E的包含是由实例（C，A）中的N→·1引起的。该图显示了参数化非终结符的子图在它们的实例之间共享。在传统的LR解析中，解析器的状态是一组核心项的闭包。在参数化LR解析中，解析器的状态是从空非终结符元组到PLR（k）项集合的映射。闭包的概念对应于状态一致性的概念。定义3.7PLR（k）预状态是一个映射，它将一个空非终结符元组发送到一组PLR（k）项。PLR（k）前状态q相对于转换图G是一致的，如果，（个）对所有C∈dom（q），[A→β·γ，v]∈q（C）且[A→β·γ，v]−→Y在G这意味着Y∈q（s（C））。PLR（k）状态是一致的PLR（k）预状态。函数close将PLR（k）前状态q映射到包含q的最小PLR（k）状态。close函数通过强制执行一致性条件来执行所有参数的实例化。这恰好是PLR解析器中唯一一个实例化发挥作用的地方！goto函数在解析器中实现状态转换。它将PLR（k）预状态和语法符号映射到PLR（k）状态。得到o（q，a）=close，C →{[A→βa·γ，v]|[A→β·aγ，v]∈q（C）}Cdom（q），得到o（q，B）=闭 C<$→{[A→βB（s）·γ，v]|[A→β·B（s）γ，v]∈q（C）}n{[A→βi·γ，v]|[A→β·iγ，v]∈q（C），Ci=B}C∈dom（q）例3.8进一步继续运行示例，部件的初始状态是PLR（0）预状态{（）→{[S→·E]}}的闭合，这是（）<$→{[S→·E]，[E→·c]，[E→·{L（C，A）}]，[E→·[L（C，E）]]}P. Thiemann，M. Neubauer / Electronic Notes in Theoretical Computer Science 110（2004）115125应用以terminal{作为参数的goto函数会产生（）<$→{[E→{·L（C，A）}]，[A→·c：E]}（C，A）→{[L→·]，[L→·N（0，1）]，[N→·1]，[N→·N（0，1）01]}为了比较，具有终端[yields（）→{[E→[·L（C，E）]]}（C，E）→{[L→·]，[L→·N（0，1）]，[N→·1]，[N→·N（0，1）01]}因此，解析状态变成模块化的，参数化部分是可重用的（但需要两阶段映射来计算goto）。4PLR（k）解析算法我们坚持Leermakers[13]并在早期的工作中被一位作者[18]利用。 的想法 功能描述是，分析器被认为是将输入字符串映射到PLR（k）项和新字符串对的非确定性函数。解析器的规格如下：（[A→β·γ，v]，wJJ）∈parse（w）i <$ w=wJwJJ<$γ <$$> wJ<$pre fixk（wJJ）=v4.1非确定性分析在我们的特定情况下，解析器函数依赖于PLR（k）状态，并且-而不是处理非确定性函数-它将返回一组PLR（k）项和未消费输入的对。有趣的是，主解析器函数相对于先前的公式没有改变[17]。[q]（w，c1... cnactive（q））=莱特雷克c0（X，w）=令qJ= goto（q，X）in [qJ]（w，c0c1. cnactive（qJ））在（ {c|α|（A，w）|[A → α·，v] ∈ q，prefixk（w）= v}{c0（a，wJ）} |w = a·wJ，a∈ nextterm（q）}）解析函数[q]有两个参数，输入字符串和一个延续列表。每一个延拓对应于一个函数，每当发生约简时，该函数就在非终结符上移位。调用continuation执行reduce操作：“从解析堆栈中弹出产生式的右侧，然后推送与左侧对应的状态。”为126P. Thiemann，M. Neubauer / Electronic Notes in Theoretical Computer Science 110（2004）115-→K→P读者习惯于基于堆栈的实现，最好把列表c1. 作为解析堆栈的最顶层项的表示。函数c0通过将对应于当前状态（自身）的延续推到延续列表上并更改根据符号X的状态。辅助函数需要扩展到PLR（k）状态。函数nactive：PLR-stateN确定在从状态q可到达的任何状态中执行reduce操作所需的最大连续数。它是q中任何项中点左边的符号的最大数量。nactive（q）= max {|β||C∈dom（q），[A→β·γ，v] ∈q（C）}下一项的另一个辅助功能：PLR-state（）产生一组终端符号，直接在一个状态中的任何项目中的点的右边。nextterm（q）={a|C∈dom（q），[A→β·aγ，v] ∈q（C）}4.2确定性分析上面的非确定性解析函数执行广义LR解析[12，21，15]，因为它“并发”探索所有解析选项为了获得确定性的解析函数，需要识别并排除具有“解析冲突”的状态。与标准LR解析一样，有两种类型的连接：移位-归约连接或归约-归约连接。定义4.1PLR（k）状态q具有移位-归约约束，如果 那里 设B，C∈dom（q）（不一定不同）使得[A→β·aγ，u] ∈q（B）且[B→δ·，v] ∈q（C），其中第一个B（aγu）= v.一个PLR（k）态q有约化-约化连续性，如果B，C∈dom（q）（不一定是不同的）使得[A→β·，v]∈q（B）和[B→δ·，v]∈q（C），其中A→β不同于B→δ.一个受限宏文法是一个PLR（k）文法，如果从文法的转换图中提取的状态都是无冲突的虽然广义移位-归约关系与标准概念相同，但归约-归约关系的限制性更小。下面是一个这个例子展示了与引理2.3中的扩展文法的区别。设G由乘积S→L（A），S→L（B），L→ε，L→0L（0），A→a，B→b其中参数化的非终结符L生成列表。(The示例从写入参数列表的项的两种可选方式的情况提取。扩展文法具有产生式S→LA，S →LB，LA →ε，LA →A LA，LB →ε，LB →B LB，A →a，B →bP. Thiemann，M. Neubauer / Electronic Notes in Theoretical Computer Science 110（2004）115127►∀►⇒并且{[S→·LA]，[S→·LB]}的（标准LR）闭包已经在[LA→·]和[LB→·]之间具有归约-归约约束（忽略任一项与[A→·a]和[B→·b]的移位-归约约束）：S→·LA，S →·LB，LA→·，LA →·A LA，LB →·，LB →·B LB，A →·a，B →·b然而，{（）→{[S→·L（A）]，[S→·L（B）]}}的PLR（0）（）→{[S→·L（A）]，[S→·L（B）]，[A→·a]，[B→·b]}（A）→{[L→·]，[L→·0L（0）]}（B）›→{[L→·]，[L→·0L（0）]}并且--根据我们的定义--不存在reduce-reduce冲突，因为在这两种情况下reduce项的潜在生产都是L→ε。除了对冲突的不同定义外，其余的冲突解决概念都与标准情况一样5属性评价与标准LR（k）解析器一样，PLR（k）解析器可以在解析期间评估S属性语法的解析树中的所有属性出现。新颖之处在于参数化非终结符的属性应该具有多态类型。为了看到这一点，让SepList（Sep，Item）：/*空*/{s1（） }| NESepList（Sep，Item）{ s2（$1）};NESepList（Sep，Item）：项目{ n1（$1）}| NESepList（Sep，Item）Sep Item{ n2（$1，$2，$3）};事实上，Sep和Item可以被视为类型变量，因此NESepList（Sep，Item）的泛型类型的形式为αβ.τ。这种观察可以表述为参数化语法的语义动作的类型系统。它依赖于一个未指定的外部类型判断<$Je：τ，它将一个类型环境<$j和一个表达式e与它的类型τ联系起来。唯一的假设类型可以包含类型变量，并且在顶层允许量化。要导出具有语义动作e的规则的右侧w { e }的类型，如判断Θ w{e}所捕获的：τ需要两个前提。首先，通过判断Θ iw来创建类型化环境来自The非终结符的键入环境，Θ，产生式的右手侧的位置，i，和产生式的右手侧，w。第二，右手128P. Thiemann，M. Neubauer / Electronic Notes in Theoretical Computer Science 110（2004）115-side是类型化环境中的语义动作的类型，如由外部判断je：τ导出。θ1wJe：τθw{e}：τ下一组规则指定了用于键入语义动作的变量环境的构造它假设操作通过位置符号$i引用右侧符号的属性。Θ►i εθi+1wθiaw，$i：θi+1wθ（j）=τθijw，$i：τθi+1wθΘ（B）=θα1. . αm.τ（θ1≤j≤m）Θθsj：τjθiB（s1. . . sm）w，$i：τ[αj→τj]下一个规则指定了一个辅助判断，用于推断参数化非终结符的实例化。Θ（j）=τθj：τΘ（B）=τθB：τ最后一组规则从产品中收集类型。 第一个rule收集所有右侧的类型，确保它们的类型都是相等的，并且结果类型相对于左侧非终结符的参数是多态的。a（A）= mΘ，1：α1，. ，m：α mw i{e i}：τΘ（A）=θα1. . . αm。τ （θ1≤j≤m）α j∈f ree（Θ，α1， . . ，αj−1）Θ<$A → w1{e1}|......这是什么？ |w n{e n}最后，文法中的产生式必须相互一致。dom（Θ）=N（φp∈P）ΘφpP6执行我们已经在Essence的上下文中实现了参数化LR解析，Essence是一个基于部分评估的LR解析器生成器，用于Scheme [17]。与大多数其他解析器生成器的本质不同，例如bison [5]或yacc [10]，无论是构建方式还是使用方式而不是测试P. Thiemann，M. Neubauer / Electronic Notes in Theoretical Computer Science 110（2004）115129以及调试运行几个编辑-生成-编译-测试循环的解析器因此，不需要生成和重新编译来尝试对语法的更改。 最后，一个被称为部分求值的自动程序转换从通用解析器产生一个生成的解析器[16，18]。这保证了一致性并确保了正确性。尽管如此，Essence的用户不需要有任何关于部分评估技术的专门知识。将参数化LR分析集成到Essence中，相当于使其通用分析器适应参数化LR分析。用于PLR的解析器生成器通过将部分评估框架应用于关于PLR（k）语法的经适配的通用解析器来再次解析结果，其方式与针对原始本质解析器所做的方式相同。Essence的通用解析器是对Scheme编程语言中通用LR解析器的功能描述的直接重新表述[13，18]。PLR（k）解析的集成导致实现了PLR语法的附加表示，用于解析项，并实现了first，goto，nactive和nextterm的改编版本。 其余的部分- Essence的基础设施，例如主解析器功能，保持不变。7相关工作解析器组合子[20，8]是在函数式编程语言中指定解析器的一种高度灵活的方式。特别地，使用多态函数和参数化解析器是用解析器组合子构造代码的自然方式。与目前的工作相比，他们执行预测或自上而下的解析。最近的进展[19]相对于早期的、效率不高的概念验证实现，已经合理地扩大了它们的范围目前的工作使一些多态性和可扩展性，使分析器组合有吸引力的LR分析器的建设。语法定义形式主义SDF [22]支持任意上下文无关语法，并为它们创建GLR解析器[12，21，15]。为方便起见，右侧可能包含一组扩展的正则运算符。SDF规范也定义了词法语法。SDF包括一个缩写mech- anism，它通过扩展工作。Chapman [2]已经探索了在产生式右边使用正则运算符的LR解析的扩展。他扩展了标准项目集的建设与新的情况下，这些运营商。然而，附加的语义动作被固定到例如。 列表结构130P. Thiemann，M. Neubauer / Electronic Notes in Theoretical Computer Science 110（2004）115-编译器构造工具箱Eli [7]也从规则的右侧语法构造自底向上的正则运算符在前面的文法变换中得到扩展。扩展的BNF产生式通常由LL解析器生成器支持[14]。一位评论者提到了van Wijngaarden（或W-）语法[23]，这是一种图灵完备的参数化语法形式主义，用于定义AL- GOL 68。从概念上讲，W-文法由两个层次组成。第一层定义了解释语法符号的上下文无关语言。这些解释用于通过替换规则模板来生成实际的语法结果然而，W-文法是一种概念建模工具，并不适合生成有效的识别器。相反，它们被设计用于描述编程语言的上下文敏感方面。它们缺乏直接参数化的简洁性和易用性，而直接参数化是编程实践中熟悉的概念。8结论和今后的工作受限宏文法是上下文无关文法的一个扩展，它支持从用户可定义的、参数化的非终结符构造模块化文法。受限宏文法精确识别上下文无关语言，并且服从线性时间分析和使用LR分析的扩展的L-属性的评估。它们特别适合于支持参数多态函数的语言，因为参数化的非终结符需要这样的函数来指定语义动作。由于多态性，它们避免了一些reduce-reduce冲突。多态属性也可以应用于普通LR解析器的冲突避免。在本形式化中，简单地合并不同参数实例的前瞻集合。细化的公式可能会考虑条件项，其中前瞻绑定到特定的参数实例。这种改进将使闭包操作能够忽略不可达的lookahead字符串，并避免其他不相关实例之间的冲突应该研究一种更直接的实现，即分解表结构和goto函数。我们希望这会更有效地减少解析表的大小，但这需要进一步的研究。第5节中的类型系统的类型可靠性的正式概念应该被定义，并且应该研究系统的类型推理未来工作的另一个途径是提出一个与LALR解析相对应的概念。它也可能是值得考虑目前的框架解析OI宏语言在其充分的一般性。在这P. Thiemann，M. Neubauer / Electronic Notes in Theoretical Computer Science 110（2004）115131在这种情况下，不可能预先计算转换图，相反，图将根据解析的输入而演变。引用[1] A.阿霍河Sethi和J. D.厄尔曼制造原则、技术和工具。艾迪生-韦斯利，1986年.[2] N. P·查普曼LR分析：理论与实践。剑桥大学出版社，剑桥，英国，1987年。[3] K. Culik和R.科恩LR-正则文法是LR（k）文法的一个推广。J.计算机系统科学，7：66[4] W.该死IO和OI层次结构。Theoretical Computer Science，20（2）：95-207，May 1982.[5] C. Donnelly 和R.斯托曼Bison- 兼容YACC 的解析器生成器。Free Software Foundation ，Boston，MA，Nov. 1995.Bison发行版[6] M. J. Fischer具有类似宏的产生式的语法。IEEEConference Record of 9th Annual Symposium onSwitching and Automata Theory，131[7] R. W. 格雷河P. Heuring，S.P. Levi，A.M. Sloane和W.M. 等等Eli：一个完整的，可扩展的编译器构造系统。Communications of the ACM，35（2）：121-130，Feb. 一九九二年[8] G. Hutton 和 E. 梅 杰 Haskell 中 的 Monadic parsing Journal of Functional Programming ， 8（4），1998.[9] E.国际化.Ecmascript语言规范。wwwhttp://www.ecmacom-internationall.org/publications/files/ECMA-ST/ECMA-262.pdf，Dec。1999. ECMA-262，第3版。[10] S. C.约翰逊yac-又一个编译器编译器。技术报告32，AT T贝尔实验室，Murray Hill，NJ，1975年。[11] D. E.高德纳从左到右的语言翻译。信息与控制，8：607[12] B.高效的非确定性分析器的确定性技术。在ICALP 1974，第255[13]