編譯原理復(fù)習(xí)重難點(diǎn)

1、第一章從本質(zhì)上來說，程序設(shè)計(jì)語言是按一定規(guī)則排列的符號(hào)集合，而編譯程序就是把這些符號(hào)集合變成機(jī)器指令的轉(zhuǎn)換器，編譯程序又稱為編譯器。程序設(shè)計(jì)語言【高級(jí)語言，低級(jí)語言（機(jī)器語言和匯編語言）】編譯過程：詞法分析，語法分析，中間代碼生成，優(yōu)化，目標(biāo)代碼產(chǎn)生。三元式定義為如下形式：（op, a1, a2)其中op為操作碼或運(yùn)算符，a1和a2為操作數(shù)或運(yùn)算分量。編譯 : 將高級(jí)語言程序翻譯成另一種語言的等價(jià)程序。解釋：翻譯一句執(zhí)行一句，邊翻譯邊執(zhí)行，直到程序結(jié)束。 與編譯的區(qū)別：不生成等價(jià)的目標(biāo)代碼程序。 優(yōu)點(diǎn)：解釋方式便于程序的調(diào)試。（編譯方式只需翻譯一次，且目標(biāo)程序的執(zhí)行速度快） （1） 詞法分析主

2、要任務(wù)：從左到右掃描源程序，逐一讀入構(gòu)成源程序的字符流，識(shí)別出 其中的一個(gè)個(gè)單詞，識(shí)別出的單詞稱單詞符號(hào)，也簡(jiǎn)稱符號(hào)。單詞是高級(jí)語言程序中有實(shí)際意義的最小語法單位。（2） 語法分析任務(wù)“組詞成句”，根據(jù)單詞分析出組成源程序的各類語法單位， 并指出其中的語法錯(cuò)誤。語法單位由源程序的單詞構(gòu)成（如表達(dá)式、語句、乃至整個(gè)程序。）語法單位的構(gòu)成規(guī)則語法規(guī)則。一個(gè)語言的詞法規(guī)則和語法規(guī)則定義了一個(gè)程序的形式結(jié)構(gòu)。語法單位的表示語法樹 （3） 語義分析和中間代碼生成任務(wù)：分析出語法單位具體的動(dòng)作意義，進(jìn)行初步翻譯，生成與源程序等價(jià)的中間代碼程序。語義: 定義一個(gè)程序所表示的意義,用語義規(guī)則描述。 中間代碼：

3、指令應(yīng)結(jié)構(gòu)簡(jiǎn)單、含義明確，易于實(shí)現(xiàn)源程序中間代碼 目標(biāo)代碼三者之間的轉(zhuǎn)換。中間代碼常用形式： 逆波蘭式、三元式、四元式等。四元式： （運(yùn)算符，對(duì)象1，對(duì)象2，結(jié)果）例：z=x+a%3*y (1)（ % a 3 t1 ） （2） （ * t1 y t2 ） (3)（3） （ + x t2 t3 ）（4） （ = t3 _ z ）（4） 代碼優(yōu)化 任務(wù)： 對(duì)中間代碼進(jìn)行等價(jià)的加工變換，以便生成更有效更節(jié)省時(shí)間和空間的目標(biāo)代碼。 例：z=x+a%3*y 的四元式序列： (1)% a 3 t1 ） （2） （ * t1 y t2 ）(3)（ + x t2 z ） （5）目標(biāo)代碼生成 任務(wù)：將中間代碼程

4、序變換成目標(biāo)代碼程序。2 按“遍”組合方式 “遍”：對(duì)源程序或等價(jià)的中間語言程序從頭到尾掃描，完成規(guī)定的 任務(wù)，并生成新的中間結(jié)果或目標(biāo)程序，稱一“遍”。編譯程序的構(gòu)造與三個(gè)方面有關(guān) :源語言 ，目標(biāo)語言，編譯方法。第二章 形式語言與自動(dòng)機(jī)理論基礎(chǔ)主要內(nèi)容：語言和文法、有限自動(dòng)機(jī)、正則表達(dá)式。語言：符號(hào)串的集合。 元素 符號(hào)串該語言的一個(gè)句子。 字母表符號(hào)串中符號(hào)的來源。【例2-1】 =a，b，c，z，x =“l(fā)augh”，則 |x|=5 =I，you，he，am，is，are，a，student， y=“I am a student”，空格不計(jì)算長(zhǎng)度，則 |y|=4。空符號(hào)串：無任何符號(hào)的串

