編譯原理各章習題

本文格式為Word版，下載可任意編輯——編譯原理各章習題其次章高級語言及其語法描述1、設有文法G[S]：S→NN→D|NDD→0|1|2|…|9

試寫出028和4321的最左推導和最右推導過程。2、證明文法G[S]是二義性文法：S→ifEthenSelseS|ifEthenS|sE→0|1

3、設有文法G[E]：E→E-T|TT→T/F|FF→i|(E)

（1）試寫出i/(i-i-i)的推導樹。

（2）試寫出（F-i）/F的短語、簡單短語和句柄。4、設∑={0,1}，請給出∑上以下語言的文法（1）所有以0開頭的串

（2）所有以0開頭，以1結(jié)尾的串5、證明文法G1和G2等價G1：S→0S1，S→01G2：A→0R，A→01，R→A1第三章有限狀態(tài)自動機和詞法分析1、請用中文描述以下正規(guī)式表示的正規(guī)集（1）0(0|1)*0（2）0*10*10*10*

2、試寫出∑＝{0，1}上以下集合的正則表達式：（1）所有以1開始和終止的符號串。（2）恰含有3個1的所有符號所組成的集合。（3）集合{01，1}。

（4）所有以111終止的符號串。

3、試寫出∑＝{0，1}上下述集合的正則表達式：（1）試寫出非負整數(shù)集的正則表達式。

（2）試寫出以非5數(shù)字為頭的所有非負整數(shù)集的正則表達式。4、試將圖3.1中所示的有限狀態(tài)自動機M最小化。

圖3.1M的狀態(tài)轉(zhuǎn)換圖

5、設∑＝{a,b}，試構(gòu)造下述正則表達式的確定性有限狀態(tài)自動機：（1）a(a|b)*baa（2）(a|b)*bbb*

6、對于以下的狀態(tài)轉(zhuǎn)換矩陣：

SABaAABbSBB^ZSABaABBbSAB^Z（1）分別畫出相應的狀態(tài)轉(zhuǎn)換圖。

（2）用自然語言分別描述它們所識別的輸入串的特征7、將圖3.2所示的非確定的有限狀態(tài)自動機確定化和最小化。

圖3.2非確定的有限狀態(tài)自動機M

第四章自頂向下語法分析1、從以下文法中消去左遞歸。

（1）S→Aa|bA→Ac|Sd（2）A→A∨B|BB→B∧C|CC→?D|DD→(A)|i

2、請消去下面文法G[S]中的回溯G[S]：S→aBc|aB→bB|?3、有文法G[S]：

S→ABA→a|?B→b|?

（1）驗證該文法是LL(1)文法；（2）請構(gòu)造預計分析表4、考慮文法G[A]：

A→aABc|d|?B→Bb|b

（1）改寫為LL(1)文法；（2）請構(gòu)造預計分析表（3）給出句子adbc的分析過程第五章自底向上語法分析

1、請對以下文法G[S]構(gòu)造算符優(yōu)先分析表

S→bAbA→(B|aB→Aa)2、文法G[S]：S→S(SaS→b

該文法是LR(0)還是SLR(1)文法？3、文法G[A]：A→(A)|a

構(gòu)造該文法的LR(0)分析表，并請描述((a))的分析過程。4、文法G[S]:S→(S)S→?

（1）這個文法是例如LR(0)文法嗎？若是，請構(gòu)造該文法的LR(0