《編譯原理與技術(shù)》期末考試試卷答案 05(軟件學(xué)院)

1、參考答案及評(píng)分標(biāo)準(zhǔn)一、填空（15分，每空1分）1高級(jí)，低級(jí)2源程序，單詞3自頂向下4綜合，繼承5結(jié)構(gòu)，名稱6非局部名字訪問，參數(shù)傳遞7上下文有關(guān)，上下文無關(guān)，正規(guī)8abcd+*+二、（15分）答：正規(guī)表達(dá)式（4）代表了這個(gè)程序段所有可能走過的全部步序列（5分）把A,T,B,I分別代表相應(yīng)的基本塊，E表示程序段的出口，則程序段可以表示為如下的流（程）圖：（5分） A T B I E轉(zhuǎn)換為等價(jià)的確定狀態(tài)自動(dòng)機(jī)如下： T 0 1 2 3 4 A T B I由上述確定狀態(tài)自動(dòng)機(jī)可以得到等價(jià)的正規(guī)表達(dá)式為：AT(BIT)*（5分）如果沒有畫流程圖而直接給出自動(dòng)機(jī)可以給分。既沒有畫流程圖，也沒有畫自動(dòng)機(jī)，

2、可以根據(jù)描述的理由是否能說明清楚酌情給分。三、（20分）答：1FIRST(S)=a,bFOLLOW(S)=$FIRST(A)=a,bFOLLOW(A)=b,$FIRST(B)=b,FOLLOW(B)=c,$(6分，每個(gè)1分)。2LL(1)分析表如下：（7分）abc$SaBcbABAaAbbBb3分析符號(hào)串baabbb是否為該文法的句子的過程如下表所示：（7分）步驟棧輸入串輸出1$Sbaabbb$2$BAbbaabbb$S bAB3$BAaabbb$4$BbAaaabbb$A aAb5$BbAabbb$6$BbbAaabbb$A aAb7$BbbAbbb$8$Bbbbbbb$A b9$Bbbbb

3、$10$Bbb$11$B$12$B 四、（25分）答：1文法G的拓廣文法G如下：（10分）SSS AadAbBbdBaA cB c 構(gòu)造識(shí)別所有活前綴的確定有限狀態(tài)自動(dòng)機(jī)（DFA）如下：SS, $ I1 I2 I6 S Aa,$S Aa,$ a S Bb,$S Bb,$SS,$S Aa,$S dAb,$S Bb,$S dBa,$A c,aB c,b I0 S A I3 I7 B b S dAb,$S dAb,$S dAb,$S dBa,$A c,bB c,a I4 I8 I11 d A b I9 I12 S dBa,$S dBa,$ B a cA c,bB c,a I5 c I10 A c,a

4、B c,b2文法的LR(1)分析表如下：（10分）狀態(tài)actiongotoabcd$SAB0S5S41231acc2S63S74S10895r5r66r17r38S119S1210r6r511r212r4從分析表中可知沒有多重表項(xiàng)，因此該文法是LR(1)文法3由識(shí)別所有活前綴的確定有限狀態(tài)自動(dòng)機(jī)（DFA）可知，存在同心集I5和I10，合并后的LR(1)項(xiàng)目集為：A c,a/b B c,a/b，可見在該項(xiàng)目集中存在歸約-歸約沖突，因此該文法不是LALR(1)文法。（5分）五、（10分，每小題5分）答：1A：array(1.100, record(xinteger)(ychar)2func：int

5、eger(integerpointer(integer)record(iinteger)(cchar)六、（15分）答：當(dāng)分析器的輸入為aacbb時(shí)翻譯結(jié)果是：12020（5分）方法一：aacbb的分析樹如下： A a B A b a B A b c由于分析器采用移進(jìn)-歸約的方式進(jìn)行，歸約時(shí)使用產(chǎn)生式的順序?yàn)椋篈 c，B Ab，A aB，B Ab，A aB，因此打印結(jié)果為：12020。方法二：句子aacbb的最右推倒為：A=aB=aAb=aaBb=aaAbb=aacbb。歸約過程是最右推導(dǎo)的逆，從右向左考察推導(dǎo)過程中使用的產(chǎn)生式即為歸約過程采用的順序，因此打印結(jié)果為：12020。方法三：移進(jìn)-歸約的分析步驟如下：棧輸入串動(dòng)作輸出$aacbb$移進(jìn)$aacbb$移進(jìn)$aacbb$移進(jìn)$aacbb$歸約，A c1$aaAbb$