編譯原理練習(xí)題一

一、選擇題

1. 下列文法中，           不是產(chǎn)生語言 {abⁿa∣n≥1} 的文法。

A．A→aBa        B→b∣bB        B．A→aB          B→ba∣bB       

C．A→aB         B→ba∣bBa      D．A→aB          B→bC         C→bC∣a

2. 設(shè)有文法G[S]：S→aAB       A→bAc∣ε       B→bB∣Ae∣ε

則經(jīng)消去ε-產(chǎn)生式后與G等價的文法G₁[S]為             。

A．S→aA∣aB∣aAB∣a       A→bc∣bAc        B→bB∣Ae∣b∣e

B．S→aAB       A→bAc      B→bB∣Ae        

C．S→aA∣aB      A→bc     B→b∣e

D．S→aA∣aB∣a       A→bc∣bAc      B→bB∣Ae∣b∣e

3. 下列文法中，           是LL(1)文法。      

A．S→bBS′a     S′→aBS′∣ε   A→S∣a    B→Ac

B．S→bS∣bA∣b     A→aA∣a             

C．E→E+T∣T    T→T*F∣F     F→(E)∣i

D．S→bBS′      S′→aBS′∣ε   A→S∣a    B→Ac

4. 下列文法中，           是簡單優(yōu)先文法。       

A．E→E+T∣T    T→T*F∣F      F→(E)∣i            

B．S→A/        A→aA∣AS∣/

C．E→E+E∣E*E∣(E)∣i      

D．E→E₁   E₁→E₁+T₁∣T₁     T₁→T   T→T*F∣F   F→(E)∣i

5. 當(dāng)掃視到數(shù)組說明進(jìn)行語義處理時，必須把一個數(shù)組的如維數(shù)、各維的上、下界等記錄下來。為了便于引用，通常是把上述內(nèi)容存放于數(shù)組相應(yīng)的            之中。

A．信息向量        B．內(nèi)情向量       C．地址向量       D．指針向

6. 設(shè)有文法G[S]：   S→aS∣W∣U       U→a           V→bV∣ac      W→aW

則經(jīng)化簡后與G等價的文法G₁[S]為           。

A．S→aS∣W          V→bV∣ac      W→aW          

B．S→aS∣U          U→a      

C．S→aS∣W∣U       U→a           W→aW          

D．S→aS             V→bV∣ac

7. 下列文法中，          是LL（1）文法。    

A．S→aS∣aA         A→bA∣ac              

B．S→AS∣b          A→SA∣a

C．E→E+E∣E*E∣(E)∣i                      

D．S→aS∣bA         A→bA∣ac

8. 所謂相容，是指在一個項(xiàng)目集中，不出現(xiàn)這樣的情況，            和歸約項(xiàng)目并存，或多個歸約項(xiàng)目并存。    

A．移進(jìn)項(xiàng)目        B．基本項(xiàng)目      C．待約項(xiàng)目        D．后繼項(xiàng)目

9. 下列表示中，            不是目前經(jīng)常使用的中間語言的形式。  

A．逆波蘭式        B．四元式       C．五元式       D．樹形表示

10. 如果從流程圖的首結(jié)點(diǎn)到流程圖中某一結(jié)點(diǎn)n的所有通路都要經(jīng)過結(jié)點(diǎn)d，我們就說結(jié)點(diǎn)d控制了結(jié)點(diǎn)n，或者把d稱為n的必經(jīng)結(jié)點(diǎn)，記作            。  

A．d DFA n        B．d DOM n       C．d DAG n       D．d DAM n

二、證明題

1、試證明文法    S→aB∣bA     A→aS∣bAA∣a     B→aBB∣bS∣b    為二義性文法。

三、簡答題

對于如下文法，求各候選式的FIRST集和各非終結(jié)符號的FOLLOW集。

S→ACAB|bA|ε        A→aAd|e        B→bB|c    C→cC|

四、應(yīng)用題    

1、對于如下的狀態(tài)轉(zhuǎn)換矩陣

分別畫出相應(yīng)的狀態(tài)轉(zhuǎn)換圖；（10分）       (2) 寫出相應(yīng)的3型文法。

2、將如圖所示的DFA最小化。

五、應(yīng)用題

1、設(shè)有文法G[E]：    E→E+T|T        T→T*F|F       F→(E)|i 

其相應(yīng)的算符優(yōu)先矩陣如下圖所示，試給出對符號串i*i+i進(jìn)行算符優(yōu)先分析的過程。

2、

試描述由文法：S→aAd      A→aAd∣bBc      B→bBc∣e      所產(chǎn)生的語言。

六、應(yīng)用題

1、設(shè)有文法G[S]： S→aABb      A→Acd∣d     B→Bce∣e

(1) 將其改寫為LL(1)文法；

(2) 構(gòu)造改寫后文法的LL(1)分析表。

2、已知文法G[S]：S→aAB     A→bA∣a    B→cB∣b   的LR(0)項(xiàng)目集及狀態(tài)轉(zhuǎn)換圖如下圖所示，

(1) 構(gòu)造LR(0)分析表；      (2) 給出對輸入符號串a(chǎn)bacb的LR分析過程。

七、簡答題

1、設(shè)有

......詳細(xì)資料請下載