編譯原理學(xué)習(xí)筆記

1、本份資料是03軟件學(xué)習(xí)委員按照老師上課復(fù)習(xí)的時(shí)候給我們講的一些考試重點(diǎn)考點(diǎn)，和我看書(shū)上網(wǎng)查資料等總結(jié)出來(lái)的一份復(fù)習(xí)筆記，一些是自己總結(jié)出來(lái)的方法，有一些考點(diǎn)這份筆記沒(méi)有覆蓋到，請(qǐng)大家補(bǔ)充.嚴(yán)重聲明：僅是個(gè)人的理解，如果有錯(cuò)請(qǐng)高手們指出，以免誤 人，謝謝如果大家有什么不明，可以共同探討 幾種文法的區(qū)分：文法分為四類(lèi)：（1）短語(yǔ)文法（0型文法）（2）上下文相關(guān)文法（1型文法）（3）上下文無(wú)關(guān)文法（2型文法）（4）正規(guī)（則）文法（3型文法）上面四種文法有包含的關(guān)系，1型文法是0型文法的一個(gè)子集，2型文法是1型 文法的一個(gè)子集，3型文法是2型文法的一個(gè)子集。一些判斷和排除的技巧：1 .正規(guī)文法右邊只有

2、一個(gè)非終止符，eg： S AB可排除此文法是正規(guī)文 法.2 .區(qū)分上下文相關(guān)文法和上下文無(wú)關(guān)文法的情況：看左端有幾個(gè)非終止符 如果不只一個(gè)，則該文法不是上下文無(wú)關(guān)文法.AB a可排除上下文相 關(guān)文法,Aa則可能是上下文無(wú)關(guān)文法.3 .對(duì)于Sa若其他推導(dǎo)式中S不出現(xiàn)在其他產(chǎn)生式的右邊，不影響正規(guī)文法要求,若出現(xiàn)在右邊，則是短語(yǔ)文法.eg: BcB則一定是短語(yǔ)文法.4 . A aB或者Aa則屬于右線性文法，A Ba或Aa屬于左線性文法.若一個(gè)文法有型如A aB又有A Ba的推導(dǎo)式，則排除該文法最多 是正規(guī)文法.給出文法用最左或最右推導(dǎo)句子建立推導(dǎo)樹(shù)例：已知文法G:E->E+T|E-T|TT-

3、>T*F|T/F|FF->(E)|i試給出下述表達(dá)式的推導(dǎo)及語(yǔ)法樹(shù)i; (2)i*i+i(3)i+i*i(4)i+(i+i)答案E=>T=>F=>i(2)E=>E+T=>T+T=>T*F+T=>F*F+T=>i*F+T=>i*i+T=>i*i+F=>i*i+i(3)E=>E+T=>T+T=>F+T=>i+T=>i+T*F=>i+F*F=>i+i*F=>i+i*i(4)E=>E+T=>T+T=>F+T=>i+T=>i+F=>i+(E)=

4、>i+(E+T)=>i+(T+T)=>i+(F+T) =>i+(i+T)=>i+(i+F)=>i+(i+i)給出語(yǔ)言 寫(xiě)出文法（題型可參照書(shū)本p39 2 -2）例：給出語(yǔ)言 anbncm | n>=1,m>=0的上下文無(wú)關(guān)文法。解：基本思路是這樣的：要求符合anbncm,因?yàn)閍與b要求個(gè)數(shù)相等，所以把它們應(yīng)看作一個(gè)整體 單元進(jìn)行，而cm做為另一個(gè)單位，初步產(chǎn)生式就應(yīng)寫(xiě)為 S->AB,其中A推出 anbn, B推出cmo因?yàn)閙可為0,故上式進(jìn)一步改寫(xiě)為S->AB|Ao接下來(lái)考慮 A,凡是要求兩個(gè)終結(jié)符個(gè)數(shù)相等的問(wèn)題，者B寫(xiě)為A->

5、aAb|ab形式，對(duì)于B就很 容易寫(xiě)成B->Bc|c 了。構(gòu)造上下文無(wú)關(guān)文法如下：S->AB|AA->aAb|abB->Bc|c證明文法的二義性（題型可參照書(shū)本p40 2-10，方法用老師給的方法）基本思路:找出一個(gè)句子，證明它可從兩種推導(dǎo)方式得到相同的推導(dǎo)結(jié)果即可 .例:證明下面文法具有二義性.S->aB|bAB->bS|aBB|bA->aS|bAA|a找出一句子aabbab有兩種不同的推導(dǎo)。S => aB=>aaBB=>aabB=>aabbS=>aabbaB=>aabbabS=>aB=>aaBB=&g

6、t;aabSB=>aabbAB=>aabbaB=>aabbab即它可以產(chǎn)生兩棵不同的語(yǔ)法樹(shù)，故它是二義的。關(guān)于NFA確定化和DFA的最小化詳見(jiàn)老師給出的習(xí)題答案.消除左遞規(guī)直接左遞規(guī)：左遞歸產(chǎn)生式AtAoHP,可以用非左遞歸的A 一 AA二 A | ；來(lái)代替，它們沒(méi)有改變從 A推導(dǎo)出的用集。eg： T t T * F | F 消除左遞規(guī)得：T t FT ' ; T 't * F T ' | 名例題可參照書(shū)本p109總結(jié):不管有多少A產(chǎn)生式，可以用下面的技術(shù)消除直接左遞歸。首先把 A產(chǎn)生 式組在一起：A T a 四 | Ac（2 | | Am | Pl

