編譯原理chpt4文法和語言

1、1第四章第四章 文法和語言文法和語言u(píng)本章內(nèi)容：本章內(nèi)容：文法和語言的形式定義文法和語言的形式定義 文法的類型文法的類型上下文無關(guān)文法及其語法樹上下文無關(guān)文法及其語法樹上下文無關(guān)文法的句型分析上下文無關(guān)文法的句型分析語法-一組規(guī)則-文法 語言語義靜態(tài)：類型匹配、作用域、動(dòng)態(tài)：功能對(duì)程序設(shè)計(jì)語言給出精確無二義的對(duì)程序設(shè)計(jì)語言給出精確無二義的語法描述（嚴(yán)謹(jǐn)、簡潔、易讀）語法描述（嚴(yán)謹(jǐn)、簡潔、易讀）2預(yù)備知識(shí)預(yù)備知識(shí) -語言概述語言概述z 任何一種語言都是由該語言的基本符號(hào)（字母表）組成的符號(hào)串（句子）的集合。z 漢語-所有符合漢語語法的句子的全體z 英語-所有符合英語語法的句子的全體z 程序設(shè)計(jì)語

2、言-所有該語言的程序的全體z 句子是無限的，但句子都是有結(jié)構(gòu)的，其構(gòu)成是有規(guī)律的（句型），可用規(guī)則嚴(yán)格定義-可用有限規(guī)則（文法），刻畫無限句子。例如： 我是學(xué)生、你學(xué)習(xí)英語、他喜歡運(yùn)動(dòng)、3z 語言具有兩個(gè)可識(shí)別的特性，即語言的形式和該形式相關(guān)聯(lián)的意義。z 如果不考慮語義，即只從語法這一側(cè)面來看語言，這種意義下的語言稱作形式語言。形式語言抽象地定義為一個(gè)數(shù)學(xué)系統(tǒng)?！靶问健笔侵高@樣的事實(shí)：語言的所有規(guī)則只以什么符號(hào)串能出現(xiàn)的方式來陳述。形式語言理論是對(duì)符號(hào)串集合的表示法、結(jié)構(gòu)及其特性的研究。是程序設(shè)計(jì)語言語法分析研究的基礎(chǔ)。4預(yù)備知識(shí) -有關(guān)定義和記號(hào)z符號(hào)：可以相互區(qū)別的記號(hào)（元素）。z字母表：

3、符號(hào)（元素）的非空有窮集合。z符號(hào)串：由字母表中的符號(hào)組成的任何有窮序列稱為該字母表上的符號(hào)串。特別空符號(hào)串。z符號(hào)串s的前綴、符號(hào)串s的后綴、符號(hào)串s的子串 對(duì)于每個(gè)符號(hào)串s，s和兩者都是符號(hào)串s的前綴，后綴和子串。 z符號(hào)串s的真前綴、真后綴、真子串x是s的前綴，后綴或子串，并且 s x5z 符號(hào)串的運(yùn)算y符號(hào)串s的長度|s|，的長度為0y連接：符號(hào)串x、y的連接,是把y的符號(hào)寫在x的符號(hào)之后得到的符號(hào)串xy，如x=ab,y=cd，則xy=abcd，特別a = a y方冪：符號(hào)串自身連接n次得到的符號(hào)串a(chǎn)n ：a1=a,a2=aa，a0=z 符號(hào)串集合：字母表上的z 兩個(gè)符號(hào)串集合A和B的

4、乘積定義為AB =xy|xA且yB 若集合A=ab,cde，B = 0,1，則 AB=ab1,ab0,cde0,cde1z *稱為的閉包，表示上的一切符號(hào)串(包括)組成的集合z 上的除外的所有符號(hào)串組成的集合+ ，稱為的正閉包。.2*.32*6z語言：字母表上的一個(gè)語言是上的一些符號(hào)串的集合 (上的每個(gè)語言是*的一個(gè)子集)。 例如：=a,b *=,a,b,aa,ab,ba,bb,aaa,aab, 集合ab,aabb,anbn,或w|w*且w=anbn,n1為字母表上的一個(gè)語言。 特別、 即 都是語言。 7語言語言上上的運(yùn)算的運(yùn)算若設(shè)L 和M是上的語言： z 語言L和M的并LM ，交，差，補(bǔ)是一

