第五章自頂向下語(yǔ)法分析方法.ppt

1、第5章,自頂向下語(yǔ)法分析方法,語(yǔ)法分析,語(yǔ)法分析是編譯程序的核心部分 作用：識(shí)別由詞法分析給出的單詞符號(hào)序列是否為給定文法的正確句子。 自頂向下分析 ( Top-Down Parsing) 也稱為面向目標(biāo)的分析方法 分為確定的和不確定的兩種分析方法,語(yǔ)法分析句形分析,句形分析就是識(shí)別一個(gè)符號(hào)串是否為某文法的句型，是某個(gè)推導(dǎo)的構(gòu)造過(guò)程。 在語(yǔ)言的編譯實(shí)現(xiàn)中，把完成句型分析的程序稱為分析程序或識(shí)別程序。 分析算法又稱識(shí)別算法。,5.1 確定的自頂向下分析思想,自頂向下從開(kāi)始符開(kāi)始分析 唯一的確定選用哪個(gè)產(chǎn)生式替換相應(yīng)的非終結(jié)符，然后繼續(xù)向下推導(dǎo)。 亦可用構(gòu)造一棵語(yǔ)法樹(shù)的方式進(jìn)行分析,自頂向下的推導(dǎo)

2、過(guò)程的例,例 5.1 若有文法G1S S pAqB A cAda B dBb 若輸入串W=pccadd 自頂向下的推導(dǎo)過(guò)程為：SpApcAdpccAddpccadd,確定的自頂向下分析思想,例5.1的文法有兩個(gè)特點(diǎn)： （1）每個(gè)產(chǎn)生式的右部都由終結(jié)符開(kāi)始 （2）如果兩個(gè)產(chǎn)生式有相同的左部，那么它們的右部由不同的終結(jié)符開(kāi)始。 根據(jù)輸入符號(hào)決定選擇產(chǎn)生式向下推導(dǎo)，分析過(guò)程是唯一確定的。,自頂向下的推導(dǎo)過(guò)程的例,例5.1的語(yǔ)法樹(shù),自頂向下的推導(dǎo)過(guò)程的例,例 5.2 若有文法G2S S Ap S Bq A a A cA B b B dB 若輸入串W=ccap 自頂向下的推導(dǎo)過(guò)程為：SApcApccAp

3、ccap,自頂向下的推導(dǎo)過(guò)程的例,例5.2的語(yǔ)法樹(shù),確定的自頂向下分析思想,例5.2的文法的特點(diǎn)： （1）產(chǎn)生式的右部不全是由終結(jié)符開(kāi)始 （2）如果兩個(gè)產(chǎn)生式有相同的左部，那么它們的右部由不同的終結(jié)符或非終結(jié)符開(kāi)始。 （3）文法中無(wú)空產(chǎn)生式,自上而下分析算法,要點(diǎn)： 由根向下構(gòu)造語(yǔ)法樹(shù) 構(gòu)造最左推導(dǎo) 推導(dǎo)出的終結(jié)符是否與當(dāng)前輸入符匹配,S AB A aA | B b | bB aaab. S AB S AB aAB A aA aaAB A aA aaaAB A aA aaa B A aaab B b,首符號(hào)的集合,定義5.1 設(shè)G=(VT,VN,S,P)是上下文無(wú)關(guān)文法，首符號(hào)的集合： FIR

4、ST()=a|*a，aVT，,V* 若* 則規(guī)定 FIRST() 文法G2(S)中： FIRST(Ap)=a,c FIRST(Bq)=b,d,文法中包含空產(chǎn)生式的情況,例5.3 若有文法GS S aA S d A bAS A 若輸入串W=abd 自頂向下的推導(dǎo)過(guò)程為：SaAabASabSabd 推導(dǎo) abASabS 利用了產(chǎn)生式 A ,自頂向下的推導(dǎo)過(guò)程的例,例5.3的語(yǔ)法樹(shù),跟隨符號(hào)的集合,定義5.2 設(shè)G=(VT,VN,S,P)是上下文無(wú)關(guān)文法，AVN S是開(kāi)始符號(hào) FOLLOW(A)=a|S*A 且aVT ， aFIRST()，VT*，V+ 若 S*A，且 * ， 則 #FOLLOW(A

