編譯程序原理與實(shí)現(xiàn)：第3章 形式語言與語法分析

1、編譯程序原理與實(shí)現(xiàn)張晶2013.02第三章 語法分析介紹第3章 outline語法分析概述1.功能需求(輸入，輸出，主要功能)2.分析算法+數(shù)據(jù)結(jié)構(gòu)3.構(gòu)造語法分析器的通用過程上下文無關(guān)文法語法分析樹和抽象語法樹二義性文法文法變換算法語法錯(cuò)誤處理知識(shí)關(guān)系圖開發(fā)語法分析程序語法定義基于上下文無關(guān)文法使用實(shí)現(xiàn)自頂向下自底向上3.1 語法分析概述部分語法分析程序的功能輸入：詞法分析程序輸出的Token/TokenList輸出：語法結(jié)構(gòu)的內(nèi)部表示(抽象語法樹，AST) 或語法錯(cuò)誤信息分析過程：從左到右掃描Token序列，根據(jù)上下文無關(guān)文法，建立語法結(jié)構(gòu)的內(nèi)部表示，檢查語法錯(cuò)誤。語法分析Token序列

2、抽象語法樹語法錯(cuò)誤語法分析過程C程序：Parser輸入：Parser輸出：if (x=y) z=1; else z=0; IF Lparen id EQ id Rparen LG id EQ num semi RG else LG id EQ num semi RGIF_Stmt=idid =idnum =idnum程序設(shè)計(jì)語言的語法結(jié)構(gòu)(1) 程序(2) 聲明- 常量聲明- 類型聲明- 變量聲明- 過程/函數(shù)聲明(3) 程序體(4) 語句（賦值語句，條件語句，循環(huán)語句，函數(shù)調(diào)用語句） (5) 表達(dá)式 (算術(shù)表達(dá)式，邏輯表達(dá)式，關(guān)系表達(dá)式)語法錯(cuò)誤語法錯(cuò)誤的類型語法結(jié)構(gòu)的開始單詞錯(cuò)誤表達(dá)式E的