5、，簡(jiǎn)稱空串，用表示，|=0【例2-4】 若 U = a，b ， V = c，d 則 UV = ac，ad，bc，bd 閉包： 若指定字母表，則*表示上的所有有窮長(zhǎng)的串的集合。* =012n * 稱為集合的閉包。 + =12n + 稱為集合的正閉包。成立的等式：* =0+ ， + =* =* 若符號(hào)串 x 是*的元素,則表示為 x* ,否則 x Ï* 。 【例2-5】 =0,1 *=,0,1,00,10,11,000,001,100,文法的形式定義：1：終結(jié)符用VT 表示、2：非終結(jié)符用VN 表示、3：規(guī)則 、4：文法 定義：一個(gè)文法是一個(gè)四元組G（VN ，VT ，S ， P） VN

6、： 非終結(jié)符集（非空）；VT ： 終結(jié)符集（非VNVTØ ； S：識(shí)別符號(hào)或開始符號(hào)，SVN，且至少在一條規(guī)則中作為左部出現(xiàn)； P ： 規(guī)則（產(chǎn)生式）的集合。用V表示 VNVT ，稱G的字母表或詞匯表。 【例2-7】 有一文法G（VN ，VT ，S ， P） 其中: VN = S VT = 0，1 開始符號(hào)是 S P = S0S1， S01 2. 擴(kuò)展的BNF 表示法 （1）“ ” 表示符號(hào)串t的多次重復(fù)，n為重復(fù)的最小次數(shù)，m為重復(fù)的最大次數(shù)，省略n、m表示t可以重復(fù)0到任意多次。 【例2-9】文法規(guī)則 S0S1|01 簡(jiǎn)化為 S0(S1|1) 或 S(0S|0)1 或 S0(S|

7、 )1（3） “ ”：t表示符號(hào)串t可選（即可有可無）?！纠?-11】C語言條件語句的語法圖：文法相關(guān)概念：定義1：如是文法G（VN ，VT ，S ， P）的一條規(guī)則， 、V * ，若有符號(hào)串 v、w 滿足 v =， w = 則稱v（應(yīng)用規(guī)則）直接產(chǎn)生w ，或稱 w 是 v 的直接推導(dǎo)，反過來稱 w 直接歸約 到 v ，記作 v w ?！纠?-13】 對(duì)文法G： S0S1 S 01 有直接推導(dǎo)序列： S 0S1 00S11000111 定義2：如果存在直接推導(dǎo)序列：v = w0 w1 w2 wn = w 則稱v 推導(dǎo)（產(chǎn)生）出w，推導(dǎo)長(zhǎng)度為n ，反過來稱w 歸約到v，記作 v w。 如果有 v

8、 w ，或 v = w ，則記作 v w?！纠?-14】 S 0S1 00S11 000111 S 推導(dǎo)出 “ 000111” ， 推導(dǎo)長(zhǎng)度3 “ 000111” 歸約到 S， 表示成 S 0001112句型和句子定義： 文法G（VN，VT，S ，P），若符號(hào)串x可由開始符號(hào)S推導(dǎo)出（S x），則稱 x 是 G 的一個(gè)句型，若x僅由終結(jié)符組成，則稱 x 為G 的一個(gè)句子。3 形式語言 定義：文法描述的語言是該文法的所有句子的集合，記作 L(G)。集合形式表示：L(G) = | S VT* 【例2-16】文法G： S 0S1 S 01 描述的語言：L(G)= 0n1n | n1 4文法的等價(jià)性