5、),跟隨符號(hào)的集合,也可定義為： FOLLOW(A)=a|S* Aa，a VT 若S* A，則規(guī)定# FOLLOW(A) #號(hào)作為輸入串的結(jié)束符，句子括號(hào)。如： #輸入串#,跟隨符號(hào)的集合,當(dāng)文法中含有形如： A A 其中 AVN ,V* 的產(chǎn)生式，當(dāng)， 不同時(shí)推導(dǎo)出空時(shí)，即： *；*，則當(dāng)： FIRST()FIRST()FOLLOW(A)=時(shí)，對(duì)于非終結(jié)符A的替換仍可唯一地確定候選。,跟隨符號(hào)的集合,即當(dāng)一非終結(jié)符的產(chǎn)生式中含有時(shí)，它的非空產(chǎn)生式的右部的FIRST集兩兩不相交，并與在推導(dǎo)過(guò)程中緊跟該非終結(jié)符右邊可能出現(xiàn)的終結(jié)符集也不相交。 由定義可以看出：所謂FIRST集和FOLLOW集是對(duì)

6、于非終結(jié)符而言的，即形成的集合是對(duì)于某一非終結(jié)符的終結(jié)符的集合，,選擇集合,定義5.3 給定上下文無(wú)關(guān)文法的產(chǎn)生式： A 其中 AVN V* 若 *，則 SELECT(A)=FIRST() 若 *，則 SELECT(A)= (FIRST()-)FOLLOW(A) 選擇集合是對(duì)某一產(chǎn)生式而言的。,LL(1)文法,定義5.4 一個(gè)上下文無(wú)關(guān)文法是LL(1)文法的充分必要條件是，對(duì)每個(gè)非終結(jié)符A的兩個(gè)不同產(chǎn)生式 A A ，滿足： SELECT(A ) SELECT(A) = 其中：， 不能同時(shí)推出 * 能使用自頂向下分析技術(shù)的文法正是 LL(1)文法,LL(1) grammar,A grammar

7、G is LL(1) iff whenever A u | v are two distinct productions of G, the following conditions hold: for no terminal a do both u and v derive strings beginning with a (i.e. first sets are disjoint) at most one of u and v can derive the empty string if v =* then v does not derive any string beginning wi

8、th a terminal in Follow(A),LL(1)文法,第一個(gè)L 從左到右掃描輸入串 第二個(gè)L 生成的是最左推導(dǎo) 1 向前看一個(gè)輸入符號(hào)(lookahead) 便可決定如何推導(dǎo)，選擇那一個(gè) 產(chǎn)生式進(jìn)行推導(dǎo)。 LL(k)文法：向前看k個(gè)符號(hào)。,predictive parser and LL(1)grammar,Predictive parser is a non-backtracking top-down parser. A predictive parser is characterized by its ability to choose the production to

9、apply solely on the basis of the next input symbol and the current nonterminal being processed. To enable this, the grammar must take a particular form. We call such a grammar LL(1). The first “L” means we scan the input from left to right; the second “L” means we create a leftmost derivation; and t

10、he 1 means one input symbol of lookahead.,LL(1)文法的例,例5.3 的文法GS是LL(1)文法 S aA S d A bAS A 有：SELECT(SaA)=a SELECT(Sd)=d SELECT(AbAS)=b SELECT(A)=a,d,# 所以： SELECT(SaA) SELECT(Sd) = SELECT(AbAS) SELECT(A) =,a d,b a,d,#,LL(1)文法的反例,例5.4 可以證明下面的文法GS不是LL(1)文法：S aAS S b A bA A 則 SELECT(SaAS)=a SELECT(Sb)=b SE

11、LECT(AbA)=b SELECT(A)=a,b 所以： SELECT(SaAS) SELECT(Sb) = SELECT(AbA) SELECT(A) ,a b,b a,b,選用自頂向下分析，首先必須判別所給文法是否為L(zhǎng)L(1)文法 對(duì)任意給定的文法需計(jì)算： FIRST集、FOLLOW集、SELECT集， 進(jìn)而判別是否為L(zhǎng)L(1)文法,5.2 LL(1)文法的判別,例5.5 若文法GS為： S AB S bC A A b B B aD C AD C b D aS D c 判別步驟：,說(shuō)明判斷LL(1)文法的步驟的例,算法：建立一維數(shù)組，上界為非終結(jié)符個(gè)數(shù) 1) 數(shù)組元素初值為“未定”,1.

