成果編譯原理chap

1、 ing/上載區(qū)/其他/編譯原理（天平與成教）92/編譯原理（天平與成教）第四章 自上而下語法分析4.1 語法分析程序的功能一、語法分析的地位 是編譯程序的核心部分。二、語法分析的功能以單詞符號為輸入識別語法成份對單詞序列進行語法檢查報錯或輸出某種形式的語法樹核心：識別由詞法分析得出的單詞序列是否是給定文法的句子。三、語法分析的理論基礎(chǔ)上下文無關(guān)文法和下推自動機第四章 自上而下語法分析 4.1 語法分析程序的功能四、語法分析的方式1、自上而下語法分析 反復使用不同產(chǎn)生式進行推導以謀求與輸入符號串相匹配。2、自下而上語法分析 對輸入符號串尋找不同產(chǎn)生式進行歸約直到文法開始符號。注：這里所說的輸入

2、符號指詞法分析所識別的單詞。第四章 自上而下語法分析4.2 自上而下語法分析法一、下推自動機模型有限狀態(tài)控制器下推棧輸入帶輸出帶注：1）PDA和FA的模型相比，多了一個下推棧。 2）PDA的動作由三個因素來決定：當前狀態(tài)、讀頭所指向符號、下推棧棧頂符號。 3）一個輸入串能被PDA所接受，僅當輸入串讀完，下推棧變空；或輸入串讀完，控制器到達某些終態(tài)。第四章 自上而下語法分析 4.2 自上而下語法分析法一、下推自動機模型注：4）輸出帶用以記錄推導或規(guī)約構(gòu)成所用的產(chǎn)生式編號。5)正規(guī)文法和有限自動機僅適合于描述和識別高級語言的各類單詞，語句可用上下文無關(guān)文法來描述，而下推自動機又恰好能識別上下文無關(guān)

3、文法所能描述的語言，因此上下文無關(guān)文法及其對應(yīng)的下推自動機就成為編譯技術(shù)中語法分析的理論基礎(chǔ)。第四章 自上而下語法分析 4.2 自上而下語法分析法二、下推自動機的形式定義PDA是一個七元組：M=(Q ,H,q0,z0,F)H：下推棧內(nèi)字母表z0 ：下推棧的棧初始符，是H中的元素。 ：Q( )H到QH*的有限子集映射。例如： (q,a,z)(q1,r1),(q2，r2)(qn,rn),其意義是：設(shè)控制器當前狀態(tài)為q,下推棧頂符號為z,輸入符號為a(可為空)，則狀態(tài)轉(zhuǎn)換到序偶集(q1,r1),(q2,r2)(qn,rn)(qi為下一狀態(tài), ri為代替z的棧頂符號串)FQ是控制器的終態(tài)集第四章 自上

4、而下語法分析 4.2 自上而下語法分析法二、下推自動機的形式定義注：1)由此定義的PDA肯定是不確定的PDA。這給語法分析會帶來不確定性。我們在構(gòu)造PDA M的算法的時候，要對PDA做一些限制。 2) PDA采用“”來表示PDA做了一步動作。 3)輸入串能為PDA所接受，僅當輸入串讀完，下推棧為空；或者輸入串讀完，控制器到達某些終態(tài)。 4)有時，下推自動機還配置輸出帶，以記錄推導或歸約過程所用的產(chǎn)生式編號。 5)對于形如A的產(chǎn)生式，有(q, ,A)=(q, ),這稱為推導 6) (q, a,a)=(q, )稱為匹配，其中a第四章 自上而下語法分析 4.2 自上而下語法分析法二、下推自動機的形式

