1、1第四章第四章 語法分析語法分析2本章內(nèi)容本章內(nèi)容q 上下文無關(guān)文法q 自頂向下分析和自底向上分析q LL文法和LR文法q Yacc3詞詞 法法分析器分析器記記 號(hào)號(hào)取下一個(gè)取下一個(gè)記號(hào)記號(hào)源程序源程序語法語法分析分析樹樹前端的前端的其余部分其余部分語法分語法分析器析器中間中間表示表示符號(hào)表符號(hào)表4.1 語法分析器的作用語法分析器的作用44.2 上下文無關(guān)文法上下文無關(guān)文法q 正則表達(dá)式的局限性 q 正規(guī)式用于定義一些簡單的語言，能表示給定結(jié)構(gòu)的固定次數(shù)的重復(fù)或者沒有指定次數(shù)的重復(fù)。 q例：a5b5,a(ba)5, a(ba)*q 當(dāng)自動(dòng)機(jī)構(gòu)造好后，anbn的n是確定的。q 正規(guī)式不能用于描述

2、配對(duì)或嵌套的結(jié)構(gòu)，例：q 配對(duì)括號(hào)串的集合，例如：()()q anbn 5q 例如，包含遞歸結(jié)構(gòu)的條件語句不能用正規(guī)表達(dá)式說明，可以用產(chǎn)生式表示：q stmt if expr then stmt else stmt| q stmt if then else stmt| q 正規(guī)表達(dá)式：(if then else)*64.2.1上下文無關(guān)文法的定義上下文無關(guān)文法的定義上下文無關(guān)文法是四元組（VT , VN , S, P）VT : 終結(jié)符集合VN : 非終結(jié)符集合S : 開始符號(hào)， S VN 唯一一個(gè)開始符號(hào)P :產(chǎn)生式集合，產(chǎn)生式形式為：A ，AVN, (VNVT )*stmt if expr

3、then stmt else stmtstatement 語句7例例4.2 定義算術(shù)表達(dá)式的文法定義算術(shù)表達(dá)式的文法expr expr op expr expr (expr)expr expr expr idop + | - | * | /operator運(yùn)算符 operand 操作數(shù)非終結(jié)符集合VN =expr,op終結(jié)符集合VT=+,-,*,/, (, ),idexpr是開始符號(hào)84.2.2 符號(hào)的使用約定符號(hào)的使用約定q 我們一般用大寫字母表示非終結(jié)符，小寫字母表示終結(jié)符，q 終結(jié)符Terminals: q a, b, c, +, -, punc, 0, 1, 9, Black stri

4、ngs: id, ifq 非終結(jié)符Non-Terminals: q A, B, C, S, 斜體串italic stringsq 文法符號(hào)： X, Y, Z 表示非終結(jié)符或終結(jié)符號(hào)q 終結(jié)符號(hào)串： u, v, z in VT* 字母表中排在后面的小寫字母q 文法符號(hào)串： , in (VT VN)*省得對(duì)每個(gè)文法要說明哪些是終結(jié)符，哪些是非終結(jié)符。省得對(duì)每個(gè)文法要說明哪些是終結(jié)符，哪些是非終結(jié)符。u=aabbcc =abAcBd9符號(hào)的使用約定符號(hào)的使用約定q 產(chǎn)生式: qA 1; A 2; ; A k; A 1 | 2 | | k 10E E A E | ( E ) | -E | idA +

5、| - | * | / 例例4.2的文法改寫為：的文法改寫為：expr expr op expr expr (expr)expr expr expr idop + | - | * | /expr expr op expr | ( expr ) | -expr| idop + | - | * | / 或114.2.3 推導(dǎo)推導(dǎo)q 把產(chǎn)生式看成重寫規(guī)則，用產(chǎn)生式右部的串來代替左部的非終結(jié)符。q 例: E E + E | E * E | (E ) | E | id q E E (E) (E + E) (id + E) (id + id)q (id + id)是文法的句子。q (id + E)等是文法