3、開始單詞是id, (, n-其他Token則出錯(cuò)語法結(jié)構(gòu)的后繼單詞錯(cuò)誤語句；語句-語句，語句標(biāo)識(shí)符或者常量錯(cuò)id := E - begin := E 或 123:=E關(guān)鍵字錯(cuò)if E then 語句 else 語句 -其他關(guān)鍵字則出錯(cuò)括號(hào)配對(duì)錯(cuò)（）（） -）（）語法錯(cuò)誤的例子int GetMax( int x ; int y) if (xy) return x else return y; vod main() real 10, y; 10 + ; GetMax( x, y) ;后繼單詞錯(cuò)括號(hào)配對(duì)錯(cuò)關(guān)鍵字錯(cuò),開始單詞錯(cuò)標(biāo)識(shí)符錯(cuò)開始單詞錯(cuò)語法分析方法自頂向下的分析 從上往下生成樹的過程自底向上的

4、分析 從下往上生成樹的過程IF_Stmt=idid =idnum =id0遞歸下降分析LL(1)分析LR(0),SLR(1),LR(1),LALR(1)語法分析與詞法分析的比較階段（Phase）輸入（Input）輸出（Output）詞法分析（scanner）字符序列Token序列語法分析（parser）Token序列抽象語法樹第3章 outline語法分析概述1.功能需求(輸入，輸出，主要功能)2.分析算法+數(shù)據(jù)結(jié)構(gòu)3.構(gòu)造語法分析器的通用過程上下文無關(guān)文法語法分析樹和抽象語法樹二義性文法文法變換算法語法錯(cuò)誤處理3.2 上下文無關(guān)文法 不是所有的Token串都是合法的程序，因此需要一個(gè)工具來描

5、述合法的Token串。 一般地，程序設(shè)計(jì)語言的結(jié)構(gòu)都是遞歸結(jié)構(gòu)(recursive structure)例如：表達(dá)式，上下文無關(guān)文法非常適合描述這種結(jié)構(gòu)變量是表達(dá)式（表達(dá)式）是表達(dá)式表達(dá)式+表達(dá)式是表達(dá)式3.2 上下文無關(guān)文法上下文無關(guān)文法是一個(gè)四元組(VT,VN,S,P)VT是有限的終極符集合VN是有限的非終極符集合S是開始符，S VNP是產(chǎn)生式的集合，且具有下面的形式： AX1X2Xn 其中AVN，Xi (VTVN )符號(hào)約定：非終極符用大寫字母表示 終極符用小寫字母表示 開始符是第一條產(chǎn)生式左部的符號(hào)不絕對(duì)！上下文無關(guān)文法的例子例1：簡(jiǎn)單算術(shù)表達(dá)式的上下文無關(guān)文法，E id E (E)E

6、 E + EE E * EE id | (E) | E + E |E * EE id | (E) | E + E |E * EVT: id, (,),+,*VN: ES : E上下文無關(guān)文法的例子例2：語句的上下文無關(guān)文法： VT：id，（，），+，*, =, if , else, while, ;VN：E, StmtS：StmtStmt id = EStmt if E Stmt else StmtStmt while E StmtStmt Stmt;Stmt E id E (E)E E + EE E * E上下文無關(guān)文法的例子例3：變量聲明的上下文無關(guān)文法： 變量聲明 變量聲明 一個(gè)變量定義

7、;變量聲明 一個(gè)變量定義 ; 變量聲明 變量定義 類型 標(biāo)識(shí)符序列標(biāo)識(shí)符序列 一個(gè)標(biāo)識(shí)符標(biāo)識(shí)符序列 一個(gè)標(biāo)識(shí)符 , 標(biāo)識(shí)符序列VarDec VarDec VarDef;VarDec VarDef; VarDecVarDef Type IdListIdList idIdList id ,IdList上下文無關(guān)文法是怎樣定義語言的？與上下文無關(guān)文法有關(guān)的一些概念直接推導(dǎo)()：如果A是一個(gè)產(chǎn)生式，則有A ,其中表示一步推導(dǎo)(用A)。這時(shí)稱是由A直接推導(dǎo)的。“” 的含義是，使用一條規(guī)則，代替左邊的某個(gè)符號(hào)，產(chǎn)生右端的符號(hào)串推導(dǎo)(+)：若通過一步或多步推導(dǎo)可從串導(dǎo)出串,則稱為的推導(dǎo),并記為 + 星推導(dǎo)(

8、*):稱 * 當(dāng)且僅當(dāng) = 或 + 例子(E) (E+T) (應(yīng)用產(chǎn)生式2)(E) (T) (應(yīng)用產(chǎn)生式1)E直接推導(dǎo)出E+T或E直接推導(dǎo)出TE T F （E） （E+T） （T+T） （F+T） （i+T） （i+F） （i+n) ,記作E + (i+n)E經(jīng)過多步推導(dǎo)出i+nE * EE * i +(i） E經(jīng)過若干步推導(dǎo)出i+(i）P:(1) E T(2) E E + T(3) T F(4) T T * F(5) F (E)(6) F i(7) F n與上下文無關(guān)文法有關(guān)的一些概念句型：如果有S * , S是文法的開始符, (VTVN )*，則稱是G的句型句子：如果有S + , S是文法

9、的開始符, VT*，則稱是G的句子語言： L(G) = | S + , VT* 即文法G的所有句子的集合文法等價(jià)： G1和G2兩個(gè)文法,若L(G1) = L(G2),則稱G1和G2等價(jià)例子句型: E, T, E+T, F, T*F, i, n, (E), . 句子: i, n, (i), (n), i+i, i+n, 語言:i, n, (i), (n), i+i, i+n , P:(1) E T(2) E E + T(3) T F(4) T T * F(5) F (E)(6) F i(7) F n與上下文無關(guān)文法有關(guān)的一些概念最左(右)推導(dǎo)：在推導(dǎo)過程中，總是對(duì)當(dāng)前符號(hào)串中最左(右)邊的非終極

10、符進(jìn)行替換，稱為最左(右)推導(dǎo),記為l(r)m規(guī)范推導(dǎo)：最右推導(dǎo)左(右)句型：通過最左(右)推導(dǎo)得到的句型，稱為左(右)句型規(guī)范句型：右句型例子最左推導(dǎo): i+T*n +F lm i + F*n + F最右推導(dǎo): i+T*n +F rm i + T*n +i左句型: i + i*F右句型: E+(i)P:(1) E T(2) E E + T(3) T F(4) T T * F(5) F (E)(6) F i(7) F n特別注意例如文法G : N D | N D D 0 | 1| 2 | | 9 N rm ND rm N 8 rm ND 8 rm N 98 rm D98 rm198,句子198

11、的最右推導(dǎo) N rm ND N D D ,句型NDD不存在最右推導(dǎo) 每個(gè)句子一定有最右(規(guī)范)推導(dǎo)每個(gè)句型不一定有最右(規(guī)范)推導(dǎo)上下文無關(guān)文法小結(jié)Context Free Grammar, CFG(VT,VN,S,P)推導(dǎo)，句型，句子，語言的概念及含義語言與文法 Chomsky文法分類Chomsky文法分類上下文無關(guān)文法只是文法的一種。文法有很多種。Chomsky將文法分為四類：0型文法：短語文法。產(chǎn)生式：，中至少有一個(gè)非終極符。0型語言。1型文法：上下文相關(guān)文法。產(chǎn)生式： A , ,可為。1型語言(上下文有關(guān)語言)。2型文法：上下文無關(guān)文法。產(chǎn)生式： A ， 可為。2型語言(上下文無關(guān)語言

12、)。3型文法：正則文法。產(chǎn)生式： A aB, A a。3型語言(正則語言)。Chomsky文法分類描述能力：0型文法 1型文法 2型文法 3型文法對(duì)應(yīng)自動(dòng)機(jī)：0型文法 對(duì)應(yīng) 圖靈機(jī)1型文法 對(duì)應(yīng) 線性有屆自動(dòng)機(jī)2型文法 對(duì)應(yīng) 下推自動(dòng)機(jī)3型文法 對(duì)應(yīng) 有限自動(dòng)機(jī)第3章 outline語法分析概述1.功能需求(輸入，輸出，主要功能)2.分析算法+數(shù)據(jù)結(jié)構(gòu)3.構(gòu)造語法分析器的通用過程上下文無關(guān)文法語法分析樹和抽象語法樹二義性文法文法變換算法語法錯(cuò)誤處理3.3 語法分析樹和抽象語法樹問題: 推導(dǎo)是從開始符產(chǎn)生句型的一種方法; 對(duì)同一個(gè)句型存在多個(gè)推導(dǎo)：NND NDD ND8 N98 或 N9D N9

13、8 或 DDD DD8 D98 198 或 D9D D98 198 或 1DD 19D 198 或 1D8 198 即線性推導(dǎo)不能唯一地表示句子的結(jié)構(gòu)語法分析樹: (Syntax Analysis Tree)用于表示句型結(jié)構(gòu)的一種較好方法;例子P:(1) E T(2) E E + T(3) T F(4) T T * F(5) F (E)(6) F i(7) F n 句型（句子） : i + i * n該句型存在多個(gè)推導(dǎo)： 語法分析樹：語法分析樹語法分析樹是針對(duì)某個(gè)特定CFG的帶標(biāo)號(hào)的樹樹的每個(gè)節(jié)點(diǎn)都標(biāo)記一個(gè)符號(hào)：樹的根節(jié)點(diǎn)標(biāo)記文法的開始符;樹的每個(gè)葉子節(jié)點(diǎn)標(biāo)記一個(gè)終極符;若有樹的中間節(jié)點(diǎn)標(biāo)記為

14、A,它有n個(gè)兒子節(jié)點(diǎn)，從左到右標(biāo)記為B1,Bn,則G中定存在產(chǎn)生式A B1 Bn; 抽象語法樹(AST)語法分析樹存在的問題包含很多不必要(對(duì)語義分析和代碼生成而言)的節(jié)點(diǎn) 抽象語法樹只包含必要的節(jié)點(diǎn)作為語法分析程序輸出 句型(句子): i + i * nP:(1) E T(2) E E + T(3) T F(4) T T * F(5) F (E)(6) F i(7) F n第3章 outline語法分析概述1.功能需求(輸入，輸出，主要功能)2.分析算法+數(shù)據(jù)結(jié)構(gòu)3.構(gòu)造語法分析器的通用過程上下文無關(guān)文法語法分析樹和抽象語法樹二義性文法文法變換算法語法錯(cuò)誤處理3.4 二義性文法二義性文法(a

15、mbiguous grammar) 如果文法的一個(gè)句子有兩棵或兩棵以上不同的語法分析樹，則稱該句子是二義性的。 包含二義性句子的文法，稱為二義性文法。二義性文法的例子P:Exp Exp + ExpExp Exp ExpExp Exp * ExpExp Exp / ExpExp (Exp)Exp idExp numid + id * id if then else if then .假設(shè)有條件語句 if e1 then if e2 then s1 else s2則可有下圖所示的兩棵不同的語法分析樹： if語句的二義性ififthenelsethene1e2s1s2elsethenifthenif

16、e1e2s1s1二義性文法(ambiguous grammar)二義性會(huì)給語法分析帶來不確定性，應(yīng)盡量避免寫出二義性的文法。但有時(shí)用二義性文法定義語法結(jié)構(gòu)更簡(jiǎn)單直觀。文法二義性問題是不可判定的，也就是不存在一種算法，能在有限步內(nèi)確切的判定一個(gè)文法不是二義性文法。若要證明文法是二義性的，只要舉出一個(gè)有兩棵以上語法分析樹的句子即可。若能控制文法的二義性，即加入人為的附加條件，則二義文法的存在并非壞事，有時(shí)二義性文法可以簡(jiǎn)化文法的表示。消除文法二義性的常用方法 1、規(guī)定符號(hào)的優(yōu)先級(jí) 2、規(guī)定符號(hào)的結(jié)合性表達(dá)式的無二義性文法有二義性的表達(dá)式文法:Exp Exp + ExpExp Exp ExpExp

17、Exp * ExpExp Exp / ExpExp (Exp)Exp idExp num無二義性的表達(dá)式的文法：E TE E + T | E - TT FT T * F | T / FF ( E )F idF numIf語句的無二義性文法定義 Stmt Matched_stmt | Unmatched_stmt Matched_stmt if E then Matched_stmt else Matched_stmt | other Unmatched_stmt if E then Stmt | if E then Matched_stmt else Unmatched_stmt第3章 out

18、line語法分析概述1.功能需求(輸入，輸出，主要功能)2.分析算法+數(shù)據(jù)結(jié)構(gòu)3.構(gòu)造語法分析器的通用過程上下文無關(guān)文法語法分析樹和抽象語法樹二義性文法文法變換算法語法錯(cuò)誤處理文法變換有些語法分析方法要求被分析的文法滿足一定的約束條件，當(dāng)被分析的文法不滿足這些條件時(shí)，常常要進(jìn)行文法變換。文法變換必須保證變換前后的兩個(gè)文法G1和G2是等價(jià)的，即L(G1) = L(G2)常用文法變換方法增補(bǔ)文法去除空產(chǎn)生式消除無用產(chǎn)生式消除特型產(chǎn)生式消除公共前綴消除左遞歸(直接，間接)文法變換算法（1）何時(shí)需要增補(bǔ)：在自底向上(bottom to up)的語法分析方法中，要求文法開始符不能出現(xiàn)在產(chǎn)生式的右部. 否

19、則，需要對(duì)文法進(jìn)行增補(bǔ)。變換方法： 在原產(chǎn)生式基礎(chǔ)上，增加一條產(chǎn)生式：Z S，S為原文法的開始符，Z為增補(bǔ)文法的開始符文法變換算法（2）文法中空產(chǎn)生式的存在常常給語法分析帶來困難，因此最好將空產(chǎn)生式消除掉。變換依據(jù)：文法G中除了S以外的空產(chǎn)生式(A)可以消除; 變換方法：找出所有可以推導(dǎo)出的非終極符,記為S;對(duì)于所有產(chǎn)生式A X1 X2 Xi-1XiXi+1XnXi S增加A X1 X2 Xi-1Xi+1Xn直到?jīng)]有新的產(chǎn)生式產(chǎn)生刪除對(duì)應(yīng)空產(chǎn)生式, 除了S不可以刪除 消除空產(chǎn)生式的例子S | A a BBA B B | aB |bS=S, B, AA BA BB S a BBSA a BB S