12、求出能推出的非終結(jié)符,求出能推出的非終結(jié)符算法,2) 掃描文法的產(chǎn)生式 (a)刪除所有右部含有終結(jié)符的產(chǎn)生式，若結(jié)果導(dǎo)致某一非終結(jié)符為左部的所有產(chǎn)生式都被刪除，將數(shù)組對(duì)應(yīng)元素標(biāo)記為“否”，說(shuō)明該非終結(jié)符不能推出。 文法中：D aS D c 被刪除，非終結(jié)符D的數(shù)組對(duì)應(yīng)元素標(biāo)記為“否”。,求出能推出的非終結(jié)符算法,(b) 若某一非終結(jié)符的某一產(chǎn)生式右部為，將數(shù)組對(duì)應(yīng)元素標(biāo)記為“是”，刪除該非終結(jié)符的所有產(chǎn)生式。 文法中：A A b B B aD 非終結(jié)符A和B有產(chǎn)生式右部為，這4個(gè)產(chǎn)生式被刪除，將數(shù)組對(duì)應(yīng)元素標(biāo)記為“是”。 文法中僅保留：S AB C AD,求出能推出的非終結(jié)符算法,3) 掃描產(chǎn)

13、生式右部的每一符號(hào) (a) 若所掃描到的非終結(jié)符在數(shù)組中的對(duì)應(yīng)元素標(biāo)記為“是”，則刪除該非終結(jié)符。若這使得產(chǎn)生式右部為空，則對(duì)產(chǎn)生式左部的非終結(jié)符的數(shù)組對(duì)應(yīng)元素改為“是”，并刪除以該非終結(jié)符為左部的所有產(chǎn)生式。 文法中：S AB 刪除A和B后產(chǎn)生式右部為空，將S的數(shù)組對(duì)應(yīng)元素改為“是”。,求出能推出的非終結(jié)符算法,(b)若所掃描到的非終結(jié)符在數(shù)組中的對(duì)應(yīng)元素標(biāo)記為“否”，則刪除該產(chǎn)生式。若結(jié)果導(dǎo)致某一非終結(jié)符為左部的所有產(chǎn)生式都被刪除，將數(shù)組對(duì)應(yīng)元素標(biāo)記為“否”。 文法中：C AD A標(biāo)記為“是”，D標(biāo)記為“否”，刪除該產(chǎn)生式，C的標(biāo)記改為為“否” 4)重復(fù)3)步完成一遍掃描。,2.計(jì)算FIR

14、ST集,1) 根據(jù)定義計(jì)算 由定義5.1 ： FIRST()=a*a，aVT，,V* 若* 則規(guī)定 FIRST() 對(duì)每一文法符號(hào)XV 計(jì)算FIRST(X) (a) 若XVT，則FIRST(X)=X,計(jì)算FIRST集,(b) 若XVN，且有產(chǎn)生式 Xa， aVT， 則 a FIRST(X) 把a(bǔ)加入到FIRST(X)中 (c) 若XVN X 則 FIRST(X)， 把也加到FIRST(X)中。,計(jì)算FIRST集,(d) 若X，Y1，Y2，Yn VN， X Y1Y2Yn 是一個(gè)產(chǎn)生式，Y1，Y2， ， Yi-1都是非終結(jié)符，而且都有*，而且，對(duì)于任何j，1ji-1，F(xiàn)IRST(Yj)都含有，則對(duì)

15、于 1in，有 FIRST(Yi-1) FIRST(X) FIRST(Yi) FIRST(X) 把FIRST(Yi-1)中的所有非元素以及FIRST(Yi)都加到FIRST(X)中,計(jì)算FIRST集,(e) 當(dāng)(d)中所有 Yi *， 1i n 則 FIRST(X)= FIRST(Y1) FIRST(Y2) FIRST(Yn) 反復(fù)使用步驟(a)(e)產(chǎn)生每個(gè)符號(hào)的FIRST集合,符號(hào)串的FIRST集合,若符號(hào)串 V* =X1 X2 Xn 當(dāng) X1* 則置FIRST()=FIRST(X1) 若對(duì)任何 j 1ji-1,2i n, FIRST(Xj) i-1 則FIRST()=FIRST(X1)-

16、FIRST(Xj) j=1 當(dāng)所有FIRST(Xj)都含有 時(shí)，則 n FIRST()=FIRST(X1) j=1,例5.5文法各非終結(jié)符的FIRST集,FIRST(S)=(FIRST(A)- ) (FIRST(B) - )b=b,a, FIRST(A)= b= b, FIRST(B)=a= a, FIRST(C)=(FIRST(A)- ) FIRST(D)FIRST(b)=b,a,c FIRST(D)=ac=a, c,每個(gè)產(chǎn)生式右部符號(hào)串的FIRST集,FIRST(AB)=b,a, FIRST(bC)= b FIRST()= FIRST(b)=b FIRST(aD)=a FIRST(AD)=

