成果編譯原理chap

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

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

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

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

5、定義由CFG G= （VN ，P，S） 構(gòu)造PDA M的算法：G= （VN ，P，S） M=（Q,H,q0,z0,F）令：Q=F=q0 即控制器只有一個(gè)狀態(tài) H= VN ; z0 =S; 映射關(guān)系如下： （1）對(duì)于形如A的產(chǎn)生式，有(q, ,A)=(q, ),這稱為推導(dǎo) （2）(q, a,a)=(q, )稱為匹配，其中a。此PDA 停止于?？?。第四章 自上而下語(yǔ)法分析 4.2 自上而下語(yǔ)法分析法二、下推自動(dòng)機(jī)的形式定義例 試給出接受語(yǔ)言Lancbn|n=0 的下推自動(dòng)機(jī)。解： 1、生成L語(yǔ)言相應(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#其分析過(guò)程：(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, , )第四章 自上而下語(yǔ)法分析 4.2 自上而下語(yǔ)法分析法三、自上而下語(yǔ)法分析的思想從文法的開(kāi)始符號(hào)開(kāi)始，反復(fù)使用不同產(chǎn)生式進(jìn)行推導(dǎo)以

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

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

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

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

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

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

13、： P Aa , APb2)消除左遞歸消除直接左遞歸消除間接左遞歸第四章 自上而下語(yǔ)法分析 4.2 自上而下語(yǔ)法分析法五、自上而下分析法的一般問(wèn)題-回溯不帶回溯的自上而下分析算法2 、消除直接左遞歸設(shè)有文法G=(VN, VT ,P,S)，其中產(chǎn)生式P為 P P| , V+ ， V+ 且不以P開(kāi)頭將它轉(zhuǎn)換為等價(jià)式： 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第四章 自上而下語(yǔ)法分析 4.2 自上而下語(yǔ)法分析法五、自上而下分析法的一般問(wèn)題-回溯不帶回溯的自上而下分析算法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ī)則改寫(xiě)為 Pi 1 | 2 | ,n , 其中Pk 1| 2| ,n 消除Pi規(guī)則的直接左遞歸；3)刪去從文法開(kāi)始符號(hào)不可達(dá)的非終結(jié)符產(chǎn)生式

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

16、）對(duì)R：S的序號(hào)大于R的序號(hào)，不處理。 對(duì)Q: R的序號(hào)1小于Q的序號(hào)2,所以改寫(xiě)Q Rb|b ，將R Sa|a的右部取代R，得到： Q Sab|ab|b,記為：（2)式； 此時(shí)， S的序號(hào)大于Q的序號(hào),不再處理。 對(duì)S： Q的序號(hào)2小于S的序號(hào)3,所以改寫(xiě)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對(duì)開(kāi)始符號(hào)S來(lái)說(shuō)都是不可達(dá)非終結(jié)符，所以刪除它們。故最后消除左遞歸后文法為： S (abc|bc|c)S S abcS| 注：1）

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

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

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

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

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

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

23、分析法五、自上而下分析法的一般問(wèn)題-回溯5、求候選式的終結(jié)首符集1) 求串的終結(jié)首符集First() b)算法第一步：求出文法中每個(gè)文法符號(hào)的首符集； 若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) 第四章 自上而下語(yǔ)法分析 4.2 自上而下語(yǔ)法分析法五、自上而下分析法的一般問(wèn)題-回溯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()第四章 自上而下語(yǔ)法分析 4.2 自上而下語(yǔ)法分析法五、自上而下分析法的一般問(wèn)題-回溯5、求候選式的終結(jié)首符集2) 求非終結(jié)符A的隨符集Follow(A) a)定義 假定S是文法G的開(kāi)始符號(hào)，對(duì)

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

26、)加入到Follow(A)中； 注：這里的文法必須是消除了左遞歸且提取了左因子后的文法。 +第四章 自上而下語(yǔ)法分析 4.2 自上而下語(yǔ)法分析法五、自上而下分析法的一般問(wèn)題-回溯5、求候選式的終結(jié)首符集2) 求非終結(jié)符A的隨符集Follow(A) c)例：對(duì)如下文法G(已加上編號(hào))： 1.E TE 2.E +TE 3.E 4.T FT 5.T *FT 6.T 7.F i 8.F (E)求各非終結(jié)符號(hào)的終結(jié)首符集和隨符集。第四章 自上而下語(yǔ)法分析 4.2 自上而下語(yǔ)法分析法五、自上而下分析法的一般問(wèn)題-回溯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)=*,+,),#第四章 自上而下語(yǔ)法分析 4.2 自上而下語(yǔ)法分析法五、自上而下分析法的一般問(wèn)題-回溯第四章 自上而下語(yǔ)法分析 4.2 自上而下語(yǔ)法分析法六、預(yù)測(cè)分析法與預(yù)測(cè)分析表的構(gòu)造 （一）不帶回溯的預(yù)測(cè)分析程序1、帶預(yù)測(cè)分析的PDA 在PDA中加入預(yù)測(cè)分析之后，可以消除自上而下分析中出現(xiàn)回溯的現(xiàn)象。此時(shí)PDA可以改造為：預(yù)測(cè)分析程序預(yù)測(cè)分析表 a+b#輸出帶S#矩陣MA,a第

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

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

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

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

32、法G, 構(gòu)造預(yù)測(cè)分析表 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)造預(yù)測(cè)分析表 返回 i + * ( )#EETEETEEE +TEEETTFTTFTTTT *FTTTFF iF (E)第四章 自上而下語(yǔ)法分析 4.2 自

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