5、個(gè)語言z 語言L和M的連接是一個(gè)語言，記為 LM=st |sL且 tM有L = L=L。 L的n次連接Ln= LL.L z 語言L的 閉包記為 L*， L*= L0 L1 L2 . L0= ， Ln= L Ln-1= Ln-1 L,n1z 語言L的正 閉包記為 L+， L+= L1 L2 L3 . L+= LL*= L*L，L*= L+ 若L1=a,b, y,z， M1=1,28,9 ， 則L1(L1M1)*=所有字母打頭的字母和數(shù)字符號(hào)串81 1 文法和語言的形式定義文法和語言的形式定義如何來描述一種語言？如何來描述一種語言？有窮語言（只含有窮個(gè)句子），可以逐一列舉有窮語言（只含有窮個(gè)句子）

6、，可以逐一列舉無窮語言，找出語言的有窮表示。有兩個(gè)途經(jīng)：無窮語言，找出語言的有窮表示。有兩個(gè)途經(jīng)： 生成方式生成方式 （文法）：每個(gè)句子可用嚴(yán)格定義的規(guī)則來構(gòu)造（文法）：每個(gè)句子可用嚴(yán)格定義的規(guī)則來構(gòu)造 識(shí)別方式識(shí)別方式（自動(dòng)機(jī)）：用一個(gè)過程，當(dāng)輸入的串屬于語言時(shí)，（自動(dòng)機(jī)）：用一個(gè)過程，當(dāng)輸入的串屬于語言時(shí)，該過程經(jīng)有限次計(jì)算后就會(huì)停止并回答該過程經(jīng)有限次計(jì)算后就會(huì)停止并回答“是是”，否則，要，否則，要么能停止并回答么能停止并回答“不是不是”，要么永遠(yuǎn)繼續(xù)下去。，要么永遠(yuǎn)繼續(xù)下去。9文法定義定義文法G定義為四元組(VN，VT，P，S )，其中 VN:非終結(jié)符號(hào)(語法實(shí)體)集；VT:終結(jié)符號(hào)集

7、；P: 規(guī)則的集合 S VN ，稱作識(shí)別符號(hào)或開始符號(hào)。 VN，VT和P是非空有窮集且VN VT = V=VN VT ，稱為文法G的字母表或字匯表 規(guī)則（產(chǎn)生式規(guī)則（產(chǎn)生式或生成式）生成式）形如，其中V+， V*。例：文法例：文法G=（VN，VT，P，S）VN = S , VT = 0, 1 , P= S0S1, S01 例例: 文法文法G=（VN，VT，P，S）VN =標(biāo)識(shí)符，字母，數(shù)字標(biāo)識(shí)符，字母，數(shù)字VT =a,b,c,x,y,z,0,1,9P= | a|z z 00|9 9 S=習(xí)慣上，只將產(chǎn)生式寫出，第一條產(chǎn)生式的左部是開始符號(hào)；習(xí)慣上，只將產(chǎn)生式寫出，第一條產(chǎn)生式的左部是開始符號(hào)；

8、大寫字母表示非終結(jié)符，小寫字母表示終結(jié)符大寫字母表示非終結(jié)符，小寫字母表示終結(jié)符 GS:GS: Aab |aA Aab |aAb | | SaS SaSb|A注意到遞歸11推導(dǎo)、歸約的定義推導(dǎo)、歸約的定義直接推導(dǎo)直接推導(dǎo)“” 是文法是文法G G的產(chǎn)生式，若有的產(chǎn)生式，若有v,wv,w滿足：滿足：v=,w=,v=,w=, 其中其中VV* *,V,V* * 則稱則稱v v直接直接推導(dǎo)推導(dǎo)到到w w（w w直接直接歸約歸約到到v v）, ,記作記作 v v w w若存在若存在v =w0 w1 . wn=w (n0)， 則記為則記為v w，稱作，稱作v推導(dǎo)出推導(dǎo)出w，或，或w歸約到歸約到v 若有若有