5、定義由CFG G= （VN ，P，S） 構(gòu)造PDA M的算法：G= （VN ，P，S） M=（Q,H,q0,z0,F）令：Q=F=q0 即控制器只有一個狀態(tài) H= VN ; z0 =S; 映射關(guān)系如下： （1）對于形如A的產(chǎn)生式，有(q, ,A)=(q, ),這稱為推導 （2）(q, a,a)=(q, )稱為匹配，其中a。此PDA 停止于?？铡５谒恼?自上而下語法分析 4.2 自上而下語法分析法二、下推自動機的形式定義例 試給出接受語言Lancbn|n=0 的下推自動機。解： 1、生成L語言相應(yīng)文法的產(chǎn)生式為S aSb|c 2、生成相應(yīng)的PDA M=(Q ,H,q0,z0,F) PDA M=(

6、q,a,b,c,S,a,b,c, ,q,S,q) 其中 為：1) (q,a,a)= (q, ) 2) (q,b,b)= (q, ) 3) (q,c,c)= (q, ) 4) (q, S)=(q,aSb),(q,c)有限狀態(tài)控制器 aacbb#輸出帶S#其分析過程：(q,aacbb,S) a(q,aacbb,aSb) (q,acbb,Sb) a(q,acbb,aSbb) (q,cbb,Sbb) b(q,cbb,cbb) (q,bb,bb) (q,b,b) (q, , )第四章 自上而下語法分析 4.2 自上而下語法分析法三、自上而下語法分析的思想從文法的開始符號開始，反復使用不同產(chǎn)生式進行推導以

7、謀求與輸入符號串相匹配。對任何輸入串W試圖用一切可能的方法，從文法的開始符號出發(fā)，自上而下地為它建立一顆語法樹。若建立成功，則W為相應(yīng)文法的一個句子。注：此處的輸入符號串是指詞法分析結(jié)果的一串二元式。 試探法1、基本構(gòu)成 約定：下推棧的初始狀態(tài)包含兩個符號：#S，其中#為棧底，S為文法開始符號。有限狀態(tài)控制器中的狀態(tài)只有一個，因此可以省缺。整個分析過程在語法分析程序控制下進行。在語法分析過程中將用到文法的產(chǎn)生式；所有這些產(chǎn)生式都被放在一個表中，該表通常被稱為語法表。語法分析程序語法表 a+b#輸出帶S#第四章 自上而下語法分析 4.2 自上而下語法分析法四、一般方法第四章 自上而下語法分析 4

8、.2 自上而下語法分析法四、一般方法2、試探法的算法（語法分析程序所要執(zhí)行動作）：（1）若棧頂符號x是非終結(jié)符，查詢語法表，找出一個以x作為左部的產(chǎn)生式，x出棧，并將其右部以自右向左順序入棧，且輸出帶記下產(chǎn)生式編號推導。（2）若棧頂符號x是終結(jié)符，且讀頭下的符號也是x，則x出棧，讀頭指向下一個符號匹配。（3）若棧頂符號x是終結(jié)符，但讀頭下的符號不是x，則匹配失敗。這說明可能前面推導時選錯了候選式，退回到上次推導現(xiàn)場(包括棧頂符號、讀頭的指針和輸出帶上信息)回溯。第四章 自上而下語法分析 4.2 自上而下語法分析法四、一般方法2、試探法的算法 （4）回溯后選取另一候選式進行推導，若沒有候選式可選

9、，則進一步回溯。若回溯到開始符號又已無候選式可選，則識別失敗。（5）若棧內(nèi)僅剩下“”，且讀頭也指向“”，則識別成功。第四章 自上而下語法分析 4.2 自上而下語法分析法四、一般方法例 文法產(chǎn)生式如下，請分析符號串x*y#的過程 1) S xAy 2) A * 3)A *語法分析程序語法表 x * y #輸出帶S#第四章 自上而下語法分析 4.2 自上而下語法分析法四、一般方法例 文法產(chǎn)生式如下，請分析符號串x*y#的過程 1) S xAy 2) A * 3)A *語法分析程序語法表 x * y #1 xAy#第四章 自上而下語法分析 4.2 自上而下語法分析法四、一般方法例 文法產(chǎn)生式如下，請

