第4章語法分析和程序

編譯原理第四章語法分析和語法分析程序本章內(nèi)容自頂向下分析和自底向上分析圍繞分析器的自動(dòng)生成展開難重點(diǎn)語法分析是編譯程序的核心部分。語法分析的作用是識(shí)別由詞法分析給出的單詞符號序列是否是給定文法的正確句子（程序）目前語法分析常用的方法有自頂向下（自上而下）分析和自底向上（自下而上）分析兩大類。自頂向下分析法：

從文法的開始符號出發(fā)，反復(fù)使用文法的產(chǎn)生式，尋找與輸入符號串匹配的推導(dǎo)。自底向上分析法：

從輸入符號串開始，逐步進(jìn)行歸約，直至歸約到文法的開始符號。自底向上的語法分析例：文法G：S→cAd

A→ab

A→a

識(shí)別輸入串w=cabd是否是該文法的句子

S A A cabd cabd cabd關(guān)?。壕浔拇_定自頂向下分析的語法分析例：文法 SaCb Ccd|c

為輸入串w=acb建立分析樹SSSaCbaaCCbbcdc試探的過程問題：會(huì)產(chǎn)生回溯–導(dǎo)致效率低自頂向下分析法的另一問題若有文法G6[S]:

(1)S→Sa

(2)S→b

推導(dǎo)baa#

問題：左遞歸—可能導(dǎo)致死循環(huán)SbSSaSSabSSaSaSSaSab自頂向下分析法需要解決的問題左遞歸對文法進(jìn)行改造回溯如何唯一地確定所采用的產(chǎn)生式？－LL(1)文法當(dāng)拒絕w時(shí),只能知道w不是句子,不知出何錯(cuò)及出在何處本節(jié)將主要介紹確定的自頂向下分析思想和對文法的要求。確定的自頂向下分析要求文法滿足LL(1)文法。

本節(jié)主要介紹內(nèi)容為：

LL(1)文法的定義和判別

非LL(1)文法的等價(jià)變換

確定的自頂向下分析方法

遞歸子程序法

預(yù)測分析方法4.1自頂向下的語法分析消除文法的左遞歸帶回溯的遞歸子程序回溯的消除及LL（1）文法4.1.1消除文法的左遞歸例：AA|A的解是：*引入新的非終結(jié)符A’,令其產(chǎn)生*,則有:AA’ A’A’|4.1.2帶回溯的遞歸子程序?qū)τ谖姆ǖ拿總€(gè)非終結(jié)符，根據(jù)其各候選式的結(jié)構(gòu),為其建立一個(gè)遞歸的子程序(函數(shù))，用于識(shí)別該非終結(jié)符所表示的語法范疇例如,產(chǎn)生式E’+TE’，相應(yīng)的子程序(函數(shù))為expr_prime(){ if(match(PLUS)){ advance(); term(); expr_prime(); } }4.1.3回溯的消除及LL（1）文法基本原理First集及Follow集的構(gòu)造分析器的構(gòu)造例：ETE’E’ATE’|ε TFT’T’MFT’|ε

F(E)|iA+|-M*|/(4.1)’對i+ii進(jìn)行預(yù)測分析的過程4.1.4某些非LL(1)文法的改造方法：消除左遞歸反復(fù)提取左因子例：EE+T|T T(E)|a(E)|a

經(jīng)改造后可得文法：

ETE’ E’+TE’| TaT’|(E) T’(E)|

這是一個(gè)LL(1)文法關(guān)于LL(1)的一些結(jié)論能由LL(1)文法產(chǎn)生的語言稱為LL(1)語言。它們已被證明具有許多重要特性，主要有：(1)任何LL(1)文法都是無二義性的；(2)左遞歸文法是非LL(1)的；(3)存在一種算法,它能判定任意文法是否為LL(1)的；(4)存在一種算法,它能判定任意兩個(gè)LL(1)文法是否等價(jià)；(5)CFL是否是LL(1)語言是不可判定的；(6)非LL(1)語言是存在的。若在分析過程中，每步向前掃描k個(gè)符號來確定選用的產(chǎn)生式，此分析方法稱為是LL(k)分析。此法極少用，故從略。習(xí)題判斷下列文法是否是LL(1)文法，如果是，請寫出LL(1)分析表；如果不是，請改造成LL(1)文法。SaFA|+aFAA+aFA|+B|F*aBBF|4.2自底向上的語法分析優(yōu)先分析法及LR分析法問題：如何確定句型的句柄如何正確地選擇產(chǎn)生式進(jìn)行歸約建立語法樹4.2.1優(yōu)先文法 簡介4.2.2LR分析法LR分析:自左至右掃描的自底向上的分析LR分析對文法要求很少,效率極高,且能及時(shí)發(fā)現(xiàn)錯(cuò)誤,是目前最廣泛使用的方法;一般用CFG描述的語言均可用LR分析法先介紹LR分析器的邏輯結(jié)構(gòu)及工作原理,再分別介紹幾種LR分析器(即LR(0),SLR(1)和LR(1))的構(gòu)造（一）LR分析器的邏輯結(jié)構(gòu)及工作原理LR分析器=輸入符號串+分析棧+總控程序+分析表例：文法G[L]:1.LE,L 2.LE 3.Ea 4.Eb分析表狀態(tài)ACTIONGOTOab，#LE0s3s4

