北方工業(yè)大學(xué)編譯原理習(xí)題集（精編版）

1、編譯原理課后習(xí)題修訂版第二章高級語言與其語法描述3、何謂“標(biāo)識符，何謂“名字，兩者的區(qū)別是什么？解：標(biāo)識符是高級語言中定義的字符串，一般是以英文字母包括大小寫字 母或下劃線開頭的，由數(shù)字、字母和下劃線組成的一定長度的字符串，它只是 一個(gè)標(biāo)志，沒有其他含義。 名字是用標(biāo)識符表示的， 但名字不僅僅是一個(gè)字符串， 它還具有屬性和值。4、令 、*和代表加、乘和乘冪， 按如下的非標(biāo)準(zhǔn)優(yōu)先級和結(jié)合性質(zhì)的約定， 計(jì)算 11*2 *1 2 的值：1、優(yōu)先順序從高至低為、*和，同級優(yōu)先采用左結(jié)合。2、優(yōu)先順序?yàn)椤?* ，同級優(yōu)先采用右結(jié)合。解：1、11*2 *1 2 = 2*2*1 2 = 4 *1 2 = 4

2、 2 =2、11*2 *1 2 =6、令文法 g6 為 ndnd，d 0 1 2 3 4 5 6 7 891、g6 的語言 l(g6) 是什么？2、給出句子 0127、34 和 568 的最左推導(dǎo)和最右推導(dǎo)。分析：根據(jù)產(chǎn)生式ndnd可以看出， n 最終可推導(dǎo)出1 個(gè)或多個(gè)可以是無窮多個(gè) d，根據(jù)產(chǎn)生式d0123456789 可以看出，每個(gè)d 可以推導(dǎo)出 0 至 9 中的某一個(gè)數(shù)字。因此，n最終推導(dǎo)出的是由0 到 9 這 10 個(gè)數(shù)字組成的字符串。解：1、l(g6 ) 是由 0 到 9 這 10 個(gè)數(shù)字組成的 字符串。 2 、 句 子 0127 、 34 和 568 的 最 左 推 導(dǎo) ： n=

3、>nd=>ndd=>nddd=>dddd=>0ddd=>01dd=>012d=>0127 n=>nd=>dd=>3d=>34 n=>nd=>ndd=>ddd=>5dd=>56d=>568句 子 0127 、 34 和 568 的 最 右 推 導(dǎo) ： n=>nd=>n7=>nd7=>n27=>nd27=>n127=>d127=>0127n=>nd=>n4=>d4=>34 n=>nd=>n8=>nd8=

4、>n68=>d68=>5687、寫一個(gè)文法，使其語言是奇數(shù)集，且每個(gè)奇數(shù)不以0 開頭。分析：此題要構(gòu)造一個(gè)文法，由它產(chǎn)生的句子是奇數(shù)，且不以0 開頭。也就是說它的每個(gè)句子都以1、3、5、7、9 中某數(shù)結(jié)尾。如果數(shù)字只有一位，那么滿足要求；如果有多位，那么要求第一位不能是0；而中間有多少位，每位是什么數(shù)字那么沒有要求。 因此我們可以把這個(gè)文法分3 局部完成， 分別用 3 個(gè)非終結(jié)符來產(chǎn)生句子的第一位、中間局部和最后一位。引入幾個(gè)非終結(jié)符，其中，一個(gè)用作38 / 35產(chǎn)生句子的開頭，可以是1 到 9 中的數(shù)，不包括 0；一個(gè)用來產(chǎn)生句子的結(jié)尾， 為奇數(shù)；另一個(gè)那么用來產(chǎn)生以非0

5、整數(shù)開頭后面跟任意多個(gè)數(shù)字的數(shù)字串，進(jìn)展分解之后，這個(gè)文法就很好寫了。解：g(s)：a2 4 6 8 d b a0c cbad 13579 s cdd8、令文法為 e t e+ te-t tft*ft/ff(e) i（1） 給出 i+i*i、i*(i+i)的最左推導(dǎo)和最右推導(dǎo)；（2） 給出 i+i+i、i+i*i和 i-i-i的語法樹。解：（1） 最左推導(dǎo)為：e=>e+t=>t+t=>f+t=>i+t=>i+t*f => i+f*f => i+i*f => i+i*i e => t => t*f => f*f => i*f