20、 A a BS Aa S a S aB 變換后得到的文法：S | A a BB | aBB | AaB | aB | Aa | aA B B | B | aB b文法變換算法（3）無用產(chǎn)生式: A , A不出現(xiàn)在任何句型中;消除方法：關(guān)鍵是找到這樣的非終極符，how?生成會(huì)出現(xiàn)在句型中的非終極符集合SSSS = S Si SS, Si 1 , Si n把1 , n中的所有非終極符加入SS中;重復(fù)直到?jīng)]有新的非終極符加入;不屬于SS的非終極符,它們的產(chǎn)生式是無用產(chǎn)生式,刪除掉;消除無用產(chǎn)生式的例子S | A a BBA B B | aB |bC cSS = SSS = S, A, BSS = S

21、, A, BC c是無用產(chǎn)生式文法變換算法（4）特型產(chǎn)生式: A B消除算法對(duì)每個(gè)非終極符A,構(gòu)造 SA = B| A+B, BVN如果C SA,而且C 不是特型產(chǎn)生式,則增加 A ;刪除特型產(chǎn)生式;刪除無用產(chǎn)生式;消除特型產(chǎn)生式的例子S | AA B | aB bSS = A,BSA = BS aS bA bS | a | bA a | bB bSB = 文法變換算法（5）消除公共前綴(left factoring)公共前綴A 1 | | n| 1| m提取公因子A A| 1| mA 1 | | n文法變換算法（6-1）消除左遞歸(left recursion) 遞歸分為直接左遞歸和間接左遞

