編譯原理復(fù)習(xí)整理(重點(diǎn)含答案)

1、1、給出下面語(yǔ)言的相應(yīng)文法 。 L1=anbnci|n1,i0從n，i的不同取值來(lái)把L1分成兩部分：前半部分是anbn：AaAb|ab后半部分是ci：BBc|所以整個(gè)文法G1S可以寫(xiě)為：G1(S):SAB ； AaAb|ab ；BcB|3、構(gòu)造一個(gè)DFA，它接受S=a，b上所有包含ab的字符串。（要求：先將正規(guī)式轉(zhuǎn)化為NFA，再將NFA確定化，最小化）4、對(duì)下面的文法G:ETE E+E| TFT TT|FPF F *F| P(E)|a|b|（1）證明這個(gè)文法是LL(1)的。（2）構(gòu)造它的預(yù)測(cè)分析表。(1)FIRST(E)=(,a,b,FIRST(E')=+,FIRST(T)=(,a,b

2、,FIRST(T')=(,a,b,FIRST(F)=(,a,b,FIRST(F')=*,FIRST(P)=(,a,b,FOLLOW(E)=#,)FOLLOW(E')=#,)FOLLOW(T)=+,),#FOLLOW(T')=+,),#FOLLOW(F)=(,a,b,+,),#FOLLOW(F')=(,a,b,+,),#FOLLOW(P)=*,(,a,b,+,),#(2)考慮下列產(chǎn)生式:FIRST(+E)FIRST()=+=FIRST(+E)FOLLOW(E')=+#,)=FIRST(T)FIRST()=(,a,b,=FIRST(T)FOLLOW(

3、T')=(,a,b,+,),#=FIRST(*F')FIRST()=*=FIRST(*F')FOLLOW(F')=*(,a,b,+,),#=FIRST(E)FIRST(a) FIRST(b) FIRST()=所以,該文法式LL(1)文法.(3)+*()ab#EE'TT'FF'P5、 考慮文法: SAS|b ASA|a（1）列出這個(gè)文法的所有LR(0) 項(xiàng)目。0. 1.2.3.4.5.6.7.8.9.10.11.(2)給出識(shí)別文法所有活前綴的DFA。1987 S A S 11100 a 432 A S 6 b 5確定化：SAab0,2,5,

4、7,101,2,5,7,8,102,3,5,7,101161,2,5,7,8,102,5,7,8,102,3,5,7,9,101162,3,5,7,102,4,5,7,8,102,3,5,7,101162,5,7,8,102,5,7,8,102,3,5,7,9,101162,3,5,7,9,102,4,5,7,8,102,3,5,7,101162,4,5,7,8,102,5,7,8,102,3,5,7,9,10116116 A S3:5:6: S A a b S a A S b S A b a A4:0:7: A S b a a b b a2:1: DFA6、設(shè)有文法：PP+Q|Q QQ*R|

5、R R(P)|i（1）證明Q*R+Q+Q是它的一個(gè)句型。（3分)P=>P+Q=>P+Q+Q=>Q+Q+Q=>Q*R+Q+Q（2） 給出Q*R+Q+Q的所有短語(yǔ)，直接短語(yǔ)和句柄。(4分)短語(yǔ): Q*R,Q*R+Q,Q*R+Q+Q 直接短語(yǔ): Q*R 句柄: Q*R（3）給出句子+*的最右推導(dǎo)。(4分)（4）給出句子+*的最左推導(dǎo)。(4分)7、設(shè)有文法：EE+T|T TT*F|F F(E)|i（1）證明E+T*F是它的一個(gè)句型。（3分)（2）給出E+T*F的所有短語(yǔ)，直接短語(yǔ)和句柄。(4分)短語(yǔ): E+T*F, T*F, 直接短語(yǔ): T*F 句柄: T*F（3） 給出句子+