9、v w或或 v=w， 則記為則記為v w例例G G：S0S1， S01 S 0S1 00S11000S11100001111 簡寫為S 00001111*12句型、句子的定義句型、句子的定義z 有文法有文法GS，若，若S x，則稱，則稱x是文法是文法G的句型。的句型。z 有文法有文法GS，若，若S x，且，且xVVT T* *，則稱，則稱x是文法是文法G的句子。的句子。例：例：GE E：EE+T|TEE+T|T TT TT* *F|FF|F F(E)|a F(E)|aE EE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*a G的句型E E，E+T，T+T，F(xiàn)+T，a

10、+T，a+T*F，a+F*F，a+a*F， a+a*a G的句子a+a*a *程序就是句子13語言的定義語言的定義L(G)=x | S x，其中S為文法的開始符號(hào)，且x VT* 例G：S0S1 | 01 L(G)=0n1n|n1例GS：（1）SaSBE | aBE （2）EBBE （3）aBab （4）bBbb （5）bEbe （6）eEee L（G）= anbnen | n1 G生成的每個(gè)串都在L(G)中，L(G)中的每個(gè)串確實(shí)能被G生成*S an-1S(BE)n-1 = an(BE)n = anB(EB)n-1E = anB(BE)n-1E = anB2(EB)n-2E2 anBnEn a

11、nbnEn anbnen*14z 已知語言描述，寫出文法 例：若語言由0、1符號(hào)串組成，串中0和1的個(gè)數(shù)相同，構(gòu)造其文法 A 0B | 1CB 1 | 1A | 0BBC 0 | 0A | 1CCz 已知文法，寫出語言描述例：GE：EE+T|T TT*F|F F(E)|az 若L(G1)=L(G2)，則稱文法G1和G2是等價(jià)的。 如G1A：A01|0E EA1與G2S：S0S1|01 等價(jià)152 2 文法及其語言的分類文法及其語言的分類通過對(duì)產(chǎn)生式通過對(duì)產(chǎn)生式施加不同的限制，施加不同的限制，Chomsky將文法分為四將文法分為四種類型，相應(yīng)產(chǎn)生四類語言：種類型，相應(yīng)產(chǎn)生四類語言：0型文法：對(duì)任

12、一產(chǎn)生式型文法：對(duì)任一產(chǎn)生式，都有，都有(V(VN NVVT T) )+ +且至少且至少含一個(gè)非終結(jié)符，含一個(gè)非終結(jié)符，(V(VN NVVT T) )* * -0型語言型語言1 1型文法：型文法：對(duì)任一產(chǎn)生式對(duì)任一產(chǎn)生式，都有，都有|， 僅僅僅僅 SS除外除外-上下文有關(guān)語言上下文有關(guān)語言2 2型文法：型文法：對(duì)任一產(chǎn)生式對(duì)任一產(chǎn)生式，都有，都有VVN N，(V(VN NVVT T) )* * 3 3型文法：型文法：任一產(chǎn)生式任一產(chǎn)生式的形式都為的形式都為AaBAaB或或AaAa， 其中其中AVAVN N ，BVBVN N ，aVaVT T * * -正則語言右線形應(yīng)注意到，上下文無關(guān)文法的定