9、定義：若有文法G1、G2，它們描述的語言相同，即 L( G1 ) = L( G2 ) 則稱兩文法 G1 和 G2 等價(jià)。 【例2-17】有文法 GA： A0R A01 RA1 描述的語言 L(G) = 0n1n | n1 。定義：若有文法G1、G2，它們描述的語言相同，即 L( G1 ) = L( G2 ) 則稱兩文法 G1 和 G2 等價(jià)。 5. 遞歸規(guī)則和遞歸文法遞歸規(guī)則：形如P1P2的規(guī)則稱遞歸規(guī)則。 若1=則稱左遞歸規(guī)則;若2=則稱右遞歸規(guī)則。遞歸文法：含有遞歸規(guī)則的文法稱遞歸文法。 P1P2的遞歸稱間接遞歸,含間接遞歸的文法也是遞歸文法。 文法分類：1、0型文法（無限制文法或短語文法

10、）定義2-7 設(shè)G=(VN，VT，P，S)，如果它的每個(gè)產(chǎn)生式滿足、(VNVT)*，且至少含有一個(gè)非終結(jié)符，則G是一個(gè)0型文法。結(jié)論：0型文法的能力相當(dāng)于圖靈機(jī)。 任何0型語言都是遞歸可枚舉的，反之，遞歸可枚舉集也必定是一個(gè)0型語言。2、1型文法 （上下文有關(guān)文法）定義2-8 設(shè)G=(VN，VT，P，S)，如果它的每個(gè)產(chǎn)生式滿足 |（僅S除外），則G是一個(gè)1型文法。 另一種描述：文法的產(chǎn)生式形如 1A2 12 其中AVN，、(VNVT)*且。 【例2-18】1型文法GS：S xSYZ | xYZ yZyzxYxy ZYYZyYyy zZzz3、2型文法 （上下文無關(guān)文法）定義2-9 設(shè)G=(V

11、N，VT，P，S)，如果它的每個(gè)產(chǎn)生式中的是一個(gè)非終結(jié)符，則G是一個(gè)2型文法或上下文無關(guān)文法。【例2-19】 2型文法GS： SE TP | TP Fi | (E) ET | ET PF | FP 4、3型文法 （正規(guī)文法或正則文法）定義2-10 設(shè)G=(VN，VT，P，S)，如果它的每個(gè)產(chǎn)生式均形如AaB 或 Aa 其中A、BVN，aVT。 【例2-20】 3型文法GS ： S aA A aA A a S a A dA A d 消除空產(chǎn)生式定理：對(duì)任一文法G1，可構(gòu)造文法G2，使得L(G1)=L(G2)，且G2中無空產(chǎn)生式。證明：根據(jù)G1，構(gòu)造G2的方法如下： (1) 令b=A | A

12、24;e(2) b=bÈA | A Þ +a, aÎb+。(3) 從G1中刪除所有空產(chǎn)生式。(4) 從G1中刪除只能導(dǎo)出空串的非終極符。(5) 對(duì)于文法中任意產(chǎn)生式AàX1X2Xi-1XiXi+1Xn a.若XiÎVT，不做動(dòng)作；b.若XiÎVN-b，不做動(dòng)作；c.若XiÎb，補(bǔ)充規(guī)則Aà X1X2Xi-1Xi+1Xn；例： AàaBcD Bàb | e DàBB | d 詳見Page18消除不可達(dá)產(chǎn)生式定理：對(duì)任一文法G1都可以構(gòu)造文法G2，使得L(G1)=L(G2)，且G2中的每個(gè)