6、*的最右推導(dǎo)。(4分)11、構(gòu)造下面正規(guī)式相應(yīng)的DFA1(0|1)*10114、對(duì)下面的文法G:Expr- Expr Expr(Expr)|Var ExprTail ExprTail- Expr|Varid VarTail VarTail(Expr) |（1） 構(gòu)造LL(1)分析表。（12分）（2） 給出對(duì)句子idid(id)的分析過(guò)程。（8分）16、已知文法GS 為： S->a|(T)T->T,S|S 消除文法GS中的左遞歸，得文法G´S。 文法G´S是否為L(zhǎng)L(1)的？若是，給出它的預(yù)測(cè)分析表。FIRST(S)=a,( FIRST(T)=a,( FIRST(

7、)=, FOLLOW(S)=),# FOLLOW(T)=) FOLLOW()=)預(yù)測(cè)分析表a(),#ST是LL(1)文法17、對(duì)下面的文法G:S ® S Ú a T | a T | Ú a T T ® Ù a T | Ù a(1) 消除該文法的左遞歸和提取左公因子；構(gòu)造各非終結(jié)符的FIRST和FOLLOW集合；18、文法G(S)及其LR分析表如下，請(qǐng)給出串baba#的分析過(guò)程。(1) S DbB(2) D d(3) D (4) B a(5) B Bba(6) B LR分析表2、寫(xiě)出表達(dá)式a=b*c+b*d對(duì)應(yīng)的逆波蘭式、四元式序列和三

8、元式序列。 答：逆波蘭式： abc*bd*+:= 四元式序列：三元式序列: OP ARG1 ARG2(1) (*， b， c， t1) (1) (* b， c )(2) (*， b， d， t2) (2) (* b， d )(3) (+， t1， t2，t3) (3) (+ (1)， (2)(4) (:=， t3， /， a)(4) (:= (3)， a)八、語(yǔ)義分析題1、將語(yǔ)句if (A<0) Ú (B>0) then while (C>0) do C:=C-D翻譯成四元式答案：100 (j<， A， 0， 104)101 (j， -， -， 102)102

9、 (j>， B， 0， 104)103 (j， -， -， 109)104 (j>， C， 0， 106)105 (j， -， -， 109)106 (-， C， D， T1)107 (:=， T1， -， C)108 (j， -， -， 104)1092、寫(xiě)出下面語(yǔ)句經(jīng)語(yǔ)法制導(dǎo)翻譯后所生成的四元式代碼序列。 if x<y then while e>c do c:=c+1 else x:=x+5答案：假設(shè)初始為100，則四元式代碼序列為 100ifx<ygoto102101goto107102ife>cgoto104103goto109104M:=C+110

10、5C:=M106goto102107N:=X+5108X:=N1098、寫(xiě)出表達(dá)式a+b*(c-d)對(duì)應(yīng)的逆波蘭式和三元式序列。答案：逆波蘭式：(abcd-*+) 三元式序列: OP ARG1 ARG2 (1) - c d (2) * b (1) (3) + a (2) 1編譯程序是對(duì)高級(jí)語(yǔ)言程序的解釋執(zhí)行。(× )2一個(gè)有限狀態(tài)自動(dòng)機(jī)中，有且僅有一個(gè)唯一的終態(tài)。(×)3一個(gè)算符優(yōu)先文法可能不存在算符優(yōu)先函數(shù)與之對(duì)應(yīng)。 ( )4語(yǔ)法分析時(shí)必須先消除文法中的左遞歸 。 (×)5LR分析法在自左至右掃描輸入串時(shí)就能發(fā)現(xiàn)錯(cuò)誤，但不能準(zhǔn)確地指出出錯(cuò)地點(diǎn)。 ()6逆波蘭表示

11、法表示表達(dá)式時(shí)無(wú)須使用括號(hào)。 ( )7靜態(tài)數(shù)組的存儲(chǔ)空間可以在編譯時(shí)確定。 (×)8進(jìn)行代碼優(yōu)化時(shí)應(yīng)著重考慮循環(huán)的代碼優(yōu)化，這對(duì)提高目標(biāo)代碼的效率將起更大作用。 (×)9兩個(gè)正規(guī)集相等的必要條件是他們對(duì)應(yīng)的正規(guī)式等價(jià)。 (× )10一個(gè)語(yǔ)義子程序描述了一個(gè)文法所對(duì)應(yīng)的翻譯工作。 (×)1.一個(gè)上下文無(wú)關(guān)文法的開(kāi)始符，可以是終結(jié)符或非終結(jié)符。 ( × )2.一個(gè)句型的直接短語(yǔ)是唯一的。 （× ）3.已經(jīng)證明文法的二義性是可判定的。 （ × ）4.每個(gè)基本塊可用一個(gè)DAG表示。 （ ）5.每個(gè)過(guò)程的活動(dòng)記錄的體積在編譯時(shí)可靜態(tài)確

12、定。 （ ）6.2型文法一定是3型文法。 （ × ）7.一個(gè)句型一定句子。 ( × )8.算符優(yōu)先分析法每次都是對(duì)句柄進(jìn)行歸約。 ( × )9.采用三元式實(shí)現(xiàn)三地址代碼時(shí)，不利于對(duì)中間代碼進(jìn)行優(yōu)化。 （ ）10.編譯過(guò)程中，語(yǔ)法分析器的任務(wù)是分析單詞是怎樣構(gòu)成的。 ( × )11.一個(gè)優(yōu)先表一定存在相應(yīng)的優(yōu)先函數(shù)。 ( )12.目標(biāo)代碼生成時(shí)，應(yīng)考慮如何充分利用計(jì)算機(jī)的寄存器的問(wèn)題。 ( )13.遞歸下降分析法是一種自下而上分析法。 ( × )14.并不是每個(gè)文法都能改寫(xiě)成LL(1)文法。 ( )15.每個(gè)基本塊只有一個(gè)入口和一個(gè)出口。 ( )

13、16.一個(gè)LL(1)文法一定是無(wú)二義的。 ( )17.逆波蘭法表示的表達(dá)試亦稱前綴式。 ( × )18.目標(biāo)代碼生成時(shí)，應(yīng)考慮如何充分利用計(jì)算機(jī)的寄存器的問(wèn)題。 ( )19.正規(guī)文法產(chǎn)生的語(yǔ)言都可以用上下文無(wú)關(guān)文法來(lái)描述。 ( )20.一個(gè)優(yōu)先表一定存在相應(yīng)的優(yōu)先函數(shù)。 ( )21.3型文法一定是2型文法。 ( )22. 如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù)，則文法是二義性的。 ( )1、簡(jiǎn)述編譯程序的工作過(guò)程：編譯程序的工作過(guò)程，是指從輸入源程序開(kāi)始到輸出目標(biāo)程序?yàn)橹沟恼麄€(gè)過(guò)程，是非常復(fù)雜的，就其過(guò)程而言，一般可以劃分為五個(gè)工作階段：詞法分析，對(duì)構(gòu)成源程序的字符串進(jìn)行掃描和

