各种文法的比较

《各种文法的比较》由会员分享，可在线阅读，更多相关《各种文法的比较（4页珍藏版）》请在金锄头文库上搜索。

1、各类文法之间的比较处理文法的语法分析器大体上可以分为三种类型：通用的、自顶向下的、和自底向上的。 象 Cocke-Younger-Kasami 算法和 Earley 算法这样的通用语法分析方法可以对任意文法进行 语法分析。然而，这些通用方法效率很低，不能用于编译器产品。编译器中常用的方法可以分为自顶向下的和自底向上的。正如它们的名字所指出的，自 顶向下的方法从语法分析树的顶部(根结点)开始向底部(叶子结点)构造树，而自底向上 的方法从叶子结点开始，逐渐向顶部构造。这两种分析方法中，语法分析器的输入总是按照 从左向右的方式被扫描，每次扫描一个符号。最高效的自顶向下方法和自底向上方法只能处理某些文

2、法子类，但其中的某些子类，特 别是LL和LR文法，的表达能力已经足以描述现代程序设计语言的大部分语法构造了。手 工实现的语法分析器通常使用LL文法；比如预测分析方法能够处理LL文法。处理较大的 LR文法类的语法分析器常常是由自动化工具构造得到的。自顶向下的文法自顶向下语法分析可以被看作是为输入串构造语法分析树的问题，它从语法分析树的根 结点开始，按照先根次序创建这棵语法分析树的各个结点。自顶向下语法分析也可以被等价 地看作寻找输入串的最左推导的过程。在一个自顶向下语法分析的每一步上，关键问题是确定对一个非终结符号，比如说 A， 应用哪个产生式。一旦某个A-产生式被选中，语法分析过程的其余部分负

