編譯原理第15章習(xí)題課答案解析

編譯原理第15章習(xí)題課答案解析2、一個(gè)典型的編譯系統(tǒng)通常由有哪些部分組成？各部分的主要功能是什么？1編譯系統(tǒng)編譯程序語法分析語義分析與中間代碼生成優(yōu)化目標(biāo)代碼生成運(yùn)行系統(tǒng)詞法分析②語法分析()：在詞法分析的基礎(chǔ)上將單詞序列分解成各類語法短語，如“程序”，“語句”，“表達(dá)式”等等。③語義分析()：語義分析是在語法分析程序確定出語法短語后，審查有無語義錯(cuò)誤，并為代碼生成階段收集類型信息。1①詞法分析()：從左到右一個(gè)字符一個(gè)字符的讀入源程序，對(duì)構(gòu)成源程序的字符串進(jìn)行掃描和分解，從而識(shí)別出一個(gè)個(gè)單詞（也稱單詞符號(hào)或簡(jiǎn)稱符號(hào)）。1⑤代碼優(yōu)化()：為了使生成的目標(biāo)代碼更為高效，可以對(duì)產(chǎn)生的中間代碼進(jìn)行變換或進(jìn)行改造，這就是代碼的優(yōu)化。⑥代碼生成()：目標(biāo)代碼生成是編譯器的最后一個(gè)階段。在生成目標(biāo)代碼時(shí)要考慮以下幾個(gè)問題：計(jì)算機(jī)的系統(tǒng)結(jié)構(gòu)、指令系統(tǒng)、寄存器的分配以及內(nèi)存的組織等。④中間代碼生成()：完成語法分析和語義處理工作后，編譯程序?qū)⒃闯绦蜃兂梢环N內(nèi)部表示形式，這種內(nèi)部表示形式叫做中間語言或稱中間代碼，它是一種結(jié)構(gòu)簡(jiǎn)單、含義明確的記號(hào)系統(tǒng)。21.寫出C語言和語言的輸入字母表。C語言：0~9數(shù)字，大小寫英文字母，鍵盤上可見的字符語言：可以包括的所有字符。6.文法G6為:N→D→0|1|2|3|4|5|6|7|8|9（1）G6的語言是什么?G6的語言是：0~9的數(shù)字組成的任意非空串L(G6)={∈{0,1,2,3,4,5,6,7,8,9}+}（2）給出句子0127、34和568的最左和最右推導(dǎo)。7、寫一文法，使其語言是奇數(shù)集。要求：不以0打頭。復(fù)雜的情況:分三部分末尾：以1|3|5|7|9結(jié)尾(一位):D→1|3|5|7|9開頭：除了0的任意數(shù)字中間部分：空或者任意數(shù)字串D→1|3|5|7|9C→εA→0所以題目要求的文法G[N]可以寫成：N→BCD|DD→1|3|5|7|9B→2|4|6|8|DC→CA|εA→0|BB→2|4|6|89、證明文法:S→||i是二義的。二義性的含義:如果文法存在某個(gè)句子對(duì)應(yīng)兩棵以上不同的語法樹，或者兩種以上不同的最左/右推導(dǎo)，則稱這個(gè)文法是二義的。首先：找到此文法對(duì)應(yīng)的一個(gè)句子其次：構(gòu)造與之對(duì)應(yīng)的兩棵語法樹SiSeSiSiiSiSiSeSii結(jié)論：因?yàn)樵撐姆ù嬖诰渥訉?duì)應(yīng)兩棵不同的語法樹，因而該文法是二義的。11、給出下面語言的相應(yīng)文法L1={n≥1≥0}G1(S):S→A→B→ε從n，i的不同取值來把L1分成兩部分：A→|前半部分是：后半部分是ci：B→|ε所以整個(gè)文法G1[S]可以寫為：L2={n≥1≥0}G2(S):S→A→εB→L3={≥0}G3(S):S→A→εB→εL4={1n0m1m0≥0}可以看成是兩部分：剩下兩邊的部分就是：S→1S0中間部分是0m1m：A→0A1|ε所以G4[S]可以寫為：S→1S0|AA→0A1|ε|A37.構(gòu)造下列正規(guī)式相應(yīng)的。步驟:①.根據(jù)正規(guī)式畫出對(duì)應(yīng)的狀態(tài)轉(zhuǎn)換圖;②.根據(jù)狀態(tài)轉(zhuǎn)換圖畫出對(duì)應(yīng)的狀態(tài)轉(zhuǎn)換矩陣;③.根據(jù)狀態(tài)轉(zhuǎn)換矩陣得到重命名后的狀態(tài)轉(zhuǎn)換矩陣;④.根據(jù)重命名后的狀態(tài)轉(zhuǎn)換矩陣得出最后的.問題：將狀態(tài)轉(zhuǎn)換圖與混淆。1(0|1)*101①.狀態(tài)轉(zhuǎn)換圖abadb1(0|1)*101a1(0|1)*101dcef1εε01101ggg②.狀態(tài)轉(zhuǎn)換矩陣II0I1{a}Φ{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}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)轉(zhuǎn)換矩陣S01A(始態(tài))ΦBBCDCCDDEDECF(終態(tài))F(終態(tài))EDAB10C1D010E10101F④1(1010*|1(010)*1)*0abdc1εε0e0101fghiεε01110jklmnεε①.狀態(tài)轉(zhuǎn)換圖②.狀態(tài)轉(zhuǎn)換矩陣③.重命名后的狀態(tài)轉(zhuǎn)換矩陣④8、給出下面正規(guī)表達(dá)式（1）以01結(jié)尾的二進(jìn)制數(shù)串。(0|1)*01（2）能被5整除的十進(jìn)制數(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）英文字母組成的所有符號(hào)串，要求符號(hào)串中的字母按字典序排列。(A|a)*(B|b)*(C|c)*…(Z|z)*（3）包含奇數(shù)個(gè)1或奇數(shù)個(gè)0的二進(jìn)制串0*1(0|10*1)*|1*0(0|10*1)*（5）沒有重複出現(xiàn)的數(shù)字的數(shù)字符號(hào)串的全體令0,1,2...9R0129記為∑i(0,1,2...,9)P（0,1,2...,9)表示0,1,2...,9的全排列∑019019P(0,1,2...,9)8、給出下面正規(guī)表達(dá)式（6）最多有一個(gè)重複出現(xiàn)的數(shù)字的數(shù)字符號(hào)串的全體∑i∑019i(0,1,2...,9)019P(0,1,2...,9)（7）不包含字串的由a和b組成的符號(hào)串的全體b*(a*|()*)*9、對(duì)下面情況給出及正規(guī)表達(dá)式：（1）{0,1}上的含有子串010的所有串。正規(guī)式：(0|1)*010(0|1)*做法同第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)轉(zhuǎn)換矩陣{0}{0,1}{1}{1}{0,1}{0,1}{1}{0}φ②.重命名后的狀態(tài)轉(zhuǎn)換矩陣01221120φ0a2baba③④.最小化Π0=({0,1},{2})1{0,1}{1}{0,1}{2}因此，不能再分02baa023145aaaabbbbbbaa(b)這道題實(shí)質(zhì)上已經(jīng)是確定化了的，所以我們只需最小化Π：{2，3，4，5}{0，1}{2，3，4，5}{0，1，3，5}分屬兩區(qū)，所以分為{2，4}{3，5}{0，1}{1}{0，1}{2，4}所以0，1等價(jià){2，4}{0，1}{2，4}{3，5}所以2，4等價(jià){3，5}{3，5}{3，5}{2，4}所以3，5等價(jià)所以分為{0，1}{2，4}{3，5}023aabbba14、構(gòu)造一個(gè)，它接受Σ={0,1}上所有滿足如下

