【文章內(nèi)容簡介】 分析的前提：文法是 LL(1)文法。 一個預測分析器的 組成部分 ： 預測分析表（ LL(1)分析表）、一個先進后出分析棧和一個總控程序。 預測分析器的總控程序?qū)τ诓煌?LL(1)文法都是相同的，而預測分析表對于不同的 LL(1)文法是不相同的。 第 4章 語法分析 2022/8/21 信息學院 孫麗云 40 ■ 預測分析表的構(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)容的空白格都標上出錯標志 error。 P67 例：文法： S?a|^|(T) T?T,S|S 試判斷該文法是否是 LL(1)文法，若不是請轉(zhuǎn)換，并求轉(zhuǎn)換后 LL(1)文法 的預測分析表。 第 4章 語法分析 2022/8/21 信息學院 孫麗云 41 ● 練習 1 Follow(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∣ term addop → + | term → term mulop factor∣ factor mulop →* factor →( exp) ∣ number 注意：先消除左遞歸 第 4章 語法分析 2022/8/21 信息學院 孫麗云 42 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) 11 10 9 7 8 8 8 8 6 6 5 4 2 2 3 3 1 1 factor mulop term’ term addop exp’ exp $ * + ) Number ( M[N,T] (3)LL(1)分析表 解 (1) 文法 1 exp → term exp’ 2 exp’→ addop term exp’ 3 exp’→ ε 4 addop → + 5 addop → 6 term → factor term’ 7 term’ → mulop factor term’ 8 term’ → ε 9 mulop → * 10 factor → (exp) 11 factor → number （ 1）對于 First(α)中的每個記號 a，都將 A → α添加到表項 M[A, a]中； （ 2）若 ε在 First(α)中，則對于 Follow(A)的每個元素 a(記號或是 $)，都將 A → α添加到 M[A, a]中。 第 4章 語法分析 2022/8/21 信息學院 孫麗云 43 ● 練習 2 2)求文法 G的 LL(1)分析表 statement → ifstmt | other ifstmt → if (exp) statement elsepart elsepart → else statement | ε exp → 0 | 1 (1) 文法 1 statement → ifstmt 2 statement → other 3 ifstmt → if (exp) statement elsepart 4 elsepart → else statement 5 elsepart →ε 6 exp → 0 7 exp → 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 ( ) 0 1 $ statement ifstmt elsepart exp 1 2 3 4 6 7 5 5 注意在構(gòu)造 LL(1)分析表之前別忘了先驗證文法是否為LL(1)文法??！ 第 4章 語法分析 2022/8/21 信息學院 孫麗云 45 3)求文法 G的 LL(1)分析表 stmtsequence →stmt stmtseq’ stmtseq’ → 。 stmtsequence|ε stmt→s ■ 課堂練習 (2)First集和 Follow集 (3)LL(1)分析表 解 (1) 文法 (1) stmtsequence →stmt stmtseq’ (2) stmtseq’ → 。 stmtsequence (3) stmtseq’ →ε (4) stmt→s M[N,T] 。 s $ stmtsequence stmtseq’ stmt 1 2 3 4 First(stmtsequence)={s} First(stmtseq’)={。, ε} First(stmt)={s} Follow(stmtsequence)={$} Follow(stmt)={。,$} Follow(stmtseq’)={$} 第 4章 語法分析 2022/8/21 信息學院 孫麗云 47 ■ 自上而下語法分析過程 參照 P68 表 例： 求文法 G的 LL(1)分析表 s1 →stmt s2 s2 → 。 s1|ε stmt→s 分別分析 s。s s。s。是否是該文法定義的語言 。 M[N,T] 。 s $ s1 s2 stmt 1 2 3 4 第 4章 語法分析 2022/8/21 信息學院 孫麗云 48 課堂練習：文法： S?a|^|(T) T?T,S|S 試判斷該文法是否是 LL(1)文法，若不是請轉(zhuǎn)換，并求轉(zhuǎn)換后 LL(1)文法 的預測分析表。 分析：句子 (a,^)是否為該文法定義的語言。 ■ 自上而下語法分析過程 參照 P68 表 （ 1） 簡單直接左遞歸的消除 A → Aα| β A → βA’ A’ → αA’| ε 消除文法中的左遞歸或提取左因子； ■ LL(1)分析方法相關(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)造預測分析表； （ 1）對于 First(α)中的每個記號 a，都將 A → α添加到表項 M[A, a]中； （ 2）若 ε在 First(α)中，則對于 Follow(A)的每個元素 a(記號或是 $)，都將 A → α添加到 M[A, a]中。 根據(jù)分析表進行自頂向下的語法分析。 第 4章 語法分析 2022/8/21 信息學院 孫麗云 50 ■ LL(1)分析方法綜合舉例 已知文法： G[S]: S→SaA|bB A→aB|c B→Bb|d 判斷” bdbac”以及” bdbab”是否是所給文法定義的語言。 步驟： （ 1）消除文法中的左遞歸或提取左因子； （ 2）求改寫文法中的非終結(jié)符的 First集和 Follow集； （ 3）判斷該文法是否是 LL(1)文法，若是，則構(gòu)造預測分析表； （ 4）根據(jù)分析表進行自頂向下的語法分析。 第 4章 語法分析 2022/8/21 信息學院 孫麗云 51 有文法 G： S→AB A→aAb|ε B→cBd|ε 該文法所定義的語言是下邊哪個集合（ ） A. {anbmdm|n,m≥0} B. {anbncmdm|n,m＞ 0} C. {anbmcmdn|n,m≥0} D. {anbncmdm|n,m≥0} ■ 期中考試 D 第 4章 語法分析 2022/8/21 信息學院 孫麗云 52 ■ 期中考試 一個文法所描述的語言是（ ）；描述一個語言的文法是（ ）。 ，也可能不唯一 A B 編譯程序中的語法分析器接受以（ ）為單位的輸入，并產(chǎn)生有關(guān)信息供以后階段使用。 C. 單詞符號 C 第 4章 語法分析 2022/8/21 信息學院 孫麗云 53 如果文法 G是無二義的，則下面說法正確的是（ ） ，它的最左或最右推導對應的語法樹相同 ■ 期中考試 D 給定文法 A?bA|cc，則符號串① cc② bcbc③bcbcc④ bccbcc⑤ bbbcc中，是該文法句子的是（ ） A.① B.③④⑤ C.②④ D.①⑤ D 第 4章 語法分析 2022/8/21 信息學院 孫麗云 54 ■ 期中考試 文法 G產(chǎn)生的（ ）的全體是該文法描述的語言 正規(guī)式 M1和 M2等價是指（ ）。 A. M1和 M2的狀態(tài)數(shù)相等 B. M1和 M2的有向邊條數(shù)相等 C. M1和 M2所識別的正規(guī)集相等 D. M1和 M2的狀態(tài)數(shù)和有向邊條數(shù)相等 設 x是符號串，符號串的冪運算 x0=（ ）。 D. ε D D C 第 4章 語法分析 2022/8/21 信息學院 孫麗云 55 ■ 期中考試 含有優(yōu)化部分的編譯程序的執(zhí)行效率高。 （ ） 對編譯程序而言，可以沒有代碼優(yōu)化的部分。 （ ） 編譯程序生成的目標程序一定是可執(zhí)行的程序。 （ ） 設 A是符號串的集合，則 A0=ε。（ ） 任何正規(guī)文法都是上下文無關(guān)文法。（ ） √ √ 第 4章 語法分析 2022/8/21 信息學院 孫麗云 56 ■ 期中考試 若一個語言是無窮集合，則定義該語言的文法也不一定是遞歸的。（ ） 規(guī)范推導是指最左推導。 （ ） 遞歸下降分析法是一種自下而上的語法分析方法。（ ） 若兩個正規(guī)式所表示的正規(guī)集相同，則認為二者是等價的。（ ） 一個確定的有窮自動機 DFA是一個三元組 （ VN,VT,P）。（ ） √ 第 4章 語法分析 2022/8/21 信息學院 孫麗云 57 ■ 期中