13、非終極符必出現(xiàn)在它的某個(gè)句型中。證明：根據(jù)G1，構(gòu)造文法G2的方法如下：(1) 令b=Z | Z是文法的開始符。(2) 遞歸擴(kuò)充b直到收斂為止，即 =bÈB | AàxByÎG1, BÎVN, AÎb(3) 若一個(gè)產(chǎn)生式左部非終極符AÏb，則刪除以A為左部的所有產(chǎn)生式。消除特型產(chǎn)生式 注：形如A->B(B為非終極符)的產(chǎn)生式為特型產(chǎn)生式，特型產(chǎn)生式在語法分析中會(huì)降低分析速度，因此應(yīng)該消除。定理：對(duì)任一文法G1，可以構(gòu)造文法G2，使得L(G1)=L(G2)，且在G2中沒有特型產(chǎn)生式。證明：構(gòu)造無特型產(chǎn)生式的文法G2的方法如下：(1

14、) 對(duì)文法G1中任意非終極符A，求集合 A=B | AÞ+B, BÎVN。(2) 若BÎbA，且Bàa是文法G中的一個(gè)非特型產(chǎn)生式，則補(bǔ)充如下規(guī)則Aà(3) 去掉文法G1中的所有的特型產(chǎn)生式。(4) 去掉新的文法中的無用產(chǎn)生式。例：AàB | D | aBBàC | bCàcDàB | d消除左遞歸一個(gè)文法含有下列形式的產(chǎn)生式時(shí)（1） A®Aa |b AÎVN, a ,b Î(VNÈVT)*（2） A ® Ba | B ® Ag | b A,B

15、ÎVN, a ,b,g Î (VNÈVT)*其中（1）為直接左遞歸，（2）為間接左遞歸，因此文法中只要有AÞ+A，則稱文法為左遞歸的。 文法的化簡(jiǎn)：文法應(yīng)沒有多余的或有害的規(guī)則。 化簡(jiǎn)：(1) 刪除形如AA的產(chǎn)生式。 (2) 刪除不可到達(dá)的文法符號(hào)及其相應(yīng)的產(chǎn)生式。 (3) 刪除不可終止的非終結(jié)符及其相應(yīng)的產(chǎn)生式。 【例2-21】 文法G： S aS | W | U U a V bV | ac W aW 化簡(jiǎn)后的文法G： S aS | U U a W 是不可終止的、V 是不可到達(dá)的。文法的二義性可見：（1）一棵語法樹表示了一個(gè)句型的多種可能的不同推導(dǎo)過程

16、， 但未必是所有的。 （2）一個(gè)句型未必只有一棵語法樹。 最左推導(dǎo)：在推導(dǎo)的任何一步（、是句型）都是對(duì)中的最左非終結(jié)符進(jìn)行替換。 最右推導(dǎo)：在推導(dǎo)的任何一步（、是句型）都是對(duì)中的最右非終結(jié)符進(jìn)行替換。也稱規(guī)范推 導(dǎo)，推出的句型稱規(guī)范句型。 例如 最左推導(dǎo)： E E*E i*E i*E+E i*i+E i*i+i 最右推導(dǎo)： E E*E E*E+E E*E+i E*i+i i*i+I顯然，一棵語法樹表示的最左（右）推導(dǎo)是唯一的！ 定義：若一個(gè)文法存在某個(gè)句子，它對(duì)應(yīng)兩棵（或以上）不同的語法樹，或 它有兩個(gè)不同的最左（右）推導(dǎo)，則該文法是二義的（具有二義性）。二義性文法：如果一個(gè)文法的某個(gè)句型有兩

17、棵不同的語法分析樹，則稱該文法二義性為二義性文法。文法G=( +,*,I,(,), E, E, P),其中P為： E ® i E ® E + E E ® E * E E ® ( E )1. 正規(guī)式和正規(guī)集的定義 定義 ：設(shè)有字母表，則（1）和 Ø都是上的正規(guī)式，所表示的正規(guī)集是和Ø； （2）若a，則a是上的正規(guī)式，所表示的正規(guī)集是a； （3）若U、V都是上的正規(guī)式，它們所表示的正規(guī)集分別記為L(zhǎng)(U) 和L(V)，則U|V（或）、U·V（連接，也可寫UV）和U*（閉包）也 都是正規(guī)式，它們所表示的正規(guī)集分別為L(zhǎng)(U)L(V)

