《編譯原理》習(xí)題整理

1、1101、“多遍掃描的編譯程序是高質(zhì)量的編譯程序，優(yōu)于單遍掃描的程序”，這種說法正確嗎？編譯程序采用多遍還是單遍需要考慮哪些因素？答：不一定。多遍編譯器結(jié)構(gòu)清晰，構(gòu)造時間短，運(yùn)行時需內(nèi)存少，產(chǎn)生的目標(biāo)代碼質(zhì)量高，但時間效率低。采用幾遍應(yīng)考慮：（1）語言的大小與結(jié)構(gòu)（2）機(jī)器規(guī)模（3）設(shè)計目的2、詞法分析和語法分析都是對字符串進(jìn)行識別的，二者有何區(qū)別？答：（1）詞法分析的輸入是源程序，它識別的對象是由字母、數(shù)字等組成的單詞符號，輸出的單詞

2、符號序列（2）語法分析的輸入是單詞符號序列（單詞符號是不可分割的語法單位），它識別的是句子，即單詞符號序列是否是個合法的句子（程序）。3、算符優(yōu)先分析法每次都是對最左素短語進(jìn)行歸約，LR分析法每次都是對句柄進(jìn)行歸4、試描述下面文法產(chǎn)生的語言。S→SAS|b|cA→aaA|a答：b，c，或者是以(b|c)開頭、以(b|c)結(jié)尾的、中間是任意個由(b|c)間隔開的奇數(shù)個a組成的字符串形如：SAS，SASAS，SASASAS，…不是正規(guī)語言，

3、不能用正規(guī)式表示5、試構(gòu)造生成下列語言的文法:L=anbnci|n=1i=0文法：S→ABA→aAb|abB→cB|ε兩者必須等價6、考慮文法：G：A→A∨B|BC→D|DB→B∧C|CD→(A)|I該文法LL（1）文法。a.是b.不是b7、LL（1）文法二義的。a.都是b.都不是c.不一定都是b8、為正規(guī)表達(dá)式(0│1)11(0│1)構(gòu)造一個最小化DFA。1、一個正規(guī)語言只能對應(yīng)(b)a.一個正規(guī)文法b.一個最小有限狀態(tài)自動機(jī)2、一個

4、上下文無關(guān)文法消除了左遞歸，提取了左公因子后是滿足LL（1）文法的(a)a.必要條件b.充分必要條件3、文法G[A]：A→bA→ABB→AbB→a是(a)a.二型文法b.正規(guī)文法4、文法G[A]：A→εA→aBB→AbB→a是(b)a.正規(guī)文法b.二型文法3109、給定下列文法和翻譯方案:S→bTcprint”1”S→aprint”2”T→Rprint”3”R→RSprint”4”R→Sprint”5”(1)是什么類型的語法制導(dǎo)定義(2

5、)bRbTcbScac是否為該文法的一個句型(3)對于上面符號串該翻譯方案輸出什么答:(1)是什么類型的語法制導(dǎo)定義(2)bRbTcbScac是否為該文法的一個句型是SbTcRRSRSRSbTcbTcRSS→bTcprint”1”S→aprint”2”T→Rprint”3”R→RSprint”4”R→Sprint”5”a(3)對于上面符號串對于上面符號串該翻譯方案輸出什么該翻譯方案輸出什么1453142431練習(xí):1.文法:Z→U0|V

6、1U→Z1|1V→Z0|0???請寫出全部由此文法描述的只含有四個符號的句子????該文法是?????????幾型文法?1.文法:Z→U0|V1U→Z1|1V→Z0|0請寫出全部由此文法描述的只含有四個符號的句子???????????????????????????該文法是?????????幾型文法???型文法2、給定前綴表示的表達(dá)式文法G:(1)E→EE(2)E→E(3)E→a(4)E→b(5)E→c試問abc是否L(G)的句子若是請