22、歸直接左遞歸: A A 1 | | A n| 1| m消除方法: A 1A| mA A 1A | | nA|消除左遞歸的例子P:(1) E T(2) E E + T(3) T F(4) T T * F(5) F (E)(6) F i(7) F n E T E E +T E | E E + T | T = + T 1 = T文法變換算法（6-2）消除左遞歸(left recursion)間接左遞歸: 消除方法: 非終極符排序消元法 S A b A S a | b 1:S 2:A A Aba | b A bA A baA | 文法變換算法（6-2）消除左遞歸(left recursion)間接左遞

23、歸: 消除方法: 非終極符排序消元法 S Qc | c Q Rb | b R S a | a 1:R 2:Q 3:S R Sa | a Q Rb | b Sab | ab | b S Qc | c Sabc | abc | bc | c S (abc | bc | c)S S abcS | 文法變換算法（6-2）消除左遞歸(left recursion)間接左遞歸: 排序不同，變換后文法也不同 S Qc | c Q Rb | b R S a | a 1:S 2:Q 3:R S Qc | c Q Rb | b R Sa | a (Qc|c)a | a Qca | ca |a (Rb|b)ca | ca | a S Qc | cQ Rb | bR (bca | ca | a)R R bcaR | 第3章 outline語法分析概述1.功能需求(輸入，輸出，主要功能)2.分析算法+數(shù)據(jù)結(jié)構(gòu)3.構(gòu)造語法分析器的通用過程上下文無關(guān)文法語法分析樹和抽象語法樹二義性文法文法變換算法語法錯(cuò)誤處理語法錯(cuò)誤處理編譯器的任務(wù)是檢測(cè)invalid的程序，并將valid的程序翻譯成目標(biāo)代碼。Erro