[第四章.3.LR分析方法.ppt

第四章（3） LR分析方法 LR分析概述 LR分析法：L——从左向右扫描输入串，R——构造最右推导的逆过程 大多数用上下文无关文法描述的高级语言的语法成分可以用LR分析器来识别。 LR分析：采用移进-归约分析，严格的规范归约。 LR分析根据当前分析栈中的符号串和向右顺序查看输入串的K(K≥0)个符号就可以唯一确定分析的动作是移进还是归约。 向前查看0个符号，就是LR(0)分析方法，向前查看1个符号，就是LR(1)方法。 LR(k)技术包含一组方法：LR(0)、SLR(1)、LR(1)和LALR(1)。 LR(0)无需预测输入符号，实现最简单，局限性最大，基本上无法实用，但是它是LR分析的基础。 简单的LR，即SLR(1)，是一种比较容易实现而且具有使用价值的方法，但是却不能分析一些常见程序语言的结构。 规范的LR分析，能够适用于很大一类文法，分析能力最强，构造方法因而也最复杂。 对LR(1)的一种改进叫做向前LR分析（简称LALR(1)，其中LA是向前look ahead的缩写），它在分析能力和构造工作方面都介于SLR(1)和LR(1)，即LALR(1)的使用范围比SLR(1)广泛，实现的工作量也相应地多。 LR分析的优缺点 优点： 比其他“移进-归约”方法使用广泛，识别率高 能用LL(1)分析法分析的所有文法都能使用LR方法来进行分析。 LR分析法在扫描输入串时就能发现其中的任何错误，并能准确地指出出错位置。 缺点： 手工构造分析表工作量太大。必须使用自动生成器。 自底向上分析法的关键问题是如何确定句柄。LR分析法与算符优先方法一样，LR方法也是通过求句柄逐步归约来进行语法分析。 在算符优先分析中，通过算符的优先关系得到句柄——“最左素短语”，LR方法中句柄是通过识别活前缀而求得。 2. 分析表的组成： 动作表(ACTION) 状态转换表(GOTO) 根据Sm和ai查action表, action[Sm, ai]有4种情况： 对于一个文法G，可以构造一个识别所有活前缀的有限自动机，在此基础上，可以把这种自动机转变成LR分析表 LR文法：对一个文法，如果能够构造一个分析表，且它的每个入口均是唯一的 如何构造LR分析表？ 练 习 求文法：S ?aS | bS |a的LR(0)项目集 LR(0)项指明了在识别过程中以某个非终结符为目标时，某时刻已进行归约到相应规则右部的多大部分。 移进项目表示需要把当前符号，即圆点之后的终结符移进分析栈； 归约项目表示需要把当前句柄，即圆点之前的符号串归约成产生式的左部符号，特别是对于初始项，则表示句子分析成功； 待约项目表示需要把当前符号，即圆点之后的非终结首先归约之后才能和圆点之前的符号串构成可以归约的句柄。 写出文法的所有项目，每个项目是一个状态 规定项目1为NFA的唯一初态 若状态i和状态j出自同一产生式，而且状态j的圆点只落后于状态i一个位置: 若i的圆点后是a，从i到j画一条弧，标记为a 若i的圆点后是A，则连两种弧：(1)从状态i画ε弧到所有的A→·β的状态。(2)从状态i到j画弧，标记为A 归约项目表示结束状态，用双圈表示 例：求文法对应的NFA S ?E E ?aA | bB A ?cA | d B ?cB | d 2)画出NFA 5、LR(0)项目集规范族的构造： LR(0)项目集规范族的定义：构成识别一个文法活前缀的DFA的项目集的全体 构造方法有两种： 1)先构造NFA，使用第三章的子集法将NFA确定化 2) 直接使用闭包和状态转换函数进行计算 1)使用第三章的子集法将NFA确定化，得到一个识别该文法的确定的有穷自动机，其每个状态是项目集 一个项目集I的闭包Closure(I)的计算： (1) I中的任何项目都?Closure(I) (2) 若A ? ?·B? ? Closure(I), 且B?VN ，则对任何关于B的产生式：B?·r?Closure(I)，r为任意符号串 (Vn: 非终结符) (3) 重复(2)直到Closure(I)不再增加为止。 例：对于文法5.7有下列项目： 1. S ?·E 2. S ?E · 3. E ?·aA 4. E ?a·A 5. E ?aA· 6. A ? · cA 7. A ?c · A 8. A ?cA · 9. A ?·d 10. A ? d· 11. E ?·bB 12. E ? b·B 13. E ? bB· 14. B ?·cB 15. B ?c·B 16. B ?cB · 17. B ?·d 18. B ? d· 状态转换函数GO(I,X)的计算：