【正文】 表 S – E E – T | E + T T – int | (E) Reduce: 如能找到一產(chǎn)生式 A – w 且棧中的內(nèi)容是 qw (q 可能為空 ), 則可以將其歸約為 過(guò)來(lái)用這個(gè)產(chǎn)生式 . 如上例 , 若棧中內(nèi)容是 (int ， 我們使用產(chǎn)生式 T– int柄把 棧中內(nèi)容歸約為 (T Shift: 如不能執(zhí)行一個(gè)歸約且在未消化的輸入中還有 token ， 就把它從輸入移到棧中 . 如上例 ,假定棧中內(nèi)容是 ( ,輸入中還有 int+int).不能對(duì) ( 執(zhí)行一個(gè)歸約，因?yàn)樗缓腿魏萎a(chǎn)生式的右端匹配 .所以把輸入的第一個(gè)符號(hào)移到棧中 ,于是棧中內(nèi)容是 (int ， 而余留的輸入是 +int) . Reduce的一個(gè)特殊情況：棧中的全部?jī)?nèi)容w歸約為開(kāi)始符號(hào) S （ 即施用 S – w） ，且沒(méi)有余留輸入了，意味著已成功分析了整個(gè)輸入串 . 移進(jìn)歸約分析中還會(huì)出現(xiàn)一種情況，就是出錯(cuò)，比如當(dāng)前的 token不能構(gòu)成一個(gè)合法句子的一部分，例如上面的文法，試分析 int+)時(shí)就會(huì)發(fā)生錯(cuò)誤 . STACK REMAINING INPUT PARSER ACTION 1 (int + int) Shift 2 ( int + int) Shift 3 (int + int) Reduce: T – int 4 (T + int) Reduce: E – T 5 (E + int) Shift 6 (E + int) Shift 7 (E + int ) Reduce: T – int 8 (E + T ) Reduce: E – E + T 9 (E ) Shift 10 (E) Reduce: T – (E) 11 T Reduce: E – T 12 E Reduce: S – E 13 S 8 (E + T ) Reduce:E – E + T 9 why?不用 E – T 9 (E ) 若使用了 E – T， 在棧中形成的 (E+E不是規(guī)范句型的 活前綴 （ viable prefixes） （ E+E不能和任何產(chǎn)生式的右端匹配 （ E+E） 不是規(guī)范句型 活前綴 是規(guī)范句型（右句型）的前綴，但不超過(guò)句柄 ? 移進(jìn)歸約分析的棧中出現(xiàn)的內(nèi)容加上余留輸入構(gòu)成規(guī)范句型 規(guī)范推導(dǎo) 規(guī)范句型 規(guī)范歸約 最右推導(dǎo)：在推導(dǎo)的任何一步 α ?β ， 其中 α 、 β 是句型，都是對(duì) α 中的最右非終結(jié)符進(jìn)行替換 最右推導(dǎo)被稱為規(guī)范推導(dǎo)。 由規(guī)范推導(dǎo)所得的句型稱為規(guī)范句型 G[S]： S→E E→E+T|T T→(E)|int S?E ?T ?(E) ?(E+T) ?(E+int) ?(T+int) ?(int+int) 規(guī)范歸約 假定 α 是 G的一個(gè)句子，稱序列 α n ,α n1 … ,α 0是 α 的一個(gè) 規(guī)范歸約 如果該序列滿足： （ 1） α n = α （ 2） α 0為文法的開(kāi)始符號(hào) （ 3）對(duì)任何 j,0j=n, α j1是從 α j經(jīng)把句柄替換為相應(yīng)產(chǎn)生式的左部而得到的 文法要求 shiftreduce or reducereduce 沖突（ conflicts） 分析程序不能決定是 shift 還是 reduce 或者分析程序歸約時(shí)有多個(gè)產(chǎn)生式可選 例子 （ dangling else） ： S – if E then S | if E then S else S 如輸入 if E then if E then S else S 分析某一時(shí)刻，棧的內(nèi)容 :if E then if E then S 而 else 是下一 token 歸約還是移進(jìn)？ 特定的一種 shiftreduce實(shí)現(xiàn)技術(shù) ＬＲ分析 L R 最右推導(dǎo) ? 分析器模型和分析算法 ? ＬＲ 分析特征討論 ＬＲ分析 器模型 總控程序 output Input S1 Xm … S1 … X1 S0 棧 狀態(tài) 文法符號(hào) ACTION GOTO LR分析表 產(chǎn)生式表 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 LR分析算法 ? 置 ip指向輸入串 w的第一個(gè)符號(hào) – 令 S為棧頂狀態(tài) – a是 ip指向的符號(hào) – 重復(fù) begin – if ACTION[S,a]=Sj – then begin PUSH j,a(進(jìn)棧 ) – ip 前進(jìn) (指向下一輸入符號(hào) ) – end – else if ACTION[S,a]=rj (第 j條產(chǎn)生式為 A??) ＬＲ分析程序 187。 end 187。 ＬＲ分析程序 ? 推導(dǎo)過(guò)程 – S ?aAcBe[1] ?aAcd[4]e[1] ?aAb[3]cd[4]e[1] – ?ab[2]b[3]cd[4]e[1] ? 規(guī)約時(shí)在棧里的句型的前綴 規(guī)約前可在棧里的規(guī)范句型 (不含句柄 ) 的前綴 – ab[2] a – aAb[3] a,aA – aAcd[4] a,aA,aAc – aAcBe[1] a,aA,aAc,aAcB R ＬＲ分析程序 ?LR 文法 ?對(duì)于一個(gè) cfg 文法 , 如果能夠構(gòu)造一張 LR 分析表 , 使得它的每一個(gè)入口均是唯一的（ Sj,rj,acc,空白 ） ， 則稱該 cfg 是 LR 文法 ． ＬＲ分析 ?特征 : – ． 規(guī)范的 – ． 符號(hào)棧中的符號(hào)是規(guī)范句型的前綴 ，且不含句柄以后的任何符號(hào) (活前綴 ) – ． 分析決策依據(jù) ―― 棧頂狀態(tài)和現(xiàn)行輸入符號(hào) ． ？ 識(shí)別活前綴的 DFA. ?四種技術(shù) – LR(0) SLR(1) LR(1) LALR(1) LR(0) 分析 LR