編譯原理-第1~5章習題課答案

chapter11、何謂源程序、目標程序、翻譯程序、編譯程序和解釋程序？它們之間可能有何種關系？源程序：用源語言編寫的程序。目標程序：源程序經(jīng)翻譯程序過加工處理后生成的程序。翻譯程序：將源程序轉換為與其邏輯上等價的目標程序。編譯程序：源語言為高級語言，目標語言為匯編語言或機器語言的翻譯程序。解釋程序：源語言程序作為輸入，但不產(chǎn)生目標程序，而是邊解釋邊執(zhí)行源程序本身。①先翻譯后執(zhí)行①邊解釋邊執(zhí)行②執(zhí)行速度快②

有利于程序的調(diào)試③多次運算③1次運算2、一個典型的編譯系統(tǒng)通常由有哪些部分組成？各部分的主要功能是什么？chapter1編譯系統(tǒng)編譯程序語法分析語義分析與中間代碼生成優(yōu)化目標代碼生成運行系統(tǒng)詞法分析②語法分析(SyntaxAnalysis)：

在詞法分析的基礎上將單詞序列分解成各類語法短語，如“程序”，“語句”，“表達式”等等。③語義分析(SyntacticAnalysis)：

語義分析是在語法分析程序確定出語法短語后，審查有無語義錯誤，并為代碼生成階段收集類型信息。chapter1①詞法分析(LexicalAnalysis)：

從左到右一個字符一個字符的讀入源程序，對構成源程序的字符串進行掃描和分解，從而識別出一個個單詞（也稱單詞符號或簡稱符號）。

chapter1⑤代碼優(yōu)化(Optimizationofcode)：

為了使生成的目標代碼更為高效，可以對產(chǎn)生的中間代碼進行變換或進行改造，這就是代碼的優(yōu)化。⑥代碼生成(Generationofcode)：

目標代碼生成是編譯器的最后一個階段。在生成目標代碼時要考慮以下幾個問題：計算機的系統(tǒng)結構、指令系統(tǒng)、寄存器的分配以及內(nèi)存的組織等。④中間代碼生成(Generationofintermediatecode)：

完成語法分析和語義處理工作后，編譯程序?qū)⒃闯绦蜃兂梢环N內(nèi)部表示形式，這種內(nèi)部表示形式叫做中間語言或稱中間代碼，它是一種結構簡單、含義明確的記號系統(tǒng)。chapter21.寫出C語言和Java語言的輸入字母表。C語言：0~9數(shù)字，大小寫英文字母，鍵盤上可見的字符Java語言：Unicode可以包括的所有字符。6.文法G6為:N→D|NDD→0|1|2|3|4|5|6|7|8|9

（1）G6的語言是什么?G6的語言是：

0~9的數(shù)字組成的任意非空串L(G6)={x|x∈{0,1,2,3,4,5,6,7,8,9}+}（2）給出句子0127、34和568的最左和最右推導。7、寫一文法，使其語言是奇數(shù)集。要求：不以0打頭。復雜的情況:分三部分末尾：以1|3|5|7|9結尾(一位):D→1|3|5|7|9開頭：除了0的任意數(shù)字中間部分：空或者任意數(shù)字串D→1|3|5|7|9C→CA|εA→0|B所以題目要求的文法G[N]可以寫成：N→BCD|DD→1|3|5|7|9B→2|4|6|8|DC→CA|εA→0|BB→2|4|6|8|D9、證明文法:S→iSeS|iS|i

是二義的。二義性的含義:如果文法存在某個句子對應兩棵以上不同的語法樹，或者兩種以上不同的最左/右推導，則稱這個文法是二義的。首先：找到此文法對應的一個句子iiiei其次：構造與之對應的兩棵語法樹SiSeSiSiiSiSiSeSii結論：因為該文法存在句子iiiei對應兩棵不同的語法樹，因而該文法是二義的。11、給出下面語言的相應文法L1={anbnci|n≥1,i≥0}G1(S):S→ABA→aAb|abB→cB|ε從n，i的不同取值來把L1分成兩部分：A→aAb|ab前半部分是anbn：

后半部分是ci：B→Bc|ε所以整個文法G1[S]可以寫為：L2={aibncn|n≥1,i≥0}G2(S):S→ABA→aA|εB→bBc|bcL3={anbnambm|m,n≥0}G3(S):S→ABA→aAb|εB→aBb|εL4={1n0m1m0n|n,m≥0}可以看成是兩部分：剩下兩邊的部分就是：S→1S0中間部分是0m1m