13、義等價(jià)于應(yīng)注意到，上下文無關(guān)文法的定義等價(jià)于BNF表示法表示法16例：例：1 1型（上下文有關(guān)）文法型（上下文有關(guān)）文法 GSGS：SCDSCDAbbAAbbA CaCA|bCB CaCA|bCB BaaBBaaB ADaD ADaD BbbBBbbB BDbD BDbD CaCa AabD AabD DbDb例：例：2 2型（上下文無關(guān)）文法型（上下文無關(guān)）文法 GSGS：SABSAB ABS|0 ABS|0 BSA|1 BSA|1例：例：3 3型文法型文法 GS： S0A|1B|00A|1B|0 A0A|1B|0S0A|1B|0S B1B|1|01B|1|017文法的類型文法的類型2型文法

14、型文法1型文法型文法0型文法型文法四類四類文法文法之間之間的的逐級(jí)逐級(jí)“包含包含”關(guān)系關(guān)系3型文法型文法有不是上下文有關(guān)語言的0型語言，有不是上下文無關(guān)語言的1型語言，有不是正則語言的上下文無關(guān)語言。18文法和識(shí)別系統(tǒng)間的關(guān)系文法和識(shí)別系統(tǒng)間的關(guān)系0型文法（短語結(jié)構(gòu)文法）的描述能力相當(dāng)于圖靈機(jī)，可以表型文法（短語結(jié)構(gòu)文法）的描述能力相當(dāng)于圖靈機(jī)，可以表征任何遞歸可枚舉集，而且任何征任何遞歸可枚舉集，而且任何0型語言都是遞歸可枚舉的型語言都是遞歸可枚舉的任何能用圖靈機(jī)描述的計(jì)算都能機(jī)械實(shí)現(xiàn)，任何能在現(xiàn)代計(jì)任何能用圖靈機(jī)描述的計(jì)算都能機(jī)械實(shí)現(xiàn)，任何能在現(xiàn)代計(jì)算機(jī)上實(shí)現(xiàn)的計(jì)算都能用圖靈機(jī)描述算機(jī)上實(shí)

15、現(xiàn)的計(jì)算都能用圖靈機(jī)描述 帶帶 a0 a1 a2 a3 a4 a5 a6 a7 a8 an-1 an 有限控制器有限控制器磁頭磁頭四類文法對(duì)應(yīng)四種語言，每種語言被一種自動(dòng)機(jī)所識(shí)別。四類文法對(duì)應(yīng)四種語言，每種語言被一種自動(dòng)機(jī)所識(shí)別。191型文法（上下文有關(guān)文法）：產(chǎn)生式的形式為1A212，即只有A出現(xiàn)在1和2的上下文中時(shí)，才允許取代A。其識(shí)別系統(tǒng)是線性界限自動(dòng)機(jī)。 2型文法（上下文無關(guān)文法）：產(chǎn)生式的形式為A，取代A時(shí)與A的上下文無關(guān)。其識(shí)別系統(tǒng)是不確定的下推自動(dòng)機(jī)。3型文法（正規(guī)文法RG）：產(chǎn)生的語言是有窮自動(dòng)機(jī)（FA）所接受的集合定理定理 設(shè)設(shè)G=（VN，VT，P，S）是3 3型文法，則存在

16、一個(gè)有窮自型文法，則存在一個(gè)有窮自 動(dòng)機(jī)動(dòng)機(jī) M=(K, , f, A, Z)M=(K, , f, A, Z)，使得，使得L(M)=L(G)L(M)=L(G)；反之，；反之，已知一有窮自動(dòng)機(jī)M=(K, , f, A, Z),存在有一個(gè)3型文法G= （VN，VT，P，S）,使得L(G)=L(M)203 3型文法型文法和有窮自動(dòng)機(jī)（有窮自動(dòng)機(jī)（FAFA）G： SaA | bB AbB | aD | a BaA | bD | b DaD | bD | a | bBASaaabbba,bDZababDBASaaabba,bb先把D看成非終態(tài)21對(duì)上的正規(guī)式r ,存在一個(gè)RG=(VN,VT,P,S)：L