3、责将相应产生式 体中的终结符号和输入相匹配。对于有些文法，我们可以构造出向前看 k 个输入符号的预测语法分析器。这一类文法有 时被称为LL(k戊法类。根据一个文法的FIRST和FOLLOW集合，我们将构造出“预测分 析表”，它指明了如何在自顶向下语法分析过程中选择产生式。这些集合也可以被用于自底 向上语法分析。对于一类被称为LL(1)的文法，我们可以构造出预测语法分析器，也就是不需要回溯的 递归下降语法分析器。LL中的第一个“L”表示从左到右扫描输入，第二个“L”表示产 生最左推导，而“1”则表示在每一步中只需要一个向前看符号来决定语法分析动作。LL(1)文法类已经足以描述大部分程序设计语言构

4、造，虽然在为源语言写出适当的文法 时需要多加小心。比如，左递归的文法和二义性的文法都不可能是LL(1)的。一个文法G是LL(1)的，当且仅当对于G的任意两个不同的产生式A a I卩，下面的条 件一定成立：1、不存在终结符号a使得a和卩都能够推导出以a开头的串。2、a和卩中最多只有一个可以推导出空串。*3、如果卩n ,那么a不能推导出任何以FOLLOW(A)中的某个终结符号开头的串。类*似地，如果an ，那么卩不能推导出任何以FOLLOW(A)中的某个终结符号开头的串。前两个条件等价于说FIRST(a)和FIRST(卩)是不相交的集合。第三个条件等价于说如果 在FIRST(P)中，那么FIRST

5、(a)和FOLLOW(A)是不相交的集合，并且当在FIRST(a)中时 类似结论成立。之所以能够为LL(1)文法构造一个预测分析器，原因是只需要检查当前输入符号就可以 决定为一个非终结符号选择哪个正确的产生式。因为有关控制流的各个语言构造带有不同的关键字，它们通常满足LL(1)的约束。比如，如果我们有如下产生式stmt - if (expr) stmt else stmt | while (expr) stmt | stmt_list那么关键字if, while和符号告诉我们：如果我们想要在输入中找到一个语句，那么只 有选择哪个产生式才可能匹配成功。接下来给出的算法将FIRST和FOLLOW集

6、合中的信息放到一个预测分析表MA,a中 去。这是一个二维数组，其中A是一个非终结符号而a是一个终结符号或特殊符号$，即输 入的结束标记。该算法基于如下的思想：只有当下一个输入符号a在FIRST(a)中时才选择*产生式ATa。只有当a=时，或更加一般化的a = 时，情况才有些复杂。在这种情况下, 如果当前输入符号在FOLLOW(A)中，或者已经到达输入中的$符号、且$在FOLLOW(A)中， 我们仍应该选择 ATa。自底向上的文法一个自底向上的语法分析过程对应于为一个输入串构造语法分析树的过程，它从叶子结 点(底部)开始逐渐向上到达根结点(顶部)。将语法分析描述为语法分析树的构造过程会 比较方便

7、，虽然编译器前端实际上并不构造出显式的语法分析树，而是直接进行翻译。LR语法分析器是表格驱动的，在这一点上它和非递归LL语法分析器很相象。如果我 们可以使用本节和下一节中的某个方法为一个文法构造出语法分析表，这个文法就被称为 LR 文法。直观地讲，只要存在一个从左到右扫描的移入-归约语法分析器，它总是能够在某 文法的最右句型的句柄出现在栈顶时识别出这个句柄，这个文法就是LR的。因为诸多原因，LR语法分析技术很有吸引力：对于几乎所有的程序设计语言构造，只要能够写出该构造的上下文无关文法，就能够构 造出识别该构造的LR语法分析器。确实存在非LR的上下文无关文法，但一般来说，常见 的程序设计语言构造

8、都可以避免使用这样的文法。LR-语法分析方法是已知的最通用的无回 溯移入-归约分析技术，并且它的实现可以和其它更原始的移入-归约方法一样高效。一个LR语法分析器可以在对输入从左到右扫描时尽可能早地检测到错误。可以使用LR方法进行语法分析的文法类型是可以使用预测分析方法或LL分析方法的 文法类型的真超集。一个文法是LR(k)的条件是当我们在一个最右句型中看到某个产生式的 右部时，我们再向前看 k 个符号就可以决定是否使用这个产生式进行归约。这个要求要比 LL(k)文法的要求宽松很多。对于LL(k)文法，我们在决定是否使用某个产生式时，只能向前 看该产生式右部推导出的串的前k个符号。因此，毫不奇怪

9、LR文法能够比LL文法描述更 多的语言。LR方法的主要弱点是在为一个典型的程序设计语言文法手工构造LR分析器时，所需 的工作量非常大。我们需要一个特殊的工具，即一个LR分析器生成工具，来帮助构造。幸 运的是有很多这样的生成工具可用。这样的生成工具将一个上下文无关文法作为输入，自动 生成一个该文法的语法分析器。如果该文法含有二义性的构造，或者含有其它难以在从左到 右扫描时进行语法分析的构造，语法分析器生成工具将对这些构造进行定位，并给出详细的 诊断信息。“简单LR语法分析技术”，或者说SLR分析技术，的中心思想是根据文法构造出LR(0) 自动机。这个自动机的状态是规范LR(0)项集族中的元素，而

10、它的转换由GOTO函数给出。LR(0)自动机是如何帮助作出移入-归约决定的呢？移入-规约决定可以按照如下方式做 出。假设文法符号串Y使LR(O)自动机从开始状态0运行到某个状态j。那么如果下一个输 入符号为a且状态j有一个a上的转换，就移入a。否则我们就选择归约动作；状态j的项 将告诉我们使用哪个产生式进行归约。图4.35中显示了一个LR语法分析器的示意图。它由一个输入、一个输出、一个栈、一 个驱动程序和一个语法分析表组成。这个分析表包括两个部分(ACTION和GOTO)。所有 LR语法分析器的驱动程序都是相同的。语法分析器从输入缓冲区逐个读入符号。当一个移 入-归约分析器移入一个符号时，一个

11、 LR 分析器移入的是一个对应的状态。每个状态都是 对它下面的栈中内容所含信息的摘要。Input 输入Stack 栈Output 输出LR parsing programLR 语法分析程序图4.35 :一个LR语法分析器的模型分析器的栈存放了一个状态序列s0sl .sm，其中sm位于栈顶。在SLR方法中，栈中 保存的是LR(0)自动机中的状态；规范LR和LALR方法和SLR方法类似。根据构造方法， 每个状态都有一个对应的文法符号。回顾一下，各个状态都和某个项集对应，并且有一个从 状态i到状态j的转换当且仅当GOTO(Ii,X)=Ij。所有到达状态j的转换一定对应于同一符号 X。因此，除了开始状

12、态0之外的每个状态都和一个唯一的文法符号相关联。分析表由两个部分组成：一个分析动作函数ACTION和一个转换函数GOTO。1、ACTION函数的参数是一个状态i和一个终结符号a (或者是$，即输入结束标记)。 ACTIONi,a 的取值可以是下列四种形式之一：a、移入j，其中j是一个状态。语法分析器采取的动作是把输入符号a高效地移入栈中， 但是使用状态j来代表a。b、归约AT卩。语法分析器的动作是把栈顶的卩高效地归约为产生式头A。c、接受。语法分析器接受输入并完成语法分析过程。d、报错。语法分析器在它的输入中发现了一个语法错误并执行某个纠正动作。2、我们把定义在项集族上的 GOTO 函数扩展为

13、定义在状态集上的函数： 如果 GOTOIi,A=Ij，那么GOTO也把状态i和一个非终结符号A映射到状态j。语法分析器根据上面的格局决定下一个动作时，首先读出当前输入符号ai和栈顶的状 态sm，然后在分析动作表中查询条目ACTOINsm,ai。对于前面提到的四种动作，每个动 作结束之后的格局如下：如果ACTIONsm,ai=移入s，语法分析器就执行一次移入动作；它将下一个状态s移入 栈中，进入格局(s0s1 . sms, ai+1. an$)符号ai不需要被存放在栈中，因为在需要时(在实践中从不需要ai)可以根据s得到 ai。现在，当前的输入符号是ai+1。如果ACTIONsm,ai=规约AT

14、卩，那么分析器执行一次归约动作，进入格局(s0s1 . sm-rs, aiai+1. an$)其中r是卩的长度，且s=GOTOsm-r,A。在这里，语法分析器首先将r个状态弹出栈, 使状态sm-r成为栈顶。然后分析器将s，即条目GOTOsm-r,A啲值，压入栈中。在一个归 约动作中，当前的输入符号不会改变。对于我们将构造的LR语法分析器，和被弹出栈的状 态对应的文法符号序列Xm-r+1 .Xm总是等于卩，即归约使用的产生式的右部。在一次归约动作之后，LR分析器将执行和归约产生式关联的语义动作，生成相应的输 出。我们暂时假设输出的内容仅仅包括打印出的归约产生式。如果ACTIONsm,ai=接受，

15、语法分析过程完成。如果ACTIONsm,ai=报错，语法分析器发现了一个语法错误，并调用一个错误恢复子 程序。所有的LR分析器都按照这个方式执行；两个LR语法分析器之间的唯一区别是它们的 语法分析表的ACTION表项和GOTO表项中包含的信息。各种文法之间的区别和联系LL与LR系列有着很大区别。LL是自顶向下分析，而LR系列是自底向上分析。LL(1)文法比LR的文法苛刻，不能有左递归也不能有回溯。而LR文法相比宽松不少，能基 本实现大多数的编程语言。从实现的角度上看，LL(1)文法容易手工实现，LR文法更多的是 程序生成的。实现方法上，LL(1)里的预测分析表的方法和LR的分析表的方法相似，都是 表驱动的。LR(0)、SLR(1)、LR(1)、LALR(1)相同点很多，上文有详细介绍，接下来就只说它们的 不同点了：LR(0)：没有lookahead,只记录栈顶的最后一个handle的信息。SLR(1)：在LR(0)的基础上，增加一个符号的lookahead(也就是当前的输入符号)。 LR(1)：由一个lookahead(当前输入符号)，记录栈内已有的所有信息。LALR(1)：合并LR(1)状态集合中所有拥有相同“core”的状态，如果出现冲突，则该 文法不是LALR文法。