18、、L(U) L(V) （乘積）和(L(U)*； （4）僅由有限次使用上述三步驟得到的表達(dá)式才是上的正規(guī)式， 僅由這些正規(guī)式所表示的集合才是上的正規(guī)集。優(yōu)先級(jí)從高到低為“*”（閉包）、“·”（連接）、“|”（或），括號(hào)優(yōu)先。 1. 正規(guī)式 正規(guī)文法 有限自動(dòng)機(jī)【確定的有窮自動(dòng)機(jī)DFA、不確定的有窮自動(dòng)機(jī)NFA】確定的有窮自動(dòng)機(jī)DFA DFA的意義： 對(duì)于*中的任何字符串t，若存在一條從初態(tài)到終態(tài)的路徑（該路徑 上的字符串為t），則t 可為DFA M所接受（或說t 是該DFA可識(shí)別的）。 若初態(tài)結(jié)也是終態(tài)結(jié)，則空字可接受。 DFA M 所能接受的字符串的全體稱為該自動(dòng)機(jī)識(shí)別的語言，記為L(zhǎng)

19、(M)。 結(jié)論：上的一個(gè)字符串集U是正規(guī)的，當(dāng)且僅當(dāng)存在一 個(gè)上的確定的 有窮自動(dòng)機(jī)DFA M，使U=L(M)。不確定的有窮自動(dòng)機(jī)NFANFA與DFA的等價(jià)性2. NFA的確定化 定義：一個(gè)狀態(tài)集合I 的閉包 closure(I) ： 若qI，則 q closure(I)； 若qI，則 q經(jīng)任意條弧而能到達(dá)的任何狀態(tài)q : q closure(I) 定義：一個(gè)狀態(tài)集合I 的a弧轉(zhuǎn)換為 Ia = closure(J) 其中: J 是所有那些可以從 I 中的某一狀態(tài)經(jīng)過一條 a 弧而到達(dá)的狀態(tài)的集合。NFA與DFA的等價(jià)性NFA M = ( Q , Q0 , Z ) DFA M¢ = (

20、 Q¢,¢, q0¢ , Z¢ ) Q¢= Ø； Z¢= Ø；Q0 ¢= eClosure (Q0 )將 Q0 ¢置為未標(biāo)記，并加入到Q¢中；While(Q¢中存在未標(biāo)記的狀態(tài)子集I) 對(duì)每個(gè)a 做 求Ia; 若Ia不在Q¢中，則把它置為未標(biāo)記后加入到Q¢中； 若Ia至少有一個(gè)是M的終態(tài)，則同時(shí)把Ia加入到Z¢ 中； 給I加上標(biāo)記；重新命名Q¢中的所有狀態(tài)子集為新的狀態(tài)；Q0 ¢對(duì)應(yīng)的新狀態(tài)q0¢ 即為DFA M&#

21、162;的初態(tài)；Z¢ 中的所有狀態(tài)子集對(duì)應(yīng)的新狀態(tài)為DFA M¢ 的終態(tài)；DFA的化簡(jiǎn)構(gòu)造與FA等價(jià)的正規(guī)式構(gòu)造與正規(guī)式等價(jià)的FA 構(gòu)造正規(guī)文法等價(jià)的FA構(gòu)造正規(guī)文法G( VN ，VT ，P，S )等價(jià)的FA M=(Q,q0, Z) 1、字母表：M的字母表對(duì)應(yīng)G的VT 2、狀態(tài)集Q: M的Q對(duì)應(yīng)G的VN 3、初態(tài)q0： M的q0對(duì)應(yīng)G的S 4、轉(zhuǎn)換函數(shù)： M的轉(zhuǎn)換函數(shù) 對(duì)應(yīng)G的AaB ， AaAaB： (A,a)=BAa ： (A,a)=Z 構(gòu)造與FA等價(jià)的正規(guī)文法 第3章 詞法分析任務(wù)：識(shí)別單詞。完成詞法分析任務(wù)的程序也稱詞法分析器或掃描器。單詞的種類單詞：程序中最小的有

22、意義的單位。五類單詞： 關(guān)鍵字、 標(biāo)識(shí)符、 常數(shù) 、 運(yùn)算符、界符。單詞的機(jī)內(nèi)表示方法 二元式： （單詞種別 ，屬性）單詞的形式描述正規(guī)式描述 正規(guī)文法描述 正規(guī)文法：每個(gè)產(chǎn)生式均形如 AaB 或 Aa 。 預(yù)處理：刪除無用空格、換行符、注釋，源程序輸入輸出等。第4章 自頂向下語法分析把句子分析的過程稱為語法分析，即完成這個(gè)任務(wù)的程序稱為語法分析程序或稱為識(shí)別程序。分析算法又稱識(shí)別算法。語法錯(cuò)誤類別 1) 程序的開始符，語句（表達(dá)式）的開始 符（后繼符）錯(cuò)    2) 標(biāo)識(shí)符（常量）錯(cuò)：該出現(xiàn)時(shí)未出現(xiàn)     3) 括號(hào)類錯(cuò)誤：不匹配