14、分解，識(shí)別出一個(gè)個(gè)的單詞；語(yǔ)法分析，根據(jù)語(yǔ)言的語(yǔ)法規(guī)則，把單詞符號(hào)串分解成各類語(yǔ)法單位；語(yǔ)義分析與中間代碼產(chǎn)生，即對(duì)各類語(yǔ)法單位，分析其漢一并進(jìn)行初步翻譯；代碼優(yōu)化，以期產(chǎn)生更高效的代碼；目標(biāo)代碼生成，把中間代碼變換成特定機(jī)器上的低級(jí)語(yǔ)言指令形式。2簡(jiǎn)述代碼優(yōu)化的目的和意義：代碼優(yōu)化是盡量生成“好”的代碼的編譯階段。也就是要對(duì)程序代碼進(jìn)行一種等價(jià)變換，在保證變換前后代碼執(zhí)行結(jié)果相同的前提下，盡量使目標(biāo)程序運(yùn)行時(shí)所需要的時(shí)間短，同時(shí)所占用的存儲(chǔ)空間少。3、 簡(jiǎn)要說(shuō)明語(yǔ)義分析的基本功能：確定類型、類型檢查、語(yǔ)義處理和某些靜態(tài)語(yǔ)義檢查。1 詞法分析：詞法分析的主要任務(wù)是從左向右掃描每行源程序的符號(hào)，

