【文章內(nèi)容簡介】 文法是不相同的。Date 39信息學院 孫麗云第 4章 語法分析■預(yù)測分析表的構(gòu)造算法預(yù)測分析表的構(gòu)造算法（ 1）計算每一非終結(jié)符的 First集和 Follow集；（ 2）對于 First(α)中的每個記號 a，都將 A→→ α添加到表項 M[A,a]中；（ 3）若 ε在在 First(α)中，則對于中，則對于 Follow(A)的每個元素的每個元素 a(記號或是記號或是 $)，都將，都將 A→→ α添加到添加到 M[A,a]中中 。（（ 4）把分析表中沒有填入內(nèi)容的空白格都標上出錯標）把分析表中沒有填入內(nèi)容的空白格都標上出錯標志志 error。P67例：文法： S?a|^|(T) T?T,S|S試判斷該文法是否是 LL(1)文法，若不是請轉(zhuǎn)換，并求轉(zhuǎn)換后 LL(1)文法 的預(yù)測分析表。的預(yù)測分析表。Date 40信息學院 孫麗云第 4章 語法分析●練習 1Follow(exp)={$,)}Follow(exp’)={$,)}Follow(addop)={(,number}Follow(term)={$,+,,)}Follow(term’)={$,+,,)}Follow(mulop)={(,number}Follow(factor)={$,+,,*,)}(1)First集和集和 Follow集集First(exp)={(,number}First(exp’)={+,,ε}First(addop)={+,}First(term)={(,number}First(term’)={*,ε}First(mulop)={*}First(factor)={(,number}文法：文法： exp → exp addop term∣termaddop →→ +|term → term mulop factor∣factormulop →*factor →( exp) ∣ number 注意：先消除左遞歸Date 41信息學院 孫麗云第 4章 語法分析Follow(exp)={$,)}Follow(exp’)={$,)}Follow(addop)={(,number)Follow(term)={$,+,,)}Follow(term’)={$,+,,)}Follow(mulop)={(,number)Follow(factor)={$,+,,*,)}(2)First集和集和 Follow集集First(exp)={(,number)First(exp’)={+,,ε}First(addop)={+,}First(term)={(,number)First(term’)={*,ε}First(mulop)={*}First(factor)={(,number)111097 8888665422 3311factormulopterm’termaddopexp’exp$*+)Number(M[N,T](3)LL(1)分析表分析表解解 (1)文法文法1exp→ termexp’2exp’→ addoptermexp’3exp’→ ε4addop→ +5addop→ 6term→→ factorterm’7term’→→ mulopfactorterm’8term’→ ε9mulop→→ *10factor→→ (exp)11factor→→ number（ 1）對于 First(α)中的每個記號 a，都將 A→→ α添加到表項 M[A,a]中；（ 2）若 ε在在 First(α)中中，則對于，則對于 Follow(A)的的每個元素每個元素 a(記號或是記號或是 $)，都將，都將 A→→ α添加到添加到M[A,a]中。中。Date 42信息學院 孫麗云第 4章 語法分析●練習 22)求文法求文法 G的的 LL(1)分析表分析表S→I|tI→i( e)SEE→ sS|εe→0|1Date 43信息學院 孫麗云(1)文法文法1statement → ifstmt2statement→other3ifstmt→if( exp)statementelsepart4elsepart→else statement5elsepart →ε6exp→07exp→1(3)LL(1)分析表分析表First(statement)={if,other}First(ifstmt)={if}First(elsepart)={else,ε}First(exp)={0,1}Follow(statement)={$,else}Follow(ifstmt)={$,else}Follow(elsepart)={$,else}Follow(exp)={)}M[N,T] if other else ()01$statementifstmtelsepartexp1 2346 755注意在構(gòu)造 LL(1)分析表之前別忘了先驗證文法是否為LL(1)文法??！Date 44信息學院 孫麗云第 4章 語法分析3)求文法求文法 G的的 LL(1)分析表分析表stmtsequence→stmtstmt seq’stmtseq’→。stmtsequence|εstmt→s■課堂練習課堂練習Date 45信息學院 孫麗云(2)First集和集和 Follow集集(3)LL(1)分析表分析表解解(1)文法文法(1)stmtsequence→stmtstmt seq’(2)stmtseq’→。stmtsequence(3)stmtseq’→ε(4)stmt→sM[N,T] 。 s $stmtsequencestmtseq’stmt12 34First(stmtsequence)={s}First(stmtseq’)={。,ε}First(stmt)={s}Follow(stmtsequence)={$}Follow(stmt)={。,$}Follow(stmtseq’)={$}Date 46信息學院 孫麗云第 4章 語法分析■自上而下語法分析過程自上而下語法分析過程 參照 P68表 例：例： 求文法求文法 G的的 LL(1)分析表分析表s1→stmts2s2→。s1|εstmt→s分別分析分別分析 s。ss。s。是否是該文法定義的語言。是否是該文法定義的語言。M[N,T]。 s $s1s2stmt12 34Date 47信息學院 孫麗云第 4章 語法分析課堂練習：文法： S?a|^|(T) T?T,S|S試判斷該文法是否是 LL(1)文法，若不是請轉(zhuǎn)換，并求轉(zhuǎn)換后 LL(1)文法 的預(yù)測分析表。的預(yù)測分析表。分析：句子分析：句子 (a,^)是否為該文法定義的語言。是否為該文法定義的語言。■自上而下語法分析過程自上而下語法分析過程 參照 P68表 Date 48信息學院 孫麗云（（ 1）簡單直接左遞歸的消除）簡單直接左遞歸的消除A→Aα|β A→βA’A’→αA’|ε消除文法中的左遞歸或提取左因子；■LL(1)分析方法相關(guān)知識總結(jié)分析方法相關(guān)知識總結(jié)（（ 2）將文法）將文法 G：： A→αβ|αγ→αβ|αγ 提取左因子。提取左因子。解：解： A→αA ’ A’→β|γ求改寫文法中的非終結(jié)符的 First集和 Follow集；判斷文法是否是 LL(1)文法；一個上下文無關(guān)文法 G是 LL(1)文法，當且僅當對 G中每個非終結(jié)符 A的任何兩個不同的規(guī)則 A?α?β滿足：Select(A?α)∩Select(A?β)=?若該文法是 LL(1)文法，則構(gòu)造預(yù)測分析表；（ 1）對于 First(α)中的每個記號 a，都將 A→→ α添加到表項 M[A,a]中；（ 2）若 ε在在 First(α)中，則對于中，則對于 Follow(A)的每個元素的每個元素 a(記號或是記號或是 $)，都將，都將 A→→ α添加到添加到 M[A,a]中。中。根據(jù)分析表進行自頂向下的語法分析。Date 49信息學院 孫麗云第 4章 語法分析■LL(1)分析方法綜合舉例分析方法綜合舉例已知文法： G[S]:S→SaA|bBA→aB|cB→Bb|d判斷 ”bdbac”以及 ”bdbab”是否是所給文法定義的語言。步驟：（ 1）消除文法中的左遞歸或提取左因子；（ 2）求改寫文法中的非終結(jié)符的 First集和 Follow集；（ 3）判斷該文法是否是 LL(1)文法，若是，則構(gòu)造預(yù)測分析表；（ 4）根據(jù)分析表進行自頂向下的語法分析。Date 50信息學院 孫麗云第 4章 —— “移進 歸約 ”與自上而下的語法分析方法進行比較：■自頂向下的分析自頂向下的分析例：設(shè)有文法 G： S→cAd 。A→ab 。A→a 。識別串 w=cabd是否是該文法的句子。Sc A d■自底向上的分析自底向上的分析Sc A da bc da bc da bAc da bASDate 51信息學院 孫麗云第 4章 語法分析G = (T, N, P, S)， S=* a ， a ∈∈ (T?N)* 稱稱 a為為 句型句型 。1）） 句型句型G = (T, N, P, S)， w = xuy ∈∈ (T?N)* 為為 文法的文法的 句型句型 ,若若 S =* xUy ,且且 U =+ u, 則則 u是句型是句型 w相對于相對于 U 的的 短語短語 ；；若若 S =* xUy,且且 U =u,則則 u是句型是句型 w相對于相對于 U 的的 簡單短語簡單短語 。其中其中 U∈∈ N， u∈∈ (T?N)+ , x, y∈∈ (T?N)* 任一句型的最左簡單短語稱為該句型的任一句型的最左簡單短語稱為該句型的 句柄句柄 。 2）短語）短語 ：： 每棵子樹的葉組成短語每棵子樹的葉組成短語簡單短語簡單短語 ：： 每棵簡單子樹的葉組成簡單短語每棵簡單子樹的葉組成簡單短語3）句柄）句柄 ：： 最左簡單子樹的葉組成句柄最左簡單子樹的葉組成句柄■概念復習概念復習歸約的過程就是尋找句柄的過程。 例：見上頁。Date 52信息學院 孫麗云第 4章 語法分析 LR分析法本節(jié)介紹四種 LR分析法： LR(0)、 SLR(1)、 LR(1)、LALR，這四種方法的 區(qū)別 只有 分析表不同 。LR分析法是一種自下而上進行規(guī)范歸約的語法分析方法。這里 L是指從左向右掃描輸入符號串，R是只構(gòu)造最右推導的逆過程。優(yōu)點：對文法的限制少的多，分析速度快；缺點：構(gòu)造 LR分析器的工作量大，實現(xiàn)困難。Date 53信息學院 孫麗云第 4章 語法分析輸入輸入 a1...ai...an$LR驅(qū)動程序驅(qū)動程序分析表分析表輸出輸出棧棧 smXmsm1Xm1...s0 actiongotoLR分析器的結(jié)構(gòu)和工作過程分析器的結(jié)構(gòu)和工作過程■LR分析器的工作原理和過程分析器的工作原理和過程Date 54信息學院 孫麗云第 4章 語法分析■LR(0)分析法分析法LR(0)分析法就是在分析的每一步，只需根據(jù)當前棧頂狀態(tài)而不必向前查看輸入符號就能確定應(yīng)采取的分析動作。LR分析器的關(guān)鍵部分是分析表的構(gòu)造。構(gòu)造 LR分析表的基本思想是從給定的上下文無關(guān)文法直接構(gòu)造識別文法所有規(guī)范句型活前綴的 DFA，然后再將 DFA轉(zhuǎn)換成一張 LR分析表。Date 55信息學院 孫麗云第 4章 語法分析為了刻畫在分析過程中，文法的一個規(guī)則右部符號串已為了刻畫在分析過程中，文法的一個規(guī)則右部符號串已有多大一部分被識別，可在文法中每個規(guī)則右部適當位有多大一部分被識別，可在文法中每個規(guī)則右部適當位置上加一個圓點來表示。置上加一個圓點來表示。 ■LR(0)項項例例 1：已知：已知 G， 求其求其項目。項目。S39。→SS→(S)S| ε 該文法有該文法有 3個產(chǎn)生式個產(chǎn)生式和和 8個項目個項目 :S39。→SS39?！鶶S→(S)SS→(S)SS→(S)SS→(S)SS→(S)SS→→ 解解 ：：Date 56信息學院 孫麗云第 4章 語法分析■LR(0)項項例例 2：已知：已知 G， 求其項目。求其項目。E’→EE→→ E+n|n 該文法有該文法有 3個產(chǎn)生式和個產(chǎn)生式和 8個項目個項目 :E’→EE’→EE→E+nE→E+nE→E+nE→E+nE→n E→n 解解 ：：Date 57信息學院 孫麗云第 4章 語法分析在文法產(chǎn)生式右部某個位置標有在文法產(chǎn)生式右部某個位置標有 ‘.’的產(chǎn)生式，稱為文法的產(chǎn)生式，稱為文法的一個的一個 LR(0)項目項目 形如形如 A?.?的項目稱為的項目稱為 初始項目初始項目 ；；形如形如 A??.的項目稱為的項目稱為 歸約項目歸約項目 ；；形如形如 A??.B?（（ B∈∈ N）的項目稱為）的項目稱為 待約項目待約項目 ；；形如形如 A??.a?（（ a∈∈ T）） 的項目稱為的項目稱為 移進項目移進項目 ；；形如形如 S’?S.的項目稱為的項目稱為 接受項目接受項目 ，其中，其中 S’為文法的唯為文法的唯一的開始符號一的開始符號■項目分類項目分類Date 58信息學院 孫麗云第 4章