23、   4) 分隔符錯(cuò)：assignment分析算法可分為：自上而下分析法：從文法的開始符號(hào)出發(fā)，尋找與輸入符號(hào)串匹配的推導(dǎo)，或者說，為輸入串尋找一個(gè)最左推導(dǎo)。自下而上分析法：從輸入符號(hào)串開始，逐步進(jìn)行歸約，直至歸約到文法的開始符號(hào)。語法分析中語法錯(cuò)誤處理要求：報(bào)告錯(cuò)誤出現(xiàn)的位置、修復(fù)錯(cuò)誤并繼續(xù)檢查后續(xù)部分、執(zhí)行開銷不應(yīng)太大。處理策略：1）緊急方式恢復(fù)； 2）短語級(jí)恢復(fù)； 3）出錯(cuò)產(chǎn)生式4）全局糾正；語法描述工具：上下文無關(guān)文法 產(chǎn)生式形如 A（AVN ，V * ) 自頂向下語法分析概述 問題的本質(zhì)：識(shí)別一個(gè)符號(hào)串是否為某文法的一個(gè)句型。即試圖按文法的規(guī)則為符號(hào)串構(gòu)造推導(dǎo)或語

24、法樹。語法分析方法： 自頂向下的語法分析方法、 自底向上的語法分析方法。4.2.1 自頂向下的語法分析方法 方法：從文法的開始符號(hào)出發(fā)，反復(fù)選用各產(chǎn)生式進(jìn)行最左推導(dǎo)，以“匹配”于輸入符號(hào)串，若推導(dǎo)成功，則輸入串是該語言的一個(gè)合法句型，否則就不是。需解決的主要問題：若同一個(gè)非終結(jié)符有多個(gè)產(chǎn)生式，則推導(dǎo)時(shí)究竟選用哪一個(gè)？ 兩種分析方法（確定的自頂向下語法分析方法，不確定的自頂向下語法分析方法 ）4.2.2 確定的自頂向下的語法分析方法 【例4-4】有文法G： SxA SyB AaA|c BbB|d句子“xaac”或“ybbd”的推導(dǎo)過程?確定的自頂向下的語法分析方法： 若在推導(dǎo)時(shí)每次都能根據(jù)輸入串

25、當(dāng)前所要匹配的符號(hào)選擇唯一的一個(gè)產(chǎn)生式往下推，則這種分析方法就稱為確定的自頂向下的語法分析方法。 顯然，能否進(jìn)行確定的自頂向下的語法分析是由文法決定的。 4.2.3 不確定的自頂向下的語法分析方法 例4-5】有文法G： SxA SxB AaA|a BbB|b句子“xaa”或“xbb”的推導(dǎo)過程？句型的推導(dǎo)過程帶“回溯” 不確定的自頂向下語法分析方法。不確定性：每一步推導(dǎo)不一定能根據(jù)當(dāng)前輸入的單詞符號(hào)唯一地確定選用的產(chǎn)生式。4.3.1 “回溯”的原因 1提取左公共因子 若有： A12n 則： A（12n） 再引入一個(gè)新的非終結(jié)符A¢ ： A A¢ A¢ 12n 注意

