文法G[S]: 步骤 符号栈 输入符号串 动作 (1)5→ aAcBe 1) # abbcde# 移进 (2)A →b 2) #a bbcde# 移进 (3)A→ Ab 3) #ab bcde# 归约(A→b) (4) B→ d 4) #aA bcde# 移进 5) #aAb cde# 归约(A→Ab) S 6) #aA cde# 移进 7) #aAc de# 移进 8) #aAcd e# 归约(B→d) A B 9) #aAcB e# 移进 10) #aAcBe # 归约 11) #s # 接受 A 对输入串abbede#的移进-规约分析过程 符号串abbcde是否是c[s]的子 S→aAcBe→aAcde→aAbcde→abbcde
文法G[S]： (1) S → aAcBe (2) A → b (3) A → Ab (4) B → d a b b c d e 步骤 符号栈 输入符号串 动作 1） # abbcde# 移进 2） #a bbcde# 移进 A 3） #ab bcde# 归约(A→b) 4） #aA bcde# 移进 A 5） #aAb cde# 归约(A→Ab) 6） #aA cde# 移进 7） #aAc de# 移进 B 8） # aAcd e# 归约(B→d) 9） #aAcB e# 移进 11） #S # 接受 S 10） #aAcBe # 归约 符号串abbcde是否是G[S]的子 对输入串abbcde#的移进-规约分析过程 SaAcBe aAcde aAbcde abbcde
步骤 符导栈输入符号串动作 状态栈 ACTION GOTO 1) # abbcde# 进 0 2) #a bbcde# 移 02 8 3) #ab bcde# 归约(A→b) 024 4) #aA bcde# 移进 023 S 5) #aAb cde# 归约(A→Ab) 0236 r 6）)#aA cde# 移进 023 6 7) #aAc de#t 移进 0235 8) aAcd e# 归约(B→d) 02358 r4 9) #aAcB e# 移进 02357 10) #aAcBe 归约(S+aAcBe) 023579 11) #5 # 接受 01 acc 对输入串abbede#的LR分析过程 ACTION GOTO 文法GS]: a c e b 9 AB (1)S→aAcBe 0 S2 1 (2)A→b 1 acc (3)A→Ab 2 54 3 (4)B→d 3 Ss 56 4 r2 re r2 ra r2 r2 S:移进，将状态和输入符进栈 5 58 7 r:归约，用第个产生式归约，同 6 r3 r3 r3 r3 r3 r3 7 时状态栈与符号栈退出相应个符 53 号，并把GOTO表相应状态和第1 8 r4 r4 r4 r4 r4 r4 个产生式的左部非终结符入栈。 9 r
步骤 符号栈 输入符号串 动作 1） # abbcde# 移进 0 S2 2） #a bbcde# 移进 02 S4 4） #aA bcde# 移进 023 S6 6） #aA cde# 移进 023 S5 7） #aAc de# 移进 0235 S8 9） #aAcB e# 移进 02357 S9 11） #S # 接受 01 acc 对输入串abbcde#的LR分析过程 3） #ab bcde# 归约(A→b) 024 r2 3 5） #aAb cde# 归约(A→Ab) 0236 r3 3 8） # aAcd e# 归约(B→d) 02358 r4 7 10） #aAcBe # 归约(S→aAcBe) 023579 r1 1 ACTION GOTO a c e b d # S A B 0 S2 1 1 acc 2 S4 3 3 S5 S6 4 r2 r2 r2 r2 r2 r2 5 S8 7 6 r3 r3 r3 r3 r3 r3 7 S9 8 r4 r4 r4 r4 r4 r4 9 r1 r1 r1 r1 r1 r1 状态栈 ACTION GOTO 文法G[S]： (1) S → aAcBe (2) A → b (3) A → Ab (4) B → d Si:移进，将状态i和输入符进栈 ri:归约，用第i个产生式归约，同 时状态栈与符号栈退出相应个符 号，并把GOTO表相应状态和第i 个产生式的左部非终结符入栈
LR分析程序 推导过程 SgaAcBel[]→aAcd[4]e[1]→aAb[3]cd[4]e[l →ab[2]b[3]cd[4]e[1] 规约时在栈里的句型的前缀 规约前可在栈里的规范句型（不含句柄） 的前缀 ab[2] a - aAb[3] a,aA aAcd[4] a,aA,aAc aAcBe[1] a,aA,aAc,aAcB
ＬＲ分析程序 推导过程 – S aAcBe[1] aAcd[4]e[1] aAb[3]cd[4]e[1] – ab[2]b[3]cd[4]e[1] 规约时在栈里的句型的前缀 规约前可在栈里的规范句型(不含句柄) 的前缀 – ab[2] a – aAb[3] a,aA – aAcd[4] a,aA,aAc – aAcBe[1] a,aA,aAc,aAcB R
LR分析程序 LR文法 对于一个cg文法，如果能够构造一张LR 分析表，使得它的每一个入口均是唯一的 (Sj,rj,acc,空白)，则称该cfg是LR文 法
ＬＲ分析程序 LR 文法 对于一个cfg 文法, 如果能够构造一张 LR 分析表, 使得它的每一个入口均是唯一的 （Sj,rj,acc,空白），则称该 cfg 是LR 文 法．
LR分析 特征： .规范的 .符号栈中的符号是规范句型的前缀， 且不含句柄以后的任何符号（活前缀） 分析决策依据一一栈顶状态和现行 输入符号.？识别活前缀的DFA. 四种技术 -LR(O)SLR(1)LR(1)LALR(1)
ＬＲ分析 特征: – ．规范的 – ．符号栈中的符号是规范句型的前缀， 且不含句柄以后的任何符号(活前缀) – ．分析决策依据――栈顶状态和现行 输入符号．？识别活前缀的 DFA. 四种技术 – LR(0) SLR(1) LR(1) LALR(1)