20112012安徽大學(xué)編譯原理補(bǔ)考試卷

1、安徽大學(xué)20 11 20 12 學(xué)年第 一 學(xué)期 編譯原理 考試試卷（B卷）（閉卷 時(shí)間120分鐘）院/系 年級(jí) 專業(yè) 姓名 學(xué)號(hào) 題 號(hào)一二三四五六七總分得 分得分一、（15分）設(shè)字母表=a，b，1. 寫出不是以a開頭，但以aa結(jié)尾的字符串集合的正規(guī)表達(dá)式r（5分）。 2. 構(gòu)造NFA M，使得 L（M）=L（r）；（5分）3. 將NFA M 確定化、最小化，得到DFA M1，使得L（M1）=L（M）。（5分）得分二、（20分）設(shè)文法GS如下：Si（B）SASaAeSABb1（5分）求出各非終結(jié)符的first集合和follow集合，填入下表：非終結(jié)符firstfollowSAB2（10分）構(gòu)

2、造預(yù)測(cè)分析表，填入下表：則規(guī) 終結(jié)符非終結(jié)符abei#SAB3（5分）該文法是LL（1）文法嗎？請(qǐng)說明理由。得分三 、（20分）設(shè)文法GS： SaSSbS Sa1. 文法GS屬于喬姆斯基哪一型文法？（2分）2. 符號(hào)串a(chǎn)bbaa 是不是該文法的一個(gè)句型？請(qǐng)證實(shí)。（方法不限）（3分）3. 若是句型，寫出該句型的所有短語、直接短語、素短語、最左素短語以及句柄（5分）4. 求出該文法的firstvt集和lastvt集，構(gòu)造算符優(yōu)先關(guān)系表填入下表。（10分）firstvtlastvtSSab#ab#四、（25分）設(shè)CFG文法GS如下：SaABeAAbcAbBd1（4分）寫出該文法的拓廣文法：2（9分）

3、構(gòu)造識(shí)別全部活前綴的DFA，填入下表：I0：S ·SS·aABe I1I2I3I4I5I6I7I9I8 S e a B A b c b d3（5分）構(gòu)造該文法的LR（0）分析表，填入下表：Iactiongotoabcde#SAB01234567894（7分）將abbc的分析過程填入下表：步驟狀態(tài)棧符號(hào)棧余留符號(hào)串a(chǎn)ctiongoto說明S0S1S2S3S4R0R1R2R3R41234567五、（5分）對(duì)于下面的程序 program test (input，output)； var a ：integerprocedure cala（x：integer); temp：integ

4、er； begin x:=a+1; temp:=a+2; x:=temp; end; begin a=2;cala ( a )；writeln（a） end.若參數(shù)傳遞的辦法分別為傳名，傳地址，傳結(jié)果，傳值，則最終打印的a值分別是多少？六、（5分）設(shè)基本塊如下：得 分A：=B*CD：=B/CE：=A+DF：=2*EG：=B*CH：=G*GF：=H*GL：=FM：=L構(gòu)造相應(yīng)的DAG，并寫出利用DAG優(yōu)化后的語句序列；（5分）七、（10分）設(shè)程序段如下：read Aread BF：=1C： =A*AD： =B*Bif CD goto L1E： =A*AF： =F+1E： =E+Fwrite Ehalt L1：E：=B*BF：=F+2write Eif E100 goto L2halt L2：F：=F-1goto L1 利用基本塊劃分方法構(gòu)造該代碼段的程序流圖（3分）；