條件的字符串：每個(gè)1都有0直接跟在右邊。思路：先寫出滿足條件的正規(guī)式，由正規(guī)式構(gòu)造，再把確定化和最小化。滿足條件的正規(guī)式：(0|10)*0110yx(0|10)*xy12100xy12100確定化：給狀態(tài)編號(hào)：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è)與G等價(jià)的左線性文法。S→0S|1S|1A|0BA→1C|1B→0C|0C→0C|1C|0|1SABCZ001110001101G[Z]:Z→Z0101B→A0|0A→B1|1確定化、最小化后的為：SB0A110Z010,1補(bǔ)充：構(gòu)造一右線性文法，使它與如下文法等價(jià)：

S→A→U→T→B→

并根據(jù)所得右線性文法，構(gòu)造出相應(yīng)的狀態(tài)轉(zhuǎn)換圖。思路：先寫出原文法所描述的語言L(G)={≥1}G[S]:S→B→C→aSaCbcBbcT44.1、考慮下面文法G1：S→a|∧|（T）T→T，S|S（1）消去G1的左遞歸；S→a|∧|（T）T→’T’→，ST’|ε（2）經(jīng)改寫后的文法是否是(1)文法，給出預(yù)測(cè)分析表。經(jīng)改寫后的文法滿足3個(gè)條件，所以是(1)的預(yù)測(cè)分析表構(gòu)造算法:1.對(duì)文法中的每個(gè)產(chǎn)生式A→α執(zhí)行第二步和第三步;(S)={a,∧,(}(T)={a,∧,(}(T’)={,,ε}(S)={),,}(T)={)}(T)={)}