15、按照詞法規(guī)則從構(gòu)成源程序的字符串中識(shí)別出一個(gè)個(gè)具有獨(dú)立意義的最小語(yǔ)法單位，并轉(zhuǎn)換成統(tǒng)一的內(nèi)部表示(token)，送給語(yǔ)法分析程序。3簡(jiǎn)述自下而上的分析方法。：所謂自下而上分析法就是從輸入串開(kāi)始，逐步進(jìn)行“歸約”，直至歸約到文法的開(kāi)始符號(hào)；或者說(shuō)從語(yǔ)法樹(shù)的末端開(kāi)始，步步向上“歸約”，直到根節(jié)點(diǎn)。2LL(1)文法：若文法的任何兩個(gè)產(chǎn)生式A ® a | b都滿足下面兩個(gè)條件：（1）FIRST(a ) Ç FIRST(b ) = f；（2）若b Þ* e ，那么FIRST(a ) Ç FOLLOW( A ) = f。我們把滿足這兩個(gè)條件的文法叫做LL(1)文法，

16、其中的第一個(gè)L代表從左向右掃描輸入，第二個(gè)L表示產(chǎn)生最左推導(dǎo)，1代表在決定分析器的每步動(dòng)作時(shí)向前看一個(gè)輸入符號(hào)。除了沒(méi)有公共左因子外，LL(1)文法還有一些明顯的性質(zhì)，它不是二義的，也不含左遞歸。3語(yǔ)法樹(shù)：句子的樹(shù)結(jié)構(gòu)表示法稱為語(yǔ)法樹(shù)(語(yǔ)法分析樹(shù)或語(yǔ)法推導(dǎo)樹(shù))。給定文法G=(VN，VT，P，S)，對(duì)于G的任何句型都能構(gòu)造與之關(guān)聯(lián)的語(yǔ)法樹(shù)。這棵樹(shù)具有下列特征：(1)根節(jié)點(diǎn)的標(biāo)記是開(kāi)始符號(hào)S。(2)每個(gè)節(jié)點(diǎn)的標(biāo)記都是V中的一個(gè)符號(hào)。(3)若一棵子樹(shù)的根節(jié)點(diǎn)為A，且其所有直接子孫的標(biāo)記從左向右的排列次序?yàn)锳1A2AR，那么A®A1A2AR一定是P中的一條產(chǎn)生式。(4)若一標(biāo)記為A的節(jié)點(diǎn)至少

17、有一個(gè)除它以外的子孫，則AVN。(5)若樹(shù)的所有葉節(jié)點(diǎn)上的標(biāo)記從左到右排列為字符串w，則w是文法G的句型；若w中僅含終結(jié)符號(hào)，則w為文法G所產(chǎn)生的句子。4LR(0)分析器：所謂LR(0)分析，是指從左至右掃描和自底向上的語(yǔ)法分析，且在分析的每一步，只須根據(jù)分析棧當(dāng)前已移進(jìn)和歸約出的全部文法符號(hào)，并至多再向前查看0個(gè)輸入符號(hào)，就能確定相對(duì)于某一產(chǎn)生式左部符號(hào)的句柄是否已在分析棧的頂部形成，從而也就可以確定當(dāng)前所應(yīng)采取的分析動(dòng)作 (是移進(jìn)還是按某一產(chǎn)生式進(jìn)行歸約等)。5語(yǔ)言和文法：文法就是語(yǔ)言結(jié)構(gòu)的定義和描述，是有窮非空的產(chǎn)生式集合。文法G定義為四元組的形式：G=(VN，VT，P，S)其中：VN