10、分析符號串x*y#的過程 1) S xAy 2) A * 3)A *語法分析程序語法表 x * y #1Ay#第四章 自上而下語法分析 4.2 自上而下語法分析法四、一般方法例 文法產(chǎn)生式如下，請分析符號串x*y#的過程 1) S xAy 2) A * 3)A *語法分析程序語法表 x * y #1,2*y#第四章 自上而下語法分析 4.2 自上而下語法分析法四、一般方法例 文法產(chǎn)生式如下，請分析符號串x*y#的過程 1) S xAy 2) A * 3)A *語法分析程序語法表 x * y #1,2*y#第四章 自上而下語法分析 4.2 自上而下語法分析法四、一般方法例 文法產(chǎn)生式如下，請分析

11、符號串x*y#的過程 1) S xAy 2) A * 3)A *語法分析程序語法表 x * y #1Ay#第四章 自上而下語法分析 4.2 自上而下語法分析法四、一般方法例 文法產(chǎn)生式如下，請分析符號串x*y#的過程 1) S xAy 2) A * 3)A *語法分析程序語法表 x * y #1,3*y#第四章 自上而下語法分析 4.2 自上而下語法分析法四、一般方法例 文法產(chǎn)生式如下，請分析符號串x*y#的過程 1) S xAy 2) A * 3)A *語法分析程序語法表 x * y #1,3y#第四章 自上而下語法分析 4.2 自上而下語法分析法四、一般方法例 文法產(chǎn)生式如下，請分析符號串

12、x*y#的過程 1) S xAy 2) A * 3)A *語法分析程序語法表 x * y #1,3#第四章 自上而下語法分析 4.2 自上而下語法分析法四、一般方法3、帶回溯的自上而下分析法的缺陷1）如果文法存在左遞歸，語法分析會無限循環(huán)下去。2）若產(chǎn)生式存在多個候選式，選擇哪個進行推導完全是盲目的。3）回溯會引起時間和空間的大量消耗。4）如果被識別的語句是錯的，算法無法指出錯誤的確切位置。第四章 自上而下語法分析 4.2 自上而下語法分析法五、自上而下分析法的一般問題-回溯不帶回溯的自上而下分析算法1 、消除左遞歸1)什么是左遞歸左遞歸：文法存在產(chǎn)生式P Pa直接左遞歸： P Pa間接左遞歸

13、： P Aa , APb2)消除左遞歸消除直接左遞歸消除間接左遞歸第四章 自上而下語法分析 4.2 自上而下語法分析法五、自上而下分析法的一般問題-回溯不帶回溯的自上而下分析算法2 、消除直接左遞歸設(shè)有文法G=(VN, VT ,P,S)，其中產(chǎn)生式P為 P P| , V+ ， V+ 且不以P開頭將它轉(zhuǎn)換為等價式： P P P P| 一般地：將P P 1| P 2|. |P m|1| 2|.| n 轉(zhuǎn)換為： P 1P| 2 p| n P P 1P| 2P| mP| 例：文法G: (1)E E+T|T (2)T T*F|F (3)F (E)| i轉(zhuǎn)化為G: (1) E TE E +TE| (2)

14、T FT T *FT| (3) F (E)| i轉(zhuǎn)化為：P BaPP P aPbP| 注：只有最左邊的P參加變換。例：文法G:P PaPb|BaP第四章 自上而下語法分析 4.2 自上而下語法分析法五、自上而下分析法的一般問題-回溯不帶回溯的自上而下分析算法3 、消除間接左遞歸1）把文法G的所有非終結(jié)符按任意順序排列成P1,P2,Pn,然后按此順序執(zhí)行步驟2。2） for (i=1,i=n,i+) for (k=1,k=i-1,k+) 把形如Pi Pk的規(guī)則改寫為 Pi 1 | 2 | ,n , 其中Pk 1| 2| ,n 消除Pi規(guī)則的直接左遞歸；3)刪去從文法開始符號不可達的非終結(jié)符產(chǎn)生式