：A→0A1|ε所以G4[S]可以寫為：S→1S0|AA→0A1|ε|Achapter37.構造下列正規(guī)式相應的DFA。步驟:①.根據(jù)正規(guī)式畫出對應的狀態(tài)轉換圖;②.根據(jù)狀態(tài)轉換圖畫出對應的狀態(tài)轉換矩陣;③.根據(jù)狀態(tài)轉換矩陣得到重命名后的狀態(tài)轉換矩陣;④.根據(jù)重命名后的狀態(tài)轉換矩陣得出最后的DFA.問題：將狀態(tài)轉換圖與DFA混淆。1(0|1)*101①.狀態(tài)轉換圖abadb1(0|1)*101a1(0|1)*101dcef1εε01101ggg②.狀態(tài)轉換矩陣II0I1{a}Φ{b,c,d}{b,c,d}{c,d}{c,d,e}{c,d}{c,d}{c,d,e}{c,d,e}{c,d,f}{c,d,e}{c,d,f}{c,d}{c,d,e,g}{c,d,e,g}{c,d,f}{c,d,e}1abdcef1εε0101gII0I1{a}Φ{b,c,d}{b,c,d}{c,d}{c,d,e}{c,d}{c,d}{c,d,e}{c,d,e}{c,d,f}{c,d,e}{c,d,f}{c,d}{c,d,e,g}{c,d,e,g}{c,d,f}{c,d,e}③.重命名后的狀態(tài)轉換矩陣S01A(始態(tài))ΦBBCDCCDDEDECF(終態(tài))F(終態(tài))EDAB10C1D010E10101F④.DFA1(1010*|1(010)*1)*0abdc1εε0e0101fghiεε01110jklmnεε①.狀態(tài)轉換圖②.狀態(tài)轉換矩陣③.重命名后的狀態(tài)轉換矩陣④.DFA8、給出下面正規(guī)表達式（1）以01結尾的二進制數(shù)串。(0|1)*01（2）能被5整除的十進制數(shù)。0|5(0|5)|(1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*（4）英文字母組成的所有符號串，要求符號串中的字母按字典序排列。(A|a)*(B|b)*(C|c)*…(Z|z)*（3）包含奇數(shù)個1或奇數(shù)個0的二進制串0*1(0|10*1)*|1*0(0|10*1)*（5）沒有重複出現(xiàn)的數(shù)字的數(shù)字符號串的全體令ri=i|,i=0,1,2...9R0|R1|R2|...|R9記為∑Rii(0,1,2...,9)P（0,1,2...,9)表示0,1,2...,9的全排列∑ri0ri1...ri9ri0ri1...ri9

P(0,1,2...,9)8、給出下面正規(guī)表達式（6）最多有一個重複出現(xiàn)的數(shù)字的數(shù)字符號串的全體∑i∑ri0ri1...ri9

i(0,1,2...,9)ri0ri1...ri9P(0,1,2...,9)（7）不包含字串a(chǎn)bb的由a和b組成的符號串的全體b*(a*|(ba)*)*9、對下面情況給出DFA及正規(guī)表達式：（1）{0,1}上的含有子串010的所有串。正規(guī)式：(0|1)*010(0|1)*DFA做法同第7題。（2）{0,1}上不含子串010的所有串。正規(guī)式：1*(0|11*1)*1*0*1*(0|11)*(0|1)1*(0|11)*1*12、將圖3.18的(a)和(b)分別確定化和最少化。(a)aaa,b10①.狀態(tài)轉換矩陣{0}{0,1}{1}{1}{0,1}{0,1}{1}{0}φ②.重命名后的狀態(tài)轉換矩陣01221120φ0a2baba③.DFA④.最小化Π0=({0,1},{2})1{0,1}a={1}{0,1}b={2}因此，不能再分02baa023145aaaabbbbbbaa(b)這道題實質(zhì)上已經(jīng)是確定化了的，所以我們只需最小化Π：{2，3，4，5}{0，1}{2，3，4，5}a={0，1，3，5}分屬兩區(qū)，所以分為{2，4}{3，5}{0，1}a={1}{0，1}b={2，4}所以0，1等價{2，4}a={0，1}{2，4}b={3，5}所以2，4等價{3，5}a={3，5}{3，5}b={2，4}所以3，5等價所以分為

{0，1}{2，4}{3，5}

023aabbba14、構造一個DFA，它接受Σ={0,1}上所有滿足如下