17、(G)=L(r)初始， VT= ，S VN ，生成正規(guī)產(chǎn)生式 Sr(R.1) 對(duì)形如 Ar1r2的正規(guī)產(chǎn)生式：Ar1B，Br2 (R.2)對(duì)形如Arr1的正規(guī)產(chǎn)生式：ArB | r1 ，BrB | r1 不斷應(yīng)用(R.x)做變換，直到每個(gè)產(chǎn)生式右端至多有一個(gè)VN例 r=a(ad)(1) Sa(ad)(2) SaA，A(ad)A(ad)B | B(ad)B | Gs: SaA A | aB | dB BaB | dB | VT=a,d VN=S,A,B 22對(duì)RG=(VN,VT,P,S),存在一個(gè) =VT上的正規(guī)式r：L(r)=L(G) AxB, By 形成正規(guī)式 A=xy AxAy 形成正規(guī)式

18、 A=xy Axy 形成正規(guī)式 A=xyGs: SaA | a AaAadAd A(ad)A(ad) A(ad)(ad) S=a(ad)(ad)a =a(ad)(ad)=a(ad) R=a(ad)233 3 上下文無關(guān)文法及其語法樹上下文無關(guān)文法及其語法樹上下文無關(guān)文法有足夠的能力描述程序設(shè)計(jì)語言的語法結(jié)構(gòu)上下文無關(guān)文法有足夠的能力描述程序設(shè)計(jì)語言的語法結(jié)構(gòu)GE： EE+T|T TT*F|F F(E)|a對(duì)a+a*a，觀察下列各種推導(dǎo)： EE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*aEE+T E+T*F E+T*a E+F*a E+a*a T+a*a F+a*

