【正文】 ate 16信息學(xué)院 求求 First集合舉例集合舉例 2求文法求文法 G的的 (1)(2)εBεDεε}{e,a,d,b,First(B)=d,b,First(D)=ε}注意：除了求非終結(jié)符的 First集外，還可求符號(hào)串的 First集。孫麗云第 4章 語(yǔ)法分析定義：定義： FOLLOW(A)={a|*S開(kāi)始符號(hào)開(kāi)始符號(hào) =則，則 Follow集合集合 S,置 $于于 FOLLOW(S) 中 。αβ是一個(gè)產(chǎn)生式 ,則把 FIRST(β)－－ {?}加至FOLLOW(B) 中 。αB是一個(gè)產(chǎn)生式 ,或 ＡＡ ? 則把 FOLLOW （（ A）） 加至 FOLLOW （（ B）） 中。孫麗云第 4章 語(yǔ)法分析●1)求文法求文法 G的的 simplegrammar)(1)→addopexprterm(3)→addop(5)→ muloptermfactor(7)→*(8)→( expr)factor First(addop)={+,} First(mulop)={*}Follow(expr)={$,+,,}$,+,,}Follow(mulop)={(,number}Follow(factor)={*,)孫麗云第 4章 語(yǔ)法分析●2)求文法求文法 G的的 factoredof→|)解：解：Date 20信息學(xué)院 舉例 33)求文法求文法 G的的 FOLLOW 集合集合 (GrammarstatementFirst(stmtsequence)={s},解：解：Date 21信息學(xué)院 課堂練習(xí) E’→+TE’|εT’→*FT’|ε(， iFIRST(T’)={*,ε}{FIRST(E’)={+,ε}{(， i})})}),FOLLOW(T’)=+),孫麗云第 4章 語(yǔ)法分析■計(jì)算。孫麗云第 4章 語(yǔ)法分析■集合是針對(duì)規(guī)則（產(chǎn)生式）的。α是文法的任一條規(guī)則，則定義：Select(A?α)=First(α) 若 α=*{?}?例：求下列文法的每個(gè)規(guī)則的 Select集合：A?aB|dB?bBA|孫麗云第 4章 語(yǔ)法分析一個(gè)上下文無(wú)關(guān)文法 G是 LL(1)文法，當(dāng)且僅當(dāng)對(duì) G中每個(gè)非終結(jié)符 A的任何兩個(gè)不同的規(guī)則 A?α)Select(A?=LL(1)文法的要求文法的要求 孫麗云第 4章 語(yǔ)法分析■?（ 2） S?aABA?bB|dA|eDate 26信息學(xué)院 → addop|左因子左因子ifstmt()()else某些非某些非 LL(1)文法到文法到 LL(1)文法的改寫文法的改寫Date 27信息學(xué)院 ?Sa對(duì)這個(gè)文法的句子不能用對(duì)這個(gè)文法的句子不能用 LL(1)文法進(jìn)行分析文法進(jìn)行分析含有左遞歸的文法使自上而下的分析過(guò)程陷入了一個(gè)死循環(huán)。消除左遞歸消除左遞歸解決辦法：消除左遞歸 → addop|孫麗云第 4章 語(yǔ)法分析將文法將文法 G：： 提取左因子。A→αA’ A’→β|γ■提取左因子。stmtsequence→stmt。stmtsequencestmtstmt→sstmtseq’stmtseq’→。stmtsequenceεstmt→s注意：不可以這樣提取：A?a(β|γ )文法中括號(hào)的含義與正規(guī)式中括號(hào)的含義不同。孫麗云第 4章 語(yǔ)法分析1)將文法將文法 G提取左因子。ifstmtifexpstatementifexpstatementstatement ifstmt → if (exp) statement elsepart elsepart → else statement |:expterm+exp提取左因子?！鷈xp’exp’→exp ∣ε練習(xí)練習(xí)Date 30信息學(xué)院 167。孫麗云第 4章 語(yǔ)法分析■LL(1)文法的要求：一個(gè)上下文無(wú)關(guān)文法 G是 LL(1)文法，當(dāng)且僅當(dāng)對(duì) G中每個(gè)非終結(jié)符 A的任何兩個(gè)不同的規(guī)則 A?α)Select(A?=例： S?aABA?bB|dA|e?Date 32信息學(xué)院 求求 First集合綜合舉例集合綜合舉例求下列各種情況下的求下列各種情況下的 First(A)(1)A∈∈ T(2)A∈∈ N例：例： ①① A?aB|ε②② A?BaB?bd|c|ε④④ A?BCaε⑤⑤ A?BCDεD?m|孫麗云第 4章 語(yǔ)法分析■B?Aa(3)C?aABDate 34信息學(xué)院 167。例如：對(duì)下列文法消除左遞歸并提取左因子：例如：對(duì)下列文法消除左遞歸并提取左因子：S?rD|rdD?D,i|i注意：含有左遞歸或左因子的文法必定不是 LL(1)文法，但不含左遞歸和左因子的文法不一定是LL(1)文法。Date 35信息學(xué)院 LL(1)文法舉例文法舉例設(shè)有文法 G[S]：S?aABbcd|?ASd|???（ 2）求每一個(gè)非終結(jié)符號(hào)的 FIRST集合。（ 4）該文法是 LL(1)文法嗎？注意檢查文法DaBD|?可去掉！不是 LL(1)文法。孫麗云第 4章 語(yǔ)法分析■消除左遞歸與回溯，還可以用 EBNF表示法：252。例：例： ifstmt ?(statementifexp )statementifstmtifstatementstatement]exp ?exp addop term | term exp ?term { addop term }252。252。例：例： A?孫麗云第 4章 語(yǔ)法分析■的定義。由于文法常常是遞歸定義的，所以相應(yīng)的函數(shù)會(huì)出現(xiàn)相由于文法常常是遞歸定義的，所以相應(yīng)的函數(shù)會(huì)出現(xiàn)相互遞歸調(diào)用的過(guò)程，所以這種分析方法稱為遞歸下降分互遞歸調(diào)用的過(guò)程，所以這種分析方法稱為遞歸下降分析法。采用此種方法進(jìn)行語(yǔ)法分析的前提：文法是 LL(1)文法。識(shí)別過(guò)程： P64P65Date 38信息學(xué)院 預(yù)測(cè)分析法與預(yù)測(cè)分析表的構(gòu)造預(yù)測(cè)分析法與預(yù)測(cè)分析表的構(gòu)造預(yù)測(cè)分析法也稱 LL(1)分析法。一個(gè)預(yù)測(cè)分析器的 組成部分 ：預(yù)測(cè)分析表（ LL(1)分析表）、一個(gè)先進(jìn)后出分析棧和一個(gè)總控程序。Date 39信息學(xué)院 預(yù)測(cè)分析表的構(gòu)造算法預(yù)測(cè)分析表的構(gòu)造算法（ 1）計(jì)算每一非終結(jié)符的 First集和 Follow集；（ 2）對(duì)于 First(α)中的每個(gè)記號(hào) a，都將 Aα添加到表項(xiàng) M[A,→→ a]中中 。P67例：文法： S?a|^|(T)T?T,S|S試判斷該文法是否是 LL(1)文法，若不是請(qǐng)轉(zhuǎn)換，并求轉(zhuǎn)換后 LL(1)文法 的預(yù)測(cè)分析表。Date 40信息學(xué)院 練習(xí) 1}Follow(exp’)={$,)}Follow(addop)={(,number}Follow(term)={$,+,,(1)First集和集和 Follow集集First(exp)={(,number}First(exp’)={+,,First(term)={(,number}First(term’)={*,First(mulop)={*}First(factor)={(,number}文法：文法： exp →| term mulop factor∣factormulop →*factor →( exp) ∣ number孫麗云第 4章 語(yǔ)法分析Follow(exp)={$,)$,+,,)}Follow(term’)={$,+,,)}Follow(mulop)={(,number)Follow(factor)={*,)}First(exp’)={+,,First(term)={(,number)First(term’)={*,First(mulop)={*}First(factor)={(,number)111097 8888665422 3311factormulopterm’termaddopexp’exp$*+)Number(M[N,T](3)LL(1)分析表分析表解解 (1)expexp’2termexp’→ ε4→ +5→ 6→→ term’7→→ factorterm’mulopfactorfactor→→ a]中；（ 2）若 ε在在 First(α)中中，則對(duì)于，則對(duì)于 Follow(A)的的每個(gè)元素每個(gè)元素 a(記號(hào)或是記號(hào)或是 $)，都將，都將 Aα添加到添加到M[A,中。孫麗云第 4章 語(yǔ)法分析●LL(1)分析表分析表S→tI→( e) sSεe01Date 43信息學(xué)院 (1)statement →statementother3→( exp)elsepart4→ statement5exp0exp1(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)={)}else ()0ifstmtelsepart孫麗云第 4章 語(yǔ)法分析3)求文法求文法 G的的 →stmt→。stmtsequence|εstmt→s■課堂練習(xí)課堂練習(xí)Date 45信息學(xué)院 (1)stmtsequencestmt seq’(2)→。stmtsequence(3)→ε(4) s $stmtsequencestmt12 34First(stmtsequence)={s},$}Follow(stmtseq’)={$}孫麗云第 4章 語(yǔ)法分析■自上而下語(yǔ)法分析過(guò)程自上而下語(yǔ)法分析過(guò)程 參照 P68LL(1)分析表分析表s1s2s2ss。是否是該文法定義的語(yǔ)言。M[N,T]。s2孫麗云第 4章 語(yǔ)法分析課堂練習(xí)：文法： S?a|^|(T)T?T,S|S試判斷該文法是否是 LL(1)文法，若不是請(qǐng)轉(zhuǎn)換，并求轉(zhuǎn)換后 LL(1)文法 的預(yù)測(cè)分析表。分析：句子分析：句子 (a,^)是否為該文法定義的語(yǔ)言?！鲎陨隙抡Z(yǔ)法分析過(guò)程自上而下語(yǔ)法分析過(guò)程 參照 P68孫麗云（（ 1）簡(jiǎn)單直接左遞歸的消除）簡(jiǎn)單直接左遞歸的消除AAα| AβA’A’αA’|LL(1)分析方法相關(guān)知識(shí)總結(jié)分析方法相關(guān)知識(shí)總結(jié)（（ 2）將文法）將文法 G：： 提取左因子。A→αA ’ A’→β|γ求改寫文法中的非終結(jié)符的 First集和 Follow集；判斷文法是否是 LL(1)文法；一個(gè)上下文無(wú)關(guān)文法 G是 LL(1)文法，當(dāng)且僅當(dāng)對(duì) G中每個(gè)非終結(jié)符 A的任何兩個(gè)不同的規(guī)則 A?α)Select(A?=→→ a]中；（ 2）若 ε在在 First(α)中，則對(duì)于中，則對(duì)于 Follow(A)的每個(gè)元素的每個(gè)元素 a(記號(hào)或是記號(hào)或是 $)，都將，都將 Aα添加到添加到 M[A,中。Date 49信息學(xué)院 LL(1)分析方法綜合舉例分析方法綜合舉例已知文法： G[S]:A→aB|c步驟：（ 1）消除文法中的左遞歸或提取左因子；（ 2）求改寫文法中的非終結(jié)符的 First集和 Follow集；（ 3）判斷該文法是否是 LL(1)文法，若是，則構(gòu)造預(yù)測(cè)分析表；（ 4）根據(jù)分析表進(jìn)行自頂向下的語(yǔ)法分析。孫麗云第 4章 —— “移進(jìn) 歸約 ”與自上而下的語(yǔ)法分析方法進(jìn)行比較：■識(shí)別串 w=cabd是否是該文法的句子。自底向上的分析自底向上的分析Sc A da bc da bc da bAc da bASDate 51信息學(xué)院 (T?N)* 稱稱 a為為 句型句型 。(T?N)* 為為 文法的文法的 句型句型 ,U =+ u, 則則 u是句型是句型 w相對(duì)于相對(duì)于 U 的的