6、的句型。stop him watching TVstop doing .12推導(dǎo)的定義推導(dǎo)的定義q 定義：設(shè)有文法定義：設(shè)有文法G = ( VT, VN, S, P)，稱串，稱串 A 直接推導(dǎo)出直接推導(dǎo)出，如果，如果A P，且，且 , (VT VN)*，并記作，并記作 A 。q 稱稱 直接歸約到直接歸約到 A 。q 如果存在一個(gè)直接推導(dǎo)序列：如果存在一個(gè)直接推導(dǎo)序列：q 0 1 . n (n=0), q則稱則稱 0推導(dǎo)出推導(dǎo)出 n，記作，記作 0n（推導(dǎo)長度（推導(dǎo)長度為為n）。）。記作或nnn*000E E (E) (E + E) (id + E) (id + id)13推導(dǎo)推導(dǎo)表示一步推導(dǎo)(

7、直接推導(dǎo))表示零步或多步推導(dǎo)對(duì)任意串如果 表示一步或多步推導(dǎo)*，。，則，且*+ 14句型、句子、語言句型、句子、語言q 對(duì)開始符號(hào)為S的文法G，wL(G)，當(dāng)且僅當(dāng) 稱w為G的句子。q 對(duì)開始符號(hào)為S的文法G，如果，則稱為G的句型。q 句子是不含非終結(jié)符的句型。q 僅含終結(jié)符號(hào)的句型是一個(gè)句子。q 語言L(G)是由文法G產(chǎn)生的所有句子的集合：q 若文法G1和文法G2所產(chǎn)生的語言相同，即L(G1) = L(G2)，則稱文法G1和文法G2等價(jià)。 wS*S|)(*TVSGL且一個(gè)一個(gè)C語言程序就是語言程序就是C語言的一個(gè)句子。語言的一個(gè)句子。15 S aSb aaSbb a3Sb3 an-1Sbn-

8、1 anbn顯然，L(G) = anbn n1 。例：已知文法G = ( a, b, S, S, P )，其中 P：S aSb ab 16最左推導(dǎo)最左推導(dǎo)left mostq 最左推導(dǎo)：推導(dǎo)過程中任何一步推導(dǎo)都是對(duì)中的最左非終結(jié)符進(jìn)行替換。q 如果是最左推導(dǎo)，可以記為q 如果 ，則稱是文法的左句型。)()()()(ididEidEEEEElmlmlmlmlmlm*lmS17最右推導(dǎo)最右推導(dǎo)q 類似的，可以定義最右推導(dǎo)：推導(dǎo)過程中任何一步推導(dǎo) 都是對(duì)中的最右非終結(jié)符進(jìn)行替換。q 最右推導(dǎo)也稱作規(guī)范推導(dǎo)。)()()()(idididEEEEEErmrmrmrmrm18歸約（歸約（reduce）q

9、定義：設(shè)和均為句型，若，則稱可以歸約為。q 規(guī)范（最右）推導(dǎo)的逆過程，稱為規(guī)范歸約。q 語法分析的核心問題就是，對(duì)于一個(gè)終結(jié)符號(hào)串x，設(shè)法從S推導(dǎo)出x，或者反過來，設(shè)法將x歸約為S。*)()()()(idididEEEEEErmrmrmrmrm最右推導(dǎo)的逆反就是最左規(guī)約最右推導(dǎo)的逆反就是最左規(guī)約194.2.4 分析樹和推導(dǎo)分析樹和推導(dǎo)分析樹是推導(dǎo)的圖形表示。-(id+id)的分析樹的分析樹EE ()EEE+idid20例例4.5 從最左推導(dǎo)構(gòu)造的分析樹從最左推導(dǎo)構(gòu)造的分析樹EEE EE ()EEE ()EEE+EE ()EEE+idEE ()EEE+idid)()()()(ididEidEEE

10、EElmlmlmlmlm21例例4.5 從最右推導(dǎo)構(gòu)造的分析樹從最右推導(dǎo)構(gòu)造的分析樹EEE EE ()EEE ()EEE+EE ()EEE+idEE ()EEE+idid)()()()(idididEEEEEErmrmrmrmrm22q 設(shè)串是文法G的句型，則至少存在一棵分析樹，它的葉子從左至右排列恰好就是。 q 注意，分析樹的形狀與推導(dǎo)順序無關(guān)，而與在推導(dǎo)時(shí)，所選擇的對(duì)句型中的非終結(jié)符號(hào)進(jìn)行替換的產(chǎn)生式有關(guān)。q 每棵分析樹都有與之對(duì)應(yīng)的唯一的最左推導(dǎo)和最右推導(dǎo)。q 但是，每個(gè)句子不一定只有唯一的分析樹。句型與分析樹的關(guān)系句型與分析樹的關(guān)系EE ()EEE+idid-(id+id)id * i

11、d + id234.2.5 二義性二義性q 二義性的一些例子q I saw a man in the hill with a telescope.q 球拍賣完了。q 父在子先亡。24q 四個(gè)人在打麻將，周圍沒有旁觀者，但是派出所卻帶走了5個(gè)人（不包括警察）。請(qǐng)問這是為什么？25文法句子文法句子id * id + id有兩個(gè)不同的最左推有兩個(gè)不同的最左推導(dǎo)：導(dǎo)：E E * E E E + E id * E E * E +E id * E + E id * E + E id * id + E id * id + E id * id + id id * id + id26二義性用分析樹表示比較直觀二

12、義性用分析樹表示比較直觀E E * E E E + E id * E E * E +E id * E + E id * E + E id * id + E id * id + E id * id + id id * id + idEEE*+EEidididEEidE*+EEidid27文法的二義性文法的二義性q 如果一個(gè)文法的句子存在兩棵分析樹，那么，該句子是二義性的。q 如果一個(gè)文法包含二義性的句子，則說這個(gè)文法是二義性文法；否則說該文法是無二義性文法。q 文法的二義性源于這樣的事實(shí)：在一個(gè)句型中，存在一個(gè)非終結(jié)符號(hào)A，對(duì)于它有兩條產(chǎn)生式可用于替換，但A的這些推導(dǎo)最終都產(chǎn)生相同的句型。28文

13、法的二義性文法的二義性q 二義性是文法的性質(zhì)。程序設(shè)計(jì)語言是無二義的。（自然語言本質(zhì)是二義的，在一定語境下沒有二義）q 文法的二義性的消除：改寫文法E E + E | E * E | (E ) | id改寫成E E + T | T （ T + T . . . + T ）T T * F | F（ F * F . . . * F ）F ( E ) | id294.2.6 驗(yàn)證文法產(chǎn)生的語言驗(yàn)證文法產(chǎn)生的語言例4.7 G : S (S) S | L(G) = 配對(duì)的括號(hào)串的集合要證明兩個(gè)問題：（1）推出的是配對(duì)括號(hào)串 （2）所有的配對(duì)括號(hào)串可由S推出按推導(dǎo)步數(shù)進(jìn)行歸納：推出的是配對(duì)括號(hào)串歸納基礎(chǔ)：

14、S 歸納假設(shè)：少于n步的推導(dǎo)都產(chǎn)生配對(duì)的括號(hào)串歸納步驟：n步的最左推導(dǎo)如下：S (S )S (x) S (x) y+30q 按串長進(jìn)行歸納：所有的配對(duì)括號(hào)串w可由S推出q 歸納基礎(chǔ)： S q 歸納假設(shè)：長度小于2n的都可以從S推導(dǎo)出來 q 歸納步驟：考慮長度為2n(n 1)的w = (x) yq 即令(x)：是w中的最短的、左括號(hào)個(gè)數(shù)和右括號(hào)個(gè)數(shù)相同的非空前綴qS (S )S (x) S (x) y() () () ()()()y(x)* 314.2.7 正規(guī)式和上下文無關(guān)文法正規(guī)式和上下文無關(guān)文法q 正規(guī)語言(RL)是上下文無關(guān)語言(CFL)的真子集，正規(guī)表達(dá)式所描述的語言可以用上下文無關(guān)文

15、法描述。q 將正規(guī)式轉(zhuǎn)換為NFA，再將NFA轉(zhuǎn)換為等價(jià)的CFG。RL: Regular LanguageCFL: Context Free LanguageCFG: Context Free Grammar32將正規(guī)表達(dá)式(a|b)*ab用CFG表示q 正規(guī)式正規(guī)式q (a|b)(a|b)* *ababq 文法文法q A0 A0 a A0 | b A0 | a A1 a A0 | b A0 | a A1q A1 A1 b A2 b A2q A2 A2 12starta0abbaabbab33ijaij 構(gòu)造規(guī)則構(gòu)造規(guī)則q 每個(gè)狀態(tài) i 有一個(gè)對(duì)應(yīng)的非終結(jié)符 Ai q If then Ai a

16、Ajq If then Ai Ajq 如果 i 是終結(jié)狀態(tài), Ai q 如果 i 是起始狀態(tài), Ai 是開始符號(hào)這些規(guī)則也可以把正規(guī)文法轉(zhuǎn)換為這些規(guī)則也可以把正規(guī)文法轉(zhuǎn)換為NFA。34正規(guī)文法正規(guī)文法q 若文法G = (VT, VN, S, P)中的每一個(gè)產(chǎn)生式形如： A aB 或 A aq其中A, BVN, aVT ，則稱G為右線性文法。q 若文法G=(VT, VN, S, P)中的每一個(gè)產(chǎn)生式形如： A Ba 或 A aq則稱G為左線性文法。q 右線性文法和左線性文法都稱為3型文法(正規(guī)文法)。q DFA是NFA的特例，但DFA的功能和NFA的功能一樣。q 也就是說，能被NFA表達(dá)的語言，

17、也可以用DFA表達(dá)。q 正規(guī)文法是上下文無關(guān)文法的特例，但是，正規(guī)文法的功能比上下文無關(guān)文法的功能弱。q 也就是說，有些語言能被上下文無關(guān)文法表達(dá)，但是不能被正規(guī)文法表達(dá)。3536q L3 =anbn | n 1 qS aSb | abq L3是不能用正規(guī)式描述的語言的一個(gè)范例是不能用正規(guī)式描述的語言的一個(gè)范例 q若存在接受若存在接受L3的的DFA D，狀態(tài)數(shù)為，狀態(tài)數(shù)為k個(gè)。個(gè)。q 設(shè)設(shè)D讀完讀完, a, aa, , ak 分別到達(dá)狀態(tài)分別到達(dá)狀態(tài)s0, s1, , skq至少有兩個(gè)狀態(tài)相同，例如是至少有兩個(gè)狀態(tài)相同，例如是si和和sj，即，即ji,且且si=sj，q則則ajbi屬于屬于L3

18、,然而然而jisifs0標(biāo)記為標(biāo)記為ai的路徑的路徑標(biāo)記為標(biāo)記為bi的路徑的路徑標(biāo)記為標(biāo)記為aj i的路的路徑徑a a a . . . a a b b b . . . b bs0 s1 s2 . . . sn-1 sn fkn假設(shè)輸入是假設(shè)輸入是aibi,那么必然有那么必然有si到到f的路徑來識(shí)別的路徑來識(shí)別bi。374.3 文法的編寫文法的編寫 q 文法的優(yōu)點(diǎn) q 文法給出了精確的，易于理解的語法說明q 自動(dòng)產(chǎn)生高效的分析器q 可以給語言定義出層次結(jié)構(gòu)q 以文法為基礎(chǔ)的語言的實(shí)現(xiàn)便于語言的修改q 文法的問題q 文法只能描述編程語言的大部分語法384.3.1 為什么要用正規(guī)式定義詞法為什么要用

19、正規(guī)式定義詞法?q 為什么不用CFG定義詞法 q 詞法規(guī)則非常簡單，不必用上下文無關(guān)文法。q 對(duì)于詞法記號(hào)，正規(guī)表達(dá)式描述簡潔且易于理解。q 從正規(guī)表達(dá)式構(gòu)造出的詞法分析器效率高。q 把詞法分析從語法分析中分離出來的理由 q 簡化設(shè)計(jì)q 編譯器的效率會(huì)改進(jìn)q 編譯器的可移植性加強(qiáng)q 便于編譯器前端的模塊劃分 394.3.2 消除二義性消除二義性stmt if expr then stmt | if expr then stmt else stmt | other 40Form 1:stmtstmtstmtexprE1S2thenelseifexprE2S1thenifstmtstmtexprE

20、1thenifstmtexprE2S2S1thenelseifstmtstmtForm 2:句型句型if E1 then if E2 then S1 else S2的分析的分析樹樹41 改寫為無二義的文法（else與最近的then匹配）stmt matched _stmt | unmatched_stmtmatched_stmtif expr then matched_stmt else matched_stmt | otherunmatched_stmt if expr then stmt | if expr then matched_stmt else unmatched_stmt424.

21、3.3 消除左遞歸消除左遞歸q 文法左遞歸A Aa q 直接左遞歸A Aa Aaaaaaaq | b q 串的特點(diǎn)ba . . . aq A Aa Aaa Aaaa Aaa baa q 消除直接左遞歸qA b Aq A a A | aaaaaaq A bA baA baaA baaA baa+43例: 算術(shù)表達(dá)文法E E + T | T E+ T . . . + T T T * F | F T* F . . . * F F ( E ) | id消除左遞歸后文法 E TE E +TE | + T . . . + T T FT T *FT | * F . . . * F F ( E ) | id4

22、4q 非直接左遞歸qS Aa | bq A Sd | q 先變換成直接左遞歸qS Aa | bqA Aad | bd | q 再消除左遞歸qS Aa | bqA bd A | A qA adA | 45間接左遞歸的消除B Saa A Bbb S Acc 將 B 代入，得到：A Sababb將 A 代入，得到：S Sabcabcbcc再消除直接左遞歸：S abcSbcScS S abcS46Algorithm4.1 消除左遞歸Input: 文法文法G with no cycles or -productionsOutput: 沒有左遞歸的等價(jià)文法沒有左遞歸的等價(jià)文法按照某個(gè)順序?qū)⒎墙K結(jié)符號(hào)排序?yàn)?/p>

