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

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