編譯原理模擬試題五

1、編譯原理模擬試題五一、是非題（請(qǐng)?jiān)诶ㄌ?hào)內(nèi)，正確的劃，錯(cuò)誤的劃×）（每個(gè)2分，共20分）1編譯程序是對(duì)高級(jí)語言程序的解釋執(zhí)行。(× )2一個(gè)有限狀態(tài)自動(dòng)機(jī)中，有且僅有一個(gè)唯一的終態(tài)。(×)3一個(gè)算符優(yōu)先文法可能不存在算符優(yōu)先函數(shù)與之對(duì)應(yīng)。 ( )4語法分析時(shí)必須先消除文法中的左遞歸 。 (×)5LR分析法在自左至右掃描輸入串時(shí)就能發(fā)現(xiàn)錯(cuò)誤，但不能準(zhǔn)確地指出出錯(cuò)地點(diǎn)。 ()9兩個(gè)正規(guī)集相等的必要條件是他們對(duì)應(yīng)的正規(guī)式等價(jià)。 (× )10一個(gè)語義子程序描述了一個(gè)文法所對(duì)應(yīng)的翻譯工作。 (×)二、選擇題(請(qǐng)?jiān)谇袄ㄌ?hào)內(nèi)選擇最確切的一項(xiàng)作為答案劃

2、一個(gè)勾，多劃按錯(cuò)論)(每個(gè)4分，共40分)1詞法分析器的輸出結(jié)果是_。A 單詞的種別編碼 B單詞在符號(hào)表中的位置C 單詞的種別編碼和自身值 D. 單詞自身值2 正規(guī)式 M 1 和 M 2 等價(jià)是指_。  A( ) M1和M2的狀態(tài)數(shù)相等          B( ) M1和M2的有向邊條數(shù)相等C( ) M1和M2所識(shí)別的語言集相等 D( ) M1和M2狀態(tài)數(shù)和有向邊條數(shù)相等 3 文法G：SxSx|y所識(shí)別的語言是_。A( ) xyx  B( ) (xyx)* C( ) xnyxn(n0)  

3、60;  D( ) x*yx* 4如果文法G是無二義的，則它的任何句子_。A( )最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語法樹必定相同 B( ) 最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語法樹可能不同 C( ) 最左推導(dǎo)和最右推導(dǎo)必定相同   D( )可能存在兩個(gè)不同的最左推導(dǎo)，但它們對(duì)應(yīng)的語法樹相同 5構(gòu)造編譯程序應(yīng)掌握_。A( )源程序   B( ) 目標(biāo)語言       C( ) 編譯方法      D( ) 以上三項(xiàng)都是 8. 優(yōu)化可生成_運(yùn)行時(shí)間短且占用存儲(chǔ)空間小_的目標(biāo)代碼

4、。三、填空題(每空1分，共10分)1計(jì)算機(jī)執(zhí)行用高級(jí)語言編寫的程序主要有兩種途徑：_解釋_和_編譯_。 2掃描器是_詞法分析器_，它接受輸入的_源程序_，對(duì)源程序進(jìn)行_詞法分析_并識(shí)別出一個(gè)個(gè)單詞符號(hào)，其輸出結(jié)果是單詞符號(hào)，供語法分析器使用。3自上而下分析法采用_移進(jìn)_、歸約、錯(cuò)誤處理、_接受_等四種操作。4一個(gè)LR分析器包括兩部分：一個(gè)總控程序和_一張分析表_。5后綴式abc-/所代表的表達(dá)式是_a/(b-c)_。 四、簡(jiǎn)答題（20分）1. 簡(jiǎn)要說明語義分析的基本功能。答：語義分析的基本功能包括: 確定類型、類型檢查、語義處理和某些靜態(tài)語義檢 查。2. 考慮文法 GS: S (T) | a+

5、S | a T T,S | S 消除文法的左遞歸及提取公共左因子。解：消除文法GS的左遞歸： S(T) | a+S | a TST T,ST| 提取公共左因子： S(T) | aS S+S | TST T,ST| 5. 已知文法 GS 為 S aSb|Sb|b ，試證明文法 GS 為二義文法。證明：由文法GS：SaSb|Sb|b，對(duì)句子aabbbb對(duì)應(yīng)的兩棵語法樹為： 因此，文法GS為二義文法。 五.計(jì)算題（10分）已知文法 A->aAd|aAb| 判斷該文法是否是 SLR(1) 文法，若是構(gòu)造相應(yīng)分析表，并對(duì)輸入串 ab# 給出分析過程。解：增加一個(gè)非終結(jié)符S/后，產(chǎn)生原文法的增廣文法有：S'->A A->aAd|aAb| 下面構(gòu)造它的LR(0)項(xiàng)目集規(guī)范族為： 從上表可看出,狀態(tài)I0和I2存在移進(jìn)-歸約沖突，該文法不是LR(0)文法。對(duì)于I0來說有：FOLLOW(A)a=b,d,#a=，所以在I0狀態(tài)下面臨輸入符號(hào)為a時(shí)移進(jìn)，為b,d,#時(shí)歸約，為其他時(shí)報(bào)錯(cuò)。