語(yǔ)法分析自下而上分析.ppt

《語(yǔ)法分析自下而上分析.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《語(yǔ)法分析自下而上分析.ppt（52頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、第五章 語(yǔ)法分析自下而上分析,內(nèi)容,自下而上分析基本問題 算符優(yōu)先分析 語(yǔ)法分析器的自動(dòng)產(chǎn)生工具YACC,5.1 自下而上分析基本問題,自下而上分析： 從輸入開始，逐步進(jìn)行“歸約”，直至歸約到文法的開始符號(hào)。,5.1.1 歸約,自下而上分析法是一種“移進(jìn)-歸約”法。 基本思想： 用一個(gè)寄存符號(hào)的先進(jìn)后出棧，把輸入符號(hào)一個(gè)一個(gè)地移進(jìn)到棧里，當(dāng)棧頂形成某個(gè)產(chǎn)生式的候選式時(shí)，即把棧頂?shù)倪@一部分替換成(歸約為)該產(chǎn)生式的左部符號(hào)。,5.1.1 歸約,例：設(shè)文法GS： (1) S aAcBe (2) A b (3) A Ab (4) B d 試對(duì)abbcde進(jìn)行“移進(jìn)-歸約”分析。,,5.1.

2、1 歸約,例：設(shè)文法GS： (1) S aAcBe (2) A b (3) A Ab (4) B d 試對(duì)abbcde進(jìn)行“移進(jìn)-歸約”分析。,5.1.1 歸約,分析樹和語(yǔ)法樹不一定一致。 自下而上分析過程：邊輸入單詞符號(hào)，邊歸約。 核心問題：識(shí)別可歸約串,b,d,b,a,c,e,5.1.2 規(guī)范歸約簡(jiǎn)述,定義：令G是一個(gè)文法，S是文法的開始符號(hào)，假定是文法G的一個(gè)句型，如果有 且,則稱是句型相對(duì)于非終結(jié)符A的短語(yǔ)。 特別是，如果有A,則稱是句型相對(duì)于規(guī)則A的直接短語(yǔ)。一個(gè)句型的最左直接短語(yǔ)稱為該句型的句柄。,5.1.2 規(guī)范歸約簡(jiǎn)述,例：文法GE： EE+T|T TT*F|

3、F F(E)|F|id 考慮文法GE上的句子id1+id2*id3。其最右推導(dǎo)和分析樹如圖5.1(a)、(b)所示。 分析樹中的葉子與短語(yǔ)、直接短語(yǔ)和句柄有下述關(guān)系。 短語(yǔ)：以非終結(jié)符為根的子樹中所有從左到右排列的葉子； 直接短語(yǔ)：只有父子關(guān)系的樹中所有從左到右排列的葉子(樹高為2)； 句柄：最左邊父子關(guān)系樹中所有從左到右排列的葉子(句柄是唯一的)。,圖5.1 id1+id2*id3的最右推導(dǎo)、分析樹與短語(yǔ) (a) 最右推導(dǎo)；(b) 分析樹；(c) 短語(yǔ),根據(jù)定義，從文法開始符號(hào)經(jīng)過0步推導(dǎo)得到E1，從E1經(jīng)過若干步推導(dǎo)得到id1+id2*id3，所以id1+id2*id3是句型id1+id

4、2*id3相對(duì)于E1的短語(yǔ)(其中和均為，是句子的全體)。 考慮推導(dǎo)E1 = E2+id2*id3 = T2+id2*id3 = F1+id2*id3 = id1+id2*id3，id1是相對(duì)于非終結(jié)符E2、T2和F1的短語(yǔ)(其中為，為+id2*id3)，特別是相對(duì)于F1的直接短語(yǔ)，也是句柄。 id1+id2不是句型id1+id2*id3中相對(duì)于任何非終結(jié)符的短語(yǔ)，因?yàn)檎也坏饺魏我粋€(gè)非終結(jié)符，它的子樹中的所有葉子構(gòu)成id1+id2。,5.1.2 規(guī)范歸約簡(jiǎn)述,例：考慮文法GE：ET|E+T TF|T*F F(E)|i和句型i1*i2+i3： 在一個(gè)句型對(duì)應(yīng)的語(yǔ)法樹中，以某非終結(jié)符為根的兩代以上的