a∧（，）#S

T

T’

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

a∧（，）#S

T

T’

S→aS→∧S→(T)T→’T→’T→’T’→’3.若ε∈(α),則對(duì)于任何b∈(A)把A→α加至M[]中(T’)(T)={)}T’→ε遞歸子程序：S; 'a''^'

'('

; ')'; ;

;T; ’T’; ‘,’

;’

:是輸入串指針?biāo)傅姆?hào):是把調(diào)至下一個(gè)輸入符號(hào):是出錯(cuò)診察程序補(bǔ)充題：有文法：E→’E’→’|εT→’T’→’|εF→（E）|iA→+|-M→*|/（1）求、集，判斷是否是（1）文法？（2）若是構(gòu)造（1）分析表？（3）簡(jiǎn)述（1）分析器的工作原理。4.2：有文法：E→’E’→|εT→’T’→T|εF→’F’→*F’|εP→(E)^（1）求、集，判斷是否是（1）文法？（2）若是構(gòu)造（1）分析表？（3）簡(jiǎn)述（1）分析器的工作原理。E→’E’→’|εT→’T’→’|εF→（E）|iA→+|-M→*|/(M)={*，/}(A)={+，-}(F)={(，i}(T’)={*，/，ε}(T)={(，i)(E’)={+，-，ε}(E)={(，i}(E)={#，)}(E’)={#，)}(T)={+，-，#，)}(T’)={+，-，#，)}(F)={*，/，+，-，#，)}(A)={(，i}(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.對(duì)文法G:E→’E’→εT→’T’→εF→’F’→*F’|εP→(E)∧1)(E)=(T)(F)(P)={(,∧}(E’)={+,ε}(T’)(T)∪{ε}={(,∧,ε}(F’)={*,ε}(E)={#,)}(E’)(E)={#,)}(T)(E’)\ε∪(E)={,)}(T’)(T)={,)}(F)(T’)\ε∪(T)={(,∧,,)}{F’)(F)={(,∧,,)}(P)(F’)\ε∪(F)={*,(,∧,,)}2)考慮下列產(chǎn)生式:()∩(ε)={+}∩{ε}=φ()∩(E')={+}∩{#,)}=φ(T)∩(ε)={(,^}∩{ε}=φ(T)∩(T')={(,^}∩{+,)}=φ(*F')∩(ε)={*}∩{ε}=φ(*F')∩(F')={*}∩{(,^,)}=φ((E))∩(a)∩(b)∩(^)=φ所以,該文法式(1)文法.3)預(yù)測(cè)分析表：4)程序E; '(''a''b''^' T;E'

E'; '+' ;E <>')'<>'#'T; '(''a''b''^' F;T'

T'; '(''a''b''^' T '*'F; '(''a''b''^' P;F'

F'; '*' ;F'

P; 'a''b''^'

'('

;E; ')'

;4.3下面文法中，那些是(1)文法的，說明理由構(gòu)造不帶回溯的自上而下分析的文法條件1.文法不含左遞歸，2.對(duì)于文法中每一個(gè)非終結(jié)符A的各個(gè)產(chǎn)生式的候選首符集兩兩不相交。即，若A→1|2|…|n則(i)∩(j)＝ (ij)3.對(duì)文法中的每個(gè)非終結(jié)符A，若它存在某個(gè)候選首符集包含，則(A)∩(A)=如果一個(gè)文法G滿足以上條件，則稱該文法G為(1)文法。 SAB是，滿足三個(gè)條件SAB對(duì)于A不滿足條件3SABA、B都不滿足條件3SBCd滿足條件3解題思路：構(gòu)造文法的預(yù)測(cè)分析表，通常應(yīng)當(dāng)按下列步驟進(jìn)行：1.消除文法的左遞歸（包括所有直接左遞歸和間接左遞歸）2.對(duì)消除左遞歸后的文法，提取公因子3.對(duì)經(jīng)過上述改造后的文法，計(jì)算它的每個(gè)非終結(jié)符的集合和集合；4.根據(jù)集合和集合構(gòu)造預(yù)測(cè)分析表：第1步對(duì)文法G的每個(gè)產(chǎn)生式Aα執(zhí)行第1步和第3步；第2步對(duì)每個(gè)終結(jié)符a∈(α),把Aα加至M[]中；第3步若∈(α),則對(duì)任何b∈(A),把Aα加至M[]中；第4步把所有無定義的M[]標(biāo)上“出錯(cuò)標(biāo)誌”4.4對(duì)下面的文法：()()|(1)構(gòu)造(1)分析表(2)給出對(duì)句子-(())分析過程4.4對(duì)下面的文法：()()|(1)構(gòu)造(1)分析表(2)給出對(duì)句子-(())分析過程4.4對(duì)下面的文法：()()|(1)構(gòu)造(1)分析表(2)給出對(duì)句子-(())分析過程(2)給出對(duì)句子-(())分析過程(2)給出對(duì)句子-(())分析過程(2)給出對(duì)句子-(())分析過程(2)給出對(duì)句子-(())分析過程51、令文法G1為：E→|TT→T*F|FF→(E)|i證明*F是它的一個(gè)句型，指出這個(gè)句型的所有短語、直接短語和句柄。EE+TT*FT*F是句型*F相對(duì)于T的短語*F句型*F相對(duì)于E的短語T*F是句型*F相對(duì)于T的直接短語T*F是句柄2、考慮下面的表格結(jié)構(gòu)文法G2：

S→a|^|(T)

T→|S（1）給出(a,())和(((),^,(a)))的最左和最右推導(dǎo)。(a,())的最左推導(dǎo)：S(T)()()()(a,(T))(a,())(a,())(a,())(a,())(((),^,(a)))的最左推導(dǎo)：S(T)()()((T))(())(())(())((()))((()))((()))((()))(((),^))(((),^))(((),^))(((),^,(a)))的最右推導(dǎo)：S(T)()()()((T))(())(())((()))((()))((()))((()))(((),^))(((),^))(((),^))(a,())的最右推導(dǎo)：S(T)()(T,(T))(T,())(T,())(T,())(T,())(S,())(a,())2）指出(((),^,(a)))的規(guī)范歸約及每一步的句柄。S(T)T,Sa(T)ST,ST,S(T)Sa^(T)ST,SaSaaS→a(((),^,(a)))ST→S(((),^,(a)))aS→a(((),^,(a)))T→T,S(((T),^,(a)))(T)S→(T)((S,^,(a)))ST→S((T,^,(a)))^S→^((,(a)))T→T,S根據(jù)這個(gè)規(guī)范規(guī)約，給出“移進(jìn)—?dú)w約”的過程，并給出它的語法樹的自下而上的構(gòu)造過程。符號(hào)棧輸入串：(((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)計(jì)算練習(xí)2文法G2的和。G2：S→a|^|(T)

T→|S(S)={a，∧，(}(T)={，，a，∧，(}(S)={a，∧，)}(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),∧),)),，)﹥.﹥.﹥.﹥.#a,#∧,#(,﹤.﹤.﹤.##.a#,∧#,）#,﹥.﹥.﹥.#,)(^a#,)(^a=.>.>.>.>.>.>.>.>.>.>.>.<.<.<.<.<.<.<.<.<.<.=.1、文法是算術(shù)文法，且不含ε產(chǎn)生式。2、由優(yōu)先關(guān)系矩陣可知，任何兩個(gè)終結(jié)符之間的優(yōu)先關(guān)系不多于一種。綜上，該文法是算術(shù)優(yōu)先文法。﹤.

，a∧（）#，

a

∧

(

)

#

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