廣東工業(yè)大學(xué) 編譯原理 模擬試卷4

編譯原理試題題號一二三四五六七八九題號一二三四五六七八九十總分滿分得分選擇題【 】1．詞法分析器的輸入是 。A．符號串 B．源程序 C．語法單位 D．目標(biāo)程序【 】2．兩個有窮自動機等價是指它們的 。狀態(tài)數(shù)相等C

有向弧數(shù)相等D【 】3．文法G：S→xSx|y所識別的語言是 。A．xy*x B．(xyx)* C．xx*yxx* D．x*yx*【 】4．設(shè)a,b,c為文法的終結(jié)符，且有優(yōu)先關(guān)系ab和bc，則 。必有C．必有

必有caD．選項、BC【 5．若狀態(tài)k含有項目Aα，且僅當(dāng)輸入符號FOLLOW(A時，才用規(guī)則A→α”歸約的語法分析方法是 。A．LALR分析法C．LR(1)分析法二判斷題1、一個LL(l)文法一定是無二義的。

B．LR(0)分析法D．SLR(1)分析法2、逆波蘭法表示的表達式亦稱前綴式。3、算符優(yōu)先關(guān)系表不一定存在對應(yīng)的優(yōu)先函數(shù)。4、同心集的合并有可能產(chǎn)生“移進/歸約”沖突。5、若主程序為0層,過程p層次為k，則p的DISPLAY表中就有k+1個元素。三填空題1、詞法分析的任務(wù)是中識別出一個。2、在分析法中，且aVT則稱“S.A”為 項目，稱.aβ”為 項目。3、規(guī)范規(guī)約每次規(guī)約的是句型。算符優(yōu)先分析法每次規(guī)約的是當(dāng)前句的 。四寫一個文法，使其語言是奇數(shù)集，且每個奇數(shù)不以0開頭。五已知文法S→a|(T)T→T，S|S給出句子（，）的最左推導(dǎo)并畫出語法樹；給出句型，）的短語、直接短語、句柄。六把語句ifx＞0andy＞0thenz：＝x＋yelsebeginx：＝x＋2y：＝y(tǒng)＋3end；翻譯成四元式序列。七設(shè)文法F→*aF|*a消除左遞歸和左因子；FIRSTFollow集合；構(gòu)造預(yù)測分析表。八設(shè)有以下程序段programmain;vara,b:integer;procedurep(x,y,z:integer);beginy:=y+1;z:=z+xend;begina:=2;b:=3;p(a+b,a,a);write(a)end.對于下列參數(shù)傳遞方式，分別寫出執(zhí)行程序后a的輸出值。傳名；傳地址。九下列文法是否為SLR(1)文法？若是，請構(gòu)造相應(yīng)的分析表。若不是，請說明理由。SSab|bRRS|a十文法S(L)|aLL,S|S(a,((a,a),(a,的一個最右推導(dǎo)；按照(a)的最右推導(dǎo)，給出移進－歸約分析器的工作步驟。PL/0:+= ++‘＋＝（設(shè)單詞內(nèi)碼分別為和PLUSPLUS）的詞法分析算法：if(CH=='＋'){① ;if( ② { )SYM=PLUSBECOME; GetCh();}elseif(CH=='+'){③}else④}答案一選擇題b,C,D,D,C二判斷題√×√×√三填空題源程序 單詞符號待約項目移進項目句柄 最左素短.解：文法S→AB|B|A0A→AD|CB→2|4|6|8C→1|3|5|7|9|BD→0|C五（，S，a2）2分）（（，S，a（T，S）a1分a1分）TS六 解（（0，0，）（2（，－，－）（3（＞，，0，）（4（，－，－）（5（＋x，，）（6（：＝1，－）（7（，－，－1）（8（＋x2）（9（：＝2，－）（10（＋，3）（1（：＝，－）（12）七.解：1（消除左遞歸，提公因左因子）S'→＋aFS'|εF→*aF'F'→F|ε（2）FIRST（S）＝｛a，十｝ FOLLOW（S）＝｛＃｝FIRST（50）＝｛＋，ε｝FOLLOW（S'）＝｛＃｝FIRST（F'）＝｛*，ε｝ FOLLOW（＋，＃｝八九. 該文法的拓廣文法為：(0)S (1)S(2)SbR (3)RS(4)Ra其LR(0)項目集規(guī)范族如下:I0:S’S·S·SabS·bRI1:S’S·

I3:SSa·bI4:SbR·I5:RS·SS·abI6:Ra·SS·abI2:SI7:SR·SR·aS·SabS·bR文法G’的識別活前綴的DFA如下所示：I0I0SI1aI3bI7abSI5I2bRI4aI6FOLLOW(S)=FOLLOW?={a,$}構(gòu)造的SLR分析表如下：狀態(tài)actiongotoa b$狀態(tài)actiongotoa b$SR0S211S3acc2S6S2543S74r2r25r3/S3r36r4r47r1r1可歸 納又可移進即存在為重定義的 入口。所以，該文法不是SLR(1)文法。十.(a)S(L(L,S(L,(L))(L,(L,S)(L,(L,(L)))(L,(L,(L,S)))(L,(L,(L,a)))(L,(L,(S,a)))(L,(L,(a,a)))(L,(S,(a,a)))(L,((L),(a,a)))(L,((L,S),(a,a)))(L,((L,a),(a,a)))(L,((S,a),(a,a)))(L,((a,a),(a,a)))(S,((a,a),(a,a)))(a,((a,a),(a,a)))(注：下劃線部分為句柄)3434$(a$(S,((a,a),(a,a)))$,((a,a),(a,a)))$步驟棧輸入動作1 $(a,((a,a),(a,a)))$移進2 $(a,((a,a),(a,a)))$移進5$(L,((a,a),(a,a)))$移進6$(L,((a,a),(a,a)))$移進7$(L,((a,a),(a,a)))$移進8$(L,((a,a),(a,a)))$移進9$(L,((a,a),(a,a)))$歸約，Sa10$(L,((S,a),(a,a)))$歸約，LS11$(L,((L,a),(a,a)))$移進12$(L,((L,a),(a,a)))$移進13$(L,((L,a),(a,a)))$歸約，Sa14$(L,((L,S),(a,a)))$歸約，LL,S15$(L,((L),(a,a)))$移進16$(L,((L),(a,a)))$歸約，S(L)17$(L,(S,(a,a)))$歸約，LS18$(L,(L,(a,a)))$移進19$(L,(L,(a,a)))$移進20$(L,(L,(a,a)))$移進21$(L,(L,(a,a)))$歸約，Sa22$(L,(L,(S,a)))$歸約，LS23$(L,(L,(L,a)))$移進24$(L,(L,(L,a)))$移進25$(L,(L,(L,a)))$歸約，Sa26$(L,(L,(L,S)))$歸約，