5、子樹的所有末端結(jié)點(diǎn)從左到右排列就是相對(duì)于該非終結(jié)符的一個(gè)短語(yǔ)，如果子樹只有兩代，則該短語(yǔ)就是直接短語(yǔ)。 E E+T E+F E+i3 T+i3 T*F+i3 T*i2+i3 F*i2+i3 i1*i2+i3 短語(yǔ)： i1，i2，i3， i1*i2， i1*i2+i3 直接短語(yǔ)： i1，i2，i3 句柄： i1,5.1.2 規(guī)范歸約簡(jiǎn)述,可用句柄來(lái)對(duì)句子進(jìn)行歸約 例：設(shè)文法GS： (1) S aAcBe (2) A b (3) A Ab (4) B d 句型 歸約規(guī)則 abbcde (2) A b aAbcde (3) A Ab aAcde (4) B d aAcBe (1) S

6、aAcBe S,5.1.2 規(guī)范歸約簡(jiǎn)述,定義：假定是文法G的一個(gè)句子，我們稱序列 n， n-1， ，0 是的一個(gè)規(guī)范歸約，如果此序列滿足： 1 n= 2 0為文法的開始符號(hào)，即0=S 3 對(duì)任何i，0 i n， i-1是從i經(jīng)把句柄替換成為相應(yīng)產(chǎn)生式左部符號(hào)而得到的。,5.1.2 規(guī)范歸約簡(jiǎn)述,把上例倒過來(lái)寫，則得到： S aAcBe aAcde aAbcde abbcde 顯然這是一個(gè)最右推導(dǎo)。 規(guī)范歸約是關(guān)于是一個(gè)最右推導(dǎo)的逆過程 最左歸約 規(guī)范推導(dǎo) 由規(guī)范推導(dǎo)推出的句型稱為規(guī)范句型。 規(guī)范歸約的中心問題：確定句型的句柄。,5.1.2 規(guī)范歸約簡(jiǎn)述,最右推導(dǎo)，推導(dǎo)的每一步結(jié)果都是

7、一個(gè)右句型。該推導(dǎo)即分析樹 “剪句柄”的全過程。,圖3.18 剪句柄的過程 (a) 句子；(b) 剪去b之后；(c) 剪去Abc之后；(d) 剪去d之后；(e) 開始符號(hào),5.1.3 符號(hào)棧的使用與語(yǔ)法樹的表示,從分析樹上直觀地看，“剪句柄”的方法十分簡(jiǎn)單。但是若在語(yǔ)法分析器中實(shí)現(xiàn)剪句柄，則有兩個(gè)問題必須解決： 確定右句型中將要?dú)w約的子串(確定句柄)； 確定如何選擇正確的產(chǎn)生式進(jìn)行歸約。 具體實(shí)現(xiàn)采用移進(jìn)歸約方法，用一個(gè)?！坝涀　睂⒁?dú)w約句柄的前綴，并用一個(gè)分析表來(lái)確定何時(shí)棧頂已形成句柄，以及形成句柄后選擇哪個(gè)產(chǎn)生式進(jìn)行歸約。,5.1.3 符號(hào)棧的使用與語(yǔ)法樹的表示,在移進(jìn)歸約分析模式中，符號(hào)