19、a a+a*aEE+T T+T T+T*F F+T*F F+F*F a+F*F a+F*a a+a*a24規(guī)范推導(dǎo)、規(guī)范句型規(guī)范推導(dǎo)、規(guī)范句型最左（最右）推導(dǎo)：在推導(dǎo)的任何一步，其中、是句型，都是對(duì)中的最左（右）非終結(jié)符進(jìn)行替換。最右推導(dǎo)被稱為規(guī)范推導(dǎo)。由規(guī)范推導(dǎo)所得的句型稱為規(guī)范句型語法樹語法樹-句型推導(dǎo)句型推導(dǎo)的的直觀表示直觀表示25語法樹語法樹-句型推導(dǎo)句型推導(dǎo)的的直觀表示直觀表示設(shè)G=( VN,VT,P,S)為一cfg，若一棵樹滿足下列4個(gè)條件，則此樹稱作G的語法樹(推導(dǎo)樹)(派生樹）：1. 每個(gè)結(jié)點(diǎn)都有一個(gè)標(biāo)記，此標(biāo)記是V的一個(gè)符號(hào)2. 根的標(biāo)記是S3. 若一結(jié)點(diǎn)n至少有一個(gè)它自己除

20、外的子孫，并且有標(biāo)記A，則肯定AVN4. 如果結(jié)點(diǎn)n有標(biāo)記A,其直接子孫結(jié)點(diǎn)從左到右的次序是n1，n2，nk，其標(biāo)記分別為A1，A2，Ak，那么AA1A2，Ak一定是P中的一個(gè)產(chǎn)生式26句型句型aabbaa的可能的可能推導(dǎo)推導(dǎo)序列和語法樹序列和語法樹 例例: GS:SaASASbAASSSaAba S a A S S b A a a b aSaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa給定文法G=(VN,VT,P,S)，對(duì)于G的任何句型都能構(gòu)造與之關(guān)聯(lián)的語法樹(推導(dǎo)樹)一棵語法樹表示了一個(gè)句

21、型的種種可能的(但未必是所有的)不同推導(dǎo)過程，包括最左(最右)推導(dǎo)。但是，一個(gè)句型是否只對(duì)應(yīng)唯一的一棵語法樹呢?一個(gè)句型是否只有唯一的一個(gè)最左(最右)推導(dǎo)呢?27例：例：G GE:E:E iE iE E+EE E+EE EE E* *E EE (E)E (E) E E E + E E + E E E * * E i E i i i i i E E E E * * E E i E + E i E + E i i i i句型句型 i*i+i 的兩個(gè)不同的最左推導(dǎo)：的兩個(gè)不同的最左推導(dǎo)：推導(dǎo)推導(dǎo)1：E E+E E*E+E i*E+E i*i+E i*i+i推導(dǎo)推導(dǎo)2：E E*E i*E i*E+E

22、i*i+E i*i+I -導(dǎo)致語義上的二義性導(dǎo)致語義上的二義性 若一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語法樹（或有兩若一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語法樹（或有兩個(gè)不同的最左（右）推導(dǎo)），則稱這個(gè)文法是個(gè)不同的最左（右）推導(dǎo)），則稱這個(gè)文法是二義二義的的很顯然，計(jì)算機(jī)很顯然，計(jì)算機(jī)不喜歡二義性不喜歡二義性。28文法二義性的解決辦法文法二義性的解決辦法句子或句型含義的二義性是由文法的二義性引起的。句子或句型含義的二義性是由文法的二義性引起的。G GE: E iE: E i E E+E E E+E E E E E* *E E E (E) E (E)解決二義性的兩種途徑某些二義文法可變換為無二義的

23、根據(jù)提出的條件直接修改編譯算法GEGE：E T|E+T E T|E+T T F|T T F|T* *F F F F （E E）|i|i直接修改編譯算法：規(guī)定算符優(yōu)先性和結(jié)合性規(guī)定算符優(yōu)先性和結(jié)合性1229但也有一些上下文無關(guān)語言，它的每一個(gè)文法都是二義的，則但也有一些上下文無關(guān)語言，它的每一個(gè)文法都是二義的，則說此語言是先天二義的。說此語言是先天二義的。判定任給的一個(gè)上下文無關(guān)文法是否二義，或它是否產(chǎn)生一個(gè)判定任給的一個(gè)上下文無關(guān)文法是否二義，或它是否產(chǎn)生一個(gè)先天二義的上下文無關(guān)語言，這兩個(gè)問題是遞歸不可解的。先天二義的上下文無關(guān)語言，這兩個(gè)問題是遞歸不可解的。在編譯實(shí)踐中形成了一些比較實(shí)用的

24、技術(shù)，可以為無二義性尋在編譯實(shí)踐中形成了一些比較實(shí)用的技術(shù)，可以為無二義性尋找一組充分條件，用于將二義性文法變換為無二義性文法。找一組充分條件，用于將二義性文法變換為無二義性文法。比如利用優(yōu)先級(jí)規(guī)則，左結(jié)合或右結(jié)合規(guī)則和最近嵌套規(guī)則比如利用優(yōu)先級(jí)規(guī)則，左結(jié)合或右結(jié)合規(guī)則和最近嵌套規(guī)則等。等。GSGS：S-S-if B then S | if B then S else S | Aif B then S | if B then S else S | AG GSS：S-S-C | UC | U C- C-if B then C else S | A if B then C else S | A U

25、- U-if B then Sif B then S就近匹配就近匹配304 4 句型的分析句型的分析句型分析就是識(shí)別一個(gè)符號(hào)串是否為某文法句型的過程。編譯程序中，完成句型分析的模塊稱為分析程序或識(shí)別程序。兩類分析方式： 自上而下分析法：從文法的開始符號(hào)出發(fā)，反復(fù)使用文法的產(chǎn)生式，尋找與輸入符號(hào)串匹配的推導(dǎo)，或者說，為輸入串尋找一個(gè)最左推導(dǎo)。自下而上分析法：從輸入串開始，進(jìn)行歸約，直至歸約到開始符號(hào) 不同分析方式反映了語法樹的的不同構(gòu)造過程反映了語法樹的的不同構(gòu)造過程31(1) S cAd (2) A ab (3) A a自上而下的語法分析自上而下的語法分析識(shí)別輸入串識(shí)別輸入串w=cad是否為該

26、文法的是否為該文法的句子句子若S cAd 后選擇(2)擴(kuò)展A，S cAd cabd那將會(huì)？w的第二個(gè)符號(hào)可以匹配，但第三個(gè)符號(hào)卻不能匹配？宣告分析失敗，顯然結(jié)論錯(cuò)誤結(jié)論錯(cuò)誤。 -錯(cuò)誤的選擇，導(dǎo)致分析的失?。∵@時(shí)應(yīng)該回朔回朔，把A為根的子樹剪掉，輸入a退還回去，再用產(chǎn)生式（3）試探自下而上的語法分析自下而上的語法分析識(shí)別輸入串識(shí)別輸入串w=cabd是否為該文法的是否為該文法的句子句子對(duì)串cabd的分析中，如果不選擇ab用產(chǎn)生式(2),而是選擇a用產(chǎn)生式(3)將a歸約到了A，那么在c A b d中無法找到一個(gè)可歸約串，最終就達(dá)不到歸約到S的結(jié)果32短語、直接短語、句柄短語、直接短語、句柄文法GS，

27、S A且A ，則稱是句型相對(duì)于非終結(jié)符A的短語。若有A 則稱是句型相對(duì)于規(guī)則A 的直接短語。一個(gè)句型的最左直接短語稱為該句型的句柄*GEGE：EE+T|TEE+T|T TT TT* *F|FF|F F(E)|i F(E)|i句型：句型：i i* *i+ii+i 短語： 直接短語： 句柄： E E T T F T F F i1 * i2 + i3 33歸約T intT + int | 移進(jìn)T + | int移進(jìn)int | * int + int移進(jìn)int * | int + int移進(jìn)|int * int + intE |歸約E T + ET + E |歸約E TT + T |移進(jìn)T | + i

28、nt歸約T int * Tint * T | + int歸約 T intint * int | + intETE+int*intTintT文法文法GE：E T + E | TT int * T | int | (E)34z 自下而上語法分析的策略：移進(jìn)-歸約分析；z 移進(jìn)就是將一個(gè)終結(jié)符推進(jìn)棧z 歸約就是將0個(gè)或多個(gè)符號(hào)從棧中彈出，根據(jù)產(chǎn)生式將一個(gè)非終結(jié)符壓入棧z 移進(jìn)-歸約過程是自頂向下最右推導(dǎo)的逆過程（規(guī)范歸約）z 我們?nèi)绾螞Q定什么時(shí)候移進(jìn)，什么時(shí)候歸約？我們?nèi)绾螞Q定什么時(shí)候移進(jìn)，什么時(shí)候歸約？y考慮考慮 int | * int + inty我們可以用我們可以用 T int進(jìn)行歸約，而得到

29、進(jìn)行歸約，而得到 T | * int + inty致命錯(cuò)誤致命錯(cuò)誤: 無法歸約到開始符號(hào)無法歸約到開始符號(hào) Ey直覺: Want to reduce only if the result can still be reduced to the start symbolz 一般的移進(jìn)一般的移進(jìn)-歸約策略：歸約策略：y若若句柄句柄在棧頂出現(xiàn)，則歸約在棧頂出現(xiàn)，則歸約y否則移進(jìn)否則移進(jìn)35文法文法GS：(1) S aAcBe(2) A b(3) A Ab(4) B da b b c de步驟步驟符號(hào)棧符號(hào)棧輸入符號(hào)串輸入符號(hào)串動(dòng)作動(dòng)作 1） # abbcde# 移進(jìn)移進(jìn) 2） #a bbcde# 移進(jìn)移進(jìn)A 3） #ab bcde# 歸約歸約(Ab) 4） #aA bcde# 移進(jìn)移進(jìn)A 5） #aAb cde# 歸約