LR分析器（LALR）4.7.ppt

4.5 LR分析器 例 E ? E + T | E ? T 下表绿色部分构成 T ? T ? F | T ? E 识别可行前缀DFA的 F ? (E ) | F ? id 状态转换表 状态 动 作 转 移 id + ? ( ) $ E T F 0 s5 s4 1 2 3 1 s6 acc 2 r2 s7 r2 r2 3 r4 r4 r4 r4 4 s5 s4 8 2 3 4.5 LR分析器 栈 输 入 动 作 0 id ? id + id $ 移进 0 id 5 ? id + id $ 按F ? id归约 0 F 3 ? id + id $ 按T ? F归约 0 T 2 ? id + id $ 移进 0 T 2 ? 7 id + id $ 移进 0 T 2 ? 7 id 5 + id $ 按F ? id归约 0 T 2 ? 7 F 10 + id $ 按T ? T?F归约 . . . . . . . . . 0 E 1 $ 接受 SLR 4.5 LR分析器 4.5.3 构造SLR分析表 术语：LR(0)项目（简称项目） 在右部的某个地方加点的产生式 加点的目的是用来表示分析过程中的状态 例 A?XYZ对应有四个项目 A ? ·XYZ A ? X·YZ A ? XY·Z A ? XYZ· 例 A? ?只有一个项目和它对应 A ? · 4.5 LR分析器 构造SLR分析表的两大步骤 1、从文法构造识别可行前缀的DFA 2、从上述DFA构造分析表 例子 1. 给出接受文法 S-(L)|a L-L,S|S 的活前缀的一个DFA 答案-1 例子 2. 求接受文法 S-Aa|bAc|dc|bda A-d 的活前缀DFA和SLR(1)分析表 答案-2（DFA） 答案-2（状态分析表） 练习 构造E-E+id|id的SLR(1)文法 答案 SLR分析 构造SLR分析表的两大步骤 从文法构造识别可行前缀的DFA 从上述DFA构造分析表 Shift Reduce - 整个表达式执行完成 Accept - 只有归约到开始符号 规范的LR 练习 构造下列文法的SLR S-V=E S-E V-*E V-id E-V 答案 4.5 LR分析器 例 SLR(1)文法的描述能力有限 S ? V = E S ? E V ? ? E V ? id E ? V I0 : S ? ? · S S ? ·V = E S ? · E V ? · ? E V ? · id E ? · V I2 : S ? V · = E E ? V · V 第一项目使得action[2, = ] = s6 第二项目使得 action[2, = ]为按 E?V归约，因为=是 E的一个后继符 在所关注场合E的后继是$： S $? V = E $ ? ? E = E $ S $? E $ ? V $ 4.5 LR分析器 4.5.4 构造规范的LR分析表 LR(1)项目： 重新定义项目，让它带上有哪些信誉好的足球投注网站符，成为如下形式 [A?? ·?, a] LR(1)项目[A?? ·?, a]对可行前缀?有效： 如果存在着推导S ?*rm ?Aw ?rm ???w，其中： ? = ??； a是w的第一个符号，或者w是?且a是$ 4.5 LR分析器 例 S ? BB B ? bB | a 从最右推导S ?*rm bbBba ?rm bbbBba看出： [B?b·B, b]对可行前缀? = bbb是有效的 对于项目[A?? ·?, a]，当?为空时，是根据有哪些信誉好的足球投注网站符a来填表（归约项目），而不是根据A的后继符来填表 4.5 LR分析器 S? ?·S, $ I0 S ?·BB, $ B ?·bB, b/a B ?·a, b/a 4.