1、編譯原理,Principles of Compiler,第五章 語法分析,5.1 概述,語法分析 輸入：為單詞的序列 任務(wù)：判斷單詞的序列是否滿足一個(gè)上下文無關(guān)文法 輸出：一個(gè)與單詞序列匹配的語法樹 語法分析的一般方法 利用一個(gè)棧表示識(shí)別的狀態(tài) 根據(jù)語法樹的生成方式分為自上而下與自下而上的兩種策略,5.2 CFG與PDA,上下文無關(guān)文法 CFG ( Context-free Grammar ) 產(chǎn)生式的形式為A ，其中A VN 上下文無關(guān)語言 CFL ( Context-free Language ) 一個(gè)語言是CFL，當(dāng)且僅當(dāng)存在CFG描述它。,5.2 CFG與PDA,下推自動(dòng)機(jī) PDA (

2、 Push Down Automata ) 帶一個(gè)棧的有窮狀態(tài)自動(dòng)機(jī) PDA讀入一個(gè)符號(hào)，在做狀態(tài)遷移的同時(shí)還能夠?qū)＿M(jìn)行操作 是棧式程序的抽象模型 CFG與PDA的等價(jià)性 一個(gè)語言是CFL，當(dāng)且僅當(dāng)存在一臺(tái)PDA識(shí)別它,5.2 CFG與PDA,下推自動(dòng)機(jī)的應(yīng)用 例：只使用一個(gè)棧與一個(gè)狀態(tài)變量，識(shí)別語言L = 0n1n | n 0 算法描述 令狀態(tài)變量s = 0， 從左向右讀入符號(hào)，重復(fù)以下動(dòng)作： 如果s = 0，那么 3.1 如果a為0，則壓入0 3.2 如果a為1，則彈出一個(gè)0，且令s = 1 如果s = 1，那么 4.1 如果a為0，則ERROR 4.2 如果a為1，則彈出一個(gè)0 如果輸

3、入結(jié)束，那么s = 0則接受，否則拒絕。,如果空棧則ERROR,如果空棧則ERROR,而且棧為空棧,5.2 CFG與PDA,下推自動(dòng)機(jī)的形式定義 一個(gè)PDA M=(Q, S, , q0, d, F)，其中： Q為狀態(tài)集 為字符集 為棧字符集 q0 Q為初始狀態(tài) F Q為接受狀態(tài)集 ：Q P( Q )， = ,5.2 CFG與PDA,PDA的語言 一個(gè)PDA M=(Q, S, , q0, d, F)接受串，如果能夠?qū)懗?= a1a2am，ai，并且存在M的一個(gè)狀態(tài)序列s0s1sm與一個(gè)棧的串序列02m，使得： s0 = q0，0 = 0im( (si+1, b) (si, ai+1, c) )，

4、其中i = c， i+1 = b，b, c ， * sm F M的語言為所有M接受的串的集合,5.3 自上而下的分析方法,一般策略 給定一個(gè)文法G，判斷一個(gè)串a(chǎn)是否屬于G的語言。 自上而下的分析方法試圖從文法的開始符號(hào)推導(dǎo)出目標(biāo)串a(chǎn)，如果成功則認(rèn)為a屬于G的語言。 由于該推導(dǎo)過程正好表示對(duì)應(yīng)語法樹從上到下的生成過程，因此稱之為自上而下的分析方法。,5.3 自上而下的分析方法,文法GS: S 0S1 | 分析過程 令輸入串a(chǎn) = 0011 分析過程即從S開始試圖推導(dǎo)出0011 S0S1 00S11 0011,S,語法樹,5.3.1 基于PDA的分析算法,基本思想 利用PDA的棧來存儲(chǔ)推導(dǎo)的中間結(jié)

5、果。 利用PDA的非確定性來“猜測(cè)”所有可能的推導(dǎo)。 采用最左推導(dǎo)，及時(shí)將推導(dǎo)產(chǎn)生出來的最左終結(jié)符與輸入匹配,5.3.1 基于PDA的分析算法,構(gòu)造思想 給定文法G=(VN,VT,P,S)，構(gòu)造PDA M=(Q,S,q0,d,F)，使M恰好接受G的語言。 PDA的分析算法 1 向棧中壓入$S。 2 如果棧頂符號(hào)為非終結(jié)符A，則非確定性地用A的所有產(chǎn)生式的右部替換棧頂?shù)腁。 3 如果棧頂符號(hào)為終結(jié)符a，則與輸入符號(hào)匹配，如果成功則從棧頂彈出a，否則該分支進(jìn)入無定義狀態(tài)（終止）。 4 如果棧頂符號(hào)為$，而且輸入符號(hào)為$（輸入結(jié)束），則接受，否則該分支進(jìn)入無定義狀態(tài)。 5 重復(fù)2,3,4。,5.3.