15、。3 、消除間接左遞歸注：1)此算法適用于消除不含形如P P的產(chǎn)生式且不含以為右部的產(chǎn)生式的文法 2)這里第二步所做的工作是： a)若產(chǎn)生式出現(xiàn)直接左遞歸則用消除直接左遞歸的方法消除掉。 b)若產(chǎn)生式右部最左符號是非終結(jié)符且其序號大于左部的非終結(jié)符，則不處理。 c)若序號小于左部的非終結(jié)符，則將這序號小的非終結(jié)符用其右部串來取代，然后消除新的直接左遞歸。第四章 自上而下語法分析 4.2 自上而下語法分析法五、自上而下分析法的一般問題-回溯不帶回溯的自上而下分析算法例：對下面文法消除左遞歸： (1) S Qc|c (2)Q Rb|b (3) R Sa|a解：1）對非終結(jié)符重新排序：R、Q、S 2

16、）對R：S的序號大于R的序號，不處理。 對Q: R的序號1小于Q的序號2,所以改寫Q Rb|b ，將R Sa|a的右部取代R，得到： Q Sab|ab|b,記為：（2)式； 此時， S的序號大于Q的序號,不再處理。 對S： Q的序號2小于S的序號3,所以改寫S Qc|c，將Q Sab|ab|b的右部取代Q，得到S Sabc|abc|bc|c;出現(xiàn)直接左遞歸，變換為： S (abc|bc|c)S S abcS| 3）由于 R Sa|a和 Q Sab|ab|b中的R,Q對開始符號S來說都是不可達非終結(jié)符，所以刪除它們。故最后消除左遞歸后文法為： S (abc|bc|c)S S abcS| 注：1）

17、若非終結(jié)符排列順序不同，改寫后的文法也不同，但它們是等價的。 2）開始符號不能改變。附：采用擴充BNF表示法改寫含直接左遞規(guī)的規(guī)則使用擴充的BNF表示() 表提因子例: Uax|ay|az 改寫為Ua(x|y|z) 重復次數(shù)的指定例：|50.a表a* 任選符號，表可有可無例:+|-第四章 自上而下語法分析 4.2 自上而下語法分析法五、自上而下分析法的一般問題-回溯不帶回溯的自上而下分析算法4、消除回溯1)產(chǎn)生回溯的原因 進行推導時，若產(chǎn)生式存在多個候選式，選擇哪個候選式進行推導存在不確定性。2)消除回溯的基本原則 對文法的任何非終結(jié)符，若能根據(jù)當前讀頭下的符號，準確的選擇一個候選式進行推導，

18、那么回溯就可以消除。 注:之所以會產(chǎn)生回溯是因為在推導匹配的過程中存在虛假匹配。第四章 自上而下語法分析 4.2 自上而下語法分析法五、自上而下分析法的一般問題-回溯不帶回溯的自上而下分析算法4、消除回溯 3)消除回溯的方法 預測與提左因子 4)預測 根據(jù)讀頭下符號選擇候選式，使其第一個符號與讀頭下符號相同，或該候選式可推導出的第一個符號與讀頭下符號相同。這相當于向前看了一個符號，所以稱為預測。 注：使用了預測之后，選擇候選式不再是盲目的了，所以也就無需回溯。第四章 自上而下語法分析 4.2 自上而下語法分析法五、自上而下分析法的一般問題-回溯不帶回溯的自上而下分析算法4、消除回溯 5)求候選

19、式的終結(jié)首符集 令G是一個不含左遞歸的文法，對G的所有非終結(jié)符的各候選式可求出它的終結(jié)首符First(). First()a| a,a VT 特例:若 ,那么 First()。 即， First()集合包括了的所有可能推導的開頭終結(jié)符或可能的。*第四章 自上而下語法分析 4.2 自上而下語法分析法五、自上而下分析法的一般問題-回溯不帶回溯的自上而下分析算法4、消除回溯 5)求候選式的終結(jié)首符集 設(shè)A是非終結(jié)符，且A|（此時與稱為非終結(jié)符A的候選式 ），當A出現(xiàn)在下推棧的棧頂，且輸入符號為a時，應(yīng)如何選擇A的候選式進行推導？這里分為四種情況： (a)若aFirst(),而aFirst()，則選A