條件的字符串：每個1都有0直接跟在右邊。思路：先寫出滿足條件的正規(guī)式，由正規(guī)式構造

NFA，再把NFA確定化和最小化。滿足條件的正規(guī)式：(0|10)*0110yx(0|10)*xy12100xy12100確定化：給狀態(tài)編號：021

01100最小化：{0,1}，{2}{0,1}0={1}{0,1}1={2}{2}0={0}，{2}1=

??{2}或{0,1}所以{0,1}不可分，用狀態(tài)0代表它們0210015、給定右線性文法G：求一個與G等價的左線性文法。S→0S|1S|1A|0BA→1C|1B→0C|0C→0C|1C|0|1SABCZ001110001101G[Z]:Z→Z0|Z1|B0|A1B→A0|0A→B1|1確定化、最小化后的DFA為：SB0A110Z010,1補充：構造一右線性文法，使它與如下文法等價：

S→ABA→UTU→a|aUT→b|bTB→c|cB

并根據(jù)所得右線性文法，構造出相應的狀態(tài)轉換圖。思路：先寫出原文法所描述的語言L(G)={ambnck|m,n,k≥1}G[S]:

S→aS|aBB→bB|bCC→cC|caSaCbcBbcTchapter44.1、考慮下面文法G1：S→a|∧|（T）

T→T，S|S（1）消去G1的左遞歸；S→a|∧|（T）T→ST’T’→，ST’|ε（2）經(jīng)改寫后的文法是否是LL(1)文法，給出預測分析表。經(jīng)改寫后的文法滿足3個條件，所以是LL(1)的預測分析表構造算法:1.對文法中的每個產(chǎn)生式A→α執(zhí)行第二步和第三步;FIRST(S)={a,∧,(}FIRST(T)={a,∧,(}FIRST(T’)={,,ε}FOLLOW(S)={),,,#}

FOLLOW(T)={)}

FOLLOW(T)={)}

a∧（，）#S

T

T’

S→aS→∧S→(T)T→ST’T→ST’T→ST’T’→,ST’T’→ε預測分析表構造算法:1.對文法中的每個產(chǎn)生式A→α執(zhí)行第二步和第三步;2.對每個終結符a∈FIRST(α),把A→a加到M[A,a]中;S→a;S→∧;S→(T);T→ST’;T’→,ST’T’→εFTRST（a）={a}FIRST（∧）={∧}FIRST（（T））={（}FIRST（ST’）={a，∧，（}FIRST（，ST’）={，}FIRST（ε）={ε}

a∧（，）#S

T

T’

S→aS→∧S→(T)T→ST’T→ST’T→ST’T’→,ST’3.若ε∈FIRST(α),則對于任何b∈FOLLOW(A)把A→α加至M[A,b]中FOLLOW(T’)=FOLLOW(T)={)}T’→ε遞歸子程序：procedureS;begin ifsym='a'orsym='^' thenabvanceelseifsym='(' thenbegin advance;T; ifsym=')'thenadvance; elseerror; end elseerrorend;procedureT;begin S;T’EndprocedureT’;begin ifsym=‘,’thenbenginadvance;S;T’endEndsym:是輸入串指針I(yè)P所指的符號advance:是把IP調(diào)至下一個輸入符號error:是出錯診察程序補充題：有文法：

E→TE’E’→ATE’|εT→FT’T’→MFT’|εF→（E）|iA→+|-M→*|/（1）求First、Follow集，判斷是否是LL（1）文法？（2）若是構造LL（1）分析表？（3）簡述LL（1）分析器的工作原理。4.2：有文法：