17、b,a,c FIRST(AS)=a FIRST(c)=c,S BdA First(S)=a,b,c,d S SAC A AB First(A)=a, b,c, A AaC A a First(A) =a A First(A) =a, B BA B CA First(B) = a,b, c, B b First(B) = b C c First(C) = c C First(C) = c, ,例：一個(gè)文法的FIRST集,2) 由關(guān)系圖法求文法符號(hào)的FIRST集,(a)每個(gè)文法符號(hào)對(duì)應(yīng)圖中一個(gè)結(jié)點(diǎn)，非終結(jié)符用FIRST(A)標(biāo)記 (b)如果文法中有產(chǎn)生式 AX，且*則從對(duì)應(yīng)A的結(jié)點(diǎn)到對(duì)應(yīng)X的結(jié)點(diǎn)連

18、一條弧 (c) 凡是從FIRST(A)結(jié)點(diǎn)有路徑到達(dá)的終結(jié)符結(jié)點(diǎn)的標(biāo)記都是FIRST(A)的成員 (d)由判別步驟1確定是否為FIRST(A)成員,由關(guān)系圖法求文法符號(hào)的FIRST集,由關(guān)系圖求例5.5的FIRST集,FIRST(S)=b,a, FIRST(A)= b, FIRST(B)=a, FIRST(C)=a,b,c FIRST(D)=a,c,3.計(jì)算FOLLOW集,1) 根據(jù)定義計(jì)算 對(duì)于文法中每一A VN 計(jì)算FOLLOW(A) (a) 對(duì)于文法的開(kāi)始符號(hào)S，把句子括號(hào)#加入到FOLLOW(S) 中； (b) 若A B是一個(gè)產(chǎn)生式，則把 FIRST()的非空元素加至FOLLOW(B)

19、中,計(jì)算FOLLOW集,若 * 即 FIRST()，則把FOLLOW(A)加至FOLLOW(B)中。 若有產(chǎn)生式A B，則所有包含A的串中，A可以被B代替，所以FOLLOW(B)包括FOLLOW(A)。 注意： 永遠(yuǎn)也不是FOLLOW集合中的元素； FOLLOW僅針對(duì)非終結(jié)符定義。,例5.5文法各非終結(jié)符的FOLLOW集,FOLLOW(S)=#FOLLOW(D)= # FOLLOW(A)=FIRST(B)- FOLLOW(S)FIRST(D)=a,#,c FOLLOW(B)= FOLLOW(S)=# FOLLOW(C)= FOLLOW(S)=# FOLLOW(D)= FOLLOW(B)FOLL

20、OW(C) =#,由關(guān)系圖法求文法符號(hào)的FOLLOW集,FOLLOW(S)=# FOLLOW(A)=a,#,c FOLLOW(B)=# FOLLOW(C)=# FOLLOW(D)=#,4.計(jì)算SELECT集,例5.5的FIRST集和FOLLOW集,計(jì)算SELECT集,SELECT(SAB)= FIRST(AB)FOLLOW(S)=b,a,# SELECT(SbC)=FIRST(bC)=b SELECT(SAB)SELECT(SbC)= b,a,#b 由LL(1)文法定義知該文法不是LL(1)文法,計(jì)算SELECT集,SELECT(A)= FIRST()FOLLOW(A)=a,c,# SELEC

21、T(Ab)=FIRST(b)=b SELECT(A)SELECT(Ab)= a,c,#b=,5.3 某些非LL(1)文法 到LL(1)文法的等價(jià)變換,自頂向下分析的主要問(wèn)題： 1.必須是LL(1)文法 2. 包含直接或間接左遞歸的文法不是LL(1)文法：消除左遞歸 3.含有左公共因子的文法不是LL(1)文法：從多個(gè)候選產(chǎn)生式中提取左因子 4.二義性：消除文法的二義性。,1. 提取左公共因子,若文法中含有形如：A|的產(chǎn)生式，使得： SELECT(A)SELECT(A) 不滿足LL(1)文法的充分必要條件。 提取左因子： A| 等價(jià)變換為 A(|) 引入A，去掉括號(hào)，變換為 AA A|,提取左公共