20、 (b)若a First(),而a First()，則選A (C) 若a First(),且a First(),則表示輸入有錯 (d)若aFirst(),且a First(),則表示終結(jié)首符集相交，需改寫原文法，進行公因子提取。注：對First()=情況，留待討論。第四章 自上而下語法分析 4.2 自上而下語法分析法五、自上而下分析法的一般問題-回溯不帶回溯的自上而下分析算法4、消除回溯 6)采用預測方法后PDA的運行設(shè)A為出現(xiàn)在棧頂?shù)姆墙K結(jié)符，如果A的所有候選式的候選首符集都兩兩不相交，那么，PDA可以根據(jù)它所面臨的讀頭符號，準確地指派某候選式替換A;但是，許多文法都存在一些非終結(jié)符，其所有

21、候選的首符集并不是兩兩不相交，這樣，仍無法選擇用哪個候選式進行推導。第四章 自上而下語法分析 4.2 自上而下語法分析法五、自上而下分析法的一般問題-回溯4、消除回溯 7)提取公共左因子 將某產(chǎn)生式A1| 2|. | n 改寫為 AA A1|2|. |n 注：1)可通過反復提取左因子，就能把所有非終結(jié)符的所有候選首符集變?yōu)閮蓛刹幌嘟弧?2)反復提取左因子也有一定代價，因為在提取過程中會大量引入非終結(jié)符和產(chǎn)生式，會增加語法分析的復雜性。5、求候選式的終結(jié)首符集1) 求串的終結(jié)首符集First() a)定義 假定是文法G的一個符號串， V* ，則 First()a| a,a VT 注： 若 ,那么

22、 First()。 First()集合是的所有可能推導出的開頭終結(jié)符或所組成的集合。 b)算法 設(shè)=X1X2Xn，其中Xi(VNVT),1i n,為了求的首符集，分兩步：首先求Xi的首符集，然后再求的首符集。*第四章 自上而下語法分析 4.2 自上而下語法分析法五、自上而下分析法的一般問題-回溯5、求候選式的終結(jié)首符集1) 求串的終結(jié)首符集First() b)算法 第一步：求出文法中每個文法符號的首符集； 若x VT ，則First(x)=x; 若XVN ，且有產(chǎn)生式X a，則將a加到 First(X)中;若X , 則也加入到 First(X)； 第四章 自上而下語法分析 4.2 自上而下語法

23、分析法五、自上而下分析法的一般問題-回溯5、求候選式的終結(jié)首符集1) 求串的終結(jié)首符集First() b)算法第一步：求出文法中每個文法符號的首符集； 若X Y1Y2Yk，其中Yj(VNVT),1j k,則按如下算法求First(X) j=0; FIRST(X)=; /初始化 REPEAT j=j+1; FIRST(X)=FIRST(X)(FIRST(Yj)-) UNTIL FIRST(Yj) 或j=k IF (j=k 且 FIRST(Yk) THEN FIRST(X)=FIRST(X) 第四章 自上而下語法分析 4.2 自上而下語法分析法五、自上而下分析法的一般問題-回溯5、求候選式的終結(jié)首

24、符集1) 求串的終結(jié)首符集First() b)算法第二步：求First() 設(shè) =X1X2Xn，其中Xi(VNVT),1i n ,則按如下算法求First() i=0; FIRST()=; /初始化 REPEAT i=i+1; FIRST()=FIRST()(FIRST(Xi)-) UNTIL FIRST(Xi) 或i=n IF (i=n 且 FIRST(Xn) THEN FIRST()=FIRST()第四章 自上而下語法分析 4.2 自上而下語法分析法五、自上而下分析法的一般問題-回溯5、求候選式的終結(jié)首符集2) 求非終結(jié)符A的隨符集Follow(A) a)定義 假定S是文法G的開始符號，對