8、棧的使用有以下四種操作形式。 移進(jìn)(shift): 把當(dāng)前輸入中的下一個(gè)終結(jié)符移進(jìn)棧； 歸約(reduce): 句柄在棧頂已形成，用適當(dāng)產(chǎn)生式左部代替句柄； 接受(accept): 宣告分析成功； 報(bào)錯(cuò)(error): 發(fā)現(xiàn)語(yǔ)法錯(cuò)誤，調(diào)用錯(cuò)誤恢復(fù)例程。,考察文法GS： SaABe Ab AAbc Bd 的輸入序列abbcde，移進(jìn)歸約方法分析的符號(hào)棧變化過程如下所示。,5.2 算符優(yōu)先分析,考慮二義文法文法G(E)： G(E)： E i| E+E|E-E|E*E|E/E|(E) 它的句子有幾種不同的規(guī)范規(guī)約。 歸約即計(jì)算表達(dá)式的值。歸約順序不同，則計(jì)算的順序也不同，結(jié)果也不一樣。起決定作用的是

9、相鄰的兩個(gè)算符之間的優(yōu)先關(guān)系。如果規(guī)定算符的優(yōu)先次序，并按這種規(guī)定進(jìn)行歸約，則歸約過程是唯一的。 所謂算符優(yōu)先分析法就是定義算符之間的某種優(yōu)先關(guān)系，借助于這種關(guān)系尋找“可歸約串”和進(jìn)行歸約。,5.2 算符優(yōu)先分析,定義任何兩個(gè)可能相繼出現(xiàn)的終結(jié)符a與b的優(yōu)先關(guān)系： 三種關(guān)系 a b a的優(yōu)先級(jí)低于b a b a的優(yōu)先級(jí)等于b a b a的優(yōu)先級(jí)高于b 注意：與數(shù)學(xué)上的、=不同，a b并不意味著b a,5.2.1 算符優(yōu)先文法及優(yōu)先表構(gòu)造,一個(gè)文法，如果它的任一產(chǎn)生式的右部都不含兩個(gè)相繼(并列)的非終結(jié)符，即不含如下形式的產(chǎn)生式右部： QR 則我們稱該文法為算符文法。 約定： a、b代表任意終

10、結(jié)符； P、Q、R代表任意非終結(jié)符； 代表由終結(jié)符和非終結(jié)符組成的任意序列，包括空字。,假定G是一個(gè)不含-產(chǎn)生式的算符文法。對(duì)于任何一對(duì)終結(jié)符a、b，我們說： 1. ab當(dāng)且僅當(dāng)文法G中含有形如Pab或PaQb的產(chǎn)生式；,如果一個(gè)算符文法G中的任何終結(jié)符對(duì)(a，b)至多只滿足下述三關(guān)系之一： a b，a b， a b 則稱G是一個(gè)算符優(yōu)先文法。,2. ab當(dāng)且僅當(dāng)G中含有形如PaR的產(chǎn)生式，而R b或R Qb；,3. ab 當(dāng)且僅當(dāng)G中含有形如PRb的產(chǎn)生式，而R a或R aQ。,5.2.1 算符優(yōu)先文法及優(yōu)先表構(gòu)造,例:考慮下面的文法GE： (1) EE+T | T (2) T