26、：提取出來后，1、2、n中的某幾個(gè)i 還可能 含有左公共因子，則可以進(jìn)一步進(jìn)行提取。4.3.2 “回溯”的消除 4.3.3 LL(1)文法的定義 問題：何種文法能進(jìn)行確定的自頂向下的語法分析？ 分兩種情況進(jìn)行分析1，不含產(chǎn)生式的文法、2含產(chǎn)生式的文法 Conclusion：當(dāng)文法中非終結(jié)符A不含產(chǎn)生式時(shí)，若其不同產(chǎn)生式的右部的FIRST集兩兩互不相交，則當(dāng)用A的產(chǎn)生式進(jìn)行推導(dǎo)時(shí)能唯一確定應(yīng)選用的產(chǎn)生式。 FOLLOW(A)= Ø 對(duì)文法的開始符號(hào)S置FOLLOW(S)= #; 對(duì)所有形如B A的產(chǎn)生式做： FOLLOW(A)= FOLLOW(A)U（FIRST（ ）-）； FOLLO

27、W(A)= FOLLOW(A)U FOLLOW(B) 對(duì)所有形如B A的產(chǎn)生式做： FOLLOW(A)= FOLLOW(A)U FOLLOW(B)Conclusion: 當(dāng)文法中非終結(jié)符A含有產(chǎn)生式時(shí)，若滿足以下條件，則當(dāng)用A 的產(chǎn)生式進(jìn)行推導(dǎo)時(shí)仍能唯一確定應(yīng)選用的產(chǎn)生式： （1）A的非產(chǎn)生式的右部的FIRST集兩兩互不相交；（2）FOLLOW(A)也不與A的任一非產(chǎn)生式的右部的FIRST集相交。另一種描述： 當(dāng)文法中有A，A時(shí)，若、不能同時(shí)推出 （設(shè) ， ），且滿足條件 FIRST()(FIRST()FOLLOW(A)=Ø 則對(duì)非終結(jié)符A的替換仍能確定唯一的產(chǎn)生式。3 LL(1)文

28、法定義：上下文無關(guān)文法是LL(1)文法的充分必要條件是： （1）文法不含左遞歸； （2）對(duì)每個(gè)非終結(jié)符A的兩個(gè)不同的產(chǎn)生式 A、 A （其中、不能同時(shí)推出），滿足條件: SELECT(A)SELECT(A)=Ø 判別LL(1)文法的方法和步驟： （1）根據(jù)定義計(jì)算每個(gè)產(chǎn)生式的SELECT集； （2）對(duì)左部相同的產(chǎn)生式，查看它們的SELECT集，若兩兩互不相交，則為L(zhǎng)L(1)文法。預(yù)測(cè)分析法 也叫LL(1) 分析法 采用這種方法進(jìn)行語法分析的程序 就叫做預(yù)測(cè)分析器或LL(1)分析器。 預(yù)測(cè)分析器由三部分組成 （一張預(yù)測(cè)分析表、一個(gè)分析用的棧、 預(yù)測(cè)分析程序） 4.4.1 預(yù)測(cè)分析表 預(yù)測(cè)分析表: 矩陣 M 表示，其中 （1）行 以文法的非終結(jié)符為行， 一個(gè)非終結(jié)符一行； （2）列 以文法的終結(jié)符或句子括號(hào)“#”為列，一個(gè)終結(jié)符或“#”占一列； （3）MA，a 兩種值： 關(guān)于A的一條產(chǎn)生式；空著（出錯(cuò)處理）。 值的獲得：根據(jù)產(chǎn)生式的SELECT集， 若 aSELECT(A)， 則 MA，a =“A”。4.4.3 預(yù)測(cè)分析程序 4.5 遞歸下降分析法 組成：每個(gè)非終結(jié)符對(duì)應(yīng)一個(gè)遞歸過程或函數(shù)，其功能是按產(chǎn)生式的右部識(shí)別由該非終結(jié)符推出的串。分析過程： 從讀入第一個(gè)單詞起，由開始符號(hào)出