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

學(xué)習(xí)資料收集于網(wǎng)絡(luò)，僅供參考1、給出下面語言的相應(yīng)文法 。L1={anbnci|n≥1,i≥0}從n，i的不同取值來把 L1分成兩部分：前半部分是 anbn：A→aAb|ab后半部分是 ci：B→Bc|ε所以整個文法 G1[S]可以寫為：G1(S):S→AB ；A→aAb|ab ；B→cB|ε3、構(gòu)造一個DFA，它接受 ={a，b}上所有包含ab的字符串。（要求：先將正規(guī)式轉(zhuǎn)化為 NFA，再將NFA確定化，最小化）學(xué)習(xí)資料學(xué)習(xí)資料收集于網(wǎng)絡(luò)，僅供參考4、對下面的文法G:E→TE’ E’→+E|ε T→FT’ T’→T|εF→PF’ F’→*F’|ε P→(E)|a|b|∧1）證明這個文法是LL(1)的。2）構(gòu)造它的預(yù)測分析表。(1)FIRST(E)={(,a,b,^} FIRST(E')={+, ε}FIRST(T)={(,a,b,^} 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,^,+,),#}考慮下列產(chǎn)生式:EE|TT|F*F|P(E)|^|a|bFIRST(+E)∩FIRST(ε)={+}∩{ε}=φFIRST(+E)∩FOLLOW(E')={+}∩{#,)}=φFIRST(T)∩FIRST(ε)={(,a,b,^}∩{ε}=φFIRST(T)∩FOLLOW(T')={(,a,b,^}∩{+,),#}=φFIRST(*F')∩FIRST(ε)={*}∩{ε}=φFIRST(*F')∩FOLLOW(F')={*}∩{(,a,b,^,+,),#}=φFIRST((E))∩FIRST(a)∩FIRST(b)∩FIRST(^)=φ所以,該文法式 LL(1)文法.(3)+ * ( ) a b ^ #學(xué)習(xí)資料學(xué)習(xí)資料收集于網(wǎng)絡(luò)，僅供參考EETE'ETE'ETE'ETE'E'EEEETTFTTFTTFTTFTT'TTTTTTTTTTTFFPFFPFFPFFPFF'FF*FFFFFFFPP(E)PaPbP^5、考慮文法: S→AS|b A→SA|a（1）列出這個文法的所有 LR(0)項目。0.SS1.SS2.SAS3.SAS4.SAS5.Sb6.Sb7.ASA8.ASA9.ASA10.AaAa給出識別文法所有活前綴的DFA。1S A7 8 9S學(xué)習(xí)資料學(xué)習(xí)資料收集于網(wǎng)絡(luò)，僅供參考a010112 3 4A Sb65確定化：SAab{0,2,5,7,10}{1,2,5,7,8,10{2,3,5,7,10}{11}{6}}{1,2,5,7,8,10{2,5,7,8,10}{2,3,5,7,9,10}{11}{6}}{2,3,5,7,10}{2,4,5,7,8,10{2,3,5,7,10}{11}{6}}{2,5,7,8,10}{2,5,7,8,10}{2,3,5,7,9,10}{11}{6}{2,3,5,7,9,10{2,4,5,7,8,10{2,3,5,7,10}{11}{6}}}{2,4,5,7,8,10{2,5,7,8,10}{2,3,5,7,9,10}{11}{6}}學(xué)習(xí)資料學(xué)習(xí)資料收集于網(wǎng)絡(luò)，僅供參考{11} φ φ φ φ{(diào)6} φ φ φ φA3:S S

S5:ASA6:ASASASSASb

SA SAA a

AabSASSASASbAaASAS ASS bS a Aa0:SSSASAbS學(xué)習(xí)資料ASAAa

A aS b S A bA4:SAS7:SASSASASASbSASSASASbAaASA學(xué)習(xí)資料收集于網(wǎng)絡(luò)，僅供參考ba a b b a1:A a 2:S bDFA6、設(shè)有文法：P→P+Q|Q Q→Q*R|R R→(P)|i（1）證明Q*R+Q+Q是它的一個句型。（3分)P=>P+Q=>P+Q+Q=>Q+Q+Q=>Q*R+Q+Q（2）給出Q*R+Q+Q的所有短語，直接短語和句柄。 (4分)短語:Q*R,Q*R+Q,Q*R+Q+Q 直接短語:Q*R 句柄:Q*R3）給出句子ｉ+ｉ*ｉ的最右推導(dǎo)。(4分)4）給出句子ｉ+ｉ*ｉ的最左推導(dǎo)。(4分)7、設(shè)有文法：E→E+T|TT→T*F|FF→(E)|i（）證明E+T*F是它的一個句型。（3分)EETET*F1（2）給出E+T*F的所有短語，直接短語和句柄。(4分)短語:E+T*F,T*F,直接短語:T*F句柄:T*F（3）給出句子ｉ+ｉ*ｉ的最右推導(dǎo)。(4分)學(xué)習(xí)資料學(xué)習(xí)資料收集于網(wǎng)絡(luò)，僅供參考11、構(gòu)造下面正規(guī)式相應(yīng)的 DFA1(0|1)*10114、對下面的文法G:Expr→-Expr Expr→(Expr)|VarExprTail ExprTail→-Expr|εVar→idVarTail VarTail→(Expr)|ε（1）構(gòu)造LL(1)分析表。（12分）學(xué)習(xí)資料學(xué)習(xí)資料收集于網(wǎng)絡(luò)，僅供參考（2）給出對句子id—id((id))的分析過程。（8分）學(xué)習(xí)資料學(xué)習(xí)資料收集于網(wǎng)絡(luò)，僅供參考16、已知文法G[S]為：S->a|^|(T)T->T,S|S①消除文法G[S]中的左遞歸，得文法 G′[S]。G(S)S a|^|(T)T STT ,ST|②文法G′[S]是否為LL(1)的？若是，給出它的預(yù)測分析表。FIRST(S)={a,^,(} FIRST(T)={a,^,(} FIRST( T)={,, }FOLLOW(S)={),,,#} FOLLOW(T)={)} FOLLOW( T)={)}預(yù)測分析表a ^ ( ) , #S S a S ^ S (T)T T ST T ST T STT T T ,ST是LL(1)文法17、對下面的文法G:S S aT| aT | aT T aT | a消除該文法的左遞歸和提取左公因子；構(gòu)造各非終結(jié)符的FIRST和FOLLOW集合；學(xué)習(xí)資料學(xué)習(xí)資料收集于網(wǎng)絡(luò)，僅供參考18、文法G(S)及其LR分析表如下，請給出串 baba#的分析過程。(1)S→DbB (2)D→d (3)D→ε(4)B→a (5)B→Bba (6)B→εLR分析表學(xué)習(xí)資料學(xué)習(xí)資料收集于網(wǎng)絡(luò)，僅供參考2、寫出表達式a=b*c+b*d對應(yīng)的逆波蘭式、四元式序列和三元式序列。答：逆波蘭式： abc*bd*+:=四元式序列： 三元式序列:OPARG1ARG2(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)學(xué)習(xí)資料學(xué)習(xí)資料收集于網(wǎng)絡(luò)，僅供參考八、語義分析題1、將語句if ((A<0) (B>0)) then while (C>0) do C:=C-D翻譯成四元式答案：100(j<，A，0，104)101(j，-，-，102)102(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、寫出下面語句經(jīng)語法制導(dǎo)翻譯后所生成的四元式代碼序列。ifx<ythenwhilee>cdoc:=c+1elsex:=x+5學(xué)習(xí)資料學(xué)習(xí)資料收集于網(wǎng)絡(luò)，僅供參考答案：假設(shè)初始為 100，則四元式代碼序列為100ifx<102gotoy101goto107102ife>cgoto104103goto109104M:=C+1105C:=M106goto102107N:=X+5108X:=N1098、寫出表達式a+b*(c-d)對應(yīng)的逆波蘭式和三元式序列。答案：逆波蘭式：(abcd-*+)三元式序列:OPARG1ARG2(1)-cd(2)*b(1)(3)+a(2)學(xué)習(xí)資料學(xué)習(xí)資料收集于網(wǎng)絡(luò)，僅供參考1．編譯程序是對高級語言程序的解釋執(zhí)行。 (×)2．一個有限狀態(tài)自動機中，有且僅有一個唯一的終態(tài)。 (×)3．一個算符優(yōu)先文法可能不存在算符優(yōu)先函數(shù)與之對應(yīng)。 (√)4．語法分析時必須先消除文法中的左遞歸 。(×)5．LR分析法在自左至右掃描輸入串時就能發(fā)現(xiàn)錯誤，但不能準(zhǔn)確地指出出錯地點。 (√)6．逆波蘭表示法表示表達式時無須使用括號。 (√)7．靜態(tài)數(shù)組的存儲空間可以在編譯時確定。 (×)8．進行代碼優(yōu)化時應(yīng)著重考慮循環(huán)的代碼優(yōu)化，這對提高目標(biāo)代碼的效率將起更大作用。(×)9．兩個正規(guī)集相等的必要條件是他們對應(yīng)的正規(guī)式等價。 (×)10．一個語義子程序描述了一個文法所對應(yīng)的翻譯工作。 (×)1.一個上下文無關(guān)文法的開始符，可以是終結(jié)符或非終結(jié)符。(×)2.一個句型的直接短語是唯一的。（×）3.已經(jīng)證明文法的二義性是可判定的。（×）4.每個基本塊可用一個DAG表示。（√）5.每個過程的活動記錄的體積在編譯時可靜態(tài)確定。（√）6.2型文法一定是3型文法。（×）7.一個句型一定句子。(×)8.算符優(yōu)先分析法每次都是對句柄進行歸約。(×)9.采用三元式實現(xiàn)三地址代碼時，不利于對中間代碼進行優(yōu)化。（√）10.編譯過程中，語法分析器的任務(wù)是分析單詞是怎樣構(gòu)成的。(×)11.一個優(yōu)先表一定存在相應(yīng)的優(yōu)先函數(shù)。(√)12.目標(biāo)代碼生成時，應(yīng)考慮如何充分利用計算機的寄存器的問題。(√)13.遞歸下降分析法是一種自下而上分析法。(×)14.并不是每個文法都能改寫成LL(1)文法。(√)15.每個基本塊只有一個入口和一個出口。(√)16.一個LL(1)文法一定是無二義的。(√)17.逆波蘭法表示的表達試亦稱前綴式。(×)18.目標(biāo)代碼生成時，應(yīng)考慮如何充分利用計算機的寄存器的問題。(√)學(xué)習(xí)資料學(xué)習(xí)資料收集于網(wǎng)絡(luò)，僅供參考19.正規(guī)文法產(chǎn)生的語言都可以用上下文無關(guān)文法來描述。(√)20.一個優(yōu)先表一定存在相應(yīng)的優(yōu)先函數(shù)。(√)21.3型文法一定是2型文法。(√)22.如果一個文法存在某個句子對應(yīng)兩棵不同的語法樹，則文法是二義性的。(√)1、簡述編譯程序的工作過程：編譯程序的工作過程，是指從輸入源程序開始到輸出目標(biāo)程序為止的整個過程，是非常復(fù)雜的，就其過程而言，一般可以劃分為五個工作階段：①詞法分析，對構(gòu)成源程序的字符串進行掃描和分解，識別出一個個的單詞； ②語法分析，根據(jù)語言的語法規(guī)則，把單詞符號串分解成各類語法單位； ③語義分析與中間代碼產(chǎn)生， 即對各類語法單位，分析其漢一并進行初步翻譯；④代碼優(yōu)化，以期產(chǎn)生更高效的代碼；⑤目標(biāo)代碼生成，把中間代碼變換成特定機器上的低級語言指令形式。2．簡述代碼優(yōu)化的目的和意義： 代碼優(yōu)化是盡量生成 “好”的代碼的編譯階段。也就是要對程序代碼進行一種等價變換，在保證變換前后代碼執(zhí)行結(jié)果相同的前提下，盡量使目標(biāo)程序運行時所需要的時間短，同時所占用的存儲空間少。3、簡要說明語義分析的基本功能 ：確定類型、類型檢查、語義處理和某些靜態(tài)語義檢查。1．詞法分析：詞法分析的主要任務(wù)是從左向右掃描每行源程序的符號，按照詞法規(guī)則從構(gòu)成源程序的字符串中識別出一個個具有獨立意義的最小語法單位， 并轉(zhuǎn)換成統(tǒng)一的內(nèi)部表示(token)，送給語法分析程序。3．簡述自下而上的分析方法。： 所謂自下而上分析法就是從輸入串開始，逐步進行 “歸約”，直至歸約到文法的開始符號；或者說從語法樹的末端開始，步步向上 “歸約”，直到根節(jié)點。2．LL(1)文法：若文法的任何兩個產(chǎn)生式 A | 都滿足下面兩個條件： （1）FIRST( )FIRST( )= ；（2）若 * ，那么FIRST( ) FOLLOW( A)= 。我們把滿足這兩個條件的文法叫做 LL(1)文法，其中的第一個 L代表從左向右掃描輸入， 第二個L表示產(chǎn)生最左推導(dǎo)，1代表在決定分析器的每步動作時向前看一個輸入符號。除了沒有公共左因子外，LL(1)文法還有一些明顯的性質(zhì)，它不是二義的，也不含左遞歸。學(xué)習(xí)資料學(xué)習(xí)資料收集于網(wǎng)絡(luò)，僅供參考3．語法樹：句子的樹結(jié)構(gòu)表示法稱為語法樹(語法分析樹或語法推導(dǎo)樹)。給定文法G=(VN，VT，P，S)，對于G的任何句型都能構(gòu)造與之關(guān)聯(lián)的語法樹。這棵樹具有下列特征：(1)根節(jié)點的標(biāo)記是開始符號S。(2)每個節(jié)點的標(biāo)記都是V中的一個符號。(3)若一棵子樹的根節(jié)點為A，且其所有直接子孫的標(biāo)記從左向右的排列次序為A1A2?AR，那么AA1A2?AR一定是P中的一條產(chǎn)生式。(4)若一標(biāo)記為A的節(jié)點至少有一個除它以外的子孫，則AVN。(5)若樹的所有葉節(jié)點上的標(biāo)記從左到右排列為字符串w，則w是文法G的句型；若w中僅含終結(jié)符號，則w為文法G所產(chǎn)生的句子。4．LR(0)分析器：所謂LR(0)分析，是指從左至右掃描和自底向上的語法分析，且在分析的每一步，只須根據(jù)分析棧當(dāng)前已移進和歸約出的全部文法符號，并至多再向前查看0個輸入符號，就能確定相對于某一產(chǎn)生式左部符號的句柄是否已在分析棧的頂部形成，從而也就可以確定當(dāng)前所應(yīng)采取的分析動作(是移進還是按某一產(chǎn)生式進行歸約等)。5．語言和文法：文法就是語言結(jié)構(gòu)的定義和描述，是有窮非空的產(chǎn)生式集合。文法G定義為四元組的形式：G=(VN，VT，P，S)其中：VN是非空有窮集合，稱為非終結(jié)符號集合；VT是非空有窮集合，稱為終結(jié)符號集合；P是產(chǎn)生式的集合(非空)；S是開始符號(或識別符號)。這里，V∩V，SVN。V=VN∪V，稱為文法G的字母表，它是出現(xiàn)文法產(chǎn)生NT=T式中的一切符號的集合。文法G所描述的語言用L(G)表示，它由文法G所產(chǎn)生的全部句子組成，即L(G)={x|S*x，其中S為文法開始符號，且xVT}簡單的說，文法描述的語言是該文法一切句子的集合。2.二義性文法：如果一個文法存在某個句子對應(yīng)兩棵不同的語法樹，則稱這個文法是二義性文法。6.語法：一組規(guī)則，用它可形成和產(chǎn)生一組合式的程序。7.文法:描述語言的語法結(jié)構(gòu)的形式規(guī)則。12.規(guī)范句型------由規(guī)范推導(dǎo)所得到的句型。句柄：一個句型的最左直接短語。21.語義：定義程序的意義的一組規(guī)則。10.短語：令G是一個文法，S劃文法的開始符號，假定 αβδ是文法G的一個句型，如果有S αAδ且A β，則稱β是句型αβδ相對非終結(jié)符 A的短語。1．編譯程序和高級語言有什么區(qū)別 ?用匯編語言或高級語言編寫的程序，必須先送入計算機，經(jīng)過轉(zhuǎn)換成用機器語言表示的目標(biāo)程序（這個過程即編譯），才能由計算機執(zhí)行。執(zhí)行轉(zhuǎn)換過程的程序叫編譯程序。匯編程序是指沒有編譯過的匯編語言源文件。編譯程序轉(zhuǎn)換過的叫目標(biāo)程序，也就是機器語言。學(xué)習(xí)資料學(xué)習(xí)資料收集于網(wǎng)絡(luò)，僅供參考編譯程序的工作情況有三種：匯編型、解釋型和編譯型。匯編型編譯程序用來將匯編語言編寫的程序，按照一一對應(yīng)的關(guān)系，轉(zhuǎn)換成用機器語言表示的程序。解釋型編譯程序?qū)⒏呒壵Z言程序的一個語句， 先解釋成為一組機器語言的指令， 然后立即執(zhí)行，執(zhí)行完了，取下一組語句解釋和執(zhí)行，如此繼續(xù)到完成一個程序止。用解釋型編譯程序，執(zhí)行速度很慢，但可以進行人和計算機的"對話"，隨時可以修改高級語言的程序。BASIC語言就是解釋型高級語言。編譯型編譯程序?qū)⒓壵Z言編寫的程序，一次就會部翻譯成機器語言表示的程序，而且過程進行很快，在過程中，不能進行人機對話修改。 FORTRAN 語言就是編譯型高級語言。1．計算機執(zhí)行用高級語言編寫的程序主要有兩種途徑： ___解釋__和__編譯___。2．掃描器是__詞法分析器___，它接受輸入的__源程序___，對源程序進行___詞法分析__并識別出一個個單詞符號，其輸出結(jié)果是單詞符號，供語法分析器使用。3．自上而下分析法采用___移進__、歸約、錯誤處理、___接受__等四種操作。4．一個LR分析器包括兩部分：一個總控程序和___一張分析表__。5．后綴式abc-/所代表的表達式是___a/(b-c)__。6．局部優(yōu)化是在__基本塊___范圍內(nèi)進行的