编译原理第4章语法分析自下而上LR分析法.ppt

4 3LR分析法 图1 语法分析概述 LR分析法是一种自下而上进行规范归约的语法分析方法 L指自左向右扫描输入串 R指最右推导 规范归约 LR分析法比递归下降分析法 LL 1 分析法对文法的限制要少得多 大多数无二义性CFG语言都可用LR分析器识别 且速度快 并能准确 指出输入串的语法错误及出错位置 LR分析法的主要缺点 手工构造工作量相当大 必须求助自动产生工具 LR分析程序 器 自左向右扫描 识别句柄 自下而上归约的语法分析程序 LR分析程序生成器 自动生成LR分析程序的程序 LR分析器 分析表 的分类 LR 0 表构造法 这种方法的局限性较大 但它是建立其它较一般的LR分析法的基础 简单LR 简称SLR 表构造法 虽然一些文法不能构造SLR分析表 但是 它是一种比较容易实现又很有使用价值的方法 规范LR表构造法 这种分析表能力最强 能够适用一大类文法 但实现代价高 或者说 分析表的体积非常大 向前LR表构造法 简称LALR 这种分析表的能力介于SIR和规范LR之间 可以高效地实现 LR分析器的工作原理规范归约 最右推导逆过程 的关键是寻找句柄 LR分析法的基本思想 在规范归约过程中 一方面记住已移进和归约出的符号串 即记住 历史 栈 另一方面根据所用产生式推测未来可能遇到的输入符 即对未来进行 展望 当一串貌似句柄的符号串呈现于分析栈栈顶时 希望能根据所记载的 历史 展望 及 现实 材料来确定栈顶符号是否构成句柄 分析表产生器 文法 分析表 LR分析程序结构 一个LR分析器实质上是一个带先进后出存储器 栈 的确定有限状态自动机 我们将把 历史 和 展望 材料综合地抽象成某些 状态 自动机 分析栈 先进后出存储器 用来存放状态 栈里的每个状态概括了从分析开始直到某一归约阶段的全部 历史 和 展望 资料 任何时候 栈顶的状态都代表了整个的历史和已推测出的展望 因此 在任何时候都可从栈顶状态得知所想了解的文法的一切信息 而没有必要从底而上翻阅整个栈 LR分析器的每一步工作都是由栈顶状态和现行输入符号所唯一决定的 4 3 1LR分析过程 LR分析的核心 分析表 分析表由ACTION表和GOTO表两部分组成 ACTION s a 表示当状态s面临输入a时的动作GOTO s x 规定了状态s面对文法符号X 非终结符 时的下一状态 文法G 1 E E T 2 E T 3 T T F 4 T F 5 F E 6 F i 分析表 图 分析表中记号的含义sj 把下一状态j和现行输入符号a移进栈 rj 按第j个产生式进行归约 acc 接受 空白格 出错标志 报错 给出下述文法G的LR分析表 幻灯片11 ACTION k a 的动作 1 移进 设表中ACTION k a Sj 当S栈顶状态为k 现行输入符号为a 总控程序根据 k 和 a 查LR 0 分析表 得 ACTION k a Sj此时 Sj表示j状态进S栈 a进T栈 文法符号栈 2 归约 设LR 0 分析表中的ACTION mn a rj 其中rj表示使用文法的第j个产生式A x1x2 xp归约 mn表示LR分析表的一个状态 假设总控程序按S栈顶状态mn和现行输入符号a查LR分析表 得ACTION mn a rj此时 S栈的状态为 m1 mn p 1 mn文法符号T栈的符号为 x1x2 xp按ACTION mn a rj的要求 S栈应删除栈顶p个状态 mn p 1 mn删除后 S栈成为 m1 mn p T栈中x1x2 xp归约成A 即T栈栈顶删除p个文法符号 非终极符A进T栈 若GOTO mn p A j 则状态j进S栈 3 接受 宣布分析成功 分析器停止工作 当S栈顶状态为k 现行输入符号为a 总控程序根据 k 和 a 查LR分析表得 ACTION k a accacc说明语法分析成功 4 报错 报告发现源程序有错 调用出错处理程序 总控程序若按 k 和 a 查表得 ACTION k a 空白说明语法分析出错 所给输入串不是本文法的句子 LR分析器总控程序的工作十分简单 它的任一步只需按分析栈栈顶状态s和现行输入符a执行ACTION s a 所规定的动作 LR分析器的工作过程可看成是栈中状态序列 已归约串和输入串构成的三元式的变化过程 2 句型分析过程 设所给输入串为 i i i 则总控程序分析此输入串的过程 如表4 11所示 通过分析 说明i i i是文法例4 4的句子 例利用上述分析表 假定输入串为i i i 描述LR分析器的工作过程 状态 符号 输入串 1 0 i i i 2 05 i i i 3 03 F i i 4 02 T i i 5 027 T i i 6 0275 T i i 7 02710 T F i 8 02 T i 9 01 E i ACTION 0 i s5移进5和i ACTION 5 r6按第6个产生式进行归约 即 6 F i GOTO 0 F 3移进状态3 ACTION 10 r3按第3个产生式进行归约 即 3 T T F GOTO 0 T 2移进状态2 例利用上述分析表 假定输入串为i i i 描述LR分析器的工作过程 续 状态 符号 输入串 10 016 E i 11 0165 E i 12 0163 E F 13 0169 E T 14 01 E ACTION 1 acc接受输入串 LR文法 LR k 文法 一个文法 如果能用一个每步顶多向前检查k个输入符号的LR分析器进行分析 则这个文法就称为LR k 文法 定义 对于一个文法 如果能够构造一张分析表 使得它的每个入口均是唯一确定的 则我们把这个文法称为LR文法 存在不是LR的上下文无关文法若一个文法的任何 移进 归约 分析器都存在下述情况 尽管栈的内容和下一输入符都已了解 但仍无法确定是 移进 还是 归约 或无法从几种可能的归约中确定其一 则该文法为非LR文法 注意 1 LR文法肯定是无二义的 一个二义文法不会是LR文法 2 LR分析技术可适当修改以适于一定的二义文法 LR分析法的主要任务 构造一张LR分析表首先讨论一种只概括 历史 资料而不包含推测性 展望 材料的 状态 希望仅由这种简单状态就能识别呈现在栈顶的某些句柄 LR 0 项目集就是这样一种简单状态 4 3 2 LR 0 项目集规范族和LR 0 分析表 两种LR 0 分析表的构造算法 方法一 先构造识别文法的活前缀非确定有限自动机 然后确定化 再构造LR 0 分析表 方法二 是直接构造LR 0 项目集规范族 再构造LR 0 分析表 方法一 LR 0 分析表的构造步骤 确定G的LR 0 项目 以LR 0 项目为状态 构造一个能识别文法G的所有活前缀的NFA 利用子集法 将NFA确定化 成为以项目集合为状态的DFA根据 上述DFA可直接构造出LR分析表 定义 文法G每一个产生式的右部添加一个圆点 称为G的一个LR 0 项目 设文法G的某一产生式为A x1x2 xn 则A x1 xi xi 1 xn称为文法G的LR 0 项目 如 A XY对应三个项目 A XYA X YA XY 而 A 的项目A B 句型的活前缀及文法的LR 0 分析表 项目的意义 指明在分析过程的某时刻 我们看到产生式多大一部分 项目在计算机中的表示 m n intm nm 代表产生式编号n 指出圆点的位置 如 abc前缀 a ab abc活前缀 规范句型的一个前缀 该前缀是不含句柄之后的任何符号 C 字的前缀 指该字的任意首部 例4 5文法为 1 S E 2 E aA 3 A cA 4 A d其句型 acd d是句柄 活前缀为 a ac acd同理 在句型 acA 中 句柄是 cA 活前缀为 a ac acA 称为活前缀原因 在右边增添一些终结符号就可以使它成为一个规范句型 在LR分析工作过程中的任何时候 栈里的文法符号 自栈底而上 X1X2 Xm应该构成活前缀 把输入串的剩余部分配上之后即应成为规范句型 如果整个输入串确实构成一个句子 因此 只要输入串的已扫描部分保持可归约成一个活前缀 那就意味着所扫描过的部分没有错误 D 对文法G 构造能识别G的所有活前缀的NFA 识别文法句型活前缀的非确定有限自动机 NFAM 包括 状态 状态转换 初态 终态 NFA的状态 是一个LR 0 项目 一个项目指明了在分析过程的某时刻看到产生式多大一部分 构造方法 a 文法开始符号的形如S S的项目为NFA的唯一初态 文法的所有LR 0 项目构成的状态都是识别文法的规范句型的活前缀的终态 活前缀识别态 b 若状态i和j出自同一个产生式 而且j的圆点只落后于i的圆点一个位置 就从i画一条标志为Xi的弧到j 即 i X X1 Xi 1 Xi Xnj X X1 Xi 1Xi Xn c 若状态i的圆点之后的符号为非终结符 如i为X A 其中A属于VN 就从状态i画 弧到所有A 状态 例 构造以下文法的NFA 文法G的所有LR 0 项目 文法GS EE aA bBA cA dB cB d 1 S E2 S E 3 E aA4 E a A5 E aA 6 A cA7 A c A8 A cA 9 A d10 A d 11 E bB12 E b B13 E bB 14 B cB15 B c B16 B cB 17 B d18 B d 利用上述规则a b c构造NFA 如图所示 E E 使用子集方法 将NFA确定化 使之成为一个以项目集合为状态的DFA 1 S E 2 E aA 3 A cA 4 A d 可将文法的LR 0 项目分成如下四类 A 归约项目S 接收项目 其中 S是开始符号A a 移进项目 其中 a VTA B 待归约项目 其中 B VN识别例4 5的文法的句型 acd 的过程 先构造识别句型的活前缀NFAM 然后确定化太繁琐 下面给出一种直接构造DFAM 的方法 3 LR 0 项目集规范族 方法二 相关定义 定义4 12若I是一个LR 0 项目集 则项目集Closure I 的定义如下 a Closure I I b 若项目A B Closure I B VN 则Closure I Closure I B c 重复 b 直至Closure I 不再扩大为止 定义4 13设I为LR 0 项目集 X是一文法符号 LR 0 状态转换函数GO I X 的定义如下 GO I X Closure J 其中 J 任何形如A X 的项目 A X I 文法 1 S E 2 E aA 3 A cA 4 A d若S E I 则Closure I S E E aA 令I0 S E E aA 则GO I0 E S E I1GO I0 a E a A A cA A d I2从项目集I0开始 将I0定义成一个状态 按照状态转换函数GO I X 的定义可以找出所有的项目集 状态 由GO I X 所产生的项目集 状态 全体称为LR 0 项目集规范族 构造一个G 它包含了整个G 但它引进了一个不出现在G中的非终结符S 并加进一个新产生式S S 而这个S 是G 的开始符号 称G 是G的拓广文法 把文法G进行拓广为了使 接受 状态易于识别 有一个仅含项目S S的状态 这就是唯一的 接受 态 拓广文法 步骤一 令NFA的初态为I 求其CLOSURE I 得到初态项目集 即 求CLOSURE S S 步骤二 对所得项目集I和文法G的每个文法符号X 包括VT和VN 计算GO I X CLOSURE J 得到新的项目集 其中J 任何形如A X 的项目 A X 属于I 步骤三 重复步骤二 直至没有新的项目集出现 经过以上步骤构造出的项目集的全体即为LR 0 项目集规范族 利用LR 0 项目集规范族和GO函数画出DFA 构造项目集规范族方法 构造LR 0 项目集规范族的 例如 文法G为 S aBCB bC c拓广文法G 为 1 S S 2 S aBC 3 B b 4 C c句子 abc 的规范归约过程如下 abc aBc aBC S S 运用图识别输入串 abc 的过程 有效项目 课本P86类似 项目A 1 2对活前缀 1是有效的 存在规范推导 在任何时候 分析栈中的活前缀X1X2 Xm的有效项目集正是状态栈顶Sm所代表的那个集合 也正是从识别活前缀的DFA的初态出发 读出X1X2 Xm后到达的那个项目集 状态 LR分析的基本定理 陈火旺 P108 文法G S S EE aA bBA cA dB cB d考虑 项目 B c BB cBB d活前缀 bcS E bB bc B 项目B c B S E bB bcB bccB 项目B cB S E bB bcB bcd 项目B d 项目A 1 2对活前缀 1是有效的 其条件是存在规范推导 相关定义 LR 0 文法 不存在以下两种冲突的文法移进 归约冲突归约 归约冲突LR 0 表 由LR 0 文法得到的分析表LR 0 分析器 使用LR 0 表的分析器 LR 0 分析表的构造 给定文法G 设文法G拓广为文法G 假若文法G 的项目集规范族 识别句型的活前缀确定有限自动机 已经给出 其状态 项目集 为I0 I1 In 则分析表的构造算法如下 算法中 Ii状态用右下角标i表示 Sj rk的意义同前 分析表的构造方法如下 1 设GO Ii X Ij 若X VT 则置Action i X Sj 表示将状态j和终结符X移进栈 若X VN 则置GOTO i X j 表示将状态转换为j进栈 2 设项目A Ii 若A不是文法的开始符号 则置Action i a rk rk表示用文法的第k个产生式进行归约 a 表示集合VT 的所有符号 若A是文法的开始符号 则置Action i acc 符号 表示句子右界符 3 分析表中的空白表示出错 1 S S 2 S aBC 3 B b 4 C c 练习 假定文法的各个产生式的编号如下 构造其LR 0 项目集规范族和LR 0 分析表 0 S E1 E aA2 E bB3 A cA4 A d5 B cB6 B d DFA构造 部分 CLOSURE S E S E E aA E bB 此即为DFA的状态0 令I S E E aA E bB GO I a CLOSURE E a A 即I中所有圆点之后紧跟a的 E a A A cA A d GO I b CLOSURE E b B E b B B cB B d GO I E CLOSURE S E S E 同上步骤 依次对各项目集进行计算 略 LR 0 分析表构造 DFA部分图 全图见下页 文法G0 S E1 E aA2 E bB3 A cA4 A d5 B cB6 B d E a b 文法G0 S E1 E aA2 E bB3 A cA4 A d5 B cB6 B d E 该文法的LR 0 分析表 该文法的LR 0 分析表如下所示 文法G0 S E1 E aA2 E bB3 A cA4 A d5 B cB6 B d 试对acccd进行分析 例 按上表对acccd进行分析步骤状态栈符号栈输入串10 acccd 202 acccd 3024 acccd 40244 acccd 502444 acccd 60244410 acccd 7024448 acccA 802448 accA 90248 acA 10026 aA 1101 E 文法G0 S E1 E aA2 E bB3 A cA4 A d5 B cB6 B d LR 0 分析法的局限性 语法动作冲突 LR 0 分析法的关键 由项目集规范族构造LR 0 分析表任给一状态 项目集 和任一符号 a a VT 使得Action i a 的值是唯一的 无冲突 若Action i a 值不唯一 我们称为语法动作冲突 分情况讨论 1 无冲突 若一个项目集Ii中仅含移进项目或仅含一个规约项目 则Action i a 的值是唯一的 其中 a VT 2 移进归约冲突 若一个项目集Ii中 既含有移进项目 又含有归约项目 此时 Action i a 值不唯一 其中 a VT i表示状态Ii 3 归约归约冲突 若一个项目集Ii中 存在两个或两个以上的归约项目 则Action i a 的值不唯一上述 2 3 两种情况中的动作冲突 有一部分可以使用FOLLOW集解决 即SLR 1 分析法 例4 6设文法为 0 S S 1 S abdD 2 S aBc 3 B b 4 D dLR 0 项目集规范族应按如下规则填写 c FOLLOW B Action 3 c r3Action 3 d S4 d不属于FOLLOW B 所以 Action 3 d r3 4 3 3 SLR 1 表的构造方法 SLR是LR 0 的一种改进 它在归约时除了考虑历史情况之外还考虑了现实输入 0 S S 1 S abdD 2 S aBc 3 B b 4 D d 对于I3SLR 1 填写规则 c FOLLOW B Action 3 c r3Action 3 d S4 为什么当x FOLLOW B 时 SLR 1 分析表填Action 3 x r3 而Action 3 d s4呢 因为S aBdD不成立 而S S abdD成立 也就是说 aBdD 不是句型 B后面只能出现 x 不能出现 d 0 S S 1 S abdD 2 S aBc 3 B b 4 D d 归约 归约冲突例若I X b A B 若当前输入符号为b 则含有移进 归约冲突 而A和B 又含有归约 归约冲突 则当I面临任何输入符号a时 可做出如下 移进 归约 决策 若a b 移进 若a属于FOLLOW A 则用A 归约 若a属于FOLLOW B 则用B 归约 此外 报错 I X b A B 2 SLR 1 表的构造方法 若项目A a 属于Ik且GO Ik a Ij a为终结符 且置ACTION k a 为 把状态j和符号a移进栈 简记为 sj 若项目A 属于Ik 那么 对任何输入符号a a FOLLOW A 置ACTION k a 为 用产生式A 进行归约 简记为 rj 其中 假定A 为文法G 的第j个产生式 若项目S S 属于Ik 则置ACTION k 为 接受 简为 acc 若GO Ik A Ij A为非终结符 则置GOTO k A j 分析表中凡不能使用规则1至4填入信息的空白格均置上 出错标志 只在归约时展望 即 已到产生式末尾 则去判断FOLLOW A SLR 1 分析表项目集 0 S S 1 S abdD 2 S aBc 3 B b 4 D d 文法G 0 S E 1 E E T 2 E T 3 T T F 4 T F 5 F E 6 F i 练习 对如下文法构造其SLR 1 分析表 FOLLOW集如下 FOLLOW S FOLLOW E FOLLOW T FOLLOW F 该文法的LR 0 项目集规范族 由这些项目集的转换函数GO表示成的DFA 文法G的非终结符的FOLLOW集如下 FOLLOW S FOLLOW E FOLLOW T FOLLOW F SLR分析表 I0 S EE E TE TT T FT FF E F i I2 E T T T F I1 S E E E T I4 F E E E TE TT T FT FF E F i I7 T T FF E F i I10 T T F I6 E E TT T FT FF E F i I8 F E E E T I11 F E I9 E E T T T F I5 F i I3 T F T E i i F F E T I2 T F i I3 I5 F I4 i I5 FOLLOW S FOLLOW E FOLLOW T FOLLOW F 文法G的SLR分析表如下所示 FOLLOW S FOLLOW E FOLLOW T FOLLOW F 任一文法 可按上述算法构造一张表 若表无多重定义入口 则此表称为SLR 1 分析表 具有SLR 1 分析表的文法 称为SLR 1 文法 具有SLR 1 分析表的分析器 SLR 1 分析表 总控程序 称为SLR 1 分析器 1 非SLR 1 文法举例例4 7文法 0 S S 1 S aCaCb 2 S aDb 3 C a 4 D a 4 3 4 LR 1 分析表的构造 I3有归约冲突 用C D的后继符号 FOLLOW C a b FOLLOW D b 解决不了冲突 因为 FOLLOW C FOLLOW D b 完整LR 0 项目集规范族见课本 0 S S 1 S aCaCb 2 S aDb 3 C a 4 D a 问题 有些无二义文法会产生 移进 归约 冲突或 归约 归约 冲突产生原因 SLR 1 分析法未包含足够多的 展望 信息解决办法 让每个状态含有更多的 展望 信息方法 重新定义项目 使得每个项目都附带有k个终结符 即每个项目的形式为 A a1a2 ak LR 1 分析表的构造 LR 0 项目A 加上k个搜索符a1a2 ak 就构成一个LR k 项目 A a1a2 ak 其中 ai VT i 1 2 k 此项目要求存在规范推导S Aa1a2 ak a1a2 ak 这里仅考虑LR 1 项目 A a LR 0 项目与LR 1 项目之间的区别是后者多了一个搜索符 2 LR k 项目与LR 1 有效项目 向前搜索符a仅对归约项目 A a 有意义 归约项目 A a 意味着 当它所属的状态呈现在栈顶且后续的输入符号为a时 才可以把栈顶上的 归约为A只研究k 1的情形 说明 定义4 15我们称一个LR 1 项目 A a 对活前缀 是有效的 如果存在规范推导S AW W其中 a FIRST W 若W 则a S AW W其中 a FIRST W 例4 8 0 S S 1 S BB 2 B aB 3 B bLR 1 项目 B a B a 对活前缀 aaa是有效的 这里 aa a B 对于活前缀 aaa 下面给出规范推导证明 S S BB Bab aBab aaBab aaa Bab即 S aaBab aaaBab aaaBab 中 aaa 是规范句型的前缀 而且不含句柄 aB 之后的符号 所以是活前缀 3 LR 1 项目集规范族的构造算法 算法与构造LR 0 项目集规范族类似 对任意LR 1 项目集I 需定义Closure I 和GO I X 其中 X VN VT 定义4 16 a 若I是一个LR 1 项目集 则置Closure I I b 若项目 A B a Closure I 且B 是一产生式 则对于b FIRST a 的每个符号 做 Closure I Closure I B b c 重复 b 直至Closure I 不再扩大为止 对于A有 S AW B W 同理对于B也符合定义 例如 文法S ABA aB b假设I S AB 则Closure I S AB A a b 定义4 17 令I是一个项目集 X是一个文法符号 函数GO I X 定义为 GO I X CLOSURE J 其中J 形如 A X a 的项目 A X a I 注意 搜索符号a不改变 例如项目集I0 S AB A a b 则GO I0 A S A B B b LR 1 项目集规范族算法设所给文法G 定义拓广文法G S voidintemsetsb G C closure S S do for C中的每个项目集I和G 中的每个文法符号X if GO I X 非空且不属于G 将GO I X 加入G while G不扩大为止 例4 7 0 S S 1 S aCaCb 2 S aDb 3 C a 4 D a 练习 例4 8 0 S S 1 S BB 2 B aB 3 B b构造LR 1 项目集规范族 0 S S 1 S BB 2 B aB 3 B b 4 构造LR 1 分析表的步骤 确定LR 1 项目 利用函数CLOSURE和GO求DFA 即 构造LR 1 项目集规范族 根据DFA 构造LR 1 分析表 根据DFA 构造LR 1 分析表 设文法G的LR 1 项目集为 I0 I1 In 在分析表中 用状态i表示第i个项目集Ii 分析表的构造算法如下 1 若LR 1 项目 A X a Ii 且GO Ii X Ij 则当X VT时 置ACTION i X Sj 当X VN时 置GOTO Ii X j 2 若 A a Ii 且A 是文法的第k个产生式 则当A Vn S 时 置ACTION i a rk rk表示使用第k个产生式的归约 当A S a 时 置ACTION i acc 3 空白表示出错 例4 8拓广文法的规范LR分析表 0 S S 2 B aB 1 S BB 3 B b LR 1 分析法小结 LR 1 分析表的构造 状态集的计算方法和LR 0 基本相同 分析表的构造方法和LR 0 基本相同 构造方法的不同点 归约动作的选择 SLR 1 分析参考FOLLOW集归约 LR 1 分析仅考虑LR 1 项目中的后继符 LR 1 方法的优缺点 解决了SLR 1 分析所难以解决的 移进 归约 或 归约 归约 冲突 LR 1 分析表状态多 规模大 算法适用范围广 4 3 5LALR 1 方法 LALR lookahead LR 技术 这种方法在实际中是经常使用的 LALR 1 和SLR LR 0 的分析表有同样多的状态 而规范LR分析表要大得多 LALR 1 的能力介于SLR 1 和规范LR 1 之间 LALR 1 分析表的构造 问题 对于一般的语言 规范LR分析表要用几千个状态 实际应用很困难分析 由例4 8中可以看到 有些状态集除了搜索符不同外是两两相同的解决办法 合并同心集 构造LALR 1 分析表 我们称两个LR 1 项目集具有相同的心 如果除去搜索符之后 这两个集合是相同的 LR 0 项目相同 将所有同心的LR 1 项目集合并后 得到一个心就是一个LR 0 项目集 说明 I3 B a B a bB aB a bB b a b I6 B a B B aB B b I36 B a B a b B aB a b B b a b 合并为 合并项目集时要修改转换函数 即GO I X 动作ACTION应进行修改 使得能够反映各被合并的集合的既定动作 LR 1 项目集导入同心集Ii0 Ii1 Iik的弧 现导入合并后的项目集JP 弧上标记不变 由同心集Ii0 Ii1 Iik导出的弧 改由JP导出 弧上标记不变 根据图4 13I3和I6 I4和I7 I8和I9分别为同心集 I3 B a B a bB aB a bB b a b I6 B a B B aB B b I4 B b a b I7 B b I8 B aB a b I9 B aB I36 B a B a b B aB a b B b a b I47 B b a b I89 B aB a b 合并为 合并为 合并为 合并同心集不会产生新的移进 归约冲突 但有可能产生新的 归约 归约 冲突 若同心集合并前 任一同心集无移进 归约冲突 则合并后 不可能引起归约 移进冲突 若 a1 am X1 Xn 则有语法分析动作冲突 反之无冲突 合并同心集 可能引起归约与归约冲突 例 下面文法是LR 1 的 但不是LALR 1 的 S SS aAd bBd aBe bAeA cB c S S S aAd S bBd S aBe S bAe S S S a Ad S a Be A c d B c e a S S b Bd S b Ae A c e B c d b A S aA d B S aB e c A c d B c e A c e B c d c 引起归约与归约冲突 I3和I5合并得 对于同一个文法 LALR分析表和SLR分析表具有相同数目的状态 却能处理一些SLR所不能分析的文法 思考 文法 S L R 2 S R 3 L R 4 L i 5 R L 0 S S判断该文法是否是LR 0 SLR 1 LR 1 LALR 1 文法 文法 S L R 2 S R 3 L R 4 L i 5 R L 0 S S S L RR L LR 0 项目 S L R R L LALR 1 项目 A 构造LALR分析表的第一个算法 步骤 构造文法G的LR 1 项目集族C I0 I1 In 把所有的同心集合并在一起 记C J0 J1 Jm 为合并后的新族 那个含有项目 S S 的Jk为分析表的初态从C 构造ACTION表构造GOTO表分析表空白格均填上 出错标志 a 若项目 A a b 属于Jk且GO Jk a Jj a为终结符 则置ACTION k a 为 sj b 若项目 A a 属于Jk 则置ACTION k a 为 用产生式A 归约 简记为 rj 其中 假定A 为文法G 的第j个产生式 c 若项目 S S 属于Jk 则置ACTION k 为 接受 简记为 acc 从C 构造ACTION表 根据图4 13I3和I6 I4和I7 I8和I9分别为同心集 I3 B a B a bB aB a bB b a b I6 B a B B aB B b I4 B b a b I7 B b I8 B aB a b I9 B aB I36 B a B a b B aB a b B b a b I47 B b a b I89 B aB a b 合并为 合并为 合并为 由合并后的集族所构成的LALR分析表 结论 LALR 1 分析法比LR 1 分析法对某些错误发现的时间推迟 合并同心集后多做了规约 一个文法是LALR 1 文法 也是LR 1 文法 但不一定是SLR 1 LR 0 文法 一个文法是LR 1 文法 不一定是LALR 1 文法 LR 1 分析方法和LL 1 分析方法的比较 LR分析方法和LL 1 分析方法的比较 LR 1 分析方法和LL 1 分析方法的比较 4 3 6二义文法的应用 任何二义文法不是一个LR文法 因而也不是SLR 1 或LALR 1 文法 但二义文法的问题是因其没有定义算符优先级和结合规则而产生了二义性 因此 下面讨论使用LR分析法的基本思想 凭借一些其它条件分析二义文法 二义文法G1 E E E E E E i非二义的文法G2 E E T TT T F FF E i对比可以发现G1有两个优点 1 若需要改变算符的优先级或结合规则 不需要改变文法G1本身 2 文法G1的分析表所包含的状态肯定比G2的状态要少得多 因为 在文法G2中含有单个非终结符的产生式 这些产生式是用来定义算符的优先级和结合规则的 它们要占用不少状态和消耗不少时间 二义文法分析 使用LR分析法的基本思想 凭借其他一些条件 来分析二义文法所定义的语言 可以根据二义文法构造出LR分析表 其步骤是 1 构造LR 0 分析表 2 对于发生冲突的项目用SLR方法解决 3 对于SLR方法解决不了的冲突借助于其它条件解决 使用算符的优先级和结合规则的有关信息解决 移进 或接受 归约 或接受 冲突 赋予每个终结符和产生式以一定的优先级 假定在面临输入符号a时碰到移进 归约 假定用A 归约 的冲突 则比较终结符a和产生式A 的优先级 若A 的优先级高于a的优先级 则执行归约 反之则执行移进 E E E E E E i1 构造LR 0 分析表 部分 E EE E EE E EE E E i E E E E EE E E E E E E E EE E EE E E i E i i i E E EE E EE E EE E E i E E E E E E EE E E I7 E E E E E E i2 用SLR方法解决部分冲突例如 状态I1 E E E E EE E i其中存在接受 移进冲突 它可以用SLR方法解决 3 用SLR方法解决不了的冲突例如 状态I7 E E E E E EE E E其中存在归约 移进冲突 此时 只能采取加入附加条件的办法 对状态7 读到 究竟应该先做加法的归约呢还是应该先做乘号的移进 由于我们认为乘法的优先级高于加法 所以这里应该做乘法的移进 对状态7 读到 究竟应该先做加法的归约呢还是应该先做加号的移进 由于我们认为相同优先级的算符服从左结合 所以这里应该做加法的归约 例4 9设描述两种条件语句的文法为 0 S S 1 S iSeS 2 S iS 3 S aFOLLOW S e 按照算法语言的习惯要求 我们规定Action 4 e S5 相当于有 else 的条件语句优先 图4 16的项目集除了 I4 以外无动作冲突 所以 人为地解决LR项目集的动作冲突 可构造出LR分析表 一 基本含义YetAnotherCompiler compilerSteveJohnson在1975年为Unix系统编写的Yacc的GNU GNU sNotUnix自由软件 版叫做Bison二 基本功能接受用户提供的文法 可能是二义性的 优先级 结合性质等附加信息 自动产生这个文法的LALR分析表 有些YACC甚至可包括接受语义描述和目标机器描述 并完成源语言到目标代码的翻译 分析表的自动生成 YACC 用生成器Yacc构造翻译器的过程 Yacc编译器 yacc源程序translate y y tab c C编译器 y tab c a out a out 源程序 输出 语法分析小结 语法分析 自上而下语法分析 自下而上语法分析 LL 1 分析法 递归下降分析法 优先分析法 LR分析法 LR 0 SLR 1 LR 1 LALR 1 直观算符优先分析法 算符优先分析法 参考资料 陈火旺 程序设计语言编译原理 第三版 国防工业出版社 83 129冯博琴译 现代编译程序设计 邮电出版社 2 2 3 2 2 4KennethC Louden 冯博琴等译 编译原理与实践 机械工业出版社AlfredV Aho RaviSethi JeffreyD Ullman Compilers Principles Techniques andTools Addison Wesly 1986