E→TE’E’→+E|εT→FT’T’→T|εF→PF’F’→*F’|εP→(E)|a|b|^（1）求First、Follow集，判斷是否是LL（1）文法？（2）若是構造LL（1）分析表？（3）簡述LL（1）分析器的工作原理。E→TE’E’→ATE’|εT→FT’T’→MFT’|εF→（E）|iA→+|-M→*|/FIRST(M)={*，/}FIRST(A)={+，-}FIRST(F)={(，i}FIRST(T’)={*，/，ε}FIRST(T)={(，i)FIRST(E’)={+，-，ε}FIRST(E)={(，i}FOLLOW(E)={#，)}FOLLOW(E’)={#，)}FOLLOW(T)={+，-，#，)}FOLLOW(T’)={+，-，#，)}FOLLOW(F)={*，/，+，-，#，)}FOLLOW(A)={(，i}FOLLOW(M)={(，i}EE→TE’

E→TE’

E’

E→ATE’E→ATE’

E’→εE’→εTT→FT’

T→FT’

T’

T’->εT’→εT’→MFT’T’→MFT’

T’→εT’→εFF→i

F→（E）

A

A→+A→-

M

M→*M→/

i+-*/（）#P81.2.對文法G:E→TE’E’→+E|εT→FT’T’→T|εF→PF’F’→*F’|εP→(E)|a|b|∧1)FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P)={(,a,b,∧}FIRST(E’)={+,ε}FIRST(T’)=FIRST(T)∪{ε}={(,a,b,∧,ε}FIRST(F’)={*,ε}FOLLOW(E)={#,)}FOLLOW(E’)=FOLLOW(E)={#,)}FOLLOW(T)=FIRST(E’)\ε∪FOLLOW(E)={+,#,)}FOLLOW(T’)=FOLLOW(T)={+,#,)}FOLLOW(F)=FIRST(T’)\ε∪FOLLOW(T)={(,a,b,∧,+,#,)}FOLLOW{F’)=FOLLOW(F)={(,a,b,∧,+,#,)}FOLLOW(P)=FIRST(F’)\ε∪FOLLOW(F)={*,(,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)預測分析表：4)程序procedureE;begin ifsym='('orsym='a'orsym='b'orsym='^' thenbeginT;E'end elseerrorendprocedureE';begin ifsym='+' thenbeginadvance;Eend elseifsym<>')'andsym<>'#'thenerrorendprocedureT;begin ifsym='('orsym='a'orsym='b'orsym='^' thenbeginF;T'end elseerrorend procedureT';begin ifsym='('orsym='a'orsym='b'orsym='^' thenT elseifsym='*'thenerrorendprocedureF;begin ifsym='('orsym='a'orsym='b'orsym='^' thenbeginP;F'end elseerrorend procedureF';begin ifsym='*' thenbeginadvance;F'endendprocedureP;begin ifsym='a'orsym='b'orsym='^' thenadvance elseifsym='('then begin advance;E; ifsym=')'thenadvance elseerror end elseerrorend;4.3下面文法中，那些是LL(1)文法的，說明理由構造不帶回溯的自上而下分析的文法條件

1.文法不含左遞歸，

2.對于文法中每一個非終結符A的各個產(chǎn)生式的候選首符集兩兩不相交。即，若A→1|2|…|n

則FIRST(i)∩FIRST(j)＝

(ij)3.對文法中的每個非終結符A，若它存在某個候選首符集包含，則FIRST(A)∩FOLLOW(A)=

如果一個文法G滿足以上條件，則稱該文法G為LL(1)文法。

4.3.1SAbcAa|Bb|是，滿足三個條件4.3.2SAbAa|B|Bb|對于A不滿足條件34.3.3SABBAAa|Bb|A、B都不滿足條件34.3.4SaSe|BBbBe|CcCe|d滿足條件3解題思路：構造文法的預測分析表，通常應當按下列步驟進行：

1.消除文法的左遞歸（包括所有直接左遞歸和間接左遞歸）

2.對消除左遞歸后的文法，提取公因子

3.對經(jīng)過上述改造后的文法，計算它的每個非終結符的FIRST集合和FOLLOW集合；

4.根據(jù)FIRST集合和FOLLOW集合構造預測分析表：第1步對文法G的每個產(chǎn)生式Aα執(zhí)行第1步和第3步；第2步對每個終結符a∈FIRST(α),把Aα加至M[A,a]中；第3步若∈FIRST(α),則對任何b∈FIRST(A),把Aα加至M[A,b]中；第4步把所有無定義的M[A,a]標上“出錯標誌”4.4對下面的文法：Expr-ExprExpr(Expr)|VarExprTailExprTail-Expr|VaridVarTailVarTail(Expr)|(1)構造LL(1)分析表(2)給出對句子id--id((id))分析過程4.4對下面的文法：Expr-ExprExpr(Expr)|VarExprTailExprTail-Expr|VaridVarTailVarTail(Expr)|(1)構造LL(1)分析表(2)給出對句子id--id((id))分析過程4.4對下面的文法：Expr-ExprExpr(Expr)|VarExprTailExprTail-Expr|VaridVarTailVarTail(Expr)|(1)構造LL(1)分析表(2)給出對句子id--id((id))分析過程(2)給出對句子id--id((id))分析過程(2)給出對句子id--id((id))分析過程(2)給出對句子id--id((id))分析過程(2)給出對句子id--id((id))分析過程chapter51、令文法G1為：

E→E+T|TT→T*F|FF→(E)|i

證明E+T*F是它的一個句型，指出這個句型的所有短語、直接短語和句柄。EE+TT*FT*F是句型E+T*F相對于T的短語E+T*F句型E+T*F相對于E的短語T*F是句型E+T*F相對于T的直接短語T*F是句柄2、考慮下面的表格結構文法G2：

S→a|^|(T)

T→T,S|S（1）給出(a,(a,a))和(((a,a),^,(a)),a)的最左和最右推導。(a,(a,a))的最左推導：S(T)(T,S)(S,S)(a,S)(a,(T))(a,(T,S))(a,(S,S))(a,(a,S))(a,(a,a))(((a,a),^,(a)),a)的最左推導：S(T)(T,S)(S,S)((T),S)((T,S),S)((T,S,S),S)((S,S,S),S)(((T,S),S,S),S)(((S,S),S,S),S)(((a,S),S,S),S)(((a,a),S,S),S)(((a,a),^,S),S)(((a,a),^,a),S)(((a,a),^,a),a)(((a,a),^,(a)),a)的最右推導：S(T)(T,S)(S,S)(S,a)((T),a)((T,S,S),S)((S,S,S),S)(((T,S),S,S),S)(((S,S),S,S),S)(((a,S),S,S),S)(((a,a),S,S),S)(((a,a),^,S),S)(((a,a),^,a),S)(((a,a),^,a),a)(a,(a,a))的最右推導：S(T)(T,S)(T,(T))(T,(T,S))(T,(T,a))(T,(S,a))(T,(a,a))(S,(a,a))(a,(a,a))2）指出(((a,a),^,(a)),a)的規(guī)范歸約及每一步的句柄。S(T)T,Sa(T)ST,ST,S(T)Sa^(T)ST,SaSaaS→a(((S,a),^,(a)),a)ST→S(((T,a),^,(a)),a)aS→a(((T,S),^,(a)),a)T,ST→T,S(((T),^,(a)),a)(T)S→(T)((S,^,(a)),a)ST→S((T,^,(a)),a)^S→^((T,S,(a)),a)T,ST→T,S根據(jù)這個規(guī)范規(guī)約，給出“移進—歸約”的過程，并給出它的語法樹的自下而上的構造過程。符號棧輸入串：(((a,a),^,(a)),a)#S(T)T,Sa(T)ST,ST,S(T)Sa^(T)ST,SaSa(((aS,TaSS)T,^ST(aST)S)ST,aST)S歸約規(guī)則句柄aS→aST→SaS→aT,ST→T,S(T)S→(T)ST→S^S→^T,ST→T,S3、(1)計算練習2文法G2的FIRSTVT和LASTVT。

G2：S→a|^|(T)

T→T,S|SFIRSTVT(S)={a，∧，(}FIRSTVT(T)={，，a，∧，(}LASTVT(S)={a，∧，)}LASTVT(T)={，，a，∧，)}S→（T）（）.T→T，S

，F(xiàn)IRSTVT(S)﹤.，a,，∧,

，(

﹤.﹤.﹤.T→T，SLASTVT(T)，﹥.a，,∧，,），,，，﹥.﹥.﹥.﹥.S→（T）(FIRSTVT(T)﹤.(a,(∧,((,(，﹤.﹤.﹤.﹤.S→（T）LASTVT(T))﹥.a),∧),)),，)﹥.﹥.﹥.﹥.對待特殊地#,把它看作句型的開始和結束符.根據(jù)#S#同理可得#a,#∧,#(,﹤.﹤.﹤.##.a#,∧#,）#,﹥.﹥.﹥.#,)(^a#,)(^a=.>.>.>.>.>.>.>.>.>.>.>.<.<.<.<.<.<.<.<.<.<.=.1、文法是算術文法，且不含ε產(chǎn)生式。2、由優(yōu)先關系矩陣可知，任何兩個終結符之間的優(yōu)先關系不多于一種。綜上，該文法是算術優(yōu)先文法。﹤.

，a∧（）#，

a

∧

(

)

#

﹥.﹥.﹥.﹥.﹥.﹥.﹥.﹥.﹥.﹥.﹥.﹤.﹤.﹤.﹤.﹤.﹤.﹤.﹤.﹤...輸入串(a,(a,a))的算符優(yōu)先過程。﹤.(﹤.a﹥.