編譯原理復習整理(重點含答案).doc

學習資料收集于網(wǎng)絡(luò)，僅供參考1、給出下面語言的相應文法 。 L1=anbnci|n1,i0從n，i的不同取值來把L1分成兩部分：前半部分是anbn：AaAb|ab后半部分是ci：BBc|所以整個文法G1S可以寫為：G1(S):SAB ； AaAb|ab ；BcB|3、構(gòu)造一個DFA，它接受S=a，b上所有包含ab的字符串。（要求：先將正規(guī)式轉(zhuǎn)化為NFA，再將NFA確定化，最小化）4、對下面的文法G:ETE E+E| TFT TT|FPF F *F| P(E)|a|b|（1）證明這個文法是LL(1)的。（2）構(gòu)造它的預測分析表。(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,+,),#(2)考慮下列產(chǎn)生式:FIRST(+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)+*()ab#EETTFFP5、 考慮文法: SAS|b ASA|a（1）列出這個文法的所有LR(0) 項目。0. 1.2.3.4.5.6.7.8.9.10.11.(2)給出識別文法所有活前綴的DFA。1987 S A S 11100 a 432 A S 6 b 5確定化：SAab0,2,5,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|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*R（3）給出句子+*的最右推導。(4分)（4）給出句子+*的最左推導。(4分)7、設(shè)有文法：EE+T|T TT*F|F F(E)|i（1）證明E+T*F是它的一個句型。（3分)（2）給出E+T*F的所有短語，直接短語和句柄。(4分)短語: E+T*F, T*F, 直接短語: T*F 句柄: T*F（3） 給出句子+*的最右推導。(4分)11、構(gòu)造下面正規(guī)式相應的DFA1(0|1)*10114、對下面的文法G:Expr- Expr Expr(Expr)|Var ExprTail ExprTail- Expr|Varid VarTail VarTail(Expr) |（1） 構(gòu)造LL(1)分析表。（12分）（2） 給出對句子idid(id)的分析過程。（8分）16、已知文法GS 為： S-a|(T)T-T,S|S 消除文法GS中的左遞歸，得文法GS。 文法GS是否為LL(1)的？若是，給出它的預測分析表。FIRST(S)=a,( FIRST(T)=a,( FIRST()=, FOLLOW(S)=),# FOLLOW(T)=) FOLLOW()=)預測分析表a(),#ST是LL(1)文法（15）（地球爺爺）的手就是（地心）引力。17、對下面的文法G:S S a T | a T | a T T a T | a(1) 消除該文法的左遞歸和提取左公因子；構(gòu)造各非終結(jié)符的FIRST和FOLLOW集合；雪（雪白）（雪花）（白雪）（下雪）（雪人）課件|教案|試卷|無需注冊臭（香） 丑（美） （東）（西） （合）（分）干（干凈）吃（吃草）辦（辦法）跳（跳高）隊（大隊）像（好像）我（我的）座（座位）18、文法G(S)及其LR分析表如下，請給出串baba#的分析過程。一座菜園 一塊點心 一只耳朵 一雙耳朵 一件衣服(1) S DbB(2) D d(3) D 2、近義詞(4) B a(5) B Bba(6) B LR分析表二、 字2、寫出表達式a=b*c+b*d對應的逆波蘭式、四元式序列和三元式序列。 答：逆波蘭式： abc*bd*+:= 四元式序列：三元式序列: OP ARG1 ARG2（男）（女） 濕（干） 紅（綠）(1) (*， b， c， t1) (1) (* b， c )(2) (*， b， d， t2) (2) (* b， d )3、日 木 女 王 日 口 4、音 門 日 禾 女 山(3) (+， t1， t2，t3) (3) (+ (1)， (2)(4) (:=， t3， /， a)(4) (:= (3)， a)八、語義分析題1、將語句if (A0) then while (C0) do C:=C-D翻譯成四元式答案：100 (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)語法制導翻譯后所生成的四元式代碼序列。 if xc do c:=c+1 else x:=x+5答案：假設(shè)初始為100，則四元式代碼序列為 100ifxcgoto104103goto109104M:=C+1105C:=M106goto102107N:=X+5108X:=N1098、寫出表達式a+b*(c-d)對應的逆波蘭式和三元式序列。答案：逆波蘭式：(abcd-*+) 三元式序列: OP ARG1 ARG2 (1) - c d (2) * b (1) (3) + a (2) 1編譯程序是對高級語言程序的解釋執(zhí)行。( )2一個有限狀態(tài)自動機中，有且僅有一個唯一的終態(tài)。()3一個算符優(yōu)先文法可能不存在算符優(yōu)先函數(shù)與之對應。 ( )4語法分析時必須先消除文法中的左遞歸 。 ()5LR分析法在自左至右掃描輸入串時就能發(fā)現(xiàn)錯誤，但不能準確地指出出錯地點。 ()6逆波蘭表示法表示表達式時無須使用括號。 ( )7靜態(tài)數(shù)組的存儲空間可以在編譯時確定。 ()8進行代碼優(yōu)化時應著重考慮循環(huán)的代碼優(yōu)化，這對提高目標代碼的效率將起更大作用。 ()9兩個正規(guī)集相等的必要條件是他們對應的正規(guī)式等價。 ( )10一個語義子程序描述了一個文法所對應的翻譯工作。 ()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ōu)先函數(shù)。 ( )12.目標代碼生成時，應考慮如何充分利用計算機的寄存器的問題。 ( )13.遞歸下降分析法是一種自下而上分析法。 ( )14.并不是每個文法都能改寫成LL(1)文法。 ( )15.每個基本塊只有一個入口和一個出口。 ( )16.一個LL(1)文法一定是無二義的。 ( )17.逆波蘭法表示的表達試亦稱前綴式。 ( )18.目標代碼生成時，應考慮如何充分利用計算機的寄存器的問題。 ( )19.正規(guī)文法產(chǎn)生的語言都可以用上下文無關(guān)文法來描述。 ( )20.一個優(yōu)先表一定存在相應的優(yōu)先函數(shù)。 ( )21.3型文法一定是2型文法。 ( )22. 如果一個文法存在某個句子對應兩棵不同的語法樹，則文法是二義性的。 ( )1、簡述編譯程序的工作過程：編譯程序的工作過程，是指從輸入源程序開始到輸出目標程序為止的整個過程，是非常復雜的，就其過程而言，一般可以劃分為五個工作階段：詞法分析，對構(gòu)成源程序的字符串進行掃描和分解，識別出一個個的單詞；語法分析，根據(jù)語言的語法規(guī)則，把單詞符號串分解成各類語法單位；語義分析與中間代碼產(chǎn)生，即對各類語法單位，分析其漢一并進行初步翻譯；代碼優(yōu)化，以期產(chǎn)生更高效的代碼；目標代碼生成，把中間代碼變換成特定機器上的低級語言指令形式。2簡述代碼優(yōu)化的目的和意義：代碼優(yōu)化是盡量生成“好”的代碼的編譯階段。也就是要對程序代碼進行一種等價變換，在保證變換前后代碼執(zhí)行結(jié)果相同的前提下，盡量使目標程序運行時所需要的時間短，同時所占用的存儲空間少。3、 簡要說明語義分析的基本功能：確定類型、類型檢查、語義處理和某些靜態(tài)語義檢查。1 詞法分析：詞法分析的主要任務(wù)是從左向右掃描每行源程序的符號，按照詞法規(guī)則從構(gòu)成源程序的字符串中識別出一個個具有獨立意義的最小語法單位，并轉(zhuǎn)換成統(tǒng)一的內(nèi)部表示(token)，送給語法分析程序。3簡述自下而上的分析方法。：所謂自下而上分析法就是從輸入串開始，逐步進行“歸約”，直至歸約到文法的開始符號；或者說從語法樹的末端開始，步步向上“歸約”，直到根節(jié)點。2LL(1)文法：若文法的任何兩個產(chǎn)生式A a | b都滿足下面兩個條件：（1）FIRST(a ) FIRST(b ) = f；（2）若b * e ，那么FIRST(a ) FOLLOW( A ) = f。我們把滿足這兩個條件的文法叫做LL(1)文法，其中的第一個L代表從左向右掃描輸入，第二個L表示產(chǎn)生最左推導，1代表在決定分析器的每步動作時向前看一個輸入符號。除了沒有公共左因子外，LL(1)文法還有一些明顯的性質(zhì)，它不是二義的，也不含左遞歸。3語法樹：句子的樹結(jié)構(gòu)表示法稱為語法樹(語法分析樹或語法推導樹)。給定文法G=(VN，VT，P，S)，對于G的任何句型都能構(gòu)造與之關(guān)聯(lián)的語法樹。這棵樹具有下列特征：(1)根節(jié)點的標記是開始符號S。(2)每個節(jié)點的標記都是V中的一個符號。(3)若一棵子樹的根節(jié)點為A，且其所有直接子孫的標記從左向右的排列次序為A1A2AR，那么AA1A2AR一定是P中的一條產(chǎn)生式。(4)若一標記為A的節(jié)點至少有一個除它以外的子孫，則AVN。(5)若樹的所有葉節(jié)點上的標記從左到右排列為字符串w，則w是文法G的句型；若w中僅含終結(jié)符號，則w為文法G所產(chǎn)生的句子。4LR(0)分析器：所謂LR(0)分析，是指從左至右掃描和自底向上的語法分析，且在分析的每一步，只須根據(jù)分析棧當前已移進和歸約出的全部文法符號，并至多再向前查看0個輸入符號，就能確定相對于某一產(chǎn)生式左部符號的句柄是否已在分析棧的頂部形成，從而也就可以確定當前所應采取的分析動作 (是移進還是按某一產(chǎn)生式進行歸約等)。5語言和文法：文法就是語言結(jié)構(gòu)的定義和描述，是有窮非空的產(chǎn)生式集合。文法G定義為四元組的形式：G=(VN，VT，P，S)其中：VN 是非空有窮集合，稱為非終結(jié)符號集合；VT 是非空有窮集合，稱為終結(jié)符號集合；P是產(chǎn)生式的集合(非空)；S是開始符號(或識別符號)。這里，VNVT=，SVN。V=VNVT，稱為文法G的字母表，它是出現(xiàn)文法產(chǎn)生式中的一切符號的集合。文法G所描述的語言用L(G)表示，它由文法G所產(chǎn)生的全部句子組成，即L(G)=x| S*x，其中S為文法開始符號，且 簡單的說，文法描述的語言是該文法一切句子的集合。2.二義性文法：如果一個文法存在某個句子對應兩棵不同的語法樹，則稱這個文法是二義性文法。6.語法：一組規(guī)則，用它可形成和產(chǎn)生一組合式的程序。7.文法:描述語言的語法結(jié)構(gòu)的形式規(guī)則。12.規(guī)范句型-由規(guī)范推導所得到的句型。15.句柄：一個句型的最左直接短語。21.語義：定義程序的意義的一組規(guī)則。10.短語：令G是一個文法，S劃文法的開始符號，假定是文法G的一個句型，如果有SA且A，則稱是句型相對非終結(jié)符A的短語。1編譯程序和高級語言有什么區(qū)別? 用匯編語言或高級語言編寫的程序，必須先送入計算機，經(jīng)過轉(zhuǎn)換成用機器語言表示的目標程序（這個過程即編譯），才能由計算機執(zhí)行。執(zhí)行轉(zhuǎn)換過程的程序叫編譯程序。匯編程序是指沒有編譯過的匯編語言源文件。編譯程序轉(zhuǎn)換過的叫目標程序，也就是機器語言。 編譯程序的工作情況有三種：匯編型、解釋型和編譯型。匯編型編譯程序用來將匯編語言編寫的程序，按照一一對應的關(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局部