22、因子的例,例5.6 若文法G1的產(chǎn)生式為： SaSb SaS S 提取左因子： SaS(b|) S 變換為文法G1： SaSA Ab A S 可以證明為G1 仍然不是一個(gè)LL(1)文法 不含左公共因子只是一個(gè)必要條件,提取左公共因子的例,例5.7 若文法G2的產(chǎn)生式為： Aad ABc BaA BbB 替換為：Aad AaAc AbBc BaA BbB 提取左因子： Aa(d|Ac) AbBc BaA BbB 引入A： AaA AbBc Ad AAc BaA BbB,可以證明是一個(gè)LL(1)文法,提取左公共因子的例,例5.8 若文法G3的產(chǎn)生式為： SaSd SAc AaS Ab 替換為：Sa

23、Sd SaSc Sbc AaS Ab 提取左因子： SaS(d|c) 引入A： SaSA Sbc Ad|c AaS Ab 右部無(wú)A，后兩個(gè)以A為左部的產(chǎn)生式應(yīng)刪除,可以證明是一個(gè)LL(1)文法,提取左公共因子的例,例5.9 若文法G4的產(chǎn)生式為： SAp|Bq AaAp|d BaBq|e 替換為：S aApp|aBqq Sdp|eq AaAp|d BaBq|e 提取左因子： Sa(App|Bqq) 引入S：SaS Sdp|eq SApp|Bqq AaAp|d BaBq|e,可以提取左因子,2.消除左遞歸,直接或間接左遞歸文法： a) AA AVN， V* b) AB BA A,BVN， ,V*

24、 a)為直接左遞歸，b) 為間接左遞歸 一個(gè)文法是左遞歸時(shí)不能采用自頂向下分析法。左遞歸文法導(dǎo)致分析過(guò)程的死循環(huán)。,例5.10 文法G5含有直接左遞歸： SSa Sb 產(chǎn)生語(yǔ)言 L=ban|0 輸入串baaaa#是該語(yǔ)言 的句子 無(wú)法確定何時(shí) 用Sb替換,直接左遞歸的例,左遞歸關(guān)于非終結(jié)符P的規(guī)則,直接左遞歸：若 P P| 、 V*且不以P開(kāi)頭 間接左遞歸：若 P * P S Aa A Sb ,消除左遞歸,消除直接左遞歸 形如：P P| 非 ，不以P打頭 改寫(xiě)為：P Q Q Q|,a)消除直接左遞歸,對(duì)文法G5： SSa Sb 可改寫(xiě)為： SbS SaS| 改寫(xiě)后的文法所產(chǎn)生的語(yǔ)言句子集仍為：

25、L=ban|0 改寫(xiě)后的文法為L(zhǎng)L1文法,消除左遞歸,消除間接左遞歸 要求文法:1. 無(wú)回路(A(+A) 2.無(wú)空產(chǎn)生式 先將間接左遞歸變成直接左遞歸，然后再消除直接左遞歸。,間接左遞歸的例,例5.11文法G6為： AaB ABb BAc Bd 若有輸入串：adbc# 分析過(guò)程的語(yǔ)法樹(shù)：,b)消除間接左遞歸,對(duì)文法G6：AaB ABb BAc Bd 替換為：AaB ABb BaBc BBbc Bd 消除左遞歸：AaB ABb B(aBc|d)B BbcB| 改寫(xiě)后的文法為L(zhǎng)L1文法,c)消除文法中一切左遞歸的算法,對(duì)文法中一切左遞歸的消除要求文法中不含回路 A+A 的推導(dǎo) 滿足這個(gè)要求的充分條

26、件是，文法中不含形如 AA 的有害規(guī)則和 A 的空產(chǎn)生式,消除文法中一切左遞歸的算法步驟,把文法的所有非終結(jié)符按某一順序排序，如：A1,A2,An 從A1開(kāi)始消除左部為A1的產(chǎn)生式的直接左遞歸，然后把左部為A1的規(guī)則的右部逐個(gè)替換左部為A2右部以A1開(kāi)始的產(chǎn)生式中的A1，并消除左部為A2的產(chǎn)生式的直接左遞歸， 去掉無(wú)用產(chǎn)生式,使用算法消除左遞歸的例,例：有文法的產(chǎn)生式為： (1) SQc|c (2) QRb|b (3)RSa|a 若排序?yàn)椋篠 Q R 無(wú)直接左遞歸，替換：(1)代入(3) (4) R Qca|ca|a 替換：(2)代入(4) (5) R Rbca|bca|ca|a 消除直接左遞