6、 => i*(e) => i*(e+ t) => i*(t+ t)=> i*(f+ t) => i*(i+ t) => i*(i+ f) => i*(i+ i)最右推導(dǎo)為：e =>e+t=>e+t*f =>e+t*i=>e+f*i =>e+i*i=> t+i*i=> f+i*i=> i+i*i e => t => t*f => f*f => f*(e) => f*(e+t)=> f*(e+ f) => f*(e+ i)=> f*(t+i) => f*(

7、f+i) => f*(i+i) => i*(i+ i)（2） 語法樹：eeee+te+te-te+tftt* tfifffiiife-tfiffiiii9、證明下面的文法是二義的：sisesis i分析：根據(jù)文法二義性定義，如果要證明該文法是二義的，必須找到一個(gè)句子，使該句子具有兩個(gè)不同的最右推導(dǎo)或兩個(gè)不同的語法樹。我們首先分析這個(gè)文 法，根據(jù)我們對程序語言的了解， 不難發(fā)現(xiàn)這個(gè)文法應(yīng)該是用來表示ifelse 結(jié)構(gòu)的用“ i 表示“ if 或語句集，用e 代表 else 。因此我們就要到ifelse結(jié)構(gòu)中去找二義性。我們知道，程序語言一般都規(guī)定else局部是和它前面離它最近的沒有被

8、匹配的if語句進(jìn)展匹配。而上面的這個(gè)文法表達(dá)不出這種 限制，因此我們可以找這樣一個(gè)句子，在else前面有兩個(gè) if 如句子 iiiei， else 和不同的 if進(jìn)展匹配時(shí)就會(huì)產(chǎn)生不同的語義。解：考慮句子 iiiei，存在如下兩個(gè)最右推導(dǎo)：s=>ises=>isei=>iisei=>iiiei s=>is=>iises=>iisei=>iiiei 由此該文法是二義的。10、把下面文法改為無二義的：s ss(s) ()分析：此題給出的文法是二義的，關(guān)鍵在于s ss是產(chǎn)生二義性的根源。我們將該產(chǎn)生式改造成等價(jià)的遞歸結(jié)構(gòu)，消除二義性。解： sts t，

9、 t (s) ()111、給出下面語言的相應(yīng)文法： l =a nbnci n1，i 0 ，lin n2 =a b c n1，i 0n n m ml3 =a b a b n，m0n m m nl4 =1 0 1 0 n，m0n ni分析：語言 l1 要求 a 和 b 的個(gè)數(shù)一樣多，且至少為一個(gè)；c 的個(gè)數(shù)為 0 個(gè)以上。因此我們可用一個(gè)非終結(jié)符去生成a b 串，用另外一個(gè)非終結(jié)符去生成c 。n ni語言 l2 要求 b 和 c 的個(gè)數(shù)一樣多， 因此可用一個(gè)非終結(jié)符去生成b c ，而使用另外一個(gè)非終結(jié)符去生成a 。因此可以模仿 l1 生成 l2。n n m mn nm m對于 l3，可將 a b

10、a b 分兩段考慮，即 a b 和 a b ，然后用兩個(gè)非終結(jié)符分別去產(chǎn)生他們。l4 不能采用分段處理的方式，它要求中間的0 和 1 的個(gè)數(shù)一樣，而且一前一后的 0 和 1 的個(gè)數(shù)一樣。對于這種題型我們可以采用從里向外擴(kuò)展的方式進(jìn)展， 即先用一個(gè)非終結(jié)符生成處于中間的m個(gè) 0 和 m個(gè) 1，然后，使用另外一個(gè)非終結(jié)符在該串的根底上擴(kuò)大前后的n 個(gè) 0 和 n 個(gè) 1。解：l1 的文法： sac； a aabab；ccc l2 的文法： sab； a aa； b bbcbc l3 的文法： sab； a aab； babbl4 的文法： s 1s0a；a0a1；第三章詞法分析1、編寫一個(gè)對于 p