23、按照某個(gè)順序?qū)⒎墙K結(jié)符號(hào)排序?yàn)?A1,A2,Anfor( i = 1; i=n; i+ ) for( j = 1; j=i 1; j+ ) 將每個(gè)形如將每個(gè)形如 Ai Aj的產(chǎn)生式替換為的產(chǎn)生式替換為 產(chǎn)生式組產(chǎn)生式組 Ai 1 | 2 | | k ; 其中其中Aj 1|2|k 是所有的是所有的 Aj 產(chǎn)生式產(chǎn)生式; 消除消除 Ai 產(chǎn)生式之間的立即左遞歸；產(chǎn)生式之間的立即左遞歸； 474.3.4 提左因子提左因子不確定選擇哪個(gè)規(guī)則來替換非終結(jié)符，例如： stmt if expr then stmt else stmt | if expr then stmt 改寫產(chǎn)生式。48改寫有左因子的文法q 對(duì)于所有形如 qA 1 | 2| | n | q 提左因子改寫為qA A| qA 1 | 2 | n 49懸空懸空else的文法的文法stmt if expr then stmt else stmt | if expr then stmt | other提取左因子，得到：stmt if expr then stmt optional_else_part | otheroptional_else_part else stmt | 504.3.5 非上下文無關(guān)的語言結(jié)構(gòu)非上下文無關(guān)的語言結(jié)構(gòu)q L1 = wcw | w屬于屬于(a | b)*q “檢查標(biāo)識(shí)符的