文法G[S]: 步骤号栈输入芬串动作 1)s→ aAcBe1) abbcdetf 移进 (2)A→b 2)#a bbcdet 移进 (3)A→Ab 3)#ab bidets 归约(A→b) (4)B→d 4)#aA badelt 移进 5)*aAb coeff 归约(A→Ab) s 6)#aA coeff 移进 7)#aAc delts 移进 8)# aAcd 归约(B→d) A B 9)#aAcB 移进 10)#aAcBe # 归约 11)#s # 接受 A 对输入串 abbcde#的移进-规约分析过程 a b bcd e 符号串 abode是否是G[S]的子 s→ aAcBe→ qAcde→ aBode→ 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
步骤静号栈输入誉号串动作 状态找 ACTION6oTo 1)# abbcde# 移进 2)#a bucdet 移进 02 3)#ab bidets 归约(A→b) 024 3 4 faA # 移进 023 5) aAb cde# 归约(A→Ab)0236 r 6)#aA celt 移进 023 faAc detts 移进 0235 8)*aAcd 归约(B→d 02358 7 9)#aAcB # 移进 02357 10)#aAcBe 归约(→ aAcBe)023579 r1 11)#S # 接受 01 对输入串 abbede井的LR分析过程 ACTEON GOTO 文法6[S]: e b d*sAB (1)S→ QAcBe (2)A→b 1 .Cc (3)A→Ab 2 (4)B→d 3 s;移进,将状态和输入进栈5 r;归约,用第个产生式归约,同 r r r3 r3 时状态栈与符号栈退出相应个符 号,并把GOTO表相应状态和第i 8 r 个产生式的左部非终结符入栈。 r1riri ri r 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分析程序 推导过程 S paAcBel]→aAcd[4lll→aAb[3Jcd[4le[1] sab 2]b[3]cd[4]e[1] 规约时在栈里的句型的前缀|规约前可在栈里的规范句型(不含句柄) 的前缀 ab[ 2 a aAb] aaA aAcd[4] aaA.aAc aAcBe aaA.aacaAcB
ＬＲ分析程序 推导过程 – 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文法 对于一个c文法,如果能够构造一张LR 分析表,使得它的每一个入口均是唯一的 (Si,ri,ac,空白),则称该c是LR文 法
ＬＲ分析程序 LR 文法 对于一个cfg 文法, 如果能够构造一张 LR 分析表, 使得它的每一个入口均是唯一的 （Sj,rj,acc,空白），则称该 cfg 是LR 文 法．
之R分析 特征: .规范的 符号栈中的符号是规范句型的前缀, 且不含句柄以后的任何符号(活前缀) -.分析决策依据一一栈顶状态和现行 输入符号.?识别活前缀的DFA 四种技术 LR(O SLR(D LR(D) LALR(1
ＬＲ分析 特征: – ．规范的 – ．符号栈中的符号是规范句型的前缀， 且不含句柄以后的任何符号(活前缀) – ．分析决策依据――栈顶状态和现行 输入符号．？识别活前缀的 DFA. 四种技术 – LR(0) SLR(1) LR(1) LALR(1)