編譯原理期末試題(含答案+大題集+重要知識點(diǎn))

1、編譯原理期末試題(一)一、是非題(請?jiān)诶ㄌ杻?nèi)，正確的劃M錯(cuò)誤的劃X)(每個(gè)2分，共20分)1 .編譯程序是對高級語言程序的解釋執(zhí)行。(X)2 .一個(gè)有限狀態(tài)自動機(jī)中，有且僅有一個(gè)唯一的終態(tài)。(3 .一個(gè)算符優(yōu)先文法可能不存在算符優(yōu)先函數(shù)與之對應(yīng)。(M4 .語法分析時(shí)必須先消除文法中的左遞歸。(5 .LR分析法在自左至右掃描輸入串時(shí)就能發(fā)現(xiàn)錯(cuò)誤，但不能準(zhǔn)確地指出出錯(cuò)地點(diǎn)。(B6 .逆波蘭表示法表示表達(dá)式時(shí)無須使用括號。(M7 .靜態(tài)數(shù)組的存儲空間可以在編譯時(shí)確定。(8 .進(jìn)行代碼優(yōu)化時(shí)應(yīng)著重考慮循環(huán)的代碼優(yōu)化，這對提高目標(biāo)代碼的效率將起更大作用。(方9 .兩個(gè)正規(guī)集相等的必要條件是他們對應(yīng)的正規(guī)

2、式等價(jià)。(X)10 .一個(gè)語義子程序描述了一個(gè)文法所對應(yīng)的翻譯工作。(二、選擇題(請?jiān)谇袄ㄌ杻?nèi)選擇最確切的一項(xiàng)作為答案劃一個(gè)勾，多劃按錯(cuò)論)(每個(gè)4分，共40分)1 詞法分析器的輸出結(jié)果是。()單詞在符號表中的位置()單詞自身值B ( ) M1 和 M2 的有向邊條數(shù)相等D ( ) M1 和 M2 狀態(tài)數(shù)和有向邊條數(shù)相等A()單詞的種別編碼BC()單詞的種別編碼和自身值D2 正規(guī)式M1和M2等價(jià)是指。A()M1和M2的狀態(tài)數(shù)相等C()M1和M2所識別的語言集相等3 .文法G:SfxSx|y所識別的語言是一A ( ) xyxB. ()(xyx)*C.()xnyxn(n0)D.()x*yx*4 .

3、如果文法G是無二義的，則它的任何句子aA()最左推導(dǎo)和最右推導(dǎo)對應(yīng)的語法樹必定相同B()最左推導(dǎo)和最右推導(dǎo)對應(yīng)的語法樹可能不同C()最左推導(dǎo)和最右推導(dǎo)必定相同D()可能存在兩個(gè)不同的最左推導(dǎo)，但它們對應(yīng)的語法樹相同5 構(gòu)造編譯程序應(yīng)掌握。A()源程序B()目標(biāo)語言C()編譯方法D()以上三項(xiàng)都是6 四元式之間的聯(lián)系是通過實(shí)現(xiàn)的。A()指示器B()臨時(shí)變量C()符號表D()程序變量7 .表達(dá)式AVB)A(CVD)的逆波蘭表示為。A.()nABACDVB.()ACDVAC. ()ABVnCDVAD.()A小ACDV8 .優(yōu)化可生成的目標(biāo)代碼。A()運(yùn)行時(shí)間較短B()占用存儲空間較小C()運(yùn)行時(shí)間短

4、但占用內(nèi)存空間大D()運(yùn)行時(shí)間短且占用存儲空間小9 下列優(yōu)化方法不是針對循環(huán)優(yōu)化進(jìn)行的。A.()強(qiáng)度削弱B()刪除歸納變量C()刪除多余運(yùn)算D()代碼外提10編譯程序使用區(qū)別標(biāo)識符的作用域。A.()說明標(biāo)識符的過程或函數(shù)名B()說明標(biāo)識符的過程或函數(shù)的靜態(tài)層次C()說明標(biāo)識符的過程或函數(shù)的動態(tài)層次D.()標(biāo)識符的行號三、填空題(每空1分，共10分)1計(jì)算機(jī)執(zhí)行用高級語言編寫的程序主要有兩種途徑：_解釋_和_編譯_。2 掃描器是_詞法分析器_，它接受輸入的_源程序_，對源程序進(jìn)行_詞法分析_并識別出一個(gè)個(gè)單詞符號，其輸出結(jié)果是單詞符號，供語法分析器使用。3 自上而下分析法采用_移進(jìn)_、歸約、錯(cuò)誤

5、處理、_接受_等四種操作。4 一個(gè)LR分析器包括兩部分：一個(gè)總控程序和_一張分析表_。5 .后綴式abc-/所代表的表達(dá)式是a/(b-c)。6 局部優(yōu)化是在_基本塊_范圍內(nèi)進(jìn)行的一種優(yōu)化。四、簡答題(20分)1. 簡要說明語義分析的基本功能。答：語義分析的基本功能包括:確定類型、類型檢查、語義處理和某些靜態(tài)語義檢查。2. 考慮文法GS:Sf(T)|a+S|aTfT,S|S消除文法的左遞歸及提取公共左因子。解：消除文法GS的左遞歸：Sf(T)|a+S|aTfSTf,ST|提取公共左因子：Sf(T)|aSSf+S|&TfSTf,ST|s3. 試為表達(dá)式w+(a+b)*(c+d/(e-10)+8)寫

6、出相應(yīng)的逆波蘭表示。解：wab+cde10-/+8+*+4. 按照三種基本控制結(jié)構(gòu)文法將下面的語句翻譯成四元式序列：while(ACAB1)C=C+1;elsewhile(A&D)A=A+2;。解：該語句的四元式序列如下(其中E1、E2和E3分別對應(yīng)AvCABvD、AR1和AWD,并且關(guān)系運(yùn)算符優(yōu)先級高)：100(j,A,C,102)101(j,_,_,113)102(j,B,D,104)103(j,_,_,113)104(j=,A,1,106)105(j,_,_,108)106(+,C,1,C)107(j,_,_,112)108(jaAd|aAb|判斷該文法是否是SLR(1)文法，若是構(gòu)造相

7、應(yīng)分析表，并對輸入串a(chǎn)b#給出分析過程。解：增加一個(gè)非終結(jié)符S/后，產(chǎn)生原文法的增廣文法有：S-AA-aAd|aAb|下面構(gòu)造它的LR(0)項(xiàng)目集規(guī)范族為ab-dSA&十溢心A+aAbI21a疝4一Ii：SfInT吟MaccAT*辿AI：L：ATaT且TUb%今aAbI以TaAN%I;Is；從上表可看出，狀態(tài)I0和I2存在移進(jìn)-歸約沖突，該文法不是LR(0)文法。對于I0來說有：FOLLOW(A)na=b,d,#na二,0所以在I0狀態(tài)下面臨輸入符號為a時(shí)移進(jìn)，為b,d,#時(shí)歸約，為其他時(shí)報(bào)錯(cuò)。對于I2來說有也有與I0完全相同的結(jié)論。這就是說，以上的移進(jìn)-歸約沖突是可以解決的，因此該文法是SL

8、R(1)文法。其SLR(1)分析表為：AEONcomab(j聿80*ri匕11建”2ri藥Ti335.別4坨r此5XlXLXl11對輸入串a(chǎn)b#合出分析過程為:步驟狀態(tài)棧符號棧輸入率ACTIOMGOTO1pf#ab#冬202*bitXi53029b#S40234ftaAb烹41501訃A*acc第9頁共6頁編譯原理期末試題（二）、是非題:1 .一個(gè)上下文無關(guān)文法的開始符，可以是終結(jié)符或非終結(jié)符。（）2 .一個(gè)句型的直接短語是唯一的。3 .已經(jīng)證明文法的二義性是可判定的。4 .每個(gè)基本塊可用一個(gè)DA砧示。5 .每個(gè)過程的活動記錄的體積在編譯時(shí)可靜態(tài)確定。6.2型文法一定是3型文法。7 .一個(gè)句型

9、一定句子。（）8 .算符優(yōu)先分析法每次都是對句柄進(jìn)行歸約。X（）9 .采用三元式實(shí)現(xiàn)三地址代碼時(shí)，不利于對中間代碼進(jìn)行優(yōu)化。10 .編譯過程中，語法分析器的任務(wù)是分析單詞是怎樣構(gòu)成的。（）11 .一個(gè)優(yōu)先表一定存在相應(yīng)的優(yōu)先函數(shù)。X（）12 .目標(biāo)代碼生成時(shí)，應(yīng)考慮如何充分利用計(jì)算機(jī)的寄存器的問題。（）13 .遞歸下降分析法是一種自下而上分析法。（）14 .并不是每個(gè)文法都能改寫成LL（1）文法。（）15 .每個(gè)基本塊只有一個(gè)入口和一個(gè)出口。（）16 .一個(gè)LL（1）文法一定是無二義的。（）17 .逆波蘭法表示的表達(dá)試亦稱前綴式。（）18 .目標(biāo)代碼生成時(shí)，應(yīng)考慮如何充分利用計(jì)算機(jī)的寄存器的問

10、題。（）19 .正規(guī)文法產(chǎn)生的語言都可以用上下文無關(guān)文法來描述。（）20 .一個(gè)優(yōu)先表一定存在相應(yīng)的優(yōu)先函數(shù)。（）21 .3型文法一定是2型文法。（）22.如果一個(gè)文法存在某個(gè)句子對應(yīng)兩棵不同的語法樹，則文法是二義性的。（）()()()()()答案：1.X2.X3.X4.V5.V6.X7.X8.X9.V10.X11.X12.V13.義14.V15.V16.V17.義18.V19.V20.義21.V22.V、填空題：2.編譯過程可分為（詞法分析）代碼生成）五個(gè)階段。,（語法分析），（語義分析與中間代碼生成）,（優(yōu)化）和（目標(biāo)3.如果一個(gè)文法存在某個(gè)句子對應(yīng)兩棵不同的語法樹，則稱這個(gè)文法是（二義性

11、的）。4 .從功能上說，程序語言的語句大體可分為（執(zhí)行性）語句和（說明性5 .語法分析器的輸入是（單詞符號），其輸出是（語法單位）。）語句兩大類。6.掃描器的任務(wù)是從（源程序中）中識別出一個(gè)個(gè)（單詞符號）。7.符號表中的信息欄中登記了每個(gè)名字的有關(guān)的性質(zhì)，如（類型、種屬、所占單元大小、地址）等等。8.一個(gè)過程相應(yīng)的DISPLAY表的內(nèi)容為（現(xiàn)行活動記錄地址和所有外層最新活動記錄的地址）10 .常用的兩種動態(tài)存貯分配辦法是（棧式）動態(tài)分配和（堆式）動態(tài)分配。11 .一個(gè)名字的屬性包括（類型）和（作用域）。12 .常用的參數(shù)傳遞方式有（傳地址），（傳值），（傳名）13 .根據(jù)優(yōu)化所涉及的程序范圍，

12、可將優(yōu)化分成為（局部優(yōu)化），（循環(huán)優(yōu)化），（全局優(yōu)化）三個(gè)級別。14 .語法分析的方法大致可分為兩類，一類是（自上而下）分析法，另一類是（自下而上）分析法。15 .預(yù)測分析程序是使用一張（分析表）和一個(gè)（符號棧）進(jìn)行聯(lián)合控制的。17.一張轉(zhuǎn)換圖只包含有限個(gè)狀態(tài)，其中有一個(gè)被認(rèn)為是（初）態(tài)；而且實(shí)際上至少要有一個(gè)（終）態(tài)。19.語法分析是依據(jù)語言的（語法）規(guī)則進(jìn)行。中間代碼產(chǎn)生是依據(jù)語言的（語義）規(guī)則進(jìn)行的。21.一個(gè)文法G,若它的預(yù)測分析表M不含多重定義，則該文法是（LL（1）文法）文法。22.對于數(shù)據(jù)空間的存貯分配，F(xiàn)ORTRAN用（靜態(tài)策略，PASCAL采用（動態(tài)）策略。24 .最右推導(dǎo)亦

13、稱為（規(guī)范推導(dǎo)），由此得到的句型稱為（規(guī)范）句型。26 .對于文法G,僅含終結(jié)符號的句型稱為（句子）。27 .所謂自上而下分析法是指（從開始符號出發(fā)，向下推導(dǎo)，推出句子）29 .局限于基本塊范圍的優(yōu)化稱（局部優(yōu)化）。30 .2型文法又稱為（上下文無關(guān)）文法；3型文法又稱為（正則）文法。32 .每條指令的執(zhí)行代價(jià)定義為（指令訪問主存次數(shù)加1）33 .算符優(yōu)先分析法每次都是對（最左素短語）進(jìn)行歸約。三、名詞解釋題：1 .局部優(yōu)化局限于基本塊范圍的優(yōu)化稱。2 .二義性文法-如果一個(gè)文法存在某個(gè)句子對應(yīng)兩棵不同的語法樹，則稱這個(gè)文法是二義性文法。3 .DISPLAY表-過程的嵌套層次顯示表，記錄該過程

14、的各外層過程的最新活動記錄的起始地址。5 .最左推導(dǎo)任何一步”=3都是對口中的最右非終結(jié)符替換。6 .語法-一組規(guī)則，用它可形成和產(chǎn)生一組合式的程序。7 .文法-描述語言的語法結(jié)構(gòu)的形式規(guī)則。8 .基本塊-指程序中一順序執(zhí)行的語句序列，其中只有一個(gè)入口和一個(gè)出口，入口就是其中的第一個(gè)語句，出口就是其中的最后一個(gè)語句。9 .語法制導(dǎo)翻譯-在語法分析過程中，根據(jù)每個(gè)產(chǎn)生式所對應(yīng)的語義子程序進(jìn)行翻譯的辦法叫做語法制導(dǎo)翻譯。10 .短語-令G是一個(gè)文法，S劃文法的開始符號，假定a38是文法G的一個(gè)句型，如果有S=aAS且A上3,則稱3是句型a3相對非終結(jié)符A的短語。11 .待用信息-如果在一個(gè)基本塊中

15、，四元式i對A定值，四元式j(luò)要引用A值，而從i到j(luò)之間沒有A的其它定值，則稱j是四元式i的變量A的待用信息。12 .規(guī)范句型-由規(guī)范推導(dǎo)所得到的句型。13 .掃描器-執(zhí)行詞法分析的程序。14 .超前搜索-在詞法分析過程中，有時(shí)為了確定詞性，需超前掃描若干個(gè)字符。15 .句柄一個(gè)句型的最左直接短語。16 .語法制導(dǎo)翻譯-在語法分析過程中，根據(jù)每個(gè)產(chǎn)生式所對應(yīng)的語義程序進(jìn)行翻譯的方法叫做語法制導(dǎo)翻譯。17 .規(guī)范句型-由規(guī)范推導(dǎo)所得到的句型。18 .素短語-素短語是指這樣一個(gè)短語，至少含有一個(gè)終結(jié)符，并且，除它自身外不再含任何更小的素短語。19 .語法-是組規(guī)則，用它可形成和產(chǎn)生一個(gè)合式的程序。_

16、20 .待用信息-如果在一個(gè)基本塊中，四元式i對A定值，面元式j(luò)要引用A值，而從i到j(luò)之間沒有A的其它定值，則稱j是四元式i的變量A的待用信息。21 .語義-定義程序的意義的一組規(guī)則。四、簡答題：1 .寫一個(gè)文法G,使其語言為不以0開頭的偶數(shù)集。2 .已知文法G（S）及相應(yīng)翻譯方案SfaAbprint1”Sfaprint2”2ASprint3”2cprint4輸入acab,輸出是什么？3 .已知文法G（S）SfbAaAf（B|aBfAa）寫出句子b（aa）b的規(guī)范歸約過程。4 .考慮下面的程序：procedurep(x,y,z);beginy:=x+y;z:=z*z;endbeginA:=2;

17、B:=A*2;P(A,A,B);PrintA,BA, B的值是什么？end.試問，若參數(shù)傳遞的方式分別采用傳地址和傳值時(shí)，程序執(zhí)行后輸出5 .文法G(S)SfdABZaA|aBfBb|描述的語言是什么？6 .證明文法G(S)SfSaS|e是二義性的。7 .已知文法G(S)SfBAZBS|dBfaA|bS|c的預(yù)測分析表如下abcd#SSfBASfBASfBAA2BSZBS2BSKdBBfaABfbSBfc給出句子adccd的分析過程。8 .寫一個(gè)文法G,使其語言為L(G)=albmclanbn|l=0,m=1,n=29 .已知文法G(S):S-a|(T)T一T,S|S的優(yōu)先關(guān)系表如下:關(guān)系a(

18、),a-.(.=.,.請計(jì)算出該優(yōu)先關(guān)系表所對應(yīng)的優(yōu)先函數(shù)表。10 .何謂優(yōu)化？按所涉及的程序范圍可分為哪幾級優(yōu)化？11 .目標(biāo)代碼有哪幾種形式？生成目標(biāo)代碼時(shí)通常應(yīng)考慮哪幾個(gè)問題？12 .一字母表2=a,b，試寫出2上所有以a為首的字組成的正規(guī)集相對應(yīng)的正規(guī)式。13 .基本的優(yōu)化方法有哪幾種？14 .寫一個(gè)文法G,使其語言為L(G尸abncn|n015 .考慮下面的程序：procedurep(x,y,z);beginy:=y+z;z:=y*z+xend;begina:=2;b:=3;p(a+b,b,a);printaend.試問，若參數(shù)傳遞的方式分別采用傳地址和傳值時(shí)，程序執(zhí)行后輸出a的值是

19、什么?16 .寫出表達(dá)式ab*(c-d)/e的逆波蘭式和三元序列。17 .證明文法G(A)AfAA|(A)|是二義性的。18 .令2=a,b,則正規(guī)式a*b|b*a表示的正規(guī)集是什么？19 .何iDDISPLAY表？其作用是什么？20. 考慮下面的程序：procedurep(x,y,z)；beginy:=y+2;z:=z+x;endbegina:=5;b:=2;p(a+b,a-b,a);printaend.試問，若參數(shù)傳遞的方式分別采用傳地址和傳值時(shí)，程序執(zhí)行后輸出a的值是什么?21. 寫一個(gè)文法G,使其語言為L(G)=anbncm|n0為奇數(shù)，m0為偶數(shù)22. 寫出表達(dá)式a:=(b+c)*e

20、+(b+c)/f的逆波蘭式和三元序列。23. 一個(gè)文法G別是LL(1)文法的充要條件是什么？24. 已知文法GSSfS*aF|aF|*aFFf+aF|+a消除文法左遞歸和提公共左因子。25. 符號表的作用是什么？符號表查找和整理技術(shù)有哪幾種？答案：1.所求文法是GS:SfAB|BA02AD|CB-2|4|6|8g1|3|5|7|9|BA0|C2.輸出是42313.句子b(aa)b的規(guī)范歸約過程:步驟符號棧輸入串動作0#b(aa)b#預(yù)備1#b(aa)b#移進(jìn)2#b(aa)b#移進(jìn)3#b(aa)b#移進(jìn)4#b(Aa)b#歸約5#b(Ma)b#移進(jìn)6#b(Ma)b#移進(jìn)7#b(Bb#歸約8#bAb

21、#歸約9#bAb#移進(jìn)10#S#接受4 .傳地址A=6,B=16傳值A(chǔ)=2,B=45 .L(G尸danbm|n0,m06 .證明：因?yàn)槲姆℅S存在句子aa有兩個(gè)不同的最左推導(dǎo)，所以文法GS是是二義性的。S=SaS=SaSaS=aSaS=aaS=aaS=SaS=aS=aSaS=aaS=aa7 .句子adccd的分析過程：步驟符號棧輸入串產(chǎn)生式0#Sadccd#1#ABadccd#SfBA2#AAaadccd#BfaA3#AAdccd#4#Addccd#Afd5#Accd#6#SBccd#2BS7#Scccd#Bfc8#Scd#9#ABcd#Bfc10#Acd#11#Ad#12#dd#Afd13#

22、8 .所求文法是GS:S一ABA一aAc|DAbD|bBfaBb|aabb9.函數(shù)a(),f4244g552310 .優(yōu)化：對程序進(jìn)行各種等價(jià)變換，使得從變換后的程序出發(fā)，能產(chǎn)生更有效的目標(biāo)代碼。三種級別：局部優(yōu)化、循環(huán)優(yōu)化、全局優(yōu)化11 .目標(biāo)代碼通常采用三種形式：機(jī)器語言，匯編語言，待裝配機(jī)器語言模塊。應(yīng)著重考慮的問題：(1)如何使生成的目標(biāo)代碼較短；(2)如何充分利用寄存器，以減少訪問內(nèi)存次數(shù)；(3)如何充分利用指令系統(tǒng)的特點(diǎn)。12 .正規(guī)式a(a|b)*。13 .刪除多余運(yùn)算，代碼外提，強(qiáng)度削弱，變換循環(huán)控制條件，合并已知量，復(fù)寫傳播和刪除無用賦值。14 .文法GS:S一aB|aB一b

23、c|bBc15.傳值a=2傳地址a=1516.逆波蘭式:abcd-*e/+三元序歹U:oparg1arg2(1) -cd(2) *b(1)(3) /(2)e(4) +a(3)17 .證明：因?yàn)槲姆℅S存在句子()有兩個(gè)不同的最左推導(dǎo)，所以文法GS是是二義性的。A=AA=(A)A=()A=()A=AA=A=(A尸()18.(ab|ba)=a,b,ab,ba,aab,bba19 .Display表：嵌套層次顯示表由于過程嵌套允許內(nèi)層過程引用外層過程定義的數(shù)據(jù)，因此，當(dāng)一個(gè)過程運(yùn)行時(shí)必須跟蹤它的所有外層過程的最新活動記錄起始地址，display表就是用于登記每個(gè)外層過程的最新活動記錄起始地址。20

24、.傳地址a=12傳值a=521 .所求文法是GS:SfACZaaAbb|ab8ccC|cc22 .逆波蘭式abc+e*bc+f/+:=三元序歹Uoparg1arg2(1) +bc(2) *(1)e(3) +bc(4) /(3)f(5) +(2)(4)(6) ：=a(5)第13頁共6頁23 .一個(gè)文法G別是LL(1)文法的充要條件是：FIRST(a)AFIRST(3)=(2)如果3=*,FIRST()AFOLLOW(A)寸24.消除左遞歸SfaFS|*aFSS*aFS|Ff+aF|+a提公共左因子,文法G(S)SfaFS|*aFSS*aFS|Ff+aFFfF|e25.作用：登記源程序中出現(xiàn)的各種

25、名字及其信息，以及了解各階段的進(jìn)展?fàn)顩r。主要技術(shù)：線性表，對折查找，雜奏技術(shù)。五、計(jì)算題：1. 設(shè)文法G(S):S-AIaI(T)TfT,S|S消除左遞歸；構(gòu)造相應(yīng)的FIRST和FOLLOW!合；構(gòu)造預(yù)測分析表2. 語句ifEthenS(1) 改寫文法，使之適合語法制導(dǎo)翻譯；(2) 寫出改寫后產(chǎn)生式的語義動作。3. 設(shè)文法G(S)：5- (T)|aTfT+S|S(1)計(jì)算FIRSTVT和LASTVT；(2)構(gòu)造優(yōu)先關(guān)系表。4. 設(shè)某語言的for語句的形式為fori:=E(1)toE(2)doS其語義解釋為1: =LIMIT:=Eagain:ifi=LIMITthenBeginS;1: =i+1

26、gotoagainEnd;(1)寫出適合語法制導(dǎo)翻譯的產(chǎn)生式；(2)寫出每個(gè)產(chǎn)生式對應(yīng)的語義動作。5. 把語句whilea0thena:=a+1elsea:=a*3-1;翻譯成四元式序列。6. 設(shè)有基本塊D:=A-CE:=A*CF:=D*ES:=2T:=A-CQ:=A*CG:=2*SJ:=T*QK:=G*5L:=K+JM:=L假設(shè)基本塊出口時(shí)只有M還被引用，請寫出優(yōu)化后的四元序歹U。7. 已知文法G(S)5- a|人|(T)TfT,S|S(1) 給出句子(a,(a,a)的最左推導(dǎo)；(2) 給出句型(T,S),a)的短語,直接短語，句柄。8. 對于C語言doSwhileE語句(1) 改寫文法，使

27、之適合語法制導(dǎo)翻譯；(2) 寫出改寫后產(chǎn)生式的語義動作。9. 已知文法G(S)SfaAcBeAfAb|bBfd(1) 給出句子abbcde的最左推導(dǎo)及畫出語法樹；(2) 給出句型aAbcde的短語、素短語。10. 設(shè)文法G(S):Sf(T)|aS|aTfT,S|S消除左遞歸和提公共左因子；構(gòu)造相應(yīng)的FIRST和FOLLO僚合；構(gòu)造預(yù)測分析表。11. 把語句ifX0VY0doX:=A*3elseY:=B+3;翻譯成四元式序列。12. 已知文法G(S)EfE+T|TTfT*F|FF-(E)|i(1) 給出句型(i+i)*i+i的最左推導(dǎo)及畫出語法樹；(2) 給出句型(E+T)*i+F的短語，素短語

28、和最左素短語。13. 設(shè)文法G(S)：SfT|SvTTfU|T入U(xiǎn)Si|-U( 1)計(jì)算FIRSTVT和LASTVT；( 2)構(gòu)造優(yōu)先關(guān)系表。第15頁共 6 頁答案：(1)消除左遞，文法變?yōu)镚S：S-人IaI(T)T-ST|S一,SL|此文法無左公共左因子。(2)構(gòu)造相應(yīng)的FIRST和FOLLOW!合：第19頁共6頁FIRST(S尸a,人,(FIRST(T尸a,A,(FIRST(丁尸,(3)構(gòu)造預(yù)測分析表：FOLLOW(S)=#,)FOLLOW(T)=FOLLOW(F)=)aA(),#SS一aS一人S一(T)TTfSTT-STT-STT一e一,ST2.(1)C-ifEthenS-CS(1)(2

29、)8ifEthenBACK(E.TC,NXQ);C.chainkE.FC5- C01)S.chain:=MERG(C.Chain,S(1).Chain)3. (1)FIRSTVT(S)=a,(FIRSTVT(T尸+,aa,(LASTVT(S)=a,)LASTVT(T尸+,a,)a+()a.+(.(2)4. (1)Ffori:=EtoEdoS-FS(2)F-fori:=EtoEdoGEN(k,E(1).place,_,entry(i);F.place:=entry(i);LIMIT:=Newtemp;GEN(k，E.place,_,LIMIT);Q:=NXQ;F.QUADkq;GEN(j,ent

30、ry(i),LIMIT,q+2)F.chain:=NXQ;GEN(j,_,_,0)S-FS(1)BACKPATCH(.chain,NXQ);GEN(+,F.place,1,F.place);GEN(j,_,_,F.QUAD);S.chain:=F.chain5.(1)(j,c,0,(5)(4) (j,_,_,(8)(5) (+,a,1,T1)(6) (:=,T1,_,a)(7) (j,_,_,(1)(8) (*,a,13,T2)(9) (-,T2,1,T3)(10) (:=,T3,_,a)(11) (j,_,_,(1)6. 優(yōu)化后的四元序列D:=A-CE:=A*CF:=D*EM:=F+207.

31、 最左推導(dǎo)S=(T)=(T,S)=(S,S)=(a,S)=(a,(T)=(a,(T,S)=(a,(S,S)=(a,(a,S)=(a,(a,a)短語(T,S),a)(T,S),a(T,S)T,Sa直接短語T,Sa句柄T,S8. (1)SfdoMlSiwhileM2EMHg(2)1.nextlist, M2.quad);1.quad);)=a, (,)=，* )=, ), # )= )MHeM.quad=nestquad;SfdoMiSiwhileM2Ebackpatch(sbackpatch(E.truelist,MS.nextlist=E.falelist;9 .(i)S=aAcBe=AAbc

32、Be=abbcBe=abbcde(2) 短語:aAbcde,Ab,d素短語:Ab,d10 .(1)Sf(L)|aSSfS|L-SLLf,SL|e(2) FIRST(S)=a,(FIRST(SFIRST(L)=a,(FIRST(LFOLLOW(S)=,),#FOLLOW(SFOLLOW(L)=)FOLLOW(L()a,#SS-(L)S一aSS，S，一S1S一s，一s:S一S一LL-SLL-SLLfSLL，L一11 .(1)(j,X,0,(5)(2) (j,_,_,(3)(3) (j0,X,0,(7)(6) (j,_,_,(7)(7) (*,A,3,T1)(8) (：=,T1,_,N)(9) (j

33、,_,_,(5)(10) (j,_,_,(13)(11) (+,B,3,T2)(12) (:=,T2,_,Y)12 .(1)E=E+T=T+T=T*F+T=F*F+T=(E)*F+T=(E+T)*F+T=(T+T)*F+T=(F+T)*F+T=(i+T)*F+T=(i+F)*F+T=(i+i)*F+T=(i+i)*i+T=(i+i)*i+F=(i+i)*i+i(2)短語i,F,E+T,(E+T),(E+T)*i,(E+T)*i+F素短語i,E+T最左素短語E+T13 .(1)FIRSTVT(S)=V,A,i,-FIRSTVT(T)=A,i,-FIRSTVT(U)=i,-LASTVT(S)=V,

34、A,i,-LASTVT(T)=A,i,-LASTVT(U)=i,-(2)iVA-S.V.A.-. *b, a I b I #16：17：項(xiàng)目集規(guī)范族看出，不存在沖突動作。，該文法是LR(1)文法(2) LR(1)分析表如下：狀態(tài)ActionGotoQB/sAB0S4S5r31*31acc2rl3SiSir36S4S4國75rar5r56r2drlrl輸入用abab的分析過程為:步驟狀態(tài)梅符號技當(dāng)前了將軻泉字-符出動作0言ababu移進(jìn)04Sabab移進(jìn)045ijaba1h*歸的B-*b047-aE3b#歸的B4aEg比abu移進(jìn)(6)034鋁ab壯移造0315堀歸的B-b0317鋁aB#也均B-aB。黑sfBB白約A-*10：0336鋁BA典約A-BA(11)M6SBA9叫囪ATBA(12)。二二A后約5-A0*5簡答題3、設(shè)有文法GS:S-S（S）S8,該文法是否為二義文法？說明理由。答：是二義的，因?yàn)閷τ冢ǎǎ┛梢詷?gòu)造兩棵不同的語法樹。SSS ( S ) S、S ( S ) S/ /(SaQ|bD|b;AbB|aA;E-aB|bFFfbD|aE|b構(gòu)造相應(yīng)的最小的DFA。解：先構(gòu)造其NFA:abSAQAABZQQDZBZQDDZABDABBQD用子集法將NFA確定化:將S、A、Q、BZ、DZ、D、B重新命名，分