11、ascal 源程序的預(yù)處理程序。 該程序的作用是， 每次被調(diào)用時(shí)都將下一個(gè)完整的語句送進(jìn)掃描緩沖區(qū)，去掉注釋行，同時(shí)要對源程序列表打印。2、請給出以下 c+程序段中的單詞符號與其屬性值。int cint： nmuldiv int n1，int n2ifn3= =0 return 0；else returnn1*n2 /n3 ；3、用類似 c或 pascal 的語言編寫過程getchar， getbc和 concat。4、用某種高級語言編寫并調(diào)試一個(gè)完整的詞法分析器。5、6、令 a、b 和 c 是任意正規(guī)式，證明以下關(guān)系成立： a a=a(a*)*= a* a*= a a* (ab)*a=a(b

12、a)*(a b)*=(a*b*)*=(a*b*)* a=baa 當(dāng)且僅當(dāng) a=a*b證明：1、aa=al(aa)=l(a) l(a)=l(a) ，所以有 aa=a。2、(a*)*= a*3、a*= a a*通過證明兩個(gè)正規(guī)式所表示的語言一樣來證明兩個(gè)正規(guī)式相等。l( a a*)=l( ) l(a)l(a*)= l() l(a)(l(a) )*0=l( ) l(a)(l(a)(l(a)12 (l(a)(l(a)12334=l( ) (l(a) (l(a)=(l(a)*=l(a*)(l(a)(l(a)即： l( a a*)=l(a*)，所以有： a*= a a*4、(ab)*a=a(ba)*利用正

13、規(guī)式的分配率和結(jié)合律直接推導(dǎo)。231(ab)*a=(ab) 0(ab) 1 (ab) 2(ab) 3)a= a (ab)a(ab)a(ab) a1=a a (ba) a (ba)12a (ba) 323=a( (ba) (ba)=a(ba)*(ba) )即： (ab)*a=a(ba)*5、(ab)*=(a*b*)*=(a*b*)* 證明: 先證(ab)*=(a*b*)*因?yàn)?l(a)l(a)*l(b)*,l(b)l(a)*l(b)*故:l(a) l(b)l(a)*l(b)*于是由此題第二小題結(jié)論可知(l(a) l(b)*(l(a)*l(b)*)*又 l(a)l(a) l(b), l(b)l(a

14、) l(b) 故:l(a)*(l(a) l(b)*l(b)*(l(a) l(b)*2因此有:l(a)*l(b)*(l(a) l(b)*(l(a) l(b)*=(l(a)l(b)*)故(l(a)*l(b)*)*(l(a)l(b)*)*由此題第二小題得 :(l(a)l(b)*)*=(l(a)l(b)*故得:(l(a)*l(b)*)*(l(a) l(b)*那么由得 :(l(a)l(b)*=(l(a)*l(b)*)*由于 l(a*b*)*=(l(a*b*)*=(l(a*)l(b*)*=(l(a)*l(b)*)*即有(l(a)l(b)*=l(a*b*)*而 (a|b)*對 應(yīng) 的 語 言 為 (l(a)

15、 l(b)*,且 (a*b*)*對 應(yīng) 的 語 言 為l(a*b*)*那么根據(jù)得 (a|b)*=(a*b*)*再證:(a*|b*)*=(a*b*)*因?yàn)?a,b 是任意正規(guī)式 , 由以上結(jié)論得 :(a*|b*)*=(a*)*(b*)*)* 又由此題第二小題目的結(jié)論可得： a*=a* ，b*=b* 因此，a*|b* *=a*b*綜合上述兩種結(jié)論，最后得：(a b)*=(a*b*)*=(a*b*)*6、a=baa 當(dāng)且僅當(dāng) a=a*b7、構(gòu)造以下正規(guī)式相應(yīng)的dfa1(0 1)*1011(1010* 1(010)*1)*00*10*10*10*(00 11)*(0110)(00 11)*(01 10

16、)(00 11)*)*解：(1) 、1(0 1)*101第一步：根據(jù)正規(guī)式構(gòu)造nfa，先引入初始狀態(tài)x 和終止?fàn)顟B(tài) y：x1(0 1)*101y再對該轉(zhuǎn)換圖進(jìn)展分解，得到分解后的nfa如以下圖：0x112314051y1第二步：對狀態(tài)x1 ，2，32 ，32 ，3，42 ，3，52 ，3，4，ynfa進(jìn)展確定化，獲得狀態(tài)轉(zhuǎn)換矩陣：0?2 ，32 ，32 ，3，52 ，32 ，3，511 ， 2， 32 ， 3， 42 ， 3， 42 ， 3， 42 ， 3， 4，y2 ， 3， 4根據(jù)轉(zhuǎn)換矩陣獲得相應(yīng)的dfa：00110210113045011第三步：化簡該dfa，獲得最簡的 dfa即為所求。

17、首先根據(jù)是否終止?fàn)顟B(tài)將所有狀態(tài)分為兩個(gè)集合 0 ， 1，2，3，4 和5 ，這里集合5 已經(jīng)不可劃分，只需考慮集合 0 ，1，2，3， 4 。0 ，1，2，3，4 0 =2 ，4，- ，0 ，1，2，3，4 1=1 ，3，5因?yàn)? ，3， 5 和2 ，4，- 不在一個(gè)集合里面，所以需要對集合 0 ，1，2， 3，4 進(jìn)展進(jìn)一步的劃分，檢查其中的所有狀態(tài)。狀態(tài) 0 不能承受字符 0，需要把狀態(tài) 0 劃分出來；另外，只有狀態(tài) 4 讀入字符 1 后進(jìn)入狀態(tài) 5，因此將狀態(tài) 4劃分出來，劃分的結(jié)果為 4 個(gè)集合： 0 ，1 ，2，3 ，4 ，5 。檢查集合 1 ，2，3 ，1 ，2，3 0=2 ，4

18、，不屬于同一個(gè)集合，因此要對集合1 ，2，3 進(jìn)展進(jìn)一步劃分，劃分結(jié)果為5 個(gè)集合： 0 ，1 ，2 ，3 ，4 ，5 。檢查集合 1 ， 2 ，1 ，2 0 =2 ，1 ， 2 1=3，不需要進(jìn)展進(jìn)一步劃分。所以最終劃分結(jié)果為5 個(gè)集合： 0 ，1 ，2 ，3 ，4 ，5 。所以，最終所求dfa如以下圖示：001110130450112、1(1010* 1(010)*1)*03、0*10*10*10*4、(00 11)*(0110)(00 11)*(01 10)(00 11)*)*8、給出下面正規(guī)表達(dá)式：（1） 以 01 結(jié)尾的二進(jìn)制數(shù)串；（2） 能被 5 整除的十進(jìn)制整數(shù)；（3） 包含奇數(shù)

19、個(gè) 1 或奇數(shù)個(gè) 0 的二進(jìn)制數(shù)串；（4） 英文字母組成的所有字符串，要求符號串中的字母依照字典序排列；（5） 沒有重復(fù)出現(xiàn)的數(shù)字的數(shù)字符號串的全體；（6） 最多有一個(gè)重復(fù)出現(xiàn)的數(shù)字的數(shù)字符號串的全體；（7） 不包含子串 abb 的由 a 和 b 組成的符號串的全體。解：1以 01 結(jié)尾的二進(jìn)制數(shù)串；分析題意，要求的是二進(jìn)制數(shù)串，即由0 和 1 構(gòu)成的串，并且必須以01 結(jié)尾，所以此題可以分兩步完成：一局部實(shí)現(xiàn)由0 和 1 構(gòu)成的任意串，一局部即 01，然后將它們連結(jié)在一起就可以了，所以所求為(1 0)*01 。2能被 5 整除的十進(jìn)制整數(shù)；分析題意，此題要求的是十進(jìn)制整數(shù)，也就是由0 至 9

20、 這 10 個(gè)數(shù)字組成的字符串，并且不能以0 開頭整數(shù)“ 0除外，要求能被 5 整除，那么該串必須以 0 或者 5 結(jié)尾。根據(jù)分析，可以把此題分成兩種情況考慮：一種情況時(shí)該整數(shù)只有一位，那么該整數(shù)有0 和 5 兩種可能；另一種情況是該整數(shù)有多位，那么該整數(shù)可以分成三局部考慮：一是第一位必須不為0；二是最后一位必須為 0 或 5；三是中間局部可有可無，并且可以由0 到 9 之間任意數(shù)字構(gòu)成，所以所求為 (1 23456789)(0 123456789)*(0 5)(0 5) 。3包含奇數(shù)個(gè) 1 或奇數(shù)個(gè) 0 的二進(jìn)制數(shù)串；此題求二進(jìn)制串，并且要求包含奇數(shù)個(gè)0 或奇數(shù)個(gè) 1，由于 0 和 1 都可

21、以在二進(jìn)制串中任何地方出現(xiàn)，所以此題只需要考慮一種情況，另一種情況也可 以類似求得?？紤]包含奇數(shù)個(gè)0 的字符串：由于只關(guān)心0 的個(gè)數(shù)的奇偶數(shù)，我們可以把二進(jìn)制串分成多段來考慮，第一段為二進(jìn)制串的開場到第一個(gè)0為止，這一段包含一個(gè)0，并且 0 的前面有 0 個(gè)或多個(gè) 1。對于剩下的二進(jìn)制串按照每段包含兩個(gè)0 的方式去劃分，即以0 開場，以 0 結(jié)尾，中間可以有 0 個(gè)或多個(gè) 1。如果一個(gè)二進(jìn)制串被這樣劃分完后，剩下的局部如果全部 是全 1 串這些全 1 串在前面劃分的串之間或最后 ，那么該二進(jìn)制串就有奇數(shù)個(gè) 0，所以該二進(jìn)制串可以這樣描述：以第一段1*0 開場，后面由全1 串1* 以與包含兩個(gè)0

22、 的串 01*0 組成，所以包含奇數(shù)個(gè)0 的正規(guī)表達(dá)式為 1*0101*0* 。所以此題所求為1*0101*0* 0*1010*1 *。4英文字母組成的所有字符串，要求符號串中的字母依照字典序排列；5沒有重復(fù)出現(xiàn)的數(shù)字的數(shù)字符號串的全體；6最多有一個(gè)重復(fù)出現(xiàn)的數(shù)字的數(shù)字符號串的全體；7不包含子串 abb 的由 a 和 b 組成的符號串的全體。9、對下面情況給出dfa與正規(guī)表達(dá)式：10 ，1 上的含有子串 010 的所有串；20 ，1 上不含子串 010 的所有串。解：1、2、直接寫出滿足條件的正規(guī)表達(dá)式?？紤]滿足條件的字符串中的 1：在串的開場局部可以有 0 個(gè)或多個(gè) 1，串的尾部也可以有 0

23、 個(gè)或多個(gè) 1，但串的中間只要出現(xiàn) 1 那么至少在兩個(gè)以上，所以滿足條件的正規(guī)表達(dá)式為 1*(0 111*)*1* 。所求的 dfa如以下圖所示：100sa11b10、一個(gè)人帶著狼、山羊和白菜在一條河的左岸。有一條船，大小正好能裝下這個(gè)人和其他三件東西中的一件。人和他的隨行物都要過到河的右岸。人每次只能將一件東西擺渡過河。但假設(shè)人將狼和羊留在同一岸而無人照顧的話，狼將把羊吃掉。類似地，假設(shè)羊和白菜留下來無人照看，羊?qū)?huì)吃掉白菜。請問是否有可能渡過河去，使得羊和白菜都不被吃掉？如果可能，請用有限自動(dòng)機(jī)寫出渡河的方法。解：11、12、將圖 3.18 的a和 b分別確定化和最小化。aa， b0a1(

24、a)abba 023baaab145bbaa(b)解：1、圖a中為一個(gè) nfa，所以需要先對它進(jìn)展確定化，得到dfa，然后再對 dfa進(jìn)展最小化。首先進(jìn)展確定化，如下兩個(gè)表所示：狀態(tài)ab狀態(tài)ab00 ，110120 ，10 ，1111210?20根據(jù)狀態(tài)轉(zhuǎn)換矩陣得到如以下圖所示的dfa：a01abab2化簡后的 dfa為：ab02a2、題中所給即為一個(gè)dfa，不需要確定化，只對它進(jìn)展最小化即可。首先將狀態(tài)劃分為兩個(gè)集合0 ， 1 ，2 ，3， 4， 5 。有0 ，1 a=1 ，0 ， 1 b=2 ，4 和2 ， 3， 4， 5 a=1 ，3，0， 5 ，2 ， 3， 4， 5 b=2 ， 3，

25、 4， 5 ，所以可以進(jìn)一步劃分為 0 ，1 ，2 ，4 ，3 ，5 ，然后有 0 ，1 a=1 ，0 ，1 b=2 ， 4 ，2 ，4 a=1 ，0 ，2 ，4 b=3 ，5 ，3 ，5 a=3 ，5 ，3 ，5 b=2 ，4 。因此， 最后劃分結(jié)果是 0 ， 1 ，2 ，4 ，3 ，5 。最小化后的 dfa如以下圖所示：aabb012ab13、1給出描述 c浮點(diǎn)數(shù)的 dfa；14、構(gòu)造一個(gè) dfa，它承受 =0 ，1 上所有滿足如下條件的字符串：每個(gè)1都有 0 直接跟在右邊。分析：對這類題型的固定解法分4 步進(jìn)展： 首先根據(jù)語言寫出正規(guī)表達(dá)式；然后根據(jù)正規(guī)表達(dá)式構(gòu)造相應(yīng)的nfa；然后，對

26、nfa進(jìn)展確定化得到dfa；最后對 dfa 化簡得到最簡 dfa。第一步：寫出正規(guī)表達(dá)式。根據(jù)題意，該 dfa承受的字符串由 0 和 1 組成， 并且每個(gè) 1 的后面都有 0 直接跟在右邊，因此，可以將該字符串理解為由 0 和10 構(gòu)成的串，那么相應(yīng)的正規(guī)表達(dá)式就是 (0 10)* 。第二步：構(gòu)造 nfa。首先得出以下圖：x(010)*y然后對上圖進(jìn)展分解后得到如以下圖所示的nfa。201x1y0第三步：確定化，得到dfa。確定化結(jié)果如表14.1 所列；給狀態(tài)編號，得到表 14.2 所示的狀態(tài)轉(zhuǎn)換矩陣：狀態(tài)01狀態(tài)01x，1，y1 ，y20121 ，y1 ，y211221 ，y表 14.1狀態(tài)

27、轉(zhuǎn)換矩陣?2表 14.21新的狀態(tài)轉(zhuǎn)換矩陣根據(jù)狀態(tài)轉(zhuǎn)換矩陣得到dfa如以下圖所示：00101102第四步：對該 dfa進(jìn)展最小化。其分析過程如下：0 ，1 ，20 ，1 0=1 ，0 ，1 1=20 ，1 ，2最小化后的 dfa如下圖，該 dfa即為所求。0101015、給定右線性文法 g： s 0s1s 1a0b a 1c1b 0c0c 0c1c 0 1求出一個(gè)與 g等價(jià)的左線性文法。分析：根據(jù)右線性文法求左線性文法沒有直接的方法，但可以通過狀態(tài)轉(zhuǎn)換 圖去轉(zhuǎn)換。可以先求出文法 g的狀態(tài)轉(zhuǎn)換圖， 再根據(jù)狀態(tài)轉(zhuǎn)換圖寫出相應(yīng)的左線性文法。文法 g對應(yīng)的狀態(tài)轉(zhuǎn)換圖如下所示：0， 1s0， 111ac

28、001b00， 1z對狀態(tài)轉(zhuǎn)換圖進(jìn)展確定化，得到狀態(tài)轉(zhuǎn)換矩陣：狀態(tài)s0s，b1s，as，bs，b，c，zs，as，as，bs，a，c，zs，b，c，zs，b，c，zs，a，c，zs，a，c，zs，b，c，zs，a，c，z給狀態(tài)編號，得到新的狀態(tài)轉(zhuǎn)換矩陣：狀態(tài)01012132214334434根據(jù)狀態(tài)轉(zhuǎn)換矩陣獲得dfa如下：000013110102141還可以對上圖的dfa進(jìn)展化簡，狀態(tài) 3 和 4 可以合并，化簡后的dfa如以下圖所示：0， 10sa0t1101b不難看出，該 dfa承受的語言是 0 ，1 上包含 00 或 11 的字符串。根據(jù)化簡后的 dfa，我們可以寫出相應(yīng)的左線性文法g：

29、t a0b1 t0t1 a b00b a1116、* 非形式的說明17、* 下面的字集是否為正規(guī)集？或?qū)懗銎湔?guī)式，或給出否證。n n（1） l1 =a b n0 ；（2） l2 =x ；（3） l3 = 。18、假定 l 和 m都是正規(guī)集：（1） 證明 lm、lm和 m補(bǔ)集也是正規(guī)的；（2） l是 l 中每個(gè)字的逆轉(zhuǎn)，證明l 也是正規(guī)的。19、寫出描述 ansi c 的單詞符號的 lex程序。20、假定有正規(guī)定義式a0ab a1a0 a 0anan-1 a n-1考慮詞形 an（1） 把 an 中所有簡名都換掉，最終所得的正規(guī)式的長度是多少？（2） 字集 an 的元素是什么？把它們非形式的表

30、示成n 的函數(shù)；（3） 證明識別 an 的 dfa只需用 2n+1 個(gè)狀態(tài)就足夠了。21、把 lex的“動(dòng)作成分加以充實(shí)使得可用它來編寫語法制導(dǎo)編輯器。第四章語法分析自上而下分析1、考慮下面的文法g1：s a (t) t t， ss1消去 g1 的左遞歸。然后對每個(gè)非終結(jié)符，寫出不帶回溯的遞歸子程序。2經(jīng)改寫后的文法是否是ll(1) 的？給出它的預(yù)測分析表。解：1按照 t、s的順序消除左遞歸，得到文法：g(s)sa (t) tstt， st對于非終結(jié)符s,t,t 的遞歸子程序如下： procedure s;beginif sym = a or sym = then advanceelse if

31、sym = ( then begin advance ;t;ifsym =) then advance elseerrorendelse error ends;procedure t;begins; t ;ends;procedure t beginif sym =, then begin advance ;endsends;s; t 2計(jì)算每個(gè)非終結(jié)符的first集合和 follow集合：firsts=a ， ( firstt=a ， ( firstt= ， follows=) ， #followt=) followt=)從而可見改造后的文法符合ll(1) 文法的充分必要條件，所以是該文法的

32、預(yù)測分析表ll(1) 的。as->as->t->s t t->s t (s->(t)t->s t ),#st tt-> t->,st2、對下面的文法 g： e tee +et ftt t f pff *f p (e) a b（1） 計(jì)算這個(gè)文法的每個(gè)非終結(jié)符的first和 follo。w（2） 證明這個(gè)文法是ll(1) 的。（3） 構(gòu)造它的預(yù)測分析表。（4） 構(gòu)造它的遞歸下降分析程序。分析：對于這類題目，我們首先應(yīng)當(dāng)檢查文法是否符合ll(1) 文法的條件， 根據(jù)需要，先通過消除左遞歸、提取右公因子的方法， 把文法改造成符合ll(1) 文法的條件，

33、在此根底上，我們才能構(gòu)造出不帶回溯的遞歸下降識別程序。注意，此題在構(gòu)造子程序時(shí)，對于每個(gè)產(chǎn)生式候選，在調(diào)用第一個(gè)非終結(jié)符對應(yīng)的子程序之前，檢查了首符集。解：（1） 計(jì)算每個(gè)非終結(jié)符的first集合和 follow集合如下： firste=( ，a，b， firste=+ ，firstt=( ， a， b， firstt=( ，a，b， firstf=( ， a， b， first f =* ， firstp=( ， a， b， followe=# ，)followe=# ， ) followt=+ ，) ，# followt=+ ，) ， #follo wf =( ，a，b， +，) ，# f

34、ollowf=( ， a， b， +，) ，# followp=* ，( ，a，b， +，) ，#（2） 本文法是 ll ( 1 )文法。證明：通過觀察可知文法中不含有左遞歸，滿足ll (1)文法定義的第一個(gè)條件。考慮以下產(chǎn)生式：e +ett f *f p(e) ab 因?yàn)椋篺irst+e first =+ = ?firste followe=+ # ，)=?firstt first =( ，a，b， = ?firstt followt=( ， a， b， + ，) ，#= ?first*f first =* = ?firstf followf=* ( ，a， b， +，) ，#=?first

35、 e firsta firstb first =?所以該文法是 ll(1) 文法。（3） 構(gòu)造其預(yù)測分析表： 預(yù)測分析表+*()ab#ee+eeettfttftttttttttte et eet eetet ee->fttftttttf fpffpfppffpffff*fffffffpp(e)papbp（4） 構(gòu)造其遞歸下降分析程序：proceduree;begint ;eend ;proceduree ; beginifsym = + thenbegin acvance ;eendend ;proceduret ; beginf ; tend ;proceduret ; beginif

36、symfirst ( t ) then telseif sym =* thenerrorend ;proceduref ; beginifsymfirst ( p )p; f;end ;procedurefbeginif sym = * thenbegin advance ;fend end;procedurepbeginif sym = aorsym = b or sym = then acvanceelseif sym = (thenbegin advance ;e ;ifsym = )then advance elseerror endelseerrorend;3、下面文法中，哪些是ll

37、(1) 的，說明理由。1、sabc aa bb2、sab aab bb3、sabbaaa bb4、saseb bbbec ccced分析：判斷文法是否是ll(1) 的，要根據(jù)ll(1) 文法的條件逐一檢查：首先要確定文法不含左遞歸；隨后計(jì)算文法的各非終結(jié)符x的首符集 firstx和隨符集followx。首先要理解這兩個(gè)集合的計(jì)算方法，特別要注意算法終止的條件：直到集合不再變化為止。也就是說，反復(fù)檢查每一個(gè)產(chǎn)生式，直到從頭到尾檢查了所有產(chǎn)生式，而first集合和 follow集合都沒有變化了，這時(shí)候計(jì)算才能完畢。最后根據(jù)ll(1) 文法的充分必要條件即ll(1) 文法定義來判斷是否是 ll(1)

38、 文法。解：（1） 該文法不含左遞歸，計(jì)算每個(gè)非終結(jié)符的first集合和 follow集合如下：firsts=a ，b，c firsta=a ， firstb=b ， follows=#followa=b ， c followb=c可見該文法滿足 ll(1) 文法的三個(gè)條件，是ll(1) 文法。（2） 該文法不含左遞歸，計(jì)算每個(gè)非終結(jié)符的first集合和 follow集合如下：first s =a ，b firsta=a ，b， firstb=b ， follo ws =# follo wa =b followb=b考慮 a a b，因?yàn)閒irstb follow a=b ? ，所以該文法不是

39、 ll(1) 文法。（3） 該文法不含左遞歸，計(jì)算每個(gè)非終結(jié)符的first集合和 follow集合如下：firsts=a ，b， firsta=a ， firstb=b ， follows=#followa=a ， b， #followb=a ， b， #考慮 aa 和 bb，因?yàn)閒irsta followa=a ?firstb followb=b ?所以該文法不是ll(1) 文法。（4） 該文法不含左遞歸，計(jì)算每個(gè)非終結(jié)符的first集合和 follow集合如下：firsts=a ，b，c，d firstb=b ，c，d first c =c ，d follo ws =e ， # follo

40、 wb =e ， # followc=e ， #可見該文法滿足ll(1) 文法的三個(gè)條件，是ll(1) 文法。4、對下面文法： expr -expr expr (expr) varexprtail-expr varid vartail vartail (expr) 1、構(gòu)造 ll(1) 分析表。2、給出對句子 id-id(id)的分析過程。分析：構(gòu)造文法的預(yù)測分析表，通常應(yīng)當(dāng)按以下順序進(jìn)展：1、消除文法的左遞歸包括所有直接左遞歸和間接左遞歸 ；2、對消除左遞歸后的文法， 提取左公因子；3、對經(jīng)過上述改造后的文法，計(jì)算它的每個(gè)非終結(jié)符的first集合和follow集合；4、根據(jù) first集合和

41、 follow集合構(gòu)造預(yù)測分析表。第一步對文法 g的每個(gè)產(chǎn)生式 a 執(zhí)行第一步和第三步； 第二步對每個(gè)終結(jié)符 afirst() ，把 a 加至 ma，a 中；第三步假設(shè) first() ，那么對任何 bfollow(a把) a 標(biāo)上“出錯(cuò)標(biāo)志。解：a 加至 ma，b 中；第四步把所有無定義的ma，1、計(jì)算每個(gè)非終結(jié)符的first集合和 follow集合如下： first(expr)=-，( ，idfirst(exprtail)=-， first(var)=idfirst(vartail)=(，follow(expr)=)， #follow(exprtail)=) ，# follow(var)=

42、-，) ，#follow(vartail)=- ， #構(gòu)造其預(yù)測分析表如下：-id()# exprexpr- exprexpr exprexpr-( expr)exprtailexprtail-exprvarvaridvartailexprtail exprtail vartailvartailvartailvartailvartail(expr)2、句子 id-id(id)的分析過程如下：步驟0符號棧# expr輸入串id-id(id)所用產(chǎn)生式#1# exprtail varid-id(id)exprvar exprtail#2# exprtail vartail idid-id(id)#

43、varid vartail3# exprtail vartail-id(id) #4# exprtail-id(id) #vartail 5# expr -id(id) #exprtail-expr6# expr-id(id) #7# expr -id(id) #expr -expr8# exprid(id) #9# exprtail varid(id) #exprvar exprtail10# exprtail vartail idid(id) #varid vartail11# exprtail vartail(id) #18#exprtail)exprtailvartail) #19#

44、exprtail ) ) exprtail) #vartail 20# exprtail ) ) #exprtail21# exprtail ) #22# exprtail#23#exprtailsuc121314151617# exprtail ) expr (# exprtail ) expr# exprtail ) ) expr ( # exprtail ) ) expr# exprtail ) ) exprtal var#exprtail)exprtail(id) #(id) #(id) # id) #id) #id) #vartail (expr)exprvar exprtailva

45、rid vartailvartail id5、把下面文法改寫為ll(1) 的：declistdeclist；decl decl decl idlist：typeidlistidlist，id idtypescalartype array(scalartypelist) of type scalartype id bound.boundboundsign intliteralid sign +- scalartypelistscalartypelist，scalartype scalartype分析：此題主要考察理解和運(yùn)用消除文法的左遞歸、提取公因子等算法的能力，為判斷文法是否是ll(1) 文法

46、，還要計(jì)算文法的first集合和 follow集合。消除文法的左遞歸的根本思想是，將文法規(guī)那么中的左遞歸結(jié)構(gòu)變換成等價(jià)的右遞歸結(jié)構(gòu)。 提取左公因子的算法， 是對包含公共左因子的產(chǎn)生式候選，反復(fù)提取左因子， 就能夠把每個(gè)非終結(jié)符 包括新引進(jìn)者 的所有候選首符集變成為兩兩不相交。 消除文法的左遞歸、 提取左公共因子后， 再計(jì)算文法的各非終結(jié)符x的首符集 firstx和隨符集follow(x，) 然后根據(jù)ll(1) 文法的充分必要條件即 ll(1) 文法的定義來判斷文法是否是ll(1) 文法。解：首先消除左遞歸，得到文法g(declist)：declistdecl declistdeclist； d

47、ecl declistdecl idlist：type idlistid idlistidlist， id listtypescalartype array(scalartypelist) of type scalartype id bound.boundbound sign intliteral id sign +- scalartypelistscalartype scalartypelistscalartypelist， scalartype scalartypelist顯然，改造后的文法沒有左公共因子，計(jì)算每個(gè)非終結(jié)符的first 集合和follow集合如下：first(declist)=id first(declist )= ；， first(decl)=id first(idlist)=id first(idlist)= ；， first(type)=id，+，- ，intliteral，arrayfi