編譯原理作業(yè)參考答案

第1章引言1、解釋下列各詞源語言:編寫源程序的語言（基本符號，關(guān)鍵字），各種程序設(shè)計語言都可以作為源語言。源程序:用接近自然語言（數(shù)學(xué)語言）的源語言（基本符號，關(guān)鍵字）編寫的程序，它是翻譯程序處理的對象。目標(biāo)程序:目標(biāo)程序是源程序經(jīng)過翻譯程序加工最后得到的程序。目標(biāo)程序（結(jié)果程序）一般可由計算機(jī)直接執(zhí)行。低級語言：機(jī)器語言和匯編語言。高級語言：是人們根據(jù)描述實(shí)際問題的需要而設(shè)計的一個記號系統(tǒng)。如同自然語言（接近數(shù)學(xué)語言和工程語言）一樣，語言的基本單位是語句，由符號組和一組用來組織它們成為有確定意義的組合規(guī)則。翻譯程序:能夠把某一種語言程序（源語言程序）改變成另一種語言程序（目標(biāo)語言程序），后者與前者在邏輯上是等價的。其中包括：編譯程序，解釋程序，匯編程序。編譯程序:把輸入的源程序翻譯成等價的目標(biāo)程序（匯編語言或機(jī)器語言），然后再執(zhí)行目標(biāo)程序（先編譯后執(zhí)行），執(zhí)行翻譯工作的程序稱為編譯程序。解釋程序:以該語言寫的源程序作為輸入，但不產(chǎn)生目標(biāo)程序。按源程序中語句動態(tài)順序逐句的邊解釋邊執(zhí)行的過程，完成翻譯工作的程序稱為解釋程序。2、什么叫“遍”？指對源程序或源程序的中間形式（如單詞，中間代碼）從頭到尾掃描一次，并作相應(yīng)的加工處理，稱為一遍。3、簡述編譯程序的基本過程的任務(wù)。編譯程序的工作是指從輸入源程序開始到輸出目標(biāo)程序?yàn)橹沟恼麄€過程，整個過程可以劃分5個階段。詞法分析：輸入源程序，進(jìn)行詞法分析，輸出單詞符號。語法分析：在詞法分析的基礎(chǔ)上，根據(jù)語言的語法規(guī)則把單詞符號串分解成各類語法單位，并判斷輸入串是否構(gòu)成語法正確的“程序”。中間代碼生成：按照語義規(guī)則把語法分析器歸約（或推導(dǎo)）出的語法單位翻譯成一定形式的中間代碼。優(yōu)化：對中間代碼進(jìn)行優(yōu)化處理。目標(biāo)代碼生成：把中間代碼翻譯成目標(biāo)語言程序。4、編譯程序與解釋程序的區(qū)別？編譯程序生成目標(biāo)程序后，再執(zhí)行目標(biāo)程序；然而解釋程序不生成目標(biāo)程序，邊解釋邊執(zhí)行。5、有人認(rèn)為編譯程序的五個組成部分缺一不可，這種看法正確嗎？編譯程序的5個階段中，詞法分析，語法分析，語義分析和代碼生成生成是必須完成的。而中間代碼生成和代碼優(yōu)化并不是必不可少的。優(yōu)化的目的是為了提高目標(biāo)程序的質(zhì)量，沒有這一部分工作，仍然能夠得到目標(biāo)代碼。6、編譯程序的分類目前基本分為：診斷編譯程序，優(yōu)化編譯程序，交叉編譯程序，可變目標(biāo)編譯程序。第2章高級語言及其語法描述1（P36）令文法為NDNDD0129（1）文法描述的語言L（G）是什么？（2）給出句子34，568的最左推導(dǎo)和最右推導(dǎo)。答：（1）L（G）={為可帶前導(dǎo)0的正整數(shù)}或L（G）={（0129）+}或L（G）={為數(shù)字串}（2）最左推導(dǎo)：NNDDD3D34NNDNDDDDD5DD56D568最右推導(dǎo)：NNDN4D434NNDN8ND8N68D685682*．寫出一個文法，使其語言是奇數(shù)集，且每個奇數(shù)是不以0開頭。答： SCAB|B（考慮了正負(fù)號） A1|2|3|4|5|6|7|8|9|AA|A0| B1|3|5|7|9 C+|-|或：（未考慮正負(fù)號） SB|AB B1|3|5|7|9 AAD|N N2|4|6|8|B D0|N或：（未考慮正負(fù)號）SC|ABC C1|3|5|7|9 A1|2|3|4|5|6|7|8|9 BBA|B0|2.（P36,8）令文法為ETE+TE-TTFT*FT/FF（E）i（1）給出該文法的VN、VT和S。（2）給出i+i*i，i*（i+i）的最左推導(dǎo)和最右推導(dǎo)。（3）給出i+i+i，i+i*i的語法樹。答：（1）VN={E,T,F}VT={+,-,*,/,(,),i}S=E（2）最左推導(dǎo)EE+TT+TF+Ti+Ti+T*Fi+F*Fi+i*Fi+i*iETT*FF*Fi*Fi*(E)i*(E+T)i*(T+T)i*(F+T)i*(i+T)i*(i+F)i*(i+i)最右推導(dǎo)EE+TE+T*FE+T*iE+F*iE+i*iT+i*iF+i*ii+i*iETT*FT*(E)T*(E+T)T*(E+F)T*(E+i)T*(T+i)T*(F+i)T*(i+i)F*(i+i)i*(i+i)=2\*GB2⑵構(gòu)造語法樹E最左推導(dǎo)構(gòu)造語法樹E+TE+TiTii3.（P36,9）證明下面的文法是二義的： SiSeS|iSi答：對于句子iiiei有兩棵不同的語法樹。因此該文法是二義的。SiSeSiiSeSiiieSiiieiSiSiiSeSiiieSiiiei第3章詞法分析1．設(shè)M=（{x，y}，{a，b}，，x，{y}）為一個非確定有限自動機(jī)NFAM，其中定義如下：（x，a）={x，y}（x，b）={y}（y，a）=（y，b）={x，y}試構(gòu)造其相應(yīng)的最小化的確定有限自動機(jī)DFAM’。答：由定義可知（x，a），（y，b）均為多值函數(shù)，所以是一個非確定有限自動機(jī)。（1）根據(jù)函數(shù)值，先構(gòu)造NFAM（2）確定化：①構(gòu)造DFAM’的轉(zhuǎn)換矩陣:IIaIb{x}①{x，y}②{y}③{x，y}②{x，y}②{x，y}②{y}③{x，y}②②確定DFAM’的初始狀態(tài)和終態(tài)：（a）轉(zhuǎn)換矩陣中I列的第一個狀態(tài)①為DFAM’的初始狀態(tài)結(jié)點(diǎn)。（b）含有y狀態(tài)的子集均為DFAM’的終態(tài)結(jié)點(diǎn)(②、③為終態(tài)結(jié)點(diǎn))。③根據(jù)DFAM’的轉(zhuǎn)換矩陣畫出對應(yīng)的狀態(tài)轉(zhuǎn)換圖：（3）最小化：①首先將其劃分成終態(tài)集{2，3}和非終態(tài)集{1}②{2，3}a=｛2｝{2，3}，{2，3}b=｛2｝{2，3}因此{(lán)2，3}已是不可再區(qū)分的,所以該DFAM’已是最小化的。2.（P64，7(1)）構(gòu)造正規(guī)式1(01)*101相應(yīng)的DFAM。答：（1）構(gòu)造NFAM。XY1（01）*XYX3514Y1X3514YX32X321542Y01X1X12345Y11011（2）構(gòu)造轉(zhuǎn)換矩陣II0I1{X}①{1,2,3}②{1,2,3}②{2,3}③{2,3,4}④{2,3}③{2,3}③{2,3,4}④{2,3,4}④{2,3,5}⑤{2,3,4}④{2,3,5}⑤{2,3}③{2,3,4,Y}⑥{2,3,4,Y}⑥{2,3,5}⑤{2,3,4}④（3）由轉(zhuǎn)換矩陣構(gòu)造DFAM3．（P64，12(a)）將下圖所示的NFAM轉(zhuǎn)換為等價的DFAM’，并將該DFA’最小化。答：該有限自動機(jī)狀態(tài)0輸入同一字符a時到達(dá)兩個不同的結(jié)點(diǎn),所以是NFA。（1）構(gòu)造轉(zhuǎn)換矩陣IIaIb{0}①{0，1}②{1}③{0，1}②{0，1}②{1}③{1}③{0}①（2）由轉(zhuǎn)換矩陣構(gòu)造DFAM12123abab（3）將DFAM最小化=1\*GB3①將DFAM的狀態(tài)劃分為非終態(tài)集{3}和終態(tài)集{1，2}=2\*GB3②對每一個子集及每一個a進(jìn)行考察；{1，2}a={2}{1，2}{1，2}b={3}{3}因此{(lán)1，2}是不可區(qū)分的，所以最終狀態(tài)為：{1，2}，{3}構(gòu)造最小化的DFAM：12，312，3ba4.（P64，12（b））將下圖所示的NFAM轉(zhuǎn)換為等價的DFAM’，并進(jìn)行最小化。答：從圖上可知該圖已經(jīng)是DFAM，先只需將其最小化。首先劃分為兩個集合：{0,1}和{2,3,4,5}{2,3,4,5}a={1,3,0,5}，劃分為：{2,4}和｛3,5｝{2,4}a={1,0}，{2,4}b={3,5}，無需劃分{3,5}a={3,5}，{3,5}b={2,4}，無需劃分{0,1}a={1}，{0,1}b={2,4}，無需劃分因此，最終的劃分為：{0,1}、{2,4}和｛3,5｝，化簡后的結(jié)果：5．（P65，14）構(gòu)造一個DFAM，它接受={0，1}上所有滿足如下條件的字符串：每個1都有0直接跟在右邊。答：（1）根據(jù)題意，得到正規(guī)式：(0|10)*（2）構(gòu)造對應(yīng)的NFAM：（3）將NFAM確定化為DFAM。相應(yīng)的DFAM的狀態(tài)轉(zhuǎn)換矩陣如下：II0I1{X,1,Y}①{1;Y}②{2}③{1,Y}②{1;Y}②{2}③{2}③{1;Y}②DFAM轉(zhuǎn)換圖：（4）將DFAM最小化：①將DFAM的狀態(tài)劃分為非終態(tài)集{3}和終態(tài)集{1,2}②對每一個子集進(jìn)行考察；{1,2}0={2}{1,2}{1,2}1={3，3}{3}因此{(lán)0,1}是不可劃分的。因此最終劃分結(jié)果為：{1,2}和{3}最小化后的DFAM：第4章語法分析-自上而下1.（P81，1）考慮下面文法GSa^(T)TT,SS（1）消除文法的左遞歸。（2）經(jīng)改寫后的文法是否是LL(1)的？給出它的預(yù)測分析表。答：消除左遞歸：Sa^(T)TST’T’,ST’|證明改寫后的文法是否是LL(1)的。FIRST(S)={a,^,(} FOLLOW(S)={，,),#}FIRST(T)={a,^,(} FOLLOW(T)={)}FIRST(T’)={，,} FOLLOW(T’)={)}=1\*GB3①證明Sa^（T）各侯選式的FIRST是否兩兩相交。FIRST（a）FIRST（^）=FIRST（a）FIRST（（）=FIRST（^）FIRST（（）==2\*GB3②證明T’，ST’的FIRST（T’）和FOLLOW（T’）是否相交。FIRST（T’）FOLLOW（T’）={，，}{}=∴該文法是LL（1）的。所以，改造后的文法是LL(1)文法③預(yù)測分析表：a^()，#SSaS^S(T)TTSTTT’ST’ST’T’T’T’,ST’2.利用P76表4.1的LL(1)分析表寫出表達(dá)式(i+i)*i的預(yù)測分析過程。步驟符號棧輸入串所用的產(chǎn)生式0#E（i+i）*i#1#E’T（i+i）*i#ETE’2#E’T’F（i+i）*i#TFT’3#E’T’）E（（i+i）*i#F（E）4#E’T’）Ei+i）*i#5#E’T’）E`Ti+i）*i#ETE’6#E’T’）E’T’Fi+i）*i#TFT’7#E’T’）E’T’ii+i）*i#Fi8#E’T’）E’T’+i）*i#9#E’T’）E’+i）*i#T’10#E’T’）E’T++i）*i#E’+TE’11#E’T’）E’Ti）*i#12#E’T’）E’T’Fi）*i#TFT’13#E’T’）E’T’ii）*i#Fi14#E’T’）E’T’）*i#15#E’T’）E’）*i#T’16#E’T’））*i#E’18#E’T’*i#19#E’T’F**i#T’*FT’20#E’T’Fi#21#E’T’ii#Fi22#E’T’#23#E’#T’24##E’3.（P81，2）對下面的文法GETE’E’+ETFT’T’TFPF’F’*F’P(E)^ab（1）計算這個文法的每個非終結(jié)符的FIRST和FOLLOW。（2）證明這個文法是LL(1)的。（3）構(gòu)造它的預(yù)測分析表。答：（1）計算每個非終結(jié)符的FIRST和FOLLOW。 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,^,),#}（求解過程：因?yàn)镋`+E，所以FIRST（E`）={+，}因?yàn)镕`*F`，所以FIRST（F`）={*，}因?yàn)镻（E）^ab，所以FIRST（P）={（，^，a，b因?yàn)镕PF`，所以FIRST（F）=FIRST（P）因?yàn)門FT`，所以FIRST（T）={FIRST（F）因?yàn)镋TE`，所以FIRST（E）=FIRST（T）因?yàn)門`T，所以FIRST（T`）=FIRST（T）{}={（，^，a，b，求非終結(jié)符的FOLLOW：因?yàn)镋TE`的E是文法的開始符號，F(xiàn)OLLOW（E）={#}，又因?yàn)镻（E），所以FOLLOW（E）={#}FIRST（））\{}={#，)}因?yàn)镋TE`，所以FOLLOW（E`）=FOLLOW（E）因?yàn)镋TE`，并且E`≠，所以FOLLOW（T）=FIRST（E`）\{},又因?yàn)镋`,所以FOLLOW（T）={+}FOLLOW（E）={+}{#,}}={+，#,}.因?yàn)門FT`，所以FOLLOW（T`）=FOLLOW（T）={+，#,}.因?yàn)門FT`，并且T`≠，所以FOLLOW（F）=FIRST（T`）\{},又因?yàn)門`,所以FOLLOW（F）={（，^，a，bFOLLOW（T）={（，^，a，b{+，#,}={（，^，a，b,+，#,因?yàn)镕PF`，所以FOLLOW（F`）=FOLLOW（F）={（，^，a，b,+，#,.因?yàn)镕PF`，并且F`≠，所以FOLLOW（P）=FIRST（F`）\{},又因?yàn)镕`,所以FOLLOW（P）={*FOLLOW（F）={*}{（，^，a，b,+,）,#={*,（，^，a，b,+，,#）（2）證明這個文法是LL(1)的該文法沒有左遞歸，只需考察：E’+ET’TF’*F’P(E)^ab由于：E’+E：FIRST(E’)={+,}∩FOLLOW(E’)={#,}}=ФT’T：FIRST(T’)={(,a,b,^,}∩FOLLOW(T’)={+,),#}=ФF’*F’：FIRST(F’)={*,}∩FOLLOW(F’)={+,(,a,b,^,),#}=ФP(E)^ab：候選式終結(jié)符首字符集兩兩不相交所以該文法為LL(1)文法。（3）LL(1)分析表+*()ab^#EETETETETE’E’E’E’E’E’+EE’E’TTFT’TFT’TFT’TFT’T’T’T’TT’T’TT’TT’TT’FFPFFPFFPFFPF’’’’F’F’F’*F’F’F’F’F’F’F’PP(E)PaPbP^第5章語法分析-自上而下分析1．（P133，1）令文法G1為:E→E+T|TT→T*F|FF→(E)|i證明E+T*F是它的一個句型，指出這個句型的所有短語，直接短語和句柄。答：因?yàn)橛校篍E+TE+T*F，所以E+T*F是文法的一個句型。短語：E+T*F,T*F直接短語：T*F句柄：T*F2.（P133，3）考慮文法G2S→a∧|(T)T→T；SS計算文法G2每個非終結(jié)符的FIRSTVT和LASTVT。構(gòu)造文法G2的優(yōu)先關(guān)系表，該文法是算符優(yōu)先文法嗎？給出輸入串(a；(a；a))的算符優(yōu)先分析過程。解：FIRSTVT和LASTVTFIRSTVT(S)={a,∧,(}FIRSTVT(T)={；，a,∧,(}LASTVT(S)={a,∧,)}LASTVG(T)={；，a,∧,)}優(yōu)先關(guān)系表a∧()；#a∧()；#是算符優(yōu)先分析文法，因?yàn)閮?yōu)先關(guān)系表中沒有沖突的關(guān)系。（3）(a,(a,a))的分析過程步驟棧余留符號串棧頂關(guān)系下一步動作0#(a；(a；a))##<.((進(jìn)棧1#(A；(a；a))#(<.aa進(jìn)棧2#(a；(a；a))#a.>；用S→a歸約3#(S；(a；a))#(<.；;進(jìn)棧4#(S;(a；a))#;<.((進(jìn)棧5#(S;(a；a))#(<.aa進(jìn)棧6#(S;(a；a))#a.>；用S→a歸約7#(S;(S；a))#(<.；;進(jìn)棧8#(S;(S;a))#;<.aa進(jìn)棧9#(S;(S;a))#a.>)用S→a歸約10#(S;(S;S))#;.>)用T→T;S歸約11#(S;(T))#())進(jìn)棧12#(S;(T))#).>)用S→(T)歸約13#(S;S)#;.>)用T→T;S歸約14#(T)#())進(jìn)棧15#(T)#).>#用S→(T)歸約16#S###結(jié)束3.（P134，5）考慮文法S→ASbA→SAa（1）構(gòu)造這個文法的LR(0)項(xiàng)目規(guī)范族及識別活前綴的DFA。（2）這個文法是SLR（1）的嗎？若是，構(gòu)造出它的SLR分析表。解：構(gòu)造拓廣文法：(0)S’→S (1)S→AS (2)S→b (3)A→SA (4)A→a（1）構(gòu)造這個文法的LR(0)項(xiàng)目規(guī)范族及識別活前綴的DFA。（2）證明文法是否是SLR(1)文法？為了驗(yàn)證這個文法是否是SLR(1)文法，必須對LR(0)項(xiàng)目集規(guī)范族的各個項(xiàng)目集I，驗(yàn)證其是否存在“移進(jìn)－歸約”、“歸約－歸約”沖突。該項(xiàng)目規(guī)范族中的I1,I5,I7存在“移進(jìn)－歸約”，只需證明存在集合的a,b，F(xiàn)OLLOW(S’)，F(xiàn)OLLOW(S)，F(xiàn)OLLOW(A)兩兩不相交。對此求出FOLLOW(S’)＝＃，F(xiàn)OLLOW(S)＝#,a,b，F(xiàn)OLLOW(A)＝a,b。驗(yàn)證如下：對狀態(tài)I1有 FOLLOW(S’)=＃；A→·a；S→·b。因此FOLLOW(S’)a,b=＃a,b=，所以不存在“移進(jìn)－歸約”沖突。對狀態(tài)I5有FOLLOW(A)=a,b；A→·a；S→·b。因此FOLLOW(A)a,b=a,ba,b，所以存在“移進(jìn)－歸約”沖突。對狀態(tài)I7也同樣存在這種沖突，即:FOLLOW(S)a,b=＃,a,ba,b因此，該文法不是SLR(1)文法。4．（P1357）證明下面文法是SLR(1)文法，但不是LR(0)文法.S→AA→Ab|bBaB→aAc|a|aAb證明：該文法的項(xiàng)目集規(guī)范族有： I0={S→?A，A→?Ab，A→?bBa} I1=GO(I0,A)={S→A?，A→A?b} I2=GO(I0,b)={A→b?Ba，B→?aAc，B→?a，B→?aAb} I3=GO(I1,b)={A→Ab?} I4=GO(I2,B)={A→bB?a} I5=GO(I2,a)={B→a?Ac，B→a?，B→a?Ab，A→?Ab，A→?bBa} I6=GO(I4,a)={A→bBa?} I7=GO(I5,A)={B→aA?c，B→aA?b，A→A?b} I8=GO(I5,b)=I2 I9=GO(I7,b)={B→aAb?，A→Ab?}因?yàn)轫?xiàng)目集I9中有A→Ab?和B→aAb?，存在“歸約-歸約”沖突，所以不是LR（0）文法。又因?yàn)镕OLLOW(A)={b，c，#}，F(xiàn)OLLOW(B)={a}使得FOLLOW(A)∩FOLLOW(B)=φ，因此構(gòu)造SLR(1)分析表時不會出現(xiàn)沖突，所以該文法是SLR(1)的。5．有文法：0．S’→E1．E→aA2．E→bB3．A→cA4．A→d5．B→cB6．B→d根據(jù)下列給出的該文法的LR(0)分析表，寫出分析符號串“accd”的分析過程。狀態(tài)ACTIONGOTOabcd#EAB0S2S311acc2S6S543S8S974r1r1r1r1r15r4r4r4r4r46S6S5107r2r2r2r2r28S8S9119r6r6r6r6r610r3r3r3r3r311r5r5r5r5r5答：步驟狀態(tài)棧符號棧輸入串動作00#accd#S2，移進(jìn)102#accd#S6，移進(jìn)2026#accd#S6，移進(jìn)30266#accd#S5，移進(jìn)402665#accd#用r4（A→d）歸約5026610#accA#用r3（A→cA）歸約602610#acA#用r3（A→cA）歸約7024#aA#用r1（E→aA）歸約801#E#acc第6章語義分析和中間代碼生成1．根據(jù)給出的語義規(guī)則，寫出下列布爾表達(dá)式的翻譯過程(假設(shè)第1條四元式地址為100)及最終產(chǎn)生的四元式序列：A<10or（Bandnot（CorD））解：語法樹：翻譯過程：（1）E1→id1relopid2 （A<10）E1.truelist:=makelist(nextquad)=100E1.falselist:=makelist(nextquad+1)=101100(j<,A,10,0)101(j,_,_,0)(j,_,_,102)步驟13回填結(jié)果(2)M1→ε:M1.quad:=102(3)E4→id(B)E4.truelist:=makelist(nextquad)=102E4.falselist:=makelist(nextquad+1)=103102(jnz,B,_,0)(jnz,B,_,104)步驟11回填結(jié)果103(j,_,_,0)(4)M2→ε:M2.quad:=104(5)E8→id(C)E8.truelist:=makelist(nextquad)=104E8.falselist:=makelist(nextquad+1)=105104(jnz,C,_,0)105(j,_,_,0)(j,_,_,106)步驟8回填結(jié)果(6)M3→ε:M3.quad:=106(7)E9→id(D)E9.truelist:=makelist(nextquad)=106E9.falselist:=makelist(nextquad+1)=107106(jnz,D,_,0)(jnz,D,_,104)步驟8的拉鏈(jnz,D,_,103)步驟11的拉鏈107(j,_,_,0)(j,_,_,100)步驟13的拉鏈(8)E7→E8orM3E9backpatch(E8.falselist,M3.quad)=(105,106)E7.truelist:=merge(E8.truelist,E9.truelist)=merge(104,106)=106E7.falselist:=E9.falselist=107(9)E6→(E7)E6.truelist:=E7.truelist=106E6.falselist:=E7.falselist=107(10)E5→notE6E5.truelist:=E6.falselist=107E5.falselist:=E6.truelist=106(11)E3→E4andM2E5backpatch(E4.truelist,M2.quad)=(102,104)E3.falselist:=merge(E4.falselist,E5.falselist)=merge(103,106)=106E3.truelist:=E5.truelist=107(12)E2→(E3)E2.truelist:=E3.truelist=107E2.falselist:=E3.falselist=106（13）E→E1orM1E2backpatch(E1.falselist,M1.quad)=(101,102)E.truelist:=merge(E1.truelist,E2.truelist)=merge(100,107)=107E.falselist:=E2.falselist=106最終結(jié)果：A<10or（Bandnot（CorD））100(j<,A,10,0)101(j,_,_,102)無條件轉(zhuǎn)102(jnz,B,_,104)條件轉(zhuǎn)103(j,_,_,0)104(jnz,C,_,0)105(j,_,_,106)無條件轉(zhuǎn)106(jnz,D,_,103)106和103是一條鏈107(j,_,_,100)107和100是一條鏈2.根據(jù)給出的語義規(guī)則，把下面的語句翻譯成四元式序列(設(shè)第1條四元式地址為100)：Whilea<candb<ddoifa=1thenc:=c*2elsea:=a+x；解:語法樹：（1）M1→M1.quad:=nextquad=100（2）E1→E1reLopE2(a<c)E1.trulist:=makelist(nextquad)=100E1.falelist:=makelist(nextquad+1)=101100(j<,a,c,0)(j<,a,c,102)，步驟（5）回填101(j,_,_,0)（3）M3→M2.quad:=nextquad=102（4）E2→E1reLopE2(b<d){E2.trulist:=makelist(nextquad)=102E2.falelist:=makelist(nextquad+1)=103102(j<,b,d,0)(j<,b,d,104)，步驟18回填103(j,_,_,0)(j,_,_,101)，步驟（5）拉鏈（5）EandM3backpatch(truelist,M3.quad)=backpatch(100,102)，用102回填100E.truelist:=E2.truelist=102E.falselist:=merge(E1.falselist,E2.falselist)=merge(101,103)=103，103指向101（6）M2→M2.quad:=nextquad=104（7）E3→E1reLopE2(a=1)E3.trulist:=makelist(nextquad)=104E3.falelist:=makelist(nextquad+1)=105104(j=,a,1,0)(j=,a,1,106)，步驟17回填105(j,_,_,0)(j,_,_,109)，步驟17回填（8）M4→M4.quad:=nextquad=106（9）E4→E1*E2(c*2)E4.place:=newtemp=T1106(*，c，2，T1)（10）A1→id:=E(c=c*2)107(:=,T1,_,c)（11）S2→A1S2.nex