121

acc

2

s5r2

3

r3r3

4

r4r4

5s3s4

626

r1

例：對符號串“a,b,a”的分析過程四個(gè)分析動(dòng)作：移進(jìn)、歸約、接受、報(bào)錯(cuò)對符號串“a,b,a”的分析過程步驟狀態(tài)棧中符號余留符號分析動(dòng)作下一狀態(tài)10#a,b,a#s33203#a,b,a#r3GOTO[0,E]=2302#E,b,a#s554025#E,b,a#s4450254#E,b,a#r4GOTO[5,E]=260252#E,E,a#s55702525#E,E,a#s338025253#E,E,a#r3GOTO[5,E]=29025252#E,E,E#r2GOTO[5,L]=610025256#E,E,L#r1GOTO[5,L]=6110256#E,L#r1GOTO[0,L]=11201#E#

（二）LR(0)分析表的構(gòu)造一些術(shù)語規(guī)范句型的活前綴將棧內(nèi)符號與未掃描的輸入串拼接起來,可得一規(guī)范句型.即棧內(nèi)符號串總是規(guī)范句型的前綴,且不含句柄右側(cè)的符號.把具有上述性質(zhì)的符號串稱為規(guī)范句型的活前綴LR(0)項(xiàng)目（看詳細(xì)內(nèi)容）LR(0)項(xiàng)目活前綴：包含全部句柄，則：進(jìn)行歸約:A,記為A;句柄中，則：應(yīng)移進(jìn)(句柄的后半部分),A12不含句柄，則：期望移進(jìn)一產(chǎn)生式的右部:A我們把右部添加了一個(gè)“”的產(chǎn)生式,稱為LR(0)項(xiàng)目LR(0)項(xiàng)目：歸約項(xiàng)目：A→接受項(xiàng)目：S’→S移進(jìn)項(xiàng)目：AX,(XVT,可以是空串)待約項(xiàng)目：AX,(XVN,可以是空串)識(shí)別所有規(guī)范句型全部活前綴的DFA例：文法G[S]：

S→A|BA→aAb|c,B→aBb|dLR(0)分析表的構(gòu)造I0:S’→·SS→·AS→·BA→·aAbA→·cB→·aBbB→·dI1:S’→S·SI2:S→A·AI3:S→B·BI4:A→a·AbA→·aAbA→·cB→a·BbB→·aBbB→·daI5:A→c·ccI6:A→d·ddaI7:A→aA·bI9:B→aB·bI8:A→aAb·I10:B→aBb·BAbb識(shí)別G[S]全部活前綴的DFAG[S]的LR(0)分析表

ACTIONGOTOabcd#SAB0s4

s5s6

1231

acc

2r1r1r1r1r1

3r2r2r2r2r2

4s4

s5s6

795r4r4r4r4r4

6r6r6r6r6r6

7

s8

8r3r3r3r3r3

9

s10

10r5r5r5r5r5

習(xí)題文法G[B]是否是LR(0)文法？如果是，請畫出LR(0)分析表；如果不是，請說明原理：B→bD;Se D→D;d|d S→s;S|sSLR(1)分析表的構(gòu)造習(xí)題文法G[S]是否是LR(0)文法？如果是，請畫出LR(0)分析表；如果不是，請說明原理：S→CbBAA→Aab|abB→C|DbC→aD→aLR(1)分析表的構(gòu)造I0:S’→·S,#S→·CbBA,#C→·a,bI1:S’→S·,#SI3:C→a·,baI2:S→C·bBA,#CI4:S→Cb·BA,#B→·C,aB→·Db,aC→·a,aD→·a,bbI5:S→CbB·A,#A→·Aab,#/aA→·ab,#/aI6:B→C·,aBCI8:C→a·,aD→a·,baI7:B→D·b,aI9:B→Db·,aDbI11:A→a·b,#/aI12:A→ab·,#/aabI10:S→CbBA·,#A→A·ab#/aAI13:A→Aa·b,#/aI14:A→Aab·,#/aab文法G[S]的LR(1)項(xiàng)目集及DFA分析表實(shí)例狀態(tài)ACTIONGOTOabcSABCD0s3

1

2

1

acc

2

s4

3