【正文】 DFA E39。 +n E→E+n S→( S→(S)Sn E→n S S→ S39。 （ 5）分析表凡不能用規(guī)則 (1)(4)填入的空白格均置為“ error”。 ■ 右句型的可行前綴 viable prefix（活前綴） 例 x中， ε ， a, ac, acA都是右句型 acA的活前綴。 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 信息學(xué)院 孫麗云 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 信息學(xué)院 孫麗云 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 信息學(xué)院 孫麗云 88 例：已知文法 G[E] ： E→ E + n | n，請使用恰當(dāng)?shù)淖韵露戏治龇椒ㄟM行語法分析，并判斷n+n∈ L(G)? (3)SLR(1)分析表 (2)識別文法活前綴的 DFA 解 : (1)拓廣文法 (4)分析過程 ■ 課堂練習(xí) 第 4章 語法分析 2022/8/21 信息學(xué)院 孫麗云 89 例：已知文法 G[S] ： S → (S)S| ε，求其 SLR(1)的分析表，并判斷 ( )( )∈ L(G)? (3)SLR(1)分析表 (2)構(gòu)造 識別文法活前綴的 DFA，并判斷用何種方法進行分析 解 : (1)拓廣文法 (4)分析過程 注意： |ε|=0，所以用 S → ε 進行歸約時，不用出棧，直接將 S入棧即可。 3. 若 x?Follow(B), 則用 B? ? 進行歸約 。 作業(yè)： P101 并用 LR(0)方法分析a01是否為該文法的句子。表示整個句子已輸入并歸約結(jié)束 )，則置 ACTION[k,$]為 “ acc”，表示接受。S S→n 3 4 根據(jù)右圖某文法識別活前綴的 DFA判斷該文法是否為LR(0)文法 第 4章 語法分析 2022/8/21 信息學(xué)院 孫麗云 73 S39。E E→ S39。S S→→E E→ go(I, X) = closure(J) 其中 J ={A??X . ? | A?? . X??I } 稱函數(shù) go(I, X)為轉(zhuǎn)移函數(shù)。 解 ： 第 4章 語法分析 2022/8/21 信息學(xué)院 孫麗云 67 在文法產(chǎn)生式右部某個位置標有‘ .’ 的產(chǎn)生式，稱為文法的一個 LR(0)項目 。 E’→E E→ E + n | n 該文法有 3個產(chǎn)生式和 8個項目 : E’→ → S LR分析器的關(guān)鍵部分是分析表的構(gòu)造。 1） 句型 G = (T, N, P, S)， w = xuy ∈ (T?N)* 為文法的 句型 , 若 S =* xUy ,且 U =+ u, 則 u是句型 w相對于 U 的 短語 ； 若 S =* xUy, 且 U =u, 則 u是句型 w相對于 U 的 簡單短語 。amp。 （ 4分）請簡述正規(guī)文法與文法描述的語言，及正規(guī)式與正規(guī)集 4個概念之間的聯(lián)系和區(qū)別。 （ ） 設(shè) A是符號串的集合，則 A0=ε。 步驟： （ 1）消除文法中的左遞歸或提取左因子； （ 2）求改寫文法中的非終結(jié)符的 First集和 Follow集； （ 3）判斷該文法是否是 LL(1)文法，若是，則構(gòu)造預(yù)測分析表； （ 4）根據(jù)分析表進行自頂向下的語法分析。是否是該文法定義的語言 。 stmtsequence|ε stmt→s ■ 課堂練習(xí) (2)First集和 Follow集 (3)LL(1)分析表 解 (1) 文法 (1) stmtsequence →stmt stmtseq’ (2) stmtseq’ → 。 使用此種方法進行語法分析的前提：文法是 LL(1)文法。 ?使用圓括號可在規(guī)則中提取因子。如：下頁例。 第 4章 語法分析 2022/8/21 信息學(xué)院 孫麗云 30 1)將文法 G 提取左因子。, $} Follow(stmtseq’)={$} 解： 第 4章 語法分析 2022/8/21 信息學(xué)院 孫麗云 22 ● 課堂練習(xí) 4)求文法 G的 FOLLOW集合 E→TE’ E’→+TE’|ε T→FT’ T’→*FT’|ε F→(E)|i FIRST(F)={ (， i } FIRST(T’)={*,ε} FIRST(T)= { (， i} FIRST(E’)={+,ε} FIRST(E)= {(， i} FOLLOW(E)={$, )} FOLLOW(E’)={$, )} FOLLOW(T)={+, ), $} FOLLOW(T’)= {+,),$} FOLLOW(F)={*, + , ), $} 解： 第 4章 語法分析 2022/8/21 信息學(xué)院 孫麗云 23 ■ First集合和 Follow集合的比較 First集合中不可能存在 $符號， Follow集合中不可能存在 ε； 通常 Follow集合是為非終結(jié)符定義的，而First集合可以為非終結(jié)符、終結(jié)符和符號串定義； Follow集合通常在產(chǎn)生式的“右邊”計算，而 First集合通常在“左邊”計算。 stmtsequence (3) stmtseq’ → ε (4) stmt→ s First(stmtsequence)={s} First(stmtseq’)={。 例： A? xa1|xa2|…|xan A?x(a1|a2|…|an) 第 4章 語法分析 2022/8/21 信息學(xué)院 孫麗云 9 ■ 回溯的消除 引起回溯的情況： （ 1）相同左部的規(guī)則，其右部左端第一個符號相同而引起回溯。 Z c A d a A?a 檢查 aa匹配 dd匹配 建立語法樹 ,末端結(jié)點為 cad與 輸入 cad相匹配 , 建立了推導(dǎo)序列 E?cAd?cad ∴ cad?L(G(E)) S=cad G[Z]: Z→cAd A→ab|a 分析工作要部分地或全部地退回去重做叫回溯 回溯分析法分析效率低，代價高，實際不常用。 語法分析程序的輸入是單詞符號序列；輸出是語法樹。 A→a。 左遞歸的消除不改變語言，但是改變了文法和分析樹。 P61 第 4章 語法分析 2022/8/21 信息學(xué)院 孫麗云 10 First集合和 Follow集合 ■ First集合 定義： FIRST(α) = {a | α = * aβ， a ?T , α,β ? (T?N)* } 若 α = * ε，則規(guī)定 ε? FIRST(α) 該集合稱為 α的頭符號集合 第 4章 語法分析 2022/8/21 信息學(xué)院 孫麗云 11 X??,則 FIRST(X)={X} X?N,且有產(chǎn)生式 X?a… ，則把 a加入到 FIRST(X)中 。 Ａ ? α B β是一個產(chǎn)生式 ,則把 FIRST(β)－ {?}加至FOLLOW(B)中 。 ■ 消除左遞歸 解決辦法：消除左遞歸 P58P59 例： exp → exp addop term | term 第 4章 語法分析 2022/8/21 信息學(xué)院 孫麗云 29 將文法 G： A→ αβ|αγ提取左因子。 自上而下語法分析方法 不確定的分析方法（回溯分析法） 確定的分析方法 （要求：無左遞歸；無回溯） 確定的自上而下的語法分析方法 遞歸下降分析方法 LL(1)分析法 （也稱預(yù)測分析法） 都要求文法是LL(1)文法 第 4章 語法分析 2022/8/21 信息學(xué)院 孫麗云 32 ■ 167。 （ 3）求每一個非終結(jié)符號的 FOLLOW集合。 由于文法常常是遞歸定義的，所以相應(yīng)的函數(shù)會出現(xiàn)相互遞歸調(diào)用的過程，所以這種分析方法稱為遞歸下降分析法。 第 4章 語法分析 2022/8/21 信息學(xué)院 孫麗云 40 ■ 預(yù)測分析表的構(gòu)造算法 （ 1）計算每一非終結(jié)符的 First集和 Follow集； （ 2）對于 First(α)中的每個記號 a，都將 A → α添加到表項 M[A, a]中； （ 3）若 ε在 First(α)中，則對于 Follow(A)的每個元素a(記號或是 $)，都將 A → α添加到 M[A, a]中 。, ε} First(stmt)={s} Follow(stmtsequence)={$} Follow(stmt)={。 分析：句子 (a,^)是否為該文法定義的語言。 C. 單詞符號 C 第 4章 語法分析 2022/8/21 信息學(xué)院 孫麗云 53 如果文法 G是無二義的，則下面說法正確的是（ ） ，它的最左或最右推導(dǎo)對應(yīng)的語法樹相同 ■ 期中考試 D 給定文法 A?bA|cc，則符號串① cc② bcbc③bcbcc④ bccbcc⑤ bbbcc中，是該文法句子的是（ ） A.① B.③④⑤ C.②④ D.①⑤ D 第 4章 語法分析 2022/8/21 信息學(xué)院 孫麗云 54 ■ 期中考試 文法 G產(chǎn)生的（ ）的全體是該文法描述的語言 正規(guī)式 M1和 M2等價是指（ ）。（ ） 規(guī)范推導(dǎo)是指最左推導(dǎo)。 第 4章 語法分析 2022/8/21 信息學(xué)院 孫麗云 59 ■ 期中考試 （ 12分）已知文法 G(E)： E?ET+|T T?TF*|F F?Famp。 第 4章 語法分析 2022/8/21 信息學(xué)院 孫麗云 60 —— “移進 歸約” 與自上而下的語法分析方法進行比較： ■ 自頂向下的分析 例：設(shè)有文法 G： S→cAd。 例：見上頁。 ■ LR(0)項 例 1：已知 G，求其項目。S)S S → (SE + n E→E 增加一個唯一的開始