7、| % | | Pn其中Pi都不以A開(kāi)始，8都非空，然后用A Tp iA1 02 A' | | Pn AAJaiA'I a? A'| | am A Q代替A產(chǎn)生式。這些產(chǎn)生式和前面的產(chǎn)生式產(chǎn)生一樣的用集，但是不再有左遞歸。間接左遞規(guī)：書(shū)本用的是用矩陣的解法，可一次性消除文法左遞規(guī).具有一般性，也 可以用代入的方法，可避免求解矩陣，在有些時(shí)候這種方法較簡(jiǎn)便 （僅代表個(gè)人意見(jiàn)）.下面用代入的方法解書(shū)本p110例4.1S >Sa | Ab | a ; A，Sc將第二式代入第一式可得：SSa | Scb | a這樣就變成直接左遞規(guī) 了，便可用消除直接左遞規(guī)的方法解答.可得

8、：S > aSS'aS'| cbS'| ；再舉一例:Gs:(1)S tQc | c (2)Q->Rb | b (3)R t Sa | a 消除左遞規(guī) 把(2)右部代入(1)(4) S > Rbc | bc | c 把(3)右部代入(4) (5) S > Sabc | abc | bc | c 消除直接左遞歸 S)(abc | bc | c)S S r abcS' | ； 文法最終為：S)(abc|bc|c)SS' > abcS | ；LR(0),LR(1),SLR(1),LALR(1)四種文法：LR(0)文法項(xiàng)目集里不含移進(jìn)

9、 一歸約，歸約一歸約沖突.如:對(duì)于某項(xiàng)目為： (1). S s；S (2). S s 當(dāng)接受下一個(gè)符號(hào)時(shí)，分析器就不知道要進(jìn)行歸約 還是繼續(xù)移進(jìn)了，這樣產(chǎn)生了移進(jìn)一歸約沖突，如果存在沖突就不是LR(0)文法了,SLR比LR(0)高級(jí)，可以處理一些沖突.如上面的這個(gè)問(wèn)題，按照SLR(0)分 析,FOLLOW(S尸a,若FOLLOW(S) != ;就可解決沖突.又如對(duì)于某項(xiàng)目發(fā)生歸 約沖突 C a D a 如果FOLLOW(C) FOLLOW(D)交集不是空的,SLR(1)不 可以分析這樣的文法，這時(shí)用LR(1)就可以解決這樣的問(wèn)題了.LR(1)的效率較低,LALR是一種規(guī)模與SLR(1)差不多，

10、分析能力和LR(1)差不了多少的分析法. 證明給出的文法是某種文法而并不是另一種文法可以利用上述文法的區(qū)別證明.LL(1)文法分析：算出非終結(jié)符的follow集合.對(duì)于某表達(dá)式如S A求出FOLLOW(S)為伊, 則寫(xiě)成S A , # ,表示當(dāng)下一個(gè)字符是#時(shí)便可照S A進(jìn)行規(guī)約.其它的式子 照此求出，這些式子的求出是得出分析表的依據(jù).然后是寫(xiě)出拓展文法，確定項(xiàng)目集規(guī)范族及相應(yīng)的 DFA.對(duì)于某表達(dá)式：如S Aab,有S - Aab S A ab S Aa b S Aab ，以此 類(lèi)推對(duì)其他產(chǎn)生式有類(lèi)似的推導(dǎo).確定DFA時(shí)，形式與LL(0)相似，只是在式子的 后面加上式子左邊的非終結(jié)符的 FO

11、LLOW1即可.例：設(shè)文法G為S AABA |£BaB | b(1)證明它是LR(1)文法；(2)構(gòu)造它的LR(1)分析表；給出輸入符號(hào)用abab的分析過(guò)程 答案(1)拓廣文法G(0) S'S (1) SBA A £ (4) B aB (5) B bFIRST(A) = £ , a, b FIRST(B) = a, bFOLLOW(S) = # FOLLOW(A) = # FOLLOW(B)= a,b,#構(gòu)造的DFA如下:10：S7 +S. 4 S->& 9 A->»BA, « A->> , 1 B-&g

12、t; aB, a|b|f B->+ b, a|b|»S->A tb15：a|b|»13：AfB& t t5, # B+aB) a|b|t Bf* 比 a|b|4B16：*14:B->a* B3B->» aB, a|b|*a|b|«B17:BT曲由項(xiàng)目集規(guī)范族看出，不存在沖突動(dòng)作該文法是LR(1)文法。LR(1)分析表狀態(tài)ActionGotoaB#SAB0S4S5r31231acc2r13S4S5r36 1314S4S575r5r5r56r27r4r4r4輸入用abab的分析過(guò)程為:步驟狀態(tài)棧符號(hào)棧當(dāng)前字符剩余字符串動(dòng)作|0#abab#移進(jìn)(2)