25、于G的任何非終結(jié)符A，定義 Follow(A)a|S Aa,a VT 注： 若 SA,則規(guī)定：# Follow(A)。 Follow(A)集合是指在所有句型中緊跟A之后的終結(jié)符或#所組成的集合。 +第四章 自上而下語法分析 4.2 自上而下語法分析法五、自上而下分析法的一般問題-回溯5、求候選式的終結(jié)首符集2) 求非終結(jié)符A的隨符集Follow(A) b)算法第一步：對文法開始符號S，將#加入到Follow(S)中；第二步：若B A是文法G的一個產(chǎn)生式，則將First()-加入到Follow(A)中;第三步：若B A是文法G的一個產(chǎn)生式,或B A是文法G的一個產(chǎn)生式,且 ，則將Follow(B

26、)加入到Follow(A)中； 注：這里的文法必須是消除了左遞歸且提取了左因子后的文法。 +第四章 自上而下語法分析 4.2 自上而下語法分析法五、自上而下分析法的一般問題-回溯5、求候選式的終結(jié)首符集2) 求非終結(jié)符A的隨符集Follow(A) c)例：對如下文法G(已加上編號)： 1.E TE 2.E +TE 3.E 4.T FT 5.T *FT 6.T 7.F i 8.F (E)求各非終結(jié)符號的終結(jié)首符集和隨符集。第四章 自上而下語法分析 4.2 自上而下語法分析法五、自上而下分析法的一般問題-回溯5、求候選式的終結(jié)首符集2) 求非終結(jié)符A的隨符集Follow(A)解：First(E)=

27、First(T)=First(F)=(, i First(E)=+, First(T)=*, Follow(E)= Follow(E)=),# Follow(T)= Follow(T)=+,),# Follow(F)=*,+,),#第四章 自上而下語法分析 4.2 自上而下語法分析法五、自上而下分析法的一般問題-回溯第四章 自上而下語法分析 4.2 自上而下語法分析法六、預測分析法與預測分析表的構(gòu)造 （一）不帶回溯的預測分析程序1、帶預測分析的PDA 在PDA中加入預測分析之后，可以消除自上而下分析中出現(xiàn)回溯的現(xiàn)象。此時PDA可以改造為：預測分析程序預測分析表 a+b#輸出帶S#矩陣MA,a第

28、四章 自上而下語法分析 4.2 自上而下語法分析法六、預測分析法與預測分析表的構(gòu)造 （一）不帶回溯的預測分析程序1、帶預測分析的PDA注：1）改造后，整個分析過程都在預測分析程序控制下工作。 2）預測分析程序用了一個預測分析表，它是預測分析程序分析時的主要依據(jù)。第四章 自上而下語法分析 4.2 自上而下語法分析法六、預測分析法與預測分析表的構(gòu)造 （一）不帶回溯的預測分析程序2、預測分析表 預測分析表是一矩陣MA,a，其中行標A是非終結(jié)符，列標a是終結(jié)符或串結(jié)束符；矩陣元素MA,a是存放A的一個侯選式，指出當前棧頂符號為A且面臨讀入符號為a時應(yīng)選的候選式；或者存放“出錯標志”，指出A不該面臨讀入

29、符號a。第四章 自上而下語法分析 4.2 自上而下語法分析法六、預測分析法與預測分析表的構(gòu)造 （一）不帶回溯的預測分析程序3、預測分析程序算法描述預測分析程序預測分析表 a輸出帶X#第四章 自上而下語法分析 4.2 自上而下語法分析法六、預測分析法與預測分析表的構(gòu)造（一）不帶回溯的預測分析程序3、預測分析程序算法描述 設(shè)棧頂符號為X，讀入符號為a，則 1)若X=a=#，則表示識別成功，退出分析程序； 2)若X=a#，則表示匹配，彈出棧頂符號X，讀頭前進一格，讓讀頭指向下一個符號，以讀入下一個符號；若X是終結(jié)符，但Xa，則調(diào)用error處理； 3)若XVN，則查預測分析表M。若MX,a中存放著關(guān)