27、歸 SQc|c QRb|b R (bca|ca|a)R R bcaR|,使用算法消除左遞歸的例,(1) SQc|c (2) QRb|b (3)RSa|a 若排序?yàn)椋篟 Q S 替換：(3)代入(2) Q Sab|ab|b 再代入(1) S Sabc|abc|bc|c 消除直接左遞歸 S (abc|bc|c)S SabcS| R (bca|ca|a)R R bcaR|,消除左遞歸的例,例：考慮文法 S (L)|a LL,S|S 消除左遞歸后的文法為 S(L)|a LSL L,SL|,5.4 不確定的自頂向下分析思想,當(dāng)文法不滿足LL(1)時(shí)，可以用不確定的自頂向下分析法(帶回溯的自頂向下分析法)

28、 當(dāng)某個(gè)非終結(jié)符的產(chǎn)生式有多個(gè)候選時(shí)，對(duì)當(dāng)前輸入符號(hào)無(wú)法確定選用唯一的產(chǎn)生式，從而引起回溯。 回溯退回，重新匹配,1.由于相同左部的產(chǎn)生式的右部FIRST集的交集不為空而引起回溯,例如，有文法： SxAy Aab|a 若當(dāng)前輸入串為 xay 對(duì)于字符 a，可選用產(chǎn)生式Aab， 但b和y不匹配，回溯，重新選用Aa,2.由于相同左部的非終結(jié)符的右部存在能 * 的產(chǎn)生式，且該非終結(jié)符FOLLOW集中含有其它右部FIRST集的元素,例如，文法： S aAS S b A bA A 對(duì)當(dāng)前輸入串 ab#，首選 S aAS 對(duì)于字符 b，可選用產(chǎn)生式 A bA A為非終結(jié)符，而且后面有S，回溯，選用產(chǎn)生式

29、A ，然后選S b，完成匹配。,3.由于文法含有左遞歸而引起回溯,例如，文法： S Sa S b 對(duì)當(dāng)前輸入串 baa#， 對(duì)于字符 b，可選用產(chǎn)生式 S b，b為終結(jié)符，不能繼續(xù)推導(dǎo)，回溯 選用產(chǎn)生式 S Sa ，再選S Sa 最后選 S b,5.5 確定的自頂向下分析方法,自頂向下分析方法有： 遞歸子程序法遞歸過(guò)程 預(yù)測(cè)分析方法無(wú)回溯的自頂向下分析,5.5.1遞歸子程序法,將一個(gè)非終結(jié)符A的文法規(guī)則看作識(shí)別A的過(guò)程的定義. 文法中的每個(gè)非終結(jié)符號(hào)對(duì)應(yīng)一個(gè)遞歸過(guò)程 根據(jù)輸入句子的當(dāng)前單詞，確定所選用的產(chǎn)生式。 當(dāng)存在多個(gè)候選產(chǎn)生式時(shí)，按照LL(1)形式唯一的確定一個(gè)產(chǎn)生式進(jìn)行推導(dǎo)。,對(duì)于產(chǎn)生

30、式右部的終結(jié)符號(hào)，則將其與輸入單詞匹配；對(duì)于產(chǎn)生式右部的非終結(jié)符號(hào)，則調(diào)用相應(yīng)的遞歸過(guò)程。 重復(fù)以上過(guò)程，構(gòu)造關(guān)于輸入句子的最左推導(dǎo)。,遞歸子程序法,5.5.2 預(yù)測(cè)分析方法,預(yù)測(cè)分析器 預(yù)測(cè)分析程序 先進(jìn)后出棧 預(yù)測(cè)分析表 僅預(yù)測(cè)分析表與文法有關(guān),非遞歸的預(yù)測(cè)分析方法 對(duì)于像匯編語(yǔ)言、Fortran等不具有遞歸機(jī)制的語(yǔ)言，需要非遞歸的分析方法。 非遞歸分析方法比遞歸分析方法的效率高,預(yù)測(cè)分析方法,根據(jù)輸入串模擬出推導(dǎo)過(guò)程。這里將推導(dǎo)產(chǎn)生的句型看作一個(gè)二元組： (已匹配的符號(hào)串 | 未匹配的符號(hào)串) matched unmatched 初態(tài)：matched = ； unmatched = S(文法開(kāi)始符號(hào)) 終態(tài)：matched = 句子； unmatched = ,預(yù)測(cè)分析方法的思想,句型的存儲(chǔ)：1、已匹配的符號(hào)串不必存儲(chǔ)。2、由于是最左推導(dǎo)，因此，