【正文】 +n 該文法有該文法有 3個產(chǎn)生式和個產(chǎn)生式和 8個項目個項目 :LR(0)項項例例 2：已知：已知 G， 求其項目?！?(SS(S)S| ε 該文法有該文法有 3個產(chǎn)生式個產(chǎn)生式和和 8個項目個項目 :S39。 ■LR(0)分析法分析法LR(0)分析法就是在分析的每一步，只需根據(jù)當(dāng)前棧頂狀態(tài)而不必向前查看輸入符號就能確定應(yīng)采取的分析動作。ai孫麗云第 4章 Date 52信息學(xué)院 語法分析G = (T, N, P, S)， S=* a ， a ∈∈ B→Bb|d判斷 ”bdbac”以及 ”bdbab”是否是所給文法定義的語言。語法分析■→→ ∩ε消除文法中的左遞歸或提取左因子；■β是否為該文法定義的語言。s。→。Date 46信息學(xué)院 stmt→sM[N,T] ?！鷖tmtstmt seq’stmtseq’$statementM[N,T] if other elsepart →ε6if文法文法1|練習(xí) 22)求文法求文法 G的的 →→ →→ *10mulopaddop→ term$,+,,term →ε}Follow(exp)={$,)a]中；（ 3）若 ε在在 First(α)中，則對于中，則對于 Follow(A)的每個元素的每個元素 a(記號或是記號或是 $)，都將，都將 A預(yù)測分析器的總控程序?qū)τ诓煌?LL(1)文法都是相同的，而預(yù)測分析表對于不同的 LL(1)文法是不相同的。自學(xué)通常若采用遞歸下降分析法，則文法采用 EBNF表示法。遞歸下降分析法遞歸下降分析法遞歸下降分析法的基本思想：遞歸下降分析法的基本思想：將一個非終結(jié)符將一個非終結(jié)符 A的文法規(guī)則看作是的文法規(guī)則看作是 ““ 識別識別 A的一個過程的一個過程”” 的定義。使用方括號 [a]表示 a的出現(xiàn)可有可無，它用來表示可供選擇的符號串。(exp)|167。（ 3）求每一個非終結(jié)符號的 FOLLOW 集合。?B如：下頁例。語法分析■B?bd|c|ε語法分析■?β)■|term 提取左因子。else)Date 29信息學(xué)院 提取左因子規(guī)則提取左因子規(guī)則例：例： 將文法將文法 GtermDate 28信息學(xué)院 ■statement易易 出現(xiàn)死循環(huán)出現(xiàn)死循環(huán)易易 造成回溯造成回溯■expexpB?a|LL(1)文法判斷舉例文法判斷舉例分別判斷下列兩個文法是否為 LL(1)文法：（ 1） A?aB|d?■?First(α)Date 23信息學(xué)院 ,FOLLOW(T)={+,(， i}語法分析●First(stmtseq’)={。語法分析●0舉例 2*,) factortermaddopexprexpression算法：Date 18信息學(xué)院 ＡＡ ?…… Aa…… ， a∈∈ T}A∈∈ N,{d,First(T)=→ Db|eT|語法分析■語法分析3)求文法求文法 G的的 ifstatement)statement → ifstmt | otherifstmt → if (exp) statement elsepartelsepart → else statement | εexp練習(xí)練習(xí)同例 1，僅符號不一樣而已Date 14信息學(xué)院 First(factor)={(,number}First(term)={(,number}→→ numberFirst(expr)={(,number}→→ addopexpr孫麗云第 4章 →/(6)(4)E→EFIRST集合集合G:C?xy|B?bd|c|ε若 X??也是一條產(chǎn)生式 ,則把 ?也加到 FIRST(X)中 . X?Y… 是一個產(chǎn)生式且 Y?N,則把 FIRST(Y)中的所有非 ?元 素都加到 FIRST(X)中 。=aβ， 語法分析First集合和 Follow集合■（ 2）相同左部的規(guī)則，其中某一右部能推出 ε串。孫麗云第 4章 exp addop term | term exp ?statementifstmt(T/F|exp’exp’ 消除消除左遞歸。termA’α2…Aterm→βA’A’ADate 5信息學(xué)院 G[Z]:建立了推導(dǎo)序列建立了推導(dǎo)序列 改選改選 A的第二右部的第二右部 但是還不能冒然宣布但是還不能冒然宣布 S?L(G[Z])c A da bZ完成進(jìn)一步推導(dǎo)完成進(jìn)一步推導(dǎo) A?abA有兩個右部有兩個右部 ,選第一個選第一個 孫麗云第 4章 語法分析例：已知符號串例：已知符號串 S=cad語法分析方法L:由左向右的處理輸入由左向右的處理輸入L:為輸入串構(gòu)造最左推導(dǎo)為輸入串構(gòu)造最左推導(dǎo)語法分析語法分析程序的功能是以詞法分析器生成的單詞符號序列作為輸入，根據(jù)語言的語法規(guī)則（文法），識別出各種語法成分，并在分析過程中進(jìn)行語法檢查，檢查所給單詞符號序列是否是該語言的文法的一個句子。Date 1信息學(xué)院 孫麗云第 4章 識別串 w=cabd是否是該文法的句子。Z→cAd 分析過程分析過程是設(shè)法建立一棵語法樹是設(shè)法建立一棵語法樹 ,使語法樹的末端結(jié)點與使語法樹的末端結(jié)點與給定符號串相匹配給定符號串相匹配 . :令令 Z為根結(jié)點為根結(jié)點 Z Z的右部的右部 ,符號串去匹配輸入串符號串去匹配輸入串 檢查檢查 選用選用 A的右部符號串匹配輸入串的右部符號串匹配輸入串 ∴∴ cad?L(G(E))S=cadZ→cAd 語法分析■βε解解 ：： expεε例：將文法例：將文法 G：： 消除左遞歸。Aα 1||A’A’Example將文法將文法 G：： exptermE→→ |(exp)使用方括號 [a]表示 a的出現(xiàn)可有可無，它用來表示可供選擇的符號串?；厮莸南厮莸南鸹厮莸那闆r：（ 1）相同左部的規(guī)則，其右部左端第一個符號相同而引起回溯。|ε■{a,FIRST(α)First集合算法集合算法 ε⑤⑤ A?BCDD?m|(2)(5)(7)→(E)FIRST集合集合 (Simpleterm(2)→→ →→ *(8) 語法分析2)求文法求文法 G的的 |statement,(2)DFirst(B)=孫麗云第 4章 =β是一個產(chǎn)生式 ,則把 FIRST(β)－－ {?}加至FOLLOW(B) 中 。語法分析●addopaddoptermfactor First(addop)={+,}First(mulop)={*}Follow(expr)={$,+,,*,)factored)statement,E’→+TE’|εT’→*FT’|ε(， i{(， i}FOLLOW(T’)=孫麗云第 4章 語法分析■?例：求下列文法的每個規(guī)則的 Select集合：A?aB|dα)?（ 2） S?aAB|(→語法分析將文法將文法 G：： stmtstmtseq’stmtseq’→。語法分析1)將文法將文法 Gifstmtif:→LL(1)文法的要求：一個上下文無關(guān)文法 G是 LL(1)文法，當(dāng)且僅當(dāng)對 G中每個非終結(jié)符 A的任何兩個不同的規(guī)則 A?例： eεB?Aa(3)例如：對下列文法消除左遞歸并提取左因子：例如：對下列文法消除左遞歸并提取左因子：?aBD|?可去掉！不是 LL(1)文法。例：例： ifstmt ?exp )statement]exp ?例：例： A?由于文法常常是遞歸定義的，所以相應(yīng)的函數(shù)會出現(xiàn)相由于文法常常是遞歸定義的，所以相應(yīng)的函數(shù)會出現(xiàn)相互遞歸調(diào)用的過程，所以這種分析方法稱為遞歸下降分互遞歸調(diào)用的過程，所以這種分析方法稱為遞歸下降分析法。a]中中 。Date 40信息學(xué)院 $,+,,孫麗云第 4章 First(exp’)={+,,term→→ factor中。tI→0statementelsepart40else )孫麗云第 4章 stmtsequence|εstmt→s■課堂練習(xí)課堂練習(xí)Date 45信息學(xué)院 →。stmt12 34First(stmtsequence)={s}語法分析■自上而下語法分析過程自上而下語法分析過程 參照 P68sM[N,T]。孫麗云（（ 1）簡單直接左遞歸的消除）簡單直接左遞歸的消除提取左因子。=中。孫麗云第 4章 識別串 w=cabd是否是該文法的句子。(T?N)* 為為 文法的文法的 句型句型 ,其中其中 U∈∈ N， u∈∈ 語法分析 LR分析法本節(jié)介紹四種 LR分析法： LR(0)、 SLR(1)、 LR(1)、LALR，這四種方法的 區(qū)別 只有 分析表不同 。a1...LR分析器的結(jié)構(gòu)和工作過程分析器的結(jié)構(gòu)和工作過程■Date 55信息學(xué)院 S39。(S)SS(S) E’→EE→解解 ：：Date 57信息學(xué)院 ?（（ S’?S增加一個唯一的開始符號 S’，及產(chǎn)生式 S’?S。(2)B(3)closure(J)X??I.構(gòu)造識別文法所有規(guī)范句型活前綴構(gòu)造識別文法所有規(guī)范句型活前綴 DFA的方法的方法Date 60信息學(xué)院 nE→EnEE→En +n0 12 E→E+構(gòu)造識別文法所有規(guī)范句型活前綴構(gòu)造識別文法所有規(guī)范句型活前綴 DFA的方法的方法課堂練習(xí)：課堂練習(xí)： 求文法求文法 G:SSS→)SS 34 5Date 62信息學(xué)院 E+nE→n 3 4根據(jù)右圖某文法識別活前綴的 DFA判斷該文法是否為LR(0)文法Date 63信息學(xué)院 SS→)SS 34 5根據(jù)下圖某文法識別活前綴的 DFA判斷該文法是否為 LR(0)文法Date 64信息學(xué)院 屬于 Ik，則對任何終結(jié)符 a（包括終結(jié)符 $），置 ACTION[k,a]為 ” rj” （注： j是產(chǎn)生式 A??的編號，而不是狀態(tài)集的狀態(tài)號）；（ 3）若項目 S’→S語法分析例例 x：已知：已知 文法文法 G[S]， 求其求其 LR(0)的分析表。|d孫麗云第 4章 s6r1r4r2s9r6r3r5A?cA4輸出：若輸出：若 w置置 ip指向指向 w$的第一個符號；的第一個符號；ifreduce輸出產(chǎn)生式輸出產(chǎn)生式 A?acceptreturnerror(■acA都是右句型都是右句型 acA的活前綴。A語法分析例：已知例：已知 文法文法 G[E]， 分析分析 i*i+i∈∈ L(G[E])|孫麗云第 4章 T?T*F(3)SLR(1)分析表分析表F???TT?EF??FF(ET?E?E+T(3)F?孫麗云第 4章 .B?FOLLOW(B)= ?■id(3)T子表和子表和 goto子表子表方法：方法：1.(a),a)=jIi,reduce(c)A)j4.語法分析(4)0T2*7F10(8)bybybybybyS孫麗云第 4章 +在在 SLR(1)方法方法 中，若項目集中，若項目集 Ik含有含有 A???，則在狀態(tài)，則在狀態(tài) k時時，僅當(dāng)輸入符號為，僅當(dāng)輸入符號為 a∈FOLLOW(A )時，才用時，才用 ” A??””進(jìn)行歸約，這樣在分析表進(jìn)行歸約，這樣在分析表 ACTION部分狀態(tài)部分狀態(tài) k行，所有行，所有b不屬于不屬于 FOLLOW(A)的欄目將空出來?！鍪且粋€ LR[0]項，稱為 “心 ”；而 a則是一個記號（先行），稱為 “向前搜索符 ”。B??是文法是文法中的一條規(guī)則，中的一條規(guī)則， b屬于 孫麗云第 4章 (4)若 GO[Ik,A]=Ij,A為非終結(jié)符，則置 GOTO（ Ik,A）=j；(5)分析表中凡不能用規(guī)則 (1)(4)填入信息的空白欄均置為 “error”。ididn求其求其 LR(1)的分析表，并判斷的分析表，并判斷 S1：： Sid4：： E,$][E→.n ,:=][S’,$