30、于X的產(chǎn)生式，則彈出X，且將相應(yīng)產(chǎn)生式右部以自右向左的順序壓入棧，在輸出帶上記下產(chǎn)生式編號；若MX,a中存放著出錯標記，則調(diào)用相應(yīng)Error處理。第四章 自上而下語法分析 4.2 自上而下語法分析法六、預測分析法與預測分析表的構(gòu)造（二）構(gòu)造預測分析表 1、基本思想 1）若A 是一個產(chǎn)生式，a First(),那么當A是棧頂符號且將讀入a時，選擇取代A匹配成功的希望最大。故，MA,a元素為A 。 2）若A ，而 ，或 ；當A是棧頂符號且將讀入a時，若a Follow(A),則棧頂?shù)腁應(yīng)被匹配；此時讀頭不前進，讓A的隨符與讀頭下的符號進行匹配，這樣輸入串匹配成功的可能最大。故MA,a元素為A (這

31、里 或 )。+第四章 自上而下語法分析 4.2 自上而下語法分析法六、預測分析法與預測分析表的構(gòu)造（二）構(gòu)造預測分析表 2、構(gòu)造算法 1）假定A 是一個產(chǎn)生式，a First(),那么當A是棧頂符號且將讀入a時， A 就應(yīng)作為選用的侯選式， A 應(yīng)填入 MA,a中。 2）若A ，而 First() ,對每個a Follow(A), 在MA,a元素中應(yīng)填A (一般填A )。 3）把所有無定義的MA,a都填上出錯標志。注：1）用此算法可以為任意文法G構(gòu)造其分析表M。 2）若是二義文法或沒有消除左遞歸和提取左因子的文法，構(gòu)造出的M包含有重定義項。即，它們的MA,a中填有一個以上的產(chǎn)生式。例：對如下文

32、法G, 構(gòu)造預測分析表 1.E TE 2.E +TE 3.E 4.T FT 5.T *FT 6.T 7.F i 8.F (E)解：1）求出各非終結(jié)符的First集和Follow集 First(E)=First(T)=First(F)=(, i First(E)=+, First(T)=*, Follow(E)= Follow(E)=),# Follow(T)= Follow(T)=+,),# Follow(F)=*,+,),#2）根據(jù)算法構(gòu)造預測分析表 返回 i + * ( )#EETEETEEE +TEEETTFTTFTTTT *FTTTFF iF (E)第四章 自上而下語法分析 4.2 自

33、上而下語法分析法六、預測分析法與預測分析表的構(gòu)造（三） LL(1)文法1、定義 若文法G的預測分析表M中不含有多重定義項，則稱G為LL (1)文法。注：1)LL(1)文法是無二義的，二義文法一定不是LL(1)文法。2) LL的含義是從左到右掃描輸入串，采用最左推導分析句子。3)數(shù)字1表示分析句子時需向前看一個輸入符號。3)有LL(1)就有 LL(k)，LL(k)向前查看k個輸入符號，選擇候選式更加準確，但M的尺寸會以nk增長，其中n=|+1。對程序設(shè)計語言取k1就夠了。第四章 自上而下語法分析 4.2 自上而下語法分析法六、預測分析法與預測分析表的構(gòu)造（三） LL(1)文法2、證明定理 文法G是LL(1)文法當且僅當對于G的每個非終結(jié)符A的任何兩個不同產(chǎn)生式A |有： 1）First() First()= 2）若 First() ，則First() Follow(A)= 注：1）可以使用這個定理直接根據(jù)首符集、隨符集來判斷文法是否是LL(1)。但判斷之前，必須消除左遞歸和提取公共左因子,因為包含左遞歸和公共左因子的文法肯定不是LL(1)文法。2）LL(1)文法只是上下文無關(guān)文法的一個子集。第四章 自上而下語法分析 4.2 自上而下語法分析法六、預測分析法與預測分析表的構(gòu)造（三） LL(1)文法例：判斷下面