18、是非空有窮集合，稱為非終結(jié)符號(hào)集合；VT 是非空有窮集合，稱為終結(jié)符號(hào)集合；P是產(chǎn)生式的集合(非空)；S是開(kāi)始符號(hào)(或識(shí)別符號(hào))。這里，VNVT=Æ，SVN。V=VNVT，稱為文法G的字母表，它是出現(xiàn)文法產(chǎn)生式中的一切符號(hào)的集合。文法G所描述的語(yǔ)言用L(G)表示，它由文法G所產(chǎn)生的全部句子組成，即L(G)=x| SÞ*x，其中S為文法開(kāi)始符號(hào)，且 簡(jiǎn)單的說(shuō)，文法描述的語(yǔ)言是該文法一切句子的集合。2.二義性文法：如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù)，則稱這個(gè)文法是二義性文法。6.語(yǔ)法：一組規(guī)則，用它可形成和產(chǎn)生一組合式的程序。7.文法:描述語(yǔ)言的語(yǔ)法結(jié)構(gòu)的形式規(guī)則。1

19、2.規(guī)范句型-由規(guī)范推導(dǎo)所得到的句型。15.句柄：一個(gè)句型的最左直接短語(yǔ)。21.語(yǔ)義：定義程序的意義的一組規(guī)則。10.短語(yǔ)：令G是一個(gè)文法，S劃文法的開(kāi)始符號(hào)，假定是文法G的一個(gè)句型，如果有SA且A，則稱是句型相對(duì)非終結(jié)符A的短語(yǔ)。1編譯程序和高級(jí)語(yǔ)言有什么區(qū)別? 用匯編語(yǔ)言或高級(jí)語(yǔ)言編寫(xiě)的程序，必須先送入計(jì)算機(jī)，經(jīng)過(guò)轉(zhuǎn)換成用機(jī)器語(yǔ)言表示的目標(biāo)程序（這個(gè)過(guò)程即編譯），才能由計(jì)算機(jī)執(zhí)行。執(zhí)行轉(zhuǎn)換過(guò)程的程序叫編譯程序。匯編程序是指沒(méi)有編譯過(guò)的匯編語(yǔ)言源文件。編譯程序轉(zhuǎn)換過(guò)的叫目標(biāo)程序，也就是機(jī)器語(yǔ)言。 編譯程序的工作情況有三種：匯編型、解釋型和編譯型。匯編型編譯程序用來(lái)將匯編語(yǔ)言編寫(xiě)的程序，按照一

20、一對(duì)應(yīng)的關(guān)系，轉(zhuǎn)換成用機(jī)器語(yǔ)言表示的程序。解釋型編譯程序?qū)⒏呒?jí)語(yǔ)言程序的一個(gè)語(yǔ)句，先解釋成為一組機(jī)器語(yǔ)言的指令，然后立即執(zhí)行，執(zhí)行完了，取下一組語(yǔ)句解釋和執(zhí)行，如此繼續(xù)到完成一個(gè)程序止。用解釋型編譯程序，執(zhí)行速度很慢，但可以進(jìn)行人和計(jì)算機(jī)的"對(duì)話"，隨時(shí)可以修改高級(jí)語(yǔ)言的程序。BASIC語(yǔ)言就是解釋型高級(jí)語(yǔ)言。編譯型編譯程序?qū)⒓?jí)語(yǔ)言編寫(xiě)的程序，一次就會(huì)部翻譯成機(jī)器語(yǔ)言表示的程序，而且過(guò)程進(jìn)行很快，在過(guò)程中，不能進(jìn)行人機(jī)對(duì)話修改。FORTRAN語(yǔ)言就是編譯型高級(jí)語(yǔ)言。1計(jì)算機(jī)執(zhí)行用高級(jí)語(yǔ)言編寫(xiě)的程序主要有兩種途徑：_解釋_和_編譯_。 2掃描器是_詞法分析器_，它接受輸入的_源程序_，對(duì)源程序進(jìn)行_詞法分析_并識(shí)別出一個(gè)個(gè)單詞符號(hào)，其輸出結(jié)果是單詞符號(hào)，供語(yǔ)法分析器使用。3自上而下分析法采用_移進(jìn)_、歸約、錯(cuò)誤處理、_接受_等四種操作。4一個(gè)LR分析器包括兩部分：一個(gè)總控程序和_一張分析表_。5后綴式