11、T*F | F (3) FP F | P (4) P(E) | i 由第(4)條規(guī)則，有 ( )； 由規(guī)則EET和TT*F， 有 *； 由(2)和(3)，可得* ； 由(1)EET和E E+T，可得+ +； 由(3)FPF和F PF，可得 。 由(4)P(E)和 EE+TT+TT*F+TF*F+T PF*F+TiF*F+T 有 ( +、( *、(和( i。,5.2.1 算符優(yōu)先文法及優(yōu)先表構(gòu)造,優(yōu)先關(guān)系表（#為終結(jié)符）,從算符優(yōu)先文法G構(gòu)造優(yōu)先關(guān)系表的算法： 通過檢查G的每個(gè)產(chǎn)生式的每個(gè)候選式，可找出所有滿足ab的終結(jié)符對(duì)。 確定滿足關(guān)系和的所有終結(jié)符對(duì)： 首先需要對(duì)G的每個(gè)非終結(jié)

12、符P構(gòu)造兩個(gè)集合FIRSTVT(P)和LASTVT(P)：,5.2.1 算符優(yōu)先文法及優(yōu)先表構(gòu)造,5.2.1 算符優(yōu)先文法及優(yōu)先表構(gòu)造,有了這兩個(gè)集合之后，就可以通過檢查每個(gè)產(chǎn)生式的候選式確定滿足關(guān)系和的所有終結(jié)符對(duì)。 如：假定有個(gè)產(chǎn)生式的一個(gè)候選形為 aP 那么，對(duì)任何bFIRSTVT(P)，有 a b。 假定有個(gè)產(chǎn)生式的一個(gè)候選形為 Pb 那么，對(duì)任何aLASTVT(P)，有 a b。,FIRSTVT(P)的算法,構(gòu)造集合FIRSTVT(P)的算法： 按其定義，可用下面兩條規(guī)則來(lái)構(gòu)造集合FIRSTVT(P)： 1. 若有產(chǎn)生式Pa或PQa，則aFIRSTVT(P

13、)； 2. 若aFIRSTVT(Q)，且有產(chǎn)生式PQ，則aFIRSTVT(P)。,FIRSTVT(P)的算法,數(shù)據(jù)結(jié)構(gòu)： 布爾數(shù)組FP，a，使得FP，a為真的條件是，當(dāng)且僅當(dāng)aFIRSTVT(P)。開始時(shí)，按上述的規(guī)則(1)對(duì)每個(gè)數(shù)組元素FP，a賦初值。 棧STACK，把所有初值為真的數(shù)組元素FP，a的符號(hào)對(duì)(P，a)全都放在STACK之中。 運(yùn)算： 如果棧STACK不空，就將頂項(xiàng)逐出，記此項(xiàng)為(Q，a)。對(duì)于每個(gè)形如PQ的產(chǎn)生式，若FP，a為假，則變其值為真且將(P，a)推進(jìn)STACK棧。 上述過程必須一直重復(fù)，直至棧STACK拆空為止。,FIRSTVT(P)的算法,如果把這個(gè)算法稍為形式化

14、一點(diǎn)，我們可得如下所示的一個(gè)程序(包括一個(gè)過程和主程序)： 過程 PROCEDURE INSERT(P，a)； IF NOT FP，a THEN BEGIN FP，a:=TRUE； 把(P，a)下推進(jìn)STACK棧 END；,FIRSTVT(P)的算法,主程序： BEGIN FOR 每個(gè)非終結(jié)符P和終結(jié)符a DO FP，a:=FALSE； FOR 每個(gè)形如Pa或PQa的產(chǎn)生式 DO INSERT(P，a)； WHILE STACK 非空 DO BEGIN 把STACK的頂項(xiàng)，記為(Q，a)，上托出去； FOR 每條形如PQ的產(chǎn)生式 DO INSERT(P，a)； END OF WH

15、ILE； END,FIRSTVT(P)的算法,這個(gè)算法的工作結(jié)果得到一個(gè)二維數(shù)組F，從它可得任何非終結(jié)符P的FIRSTVT。 FIRSTVT(P)a | FP，a=TRUE 同理，可構(gòu)造計(jì)算LASTVT的算法。,5.2.1 算符優(yōu)先文法及優(yōu)先表構(gòu)造,使用每個(gè)非終結(jié)符P的FIRSTVT(P)和LASTVT(P)，就能夠構(gòu)造文法G的優(yōu)先表。構(gòu)造優(yōu)先表的算法是： FOR 每條產(chǎn)生式PX1X2Xn DO FOR i:=1 TO n-1 DO BEGIN IF Xi和Xi+1均為終結(jié)符 THEN 置XiXi+1 IF in-2且Xi和Xi+2都為終結(jié)符 但Xi+1為非終結(jié)符 THEN 置XiXi

16、+2； IF Xi為終結(jié)符而Xi+1為非終結(jié)符 THEN FOR FIRSTVT(Xi+1)中的每個(gè)a DO 置 Xia； IF Xi為非終結(jié)符而Xi+1為終結(jié)符 THEN FOR LASTVT(Xi)中的每個(gè)a DO 置 aXi+1 END,5.2.1 算符優(yōu)先文法及優(yōu)先表構(gòu)造,例: 考慮下面的文法GE： (1) EE+T | T (2) TT*F | F (3) FP F | P (4) P(E) | i 1. 計(jì)算文法G的FIRSTVT和LASTVT; 2. 構(gòu)造優(yōu)先關(guān)系表; 3. G是算符優(yōu)先文法嗎?,G的算符優(yōu)先關(guān)系表： 結(jié)論: G是算符優(yōu)先文法,5.2.2

17、 算符優(yōu)先分析算法,為了解決在算符優(yōu)先分析過程中如何尋找到可歸約串的問題，引進(jìn)最左素短語(yǔ)的概念。 一個(gè)文法G的句型的素短語(yǔ)是指這樣一個(gè)短語(yǔ)，它至少含有一個(gè)終結(jié)符，并且，除它自身之外不再含任何更小的素短語(yǔ)。 最左素短語(yǔ)是指處于句型最左邊的那個(gè)素短語(yǔ)。,考慮下面的文法G(E)： (1) EE+T | T (2) TT*F | F (3) FP F | P (4) P(E) | i 句型：T+F*P+i 短語(yǔ)：T+F*P+i, T, F， P, F*P, i, T+F*P 直接短語(yǔ)：T, F, P, i 句柄：T 素短語(yǔ)： F*P, i 最左素短語(yǔ)： F*P,5.2.2 算符優(yōu)先分析算法,5.

18、2.2 算符優(yōu)先分析算法,算符優(yōu)先文法句型(括在兩個(gè)之間)的一般形式寫成： #N1a1N2a2NnanNn+1# 其中，每個(gè)ai都是終結(jié)符，Ni是可有可無(wú)的非終結(jié)符。 定理： 一個(gè)算符優(yōu)先文法G的任何句型的最左素短語(yǔ)是滿足如下條件的最左子串 NjajNiaiNi+1， aj-1 aj aj aj+1，，ai-1 ai ai ai+1,5.2.2 算符優(yōu)先分析算法,算符優(yōu)先分析法是一種廣為應(yīng)用、行之有效的方法。 用于分析各類表達(dá)式 ALGOL 60 算符優(yōu)先分析法特點(diǎn)： 優(yōu)點(diǎn): 簡(jiǎn)單，快速 缺點(diǎn): 可能錯(cuò)誤接受非法句子，能力有限. 算符優(yōu)先分析算法： 使用一個(gè)符號(hào)棧S，用它寄存

19、終結(jié)符和非終結(jié)符，k代表符號(hào)棧S的使用深度。,5.2.2 算符優(yōu)先分析算法,1 k:=1; Sk:=#; 2 REPEAT 3 把下一個(gè)輸入符號(hào)讀進(jìn)a中； 4 IF SkVT THEN j:=k ELSE j:=k-1; 5 WHILE Sja DO 6 BEGIN 7 REPEAT 8 Q:=Sj; 9 IF Sj-1VT THEN j:=j-1 ELSE j:=j-2 10 UNTIL SjQ; 11 把Sj+1Sk歸約為某個(gè)N； 12 k:=j+1; 13 Sk:=N 14 END OF WHILE; 15 IF Sja OR Sja THEN 16

20、 BEGIN k:=k+1; Sk:=a END 17 ELSE ERROR /*調(diào)用出錯(cuò)診察程序*/ 18 UNTIL a=#,5.2.2 算符優(yōu)先分析算法,在算法的工作過程中，若出現(xiàn)j減1后的值小于等于0時(shí)，則意味著輸入串有錯(cuò)。在正確的情況下，算法工作完畢時(shí)，符號(hào)棧S應(yīng)呈現(xiàn)：# N #。 算法的第11行中的N是指那樣一個(gè)產(chǎn)生式的左部符號(hào)，此產(chǎn)生式的右部和Sj+1Sk 構(gòu)成如下一一對(duì)應(yīng)關(guān)系：自左至右，終結(jié)符對(duì)終結(jié)符，非終結(jié)符對(duì)非終結(jié)符，而且對(duì)應(yīng)的終結(jié)符相同。由于非終結(jié)符對(duì)歸約沒有影響，因此，非終結(jié)符根本可以不進(jìn)符號(hào)棧S。,5.2.2 算符優(yōu)先分析算法,算符優(yōu)先分析一般并不等價(jià)于規(guī)范

21、歸約,5.2.3 優(yōu)先函數(shù),把每個(gè)終結(jié)符與兩個(gè)自然數(shù)f()與g()相對(duì)應(yīng)，使得 若1 2，則f(1) g(2) f稱為入棧優(yōu)先函數(shù)，g稱為比較優(yōu)先函數(shù)。 優(yōu)點(diǎn):便于比較，節(jié)省空間； 缺點(diǎn):原來(lái)不存在優(yōu)先關(guān)系的兩個(gè)終結(jié)符，由于自然數(shù)相對(duì)應(yīng)，變成可以比較的。要進(jìn)行一些特殊的判斷。,5.2.3 優(yōu)先函數(shù),文法GE (1) EE+T | T (2) TT*F | F (3) FP F | P (4) P(E) | i 的優(yōu)先函數(shù)如下表：,有許多優(yōu)先關(guān)系表不存在優(yōu)先函數(shù)，如： 不存在對(duì)應(yīng)的優(yōu)先函數(shù)f和g 假定存在f和g，則有 f(a)=g(a)，f(a)g(b)， f(b)=g(a)，f(b)=g

22、(b) 導(dǎo)致如下矛盾: f(a) g(b) = f(b) = g(a) = f(a) 如果優(yōu)先函數(shù)存在，則不唯一(無(wú)窮多),5.2.3 優(yōu)先函數(shù),如果優(yōu)先函數(shù)存在，則可以通過以下三個(gè)步驟從優(yōu)先表構(gòu)造優(yōu)先函數(shù): 1 對(duì)于每個(gè)終結(jié)符a，令其對(duì)應(yīng)兩個(gè)符號(hào)fa和ga，畫一以所有符號(hào)fa和ga為結(jié)點(diǎn)的方向圖。如果ab，則從fa畫一條弧至gb，如果ab，則畫一條弧從gb至fa。 2 對(duì)每個(gè)結(jié)點(diǎn)都賦予一個(gè)數(shù)，此數(shù)等于從該結(jié)點(diǎn)出發(fā)所能到達(dá)的結(jié)點(diǎn)(包括出發(fā)點(diǎn)自身)。賦給fa的數(shù)作為f(a)，賦給ga的數(shù)作為g(a)。 3 檢查所構(gòu)造出來(lái)的函數(shù)f和g是否與原來(lái)的關(guān)系矛盾。若沒有矛盾，則f和g就是要求的優(yōu)先函數(shù)，若

23、有矛盾，則不存在優(yōu)先函數(shù)。,5.2.3 優(yōu)先函數(shù),例:求文法G(E) (1) EE+T | T (2) TT*F | F (3) FP F | P (4) P(E) | i 的終結(jié)符+，*，，i所對(duì)應(yīng)的優(yōu)先函數(shù)。,5.2.3 優(yōu)先函數(shù),5.2.3 優(yōu)先函數(shù),練習(xí),1 已知文法GS為：Sa||(T) TT,S|S (1) 計(jì)算GS的FIRSTVT和LASTVT。 (2) 構(gòu)造GS的算符優(yōu)先關(guān)系表并說明GS是否為算符優(yōu)先文法。 (3) 給出輸入串 (a,(a,a))#的算符優(yōu)先分析過程。,文法：Sa||(T) TT,S|S 展開為： SaSS(T) TT,S TS (1) FIRSTVT -- LASTVT表,(2)算符優(yōu)先關(guān)系表如下: 表中無(wú)多重入口所以是算符優(yōu)先（OPG）文法。,(3) 對(duì)輸入串（a,(a,a)）# 的算符優(yōu)先分析過程為：,