6、1 基于PDA的分析算法,PDA的構(gòu)造方法 給定文法GS: S 0S1 | 01 構(gòu)造步驟 構(gòu)造初始遷移 為每一條產(chǎn)生式構(gòu)造對(duì)應(yīng)的遷移 為每一個(gè)終結(jié)符的匹配構(gòu)造對(duì)應(yīng)的遷移 構(gòu)造猜測(cè)成功的遷移,5.3.1 基于PDA的分析算法,5.3.1 基于PDA的分析算法,算法特點(diǎn) 通用性好 抽象層次高 算法效率低,5.3.2 左遞歸的消除,直接左遞歸的消除 產(chǎn)生式P P | 改寫為：P P，P P | 一般形式的直接左遞歸 P P1 | P2 | | Pm | 1 | 2 | | n 改寫為： P 1P | 2P | | nP P 1P | 2P | | mP | ,5.3.2 左遞歸的消除,間接左遞歸

7、S Qc | c Q Rb | b R Ca | a 間接左遞歸產(chǎn)生的原因 推導(dǎo)串的首個(gè)非終結(jié)符存在環(huán)路 消除方法：打破可能存在的環(huán)路,5.3.2 左遞歸的消除,間接左遞歸的消除算法 將文法中所有非終結(jié)符排列為P1, P2, , Pn for i := 1 to n do for j := 1 to i 1 do 將形如Pi Pj的產(chǎn)生式改寫為：Pi 1 | 2 | | k，其中Pj 1 | 2 | | k； 消除Pi的直接左遞歸； next next,5.3.3 LL(k)分析方法,概述 向前查看k個(gè)符號(hào)，以協(xié)助選擇正確的產(chǎn)生式進(jìn)行推導(dǎo)，從而避免回溯 如果對(duì)某一文法不能避免回溯，則LL(k)

8、無法分析該文法 LL(1)與LL(2)是最常見的LL分析方法,5.3.3 LL(k)分析方法,LL(1)算法基本思想 將文法的開始符號(hào)S壓入棧中 從左向右讀輸入符號(hào)，重復(fù)以下 2.1 如果棧頂元素為終結(jié)符，則用與輸入符號(hào)a匹配，匹配成功則彈出一個(gè)符號(hào)，否則ERROR 2.2 如果棧頂元素為非終結(jié)符A，輸入符號(hào)為a，則選擇一條能夠產(chǎn)生首字符a的產(chǎn)生式進(jìn)行推導(dǎo)，用產(chǎn)生式的右部替換棧中的A 2.3 空棧，則判斷輸入是否結(jié)束，如果結(jié)束則接受，否則ERROR,5.3.3 LL(k)分析方法,產(chǎn)生式首字符的判斷方法 利用FIRST函數(shù)以及FOLLOW函數(shù)進(jìn)行判斷 FIRST函數(shù) FIRST() = a |

9、 * a, a VT, (VNVT)* 如果 * ，那么FIRST() FOLLOW函數(shù) FOLLOW(A) = a | S * Aa, a VT, , (VNVT)* 如果S * A，則令$ FOLLOW(A),5.3.3 LL(k)分析方法,產(chǎn)生式的選擇方法 假設(shè)棧頂元素為A，輸入符號(hào)為a， A 1 | 2 | | n 如果a FIRST(i) ，那么選擇i 如果i * ，且a FOLLOW(A)，那么選擇i,5.3.3 LL(k)分析方法,FIRST函數(shù)的構(gòu)造 計(jì)算文法符號(hào)A的FIRST(A)，應(yīng)用以下規(guī)則，直到結(jié)果集合不能再增加為止： 如果AVT，那么FIRST(A) = A 如果A，

10、那么令 FIRST(A) 如果AVN而且AX1X2Xn，那么 令FIRST(X1) FIRST(A) 如果存在i使得ji(FIRST(Xj)，那么令FIRST(Xi) FIRST(A) 如果jn(FIRST(Xj)，那么令 FIRST(A),5.3.3 LL(k)分析方法,FIRST函數(shù)的構(gòu)造 計(jì)算符號(hào)串的FIRST()， = X1X2Xn，應(yīng)用以下規(guī)則，直到結(jié)果集合不能再增加為止： 令FIRST(X1) FIRST() 如果存在i使得ji(FIRST(Xj)，那么令FIRST(Xi) FIRST() 如果jn(FIRST(Xj)，那么令 FIRST(),5.3.3 LL(k)分析方法,FOLLOW函數(shù)的構(gòu)造 計(jì)算非終結(jié)符A的FOLLOW(A)，應(yīng)用以下規(guī)則，直到結(jié)果集合不能再增加為止： 如果A = S，那么令$ FOLLOW(A) 如果B A，那么令FIRST() FOLLOW(A) 如果B A，或者B A，其中 FIRST()，那么令FOLLOW(B) FOLLOW(A),5.3.3 LL(k)分析方法,預(yù)測(cè)分析表 FIRST與FOLLOW函數(shù)的計(jì)算需要消耗時(shí)間，因此需要根據(jù)所有可能，預(yù)先計(jì)算出產(chǎn)生式的選擇 考慮所有可能的棧頂元素A與輸入符號(hào)a 構(gòu)造方法 構(gòu)造二維分析表M 如果有產(chǎn)生式A，且終結(jié)符aFIRS