【正文】 s5 s6 s8 s9 r1 r1 r1 r1 r1 s5 s6 r4 r4 r4 r4 r4 r2 r2 r2 r2 r2 s8 s9 r6 r6 r6 r6 r6 r3 r3 r3 r3 r3 r5 r5 r5 r5 r5 1 4 7 10 11 (2)LR(0)分析表 (1)識別文法活前綴的 DFA A?d. A? A?.cA A?.d S? A?.cA A?.d S? B?.cB B?.d B? B?.cB B?.d S??.S S?.aA S?.bB start S??S. A?cA. S?aA. A d d A c a b S S?bB. B?cB. B?d. B d d B c c c 0 1 2 3 6 7 8 9 10 11 4 5 0 S??S 1 S?aA 2 S?bB 3 A?cA 4 A?d 5 B?cB 6 B?d 第 4章 語法分析 2022/8/21 信息學院 孫麗云 77 輸入：一個輸入串 w和文法 G的一張 LR分析表 M。 輸出：若 w ?L(G),輸出 w的一個自底向上的分析；否則，輸出一個出錯表示。 方法：分別置放 s0(初態(tài) )到棧中和 w$（ w為輸入串， $為界符）到輸入緩沖器中 。 置 ip指向 w$的第一個符號； repeat forever begin 令 s是棧頂狀態(tài)且 a是 ip所指向的符號 if action[s,a] = shift s? then begin 將 a和 s?先后 壓入棧內； 使 ip指向輸入串中的下一個符號； end else if action[s,a] = reduce A? ? then begin 從棧頂彈出 2*|?|個符號； 令 s?是當前 棧頂狀態(tài)； 把 A和 goto[s?,A]先后入棧； 輸出產生式 A? ? end else if action[s,a] = accept then return else error( ) end ■ LR(0)分析算法 算法在教材 P79 例：利用 LR(0)法分析上頁例 x中 acd是否是文法的句子。 作業(yè)： P101 并用 LR(0)方法分析a01是否為該文法的句子。 第 4章 語法分析 2022/8/21 信息學院 孫麗云 78 在進行 LR語法分析過程中，可以發(fā)現(xiàn)當前棧和輸入串之間發(fā)生了間隔，在每種情況下， 分析棧 的符號序列被稱為右句型的 可行前綴（不含句柄之后的任何符號） 。 ■ 右句型的可行前綴 viable prefix（活前綴） 例 x中， ε ， a, ac, acA都是右句型 acA的活前綴。 第 4章 語法分析 2022/8/21 信息學院 孫麗云 79 例：已知文法 G[A]： A ? ( A ) | d 求其 LR(0)的分析表，并判斷 ((d))∈ L(G)? (3)LR(0)分析表 (2)識別文法活前綴的 DFA 解 : (1)拓廣文法 (4)分析過程 ■ 課堂練習 第 4章 語法分析 2022/8/21 信息學院 孫麗云 80 例：已知文法 G[E]， 分析 i*i+i∈ L(G[E]) ? E?E+T | T T?T*F | F F? (E) | i 出現(xiàn)問題：由該文法識別活前綴的 DFA看的出來，有的有效項目集中存在著 移進－歸約 沖突，不能用LR(0)分析方法進行分析。 解決方法：對含有沖突的項目集向前查看一個輸入符號，這種分析方法稱為 SLR(1)分析方法 。 復習： LR(0)文法中不能存在 移進－歸約 沖突或者歸約－歸約 沖突。 ■ 引例 第 4章 語法分析 2022/8/21 信息學院 孫麗云 81 解 ： (1)拓廣文法 G的拓廣文法 G?[E?]： (0) E? ? E (4) T?F (1) E?E+T (5) F? (E) (2) E?T (6) F? i (3) T?T*F (2)識別文法的活前綴的 DFA (3)SLR(1)分析表 (4)分析過程 例：已知文法 G[E]， 并用 SLR(1)方法分析i*i+i∈ L(G[E]) ? E?E+T | T T?T*F | F F? (E) | i SLR(1)的分析過程與 LR(0)的分析過程完全一樣，唯一不同的是分析表！ E ’??E E ??E+T E ??T T ??T*F T ??F F ? ?(E) F ??id E E’?E? E ?E ? +T T E ?T? T ?T?*F ( F ? (? E) E ??E+T E ??T T ??T*F T ??F F ? ?(E) F ??id I0 I1 I2 I6 F T ?F? I3 F ?id? id I5 T I2 F I3 id I5 ( E ?E+ ? T T ??T*F T ??F F ? ?(E) F ??id + * T ?T* ? F F ? ?(E) F ??id I7 F ? (E ?) E ?E?+T E I8 T E ?E+ T ? T ?T?*F I9 F I3 id I5 ( F T ?T* F ? I10 id I4 ( I4 * I7 ) F ? (E) ? + I6 I11 G?： (0) E? ? E (1) E?E+T (2) E?T (3) T?T*F (4) T?F (5) F? (E) (6) F? id (2)識別文法的活前綴的 DFA 第 4章 語法分析 2022/8/21 信息學院 孫麗云 83 若有效項目集中存在沖突動作 : I = { X ? ? . b?, A? ? . , B? ? . } 將 b移進棧 將 ?歸約為 A 將 ?歸約為 B 解決方法： 設當前輸入符號為 x, 1. 若 x= b, 則移進 。 2. 若 x?Follow(A), 則用 A? ? 進行歸約 。 3. 若 x?Follow(B), 則用 B? ? 進行歸約 。 4. 其余情況報錯 . 要求： 移進項目的符號集 ?FOLLOW(A) ? FOLLOW(B)=? ■ SLR(1)分析法 第 4章 語法分析 2022/8/21 信息學院 孫麗云 84 對于表達式文法的例子， FOLLOW集如下： G?： (0) E? ? E (4) T?F (1) E?E+T (5) F? (E) (2) E?T (6) F? id (3) T?T*F I2: FOLLOW(E)∩{*}=Φ I9: FOLLOW(E)∩{*}=Φ ∴ 可用 SLR(1)方法實現(xiàn) FOLLOW集 E’ $ E $，）， + T $，）， +， * F $，）， +， * E ?E+ T ? T ?T?*F E ?T? T ?T?*F I2: I9: 第 4章 語法分析 2022/8/21 信息學院 孫麗云 85 ● SLR分析表的構造算法 輸入：一個拓廣文法 G? 輸出：對于 G?的分析表的 action 子表和 goto子表 方法： 1. 構造 G?的 LR(0)項目集規(guī)范族。 2. 對于狀態(tài) Ii的分析動作如下： (a) 若 A?? . aB ? Ii且 go (Ii ,a)= Ij action[i,a] = shift j (b) 若 A?? . ? Ii, 對于所有 a ? Follow(A) action[i,a] = reduce A?? , A? S? (c) 若 S??S. ? Ii, action[i, $]= accept 3. 若 go(Ii, A) = Ij, A?VN , 則 goto[i,A] = j 4. 分析表其余位置為 error 第 4章 語法分析 2022/8/21 信息學院 孫麗云 86 (3)SLR分析表 Follow(E)={$, +,)} ACTION GOTO + * ( ) id $ E T F 0 S4 S5 1 2 3 1 S6 ACC 2 R2 S7 R2 R2 3 R4 R4 R4 R4 4 S4 S5 8 2 3 5 R6 R6 R6 R6 6 S4 S5 9 3 7 S4 S5 10 8 S6 S11 9 R1 S7 R1 R1 10 R3 R3 R3 R3 11 R5 R5 R5 R5 第 4章 語法分析 2022/8/21 信息學院 孫麗云 87 (4) id*id+id的 LR分析過程 分析棧 輸入串 動作 (1) 0 (2) 0id5 (3) 0F3 (4) 0T2 (5) 0T2*7 (6) 0T2*7id5 (7) 0T2*7F10 (8) 0T2 (9) 0E1 (10) 0E1+6 (11) 0E1+6id5 (12) 0E1+6F3 (13) 0E1+6T9 (14) 0E1 id*id+id$ *id+id$ *id+id$ *id+id$ id+id$ +id$ +id$ +id$ +id$ id$ $ $ $ $ shift reduce by F?id reduce by T?F shift shift reduce by F?id reduce by T?T*F reduce by E?T shift shift reduce by F?id reduce by T?F reduce by E?E+T accept 第 4章 語法分析 2022/8/21 信息學院 孫麗云 88 例：已知文法 G[E] ： E→ E + n | n，請使用恰當的自下而上分析方法進行語法分析，并判斷n+n∈ L(G)? (3)SLR(1)分析表 (2)識別文法活前綴的 DFA 解 : (1)拓廣文法 (4)分析過程 ■ 課堂練習 第 4章 語法分析 2022/8/21 信息學院 孫麗云 89 例：已知文法 G[S] ： S → (S)S| ε，求其 SLR(1)的分析表，并判斷 ( )( )∈ L(G)? (3)SLR(1)分析表 (2)構造 識別文法活前綴的 DFA，并判斷用何種方法進行分析 解 : (1)拓廣文法 (4)分析過程 注意： |ε|=0，所以用 S → ε 進行歸約時，不用出棧，直接將 S入棧即可。 ■ 課后作業(yè) LR(0)分析不了的， SLR(1)有可能能分析； LR(0)能分析的， SLR(1)都能分析！ 第 4章 語法分析 2022/8/21 信息學院 孫麗云 90 SLR(1)方法與 LR(0)方法的區(qū)別 僅在于有效項目集中有歸約項目時： 在 LR(0)方法 中，若項目集 Ik含有 A???，則在狀態(tài) k時，無論面臨什么輸入符號都用 “ A??”進行歸約 ——即假定 A??產生式編號為 j，則在分析表 ACTION部分，對應狀態(tài) k行的所有欄目都填 ” rj”。 在 S