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

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

2、 = （2）、11*2*12 = 6、令文法G6為NDND，D0123456789（1）、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=>ND=>NDD=>NDDD=>DDDD=>0DDD=>01D

3、D=>012D=>0127N=>ND=>DD=>3D=>34N=>ND=>NDD=>DDD=>5DD=>56D=>568句子0127、34和568的最右推導(dǎo)：N=>ND=>N7=>ND7=>N27=>ND27=>N127=>D127=>0127N=>ND=>N4=>D4=>34N=>ND=>N8=>ND8=>N68=>D68=>5687、寫一個(gè)文法，使其語言是奇數(shù)集，且每個(gè)奇數(shù)不以0開頭。分析：本題要構(gòu)造一個(gè)文法，由

4、它產(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è)用作產(chǎn)生句子的開頭，可以是1到9中的數(shù)，不包括0；一個(gè)用來產(chǎn)生句子的結(jié)尾，為奇數(shù)；另一個(gè)則用來產(chǎn)生以非0整數(shù)開頭后面跟任意多個(gè)數(shù)字的數(shù)字串，進(jìn)行分解之后，這個(gè)文法就很好寫了。解：G(S)：A2468D BA0 CCBA D13579 SCDD8、令文法為ETE+ TE-T TFT*F

5、T/F F(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*iE => T => T*F => F*F => i*F => i*(E) => i*(E+ T) => i*(T+ T)=> i*(F+ T) => i*(i+ T) => i*(i+ F) =>

6、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*iE => T => T*F => F*F => F*(E) => F*(E+T) => F*(E+ F) => F*(E+ i)=> F*(T+i) => F*(F+i) => F*(i+i) => i*(i+ i)（2） 語法樹：FTETE+EFi+TFiiE+TEFi*TFiTFiEE-TEFiTFi-Fi9、證明下面的

7、文法是二義的：SiSeSiSi分析：根據(jù)文法二義性定義，如果要證明該文法是二義的，必須找到一個(gè)句子，使該句子具有兩個(gè)不同的最右推導(dǎo)或兩個(gè)不同的語法樹。我們首先分析這個(gè)文法，根據(jù)我們對(duì)程序語言的了解，不難發(fā)現(xiàn)這個(gè)文法應(yīng)該是用來表示ifelse結(jié)構(gòu)的（用“i”表示“if”或語句集，用e代表else）。因此我們就要到ifelse結(jié)構(gòu)中去找二義性。我們知道，程序語言一般都規(guī)定else部分是和它前面離它最近的沒有被匹配的if語句進(jìn)行匹配。而上面的這個(gè)文法體現(xiàn)不出這種限制，因此我們可以找這樣一個(gè)句子，在else前面有兩個(gè)if（如句子iiiei），else和不同的if進(jìn)行匹配時(shí)就會(huì)產(chǎn)生不同的語義。解：考慮句

8、子iiiei，存在如下兩個(gè)最右推導(dǎo)：S=>iSeS=>iSei=>iiSei=>iiieiS=>iS=>iiSeS=>iiSei=>iiiei由此該文法是二義的。10、把下面文法改為無二義的：SSS(S)( )分析：本題給出的文法是二義的，關(guān)鍵在于SSS是產(chǎn)生二義性的根源。我們將該產(chǎn)生式改造成等價(jià)的遞歸結(jié)構(gòu)，消除二義性。解：STST，T(S)( )11、給出下面語言的相應(yīng)文法：L1=anbncin1，i0， L2=aibncnn1，i0L3=anbnambmn，m0L4=1n0m1m0nn，m0分析：語言L1要求a和b的個(gè)數(shù)一樣多，且至少為一個(gè)；

9、c的個(gè)數(shù)為0個(gè)以上。因此我們可用一個(gè)非終結(jié)符去生成anbn串，用另外一個(gè)非終結(jié)符去生成ci。語言L2要求b和c的個(gè)數(shù)一樣多，因此可用一個(gè)非終結(jié)符去生成bncn，而使用另外一個(gè)非終結(jié)符去生成ai。因此可以模仿L1生成L2。對(duì)于L3，可將anbnambm分兩段考慮，即anbn和ambm，然后用兩個(gè)非終結(jié)符分別去產(chǎn)生他們。L4不能采用分段處理的方式，它要求中間的0和1的個(gè)數(shù)相同，而且一前一后的0和1的個(gè)數(shù)相同。對(duì)于這種題型我們可以采用從里向外擴(kuò)展的方式進(jìn)行，即先用一個(gè)非終結(jié)符生成處于中間的m個(gè)0和m個(gè)1，然后，使用另外一個(gè)非終結(jié)符在該串的基礎(chǔ)上擴(kuò)充前后的n個(gè)0和n個(gè)1。解：L1的文法：SAC；AaA

10、bab；CcCL2的文法：SAB；AaA；BbBcbcL3的文法：SAB；AaAb；BaBbL4的文法： S1S0A； A0A1；第三章 詞法分析1、 編寫一個(gè)對(duì)于Pascal源程序的預(yù)處理程序。該程序的作用是，每次被調(diào)用時(shí)都將下一個(gè)完整的語句送進(jìn)掃描緩沖區(qū)，去掉注釋行，同時(shí)要對(duì)源程序列表打印。2、 請(qǐng)給出以下C+程序段中的單詞符號(hào)及其屬性值。int CInt：nMulDiv（int n1，int n2）if （n3= =0）return 0；else return（n1*n2）/n3；3、 用類似C或Pascal的語言編寫過程GetChar，GetBC和Concat。4、 用某種高級(jí)語言編寫

11、并調(diào)試一個(gè)完整的詞法分析器。5、 證明3.3.1中關(guān)于正規(guī)式的交換律、結(jié)合律等五個(gè)關(guān)系。6、 令A(yù)、B和C是任意正規(guī)式，證明以下關(guān)系成立：AA=A(A*)*= A*A*=A A*(AB)*A=A(BA)*(AB)*=(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) )*=L()L(A)(L(A)0(L(A)1(L(A)2(L(A)3)=L

12、()(L(A)1(L(A)2(L(A)3(L(A)4=(L(A)*=L(A*)即：L(A A*)=L(A*)，所以有：A*=A A*（4）、(AB)*A=A(BA)*利用正規(guī)式的分配率和結(jié)合律直接推導(dǎo)。(AB)*A=(AB)0(AB)1(AB)2(AB)3)A=A(AB)1A(AB)2A(AB)3A=AA (BA)1A (BA)2A (BA)3=A(BA)1(BA)2(BA)3)=A(BA)*即：(AB)*A=A(BA)*（5）、(AB)*=(A*B*)*=(A*B*)*證明:先證(AB)*=(A*B*)*因?yàn)長(zhǎng)(A)L(A) *L(B) *,L(B) L(A) *L(B) *故:L(A) L

13、(B) L(A) *L(B) *于是由本題第二小題結(jié)論可知(L(A)L(B) *(L(A) *L(B)*)* 又L(A)L(A)L(B), L(B) L(A)L(B)故:L(A)*(L(A)L(B)* L(B)*(L(A)L(B)*因此有:L(A)*L(B)* (L(A)L(B)* (L(A)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*B*)*=

14、(L(A*B*)*=(L(A*)L(B*)*=(L(A)*L(B)*)*即有(L(A)L(B)*=L(A*B*)* 而(A|B)*對(duì)應(yīng)的語言為(L(A)L(B)*,且(A*B*)*對(duì)應(yīng)的語言為L(zhǎng)(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é)論，最后得：(AB)*=(A*B*)*=(A*B*)*（6）、A=baA當(dāng)且僅當(dāng)A=a*b7、 構(gòu)造下列正規(guī)式相應(yīng)的D

15、FA1(01)*1011(1010*1(010)*1)*00*10*10*10*(0011)*(0110)(0011)*(0110)(0011)*)*解：(1)、1(01)*101第一步：根據(jù)正規(guī)式構(gòu)造NFA，先引入初始狀態(tài)X和終止?fàn)顟B(tài)Y：X1(01)*101Y再對(duì)該轉(zhuǎn)換圖進(jìn)行分解，得到分解后的NFA如下圖：X12345Y110101第二步：對(duì)NFA進(jìn)行確定化，獲得狀態(tài)轉(zhuǎn)換矩陣：狀態(tài)01XØ1，2，31，2，32，32，3，42，32，32，3，42，3，42，3，52，3，42，3，52，32，3，4，Y2，3，4，Y2，3，52，3，4根據(jù)轉(zhuǎn)換矩陣獲得相應(yīng)的DFA：0123410

16、0010111501第三步：化簡(jiǎn)該DFA，獲得最簡(jiǎn)的DFA即為所求。首先根據(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，40=2，4，-，0，1，2，3，41=1，3，5因?yàn)?，3，5和2，4，-不在一個(gè)集合里面，所以需要對(duì)集合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，30=2，4，不屬于同一個(gè)集合，因此要對(duì)集合1，2

17、，3進(jìn)行進(jìn)一步劃分，劃分結(jié)果為5個(gè)集合：0，1，2，3，4，5。檢查集合1，2，1，20=2，1，21=3，不需要進(jìn)行進(jìn)一步劃分。所以最終劃分結(jié)果為5個(gè)集合：0，1，2，3，4，5。所以，最終所求DFA如下圖示：01341001011501（2）、1(1010*1(010)*1)*0（3）、0*10*10*10*（4）、(0011)*(0110)(0011)*(0110)(0011)*)*8、 給出下面正規(guī)表達(dá)式：（1） 以01結(jié)尾的二進(jìn)制數(shù)串；（2） 能被5整除的十進(jìn)制整數(shù)；（3） 包含奇數(shù)個(gè)1或奇數(shù)個(gè)0的二進(jìn)制數(shù)串；（4） 英文字母組成的所有字符串，要求符號(hào)串中的字母依照字典序排列；（5）

18、 沒有重復(fù)出現(xiàn)的數(shù)字的數(shù)字符號(hào)串的全體；（6） 最多有一個(gè)重復(fù)出現(xiàn)的數(shù)字的數(shù)字符號(hào)串的全體；（7） 不包含子串a(chǎn)bb的由a和b組成的符號(hào)串的全體。解：（1）以01結(jié)尾的二進(jìn)制數(shù)串；分析題意，要求的是二進(jìn)制數(shù)串，即由0和1構(gòu)成的串，并且必須以01結(jié)尾，所以本題可以分兩步完成：一部分實(shí)現(xiàn)由0和1構(gòu)成的任意串，一部分即01，然后將它們連結(jié)在一起就可以了，所以所求為(10)*01。（2）能被5整除的十進(jìn)制整數(shù)；分析題意，本題要求的是十進(jìn)制整數(shù)，也就是由0至9這10個(gè)數(shù)字組成的字符串，并且不能以0開頭（整數(shù)“0”除外），要求能被5整除，則該串必須以0或者5結(jié)尾。根據(jù)分析，可以把本題分成兩種情況考慮：一種

19、情況時(shí)該整數(shù)只有一位，則該整數(shù)有0和5兩種可能；另一種情況是該整數(shù)有多位，則該整數(shù)可以分成三部分考慮：一是第一位必須不為0；二是最后一位必須為0或5；三是中間部分可有可無，并且可以由0到9之間任意數(shù)字構(gòu)成，所以所求為(123456789) (0123456789)*(05)(05)。（3）包含奇數(shù)個(gè)1或奇數(shù)個(gè)0的二進(jìn)制數(shù)串；本題求二進(jìn)制串，并且要求包含奇數(shù)個(gè)0或奇數(shù)個(gè)1，由于0和1都可以在二進(jìn)制串中任何地方出現(xiàn)，所以本題只需要考慮一種情況，另一種情況也可以類似求得。考慮包含奇數(shù)個(gè)0的字符串：由于只關(guān)心0的個(gè)數(shù)的奇偶數(shù)，我們可以把二進(jìn)制串分成多段來考慮，第一段為二進(jìn)制串的開始到第一個(gè)0為止，這一

20、段包含一個(gè)0，并且0的前面有0個(gè)或多個(gè)1。對(duì)于剩下的二進(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的串（01*0）組成，所以包含奇數(shù)個(gè)0的正規(guī)表達(dá)式為1*0（101*0）*。所以本題所求為1*0（101*0）*0*1（010*1）*。（4）英文字母組成的所有字符串，要求符號(hào)串中的字母依照字典序排列；（5）沒有重復(fù)出現(xiàn)的數(shù)字的數(shù)字符號(hào)串的全體；（6）

21、最多有一個(gè)重復(fù)出現(xiàn)的數(shù)字的數(shù)字符號(hào)串的全體；（7）不包含子串a(chǎn)bb的由a和b組成的符號(hào)串的全體。9、 對(duì)下面情況給出DFA及正規(guī)表達(dá)式： （1）0，1上的含有子串010的所有串；（2）0，1上不含子串010的所有串。解：（1）、（2）、直接寫出滿足條件的正規(guī)表達(dá)式。考慮滿足條件的字符串中的1：在串的開始部分可以有0個(gè)或多個(gè)1，串的尾部也可以有0個(gè)或多個(gè)1，但串的中間只要出現(xiàn)1則至少在兩個(gè)以上，所以滿足條件的正規(guī)表達(dá)式為1*(0111*)*1*。所求的DFA如下圖所示：AS10a11B010、 一個(gè)人帶著狼、山羊和白菜在一條河的左岸。有一條船，大小正好能裝下這個(gè)人和其他三件東西中的一件。人和他的

22、隨行物都要過到河的右岸。人每次只能將一件東西擺渡過河。但若人將狼和羊留在同一岸而無人照顧的話，狼將把羊吃掉。類似地，若羊和白菜留下來無人照看，羊?qū)?huì)吃掉白菜。請(qǐng)問是否有可能渡過河去，使得羊和白菜都不被吃掉？如果可能，請(qǐng)用有限自動(dòng)機(jī)寫出渡河的方法。解：11、12、 將圖3.18的（a）和（b）分別確定化和最小化。10a，baa(a)20baa(b)1543bbbbbaaaaa解：（1）、圖（a）中為一個(gè)NFA，所以需要先對(duì)它進(jìn)行確定化，得到DFA，然后再對(duì)DFA進(jìn)行最小化。首先進(jìn)行確定化，如下兩個(gè)表所示：狀態(tài)ab00，110，10，1110Ø 狀態(tài)ab01211220根據(jù)狀態(tài)轉(zhuǎn)換矩陣得

23、到如下圖所示的DFA：210bbaaa化簡(jiǎn)后的DFA為：20baa（2）、題中所給即為一個(gè)DFA，不需要確定化，只對(duì)它進(jìn)行最小化即可。首先將狀態(tài)劃分為兩個(gè)集合0，1，2，3，4，5。有0，1a=1，0，1b=2，4和2，3，4，5a=1，3，0，5，2，3，4，5b=2，3，4，5，所以可以進(jìn)一步劃分為0，1，2，4，3，5，然后有0，1a=1，0，1b=2，4，2，4a=1，0，2，4b=3，5，3，5a=3，5，3，5b=2，4。因此，最后劃分結(jié)果是0，1，2，4，3，5。最小化后的DFA如下圖所示：10b aa2b ba13、 （1）給出描述C浮點(diǎn)數(shù)的DFA；14、 構(gòu)造一個(gè)DFA，它接

24、受=0，1上所有滿足如下條件的字符串：每個(gè)1都有0直接跟在右邊。分析：對(duì)這類題型的固定解法分4步進(jìn)行：首先根據(jù)語言寫出正規(guī)表達(dá)式；然后根據(jù)正規(guī)表達(dá)式構(gòu)造相應(yīng)的NFA；然后，對(duì)NFA進(jìn)行確定化得到DFA；最后對(duì)DFA化簡(jiǎn)得到最簡(jiǎn)DFA。第一步：寫出正規(guī)表達(dá)式。根據(jù)題意，該DFA接受的字符串由0和1組成，并且每個(gè)1的后面都有0直接跟在右邊，因此，可以將該字符串理解為由0和10構(gòu)成的串，則相應(yīng)的正規(guī)表達(dá)式就是(010)*。第二步：構(gòu)造NFA。首先得出下圖：(010)*XY然后對(duì)上圖進(jìn)行分解后得到如下圖所示的NFA。XY12010第三步：確定化，得到DFA。確定化結(jié)果如表14.1所列；給狀態(tài)編號(hào)，得到

25、表14.2所示的狀態(tài)轉(zhuǎn)換矩陣：狀態(tài)01X，1，Y1，Y21，Y1，Y221，YØ表14.1 狀態(tài)轉(zhuǎn)換矩陣狀態(tài)0101211221表14.2 新的狀態(tài)轉(zhuǎn)換矩陣根據(jù)狀態(tài)轉(zhuǎn)換矩陣得到DFA如下圖所示：21011000第四步：對(duì)該DFA進(jìn)行最小化。其分析過程如下：0，1，20，10=1，0，11=20，1，2最小化后的DFA如圖所示，該DFA即為所求。1010015、 給定右線性文法G：S0S1S1A0BA1C1B0C0C0C1C01求出一個(gè)與G等價(jià)的左線性文法。分析：根據(jù)右線性文法求左線性文法沒有直接的方法，但可以通過狀態(tài)轉(zhuǎn)換圖去轉(zhuǎn)換。可以先求出文法G的狀態(tài)轉(zhuǎn)換圖，再根據(jù)狀態(tài)轉(zhuǎn)換圖寫出相應(yīng)

26、的左線性文法。文法G對(duì)應(yīng)的狀態(tài)轉(zhuǎn)換圖如下所示：SZ100，1BCA10，10，1001對(duì)狀態(tài)轉(zhuǎn)換圖進(jìn)行確定化，得到狀態(tài)轉(zhuǎn)換矩陣：狀態(tài)01SS，BS，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)編號(hào)，得到新的狀態(tài)轉(zhuǎn)換矩陣：狀態(tài)01012132214334434根據(jù)狀態(tài)轉(zhuǎn)換矩陣獲得DFA如下：040123100101101還可以對(duì)上圖的DFA進(jìn)行化簡(jiǎn)，狀態(tài)3和4可以合并，化簡(jiǎn)后的DFA如下圖所示：0，1ST01BA0101不難看出，該DFA接受的語言是0，1上包含00或11的字符串。根據(jù)化簡(jiǎn)后的DF

27、A，我們可以寫出相應(yīng)的左線性文法G：TA0B1T0T1AB00BA1116、 *非形式的說明17、 *下面的字集是否為正規(guī)集？或?qū)懗銎湔?guī)式，或給出否證。（1） L1=anbnn0；（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的單詞符號(hào)的LEX程序。20、 假定有正規(guī)定義式A0abA1A0 A0AnAn-1 An-1考慮詞形An（1） 把An中所有簡(jiǎn)名都換掉，最終所得的正規(guī)式的長(zhǎng)度是多少？（2） 字集An的元素是什么？把它們非形式的表示成n的函數(shù)；（3）

28、 證明識(shí)別An的DFA只需用2n+1個(gè)狀態(tài)就足夠了。21、 把LEX的“動(dòng)作”成分加以充實(shí)使得可用它來編寫語法制導(dǎo)編輯器。第四章 語法分析自上而下分析1、考慮下面的文法G1： Sa(T)TT，SS（1）消去G1的左遞歸。然后對(duì)每個(gè)非終結(jié)符，寫出不帶回溯的遞歸子程序。（2）經(jīng)改寫后的文法是否是LL(1)的？給出它的預(yù)測(cè)分析表。解：（1）按照T、S的順序消除左遞歸，得到文法：G(S)Sa(T)TSTT，ST 對(duì)于非終結(jié)符S,T, T的遞歸子程序如下：Procedure S;Begin If sym = a or sym = Then advanceElse ifsym = (Then begin

29、Advance ; T; If sym = ) Then advance Else errorEndElse errorEnds;Procedure T;Begin S; T;Ends;Procedure TBegin If sym = ,Then begin Advance ;S; T Endsends;（2）計(jì)算每個(gè)非終結(jié)符的FIRST集合和FOLLOW集合：FIRST（S）=a，( FIRST（T）=a，( FIRST（T）=，F(xiàn)OLLOW（S）= )，#FOLLOW（T）= ) FOLLOW（T）= ) 從而可見改造后的文法符合LL(1)文法的充分必要條件，所以是LL(1)的。 該文法

30、的預(yù)測(cè)分析表a(),#SS->aS->S->(T)TT->S TT->S TT->S TTT->T->,S T2、對(duì)下面的文法G：ETEE+ETFTTTFPFF*FP(E)ab（1） 計(jì)算這個(gè)文法的每個(gè)非終結(jié)符的FIRST和FOLLOW。（2） 證明這個(gè)文法是LL(1)的。（3） 構(gòu)造它的預(yù)測(cè)分析表。（4） 構(gòu)造它的遞歸下降分析程序。分析：對(duì)于這類題目，我們首先應(yīng)當(dāng)檢查文法是否符合LL(1)文法的條件，根據(jù)需要，先通過消除左遞歸、提取右公因子的方法，把文法改造成符合LL(1)文法的條件，在此基礎(chǔ)上，我們才能構(gòu)造出不帶回溯的遞歸下降識(shí)別程序。注意，

31、本題在構(gòu)造子程序時(shí)，對(duì)于每個(gè)產(chǎn)生式候選，在調(diào)用第一個(gè)非終結(jié)符對(duì)應(yīng)的子程序之前，檢查了首符集。解：（1） 計(jì)算每個(gè)非終結(jié)符的FIRST集合和FOLLOW集合如下：FIRST（E）=(，a，b，F(xiàn)IRST（E）=+，F(xiàn)IRST（T）=(，a，b，F(xiàn)IRST（T）=(，a，b，F(xiàn)IRST（F）=(，a，b，F(xiàn)IRST（F）=*，F(xiàn)IRST（P）=(，a，b，F(xiàn)OLLOW（E）=#，)FOLLOW（E）=#，)FOLLOW（T）=+，)，#FOLLOW（T）=+，)，#FOLLOW（F）=(，a，b，+，)，#FOLLOW（F）=(，a，b，+，)，#FOLLOW（P）=*，(，a，b，+，)，#（2

32、） 本文法是LL ( 1 )文法。證明： 通過觀察可知文法中不含有左遞歸，滿足LL (1)文法定義的第一個(gè)條件?？紤]下列產(chǎn)生式：E+ETTF*FP(E)ab因?yàn)椋篎IRST（+E）FIRST（）=+=ØFIRST（E）FOLLOW（E）=+#，)= ØFIRST（T）FIRST（）=(，a，b，=ØFIRST（T）FOLLOW（T）=(，a，b，+，)，#=ØFIRST（*F）FIRST（）=*=ØFIRST（F）FOLLOW（F）=*(，a，b，+，)，#= ØFIRST（E）FIRST（a）FIRST（b）FIRST（）= 

33、16;所以該文法是LL(1)文法。（3） 構(gòu)造其預(yù)測(cè)分析表： 預(yù)測(cè)分析表+ * ( ) a b #EEàT EEàT EEàT EEàT EEEà+EE àE ->TT àFTTàFTTàFTTàFTTTàT à TTàTàTTàTT àTTàFF àPFFàPFPàPFFàPFFF à F à*FF à FàFàFàF&

34、#224;FàPP à(E)PàaPàbPà （4） 構(gòu)造其遞歸下降分析程序： Procedure E;Begin T ;EEnd ;Procedure E ;Begin Ifsym = + Then begin Acvance ;E End End ;ProcedureT ;Begin F ; TEnd ;Procedure T ;Begin If sym first ( T ) Then T Else if sym = * then errorEnd ;Procedure F ;Begin If sym first ( P ) P; F;E

35、nd ; Procedure F BeginIf sym = * Then begin Advance ; F EndEnd;Procedure P Begin Ifsym = a orsym = b or sym = Then acvance Else if sym = ( Then begin Advance ; E ; If sym = ) Then advance Else errorEndElse error End;3、下面文法中，哪些是LL(1)的，說明理由。（1）、SAbcAaBb（2）、SAbAaBBb（3）、SABBAAaBb（4）、SaSeBBbBeCCcCed分析：判斷

36、文法是否是LL(1)的，要根據(jù)LL(1)文法的條件逐一檢查：首先要確定文法不含左遞歸；隨后計(jì)算文法的各非終結(jié)符（X）的首符集FIRST（X）和隨符集FOLLOW（X）。首先要理解這兩個(gè)集合的計(jì)算方法，特別要注意算法終止的條件：直到集合不再變化為止。也就是說，反復(fù)檢查每一個(gè)產(chǎn)生式，直到從頭到尾檢查了所有產(chǎn)生式，而FIRST集合和FOLLOW集合都沒有變化了，這時(shí)候計(jì)算才能結(jié)束。最后根據(jù)LL(1)文法的充分必要條件（即LL(1)文法定義）來判斷是否是LL(1)文法。解：（1） 該文法不含左遞歸，計(jì)算每個(gè)非終結(jié)符的FIRST集合和FOLLOW集合如下：FIRST（S）=a，b，cFIRST（A）=a

37、，F(xiàn)IRST（B）=b，F(xiàn)OLLOW（S）=#FOLLOW（A）=b，cFOLLOW（B）=c可見該文法滿足LL(1)文法的三個(gè)條件，是LL(1)文法。（2） 該文法不含左遞歸，計(jì)算每個(gè)非終結(jié)符的FIRST集合和FOLLOW集合如下：FIRST（S）=a，bFIRST（A）=a，b，F(xiàn)IRST（B）=b，F(xiàn)OLLOW（S）=#FOLLOW（A）=bFOLLOW（B）=b考慮AaB，因?yàn)镕IRST（B）FOLLOW（A）=bØ，所以該文法不是LL(1)文法。（3） 該文法不含左遞歸，計(jì)算每個(gè)非終結(jié)符的FIRST集合和FOLLOW集合如下：FIRST（S）=a，b，F(xiàn)IRST（A）=a，

38、FIRST（B）=b，F(xiàn)OLLOW（S）=#FOLLOW（A）=a，b，#FOLLOW（B）=a，b，#考慮Aa和Bb，因?yàn)镕IRST（a）FOLLOW（A）=aØFIRST（b）FOLLOW（B）=bØ所以該文法不是LL(1)文法。（4） 該文法不含左遞歸，計(jì)算每個(gè)非終結(jié)符的FIRST集合和FOLLOW集合如下：FIRST（S）=a，b，c，dFIRST（B）=b，c，dFIRST（C）=c，dFOLLOW（S）=e，#FOLLOW（B）=e，#FOLLOW（C）=e，#可見該文法滿足LL(1)文法的三個(gè)條件，是LL(1)文法。4、對(duì)下面文法：Expr-ExprExpr(

39、Expr)Var ExprTail-ExprVarid VarTailVarTail(Expr)（1）、構(gòu)造LL(1)分析表。（2）、給出對(duì)句子id-id(id)的分析過程。分析：構(gòu)造文法的預(yù)測(cè)分析表，通常應(yīng)當(dāng)按下列順序進(jìn)行：（1）、消除文法的左遞歸（包括所有直接左遞歸和間接左遞歸）；（2）、對(duì)消除左遞歸后的文法，提取左公因子；（3）、對(duì)經(jīng)過上述改造后的文法，計(jì)算它的每個(gè)非終結(jié)符的FIRST集合和FOLLOW集合；（4）、根據(jù)FIRST集合和FOLLOW集合構(gòu)造預(yù)測(cè)分析表。第一步對(duì)文法G的每個(gè)產(chǎn)生式A執(zhí)行第一步和第三步；第二步對(duì)每個(gè)終結(jié)符aFIRST()，把A加至MA，a中；第三步若FIRST

40、()，則對(duì)任何bFOLLOW(A)把A加至MA，b中；第四步把所有無定義的MA，a標(biāo)上“出錯(cuò)標(biāo)志”。解：（1）、計(jì)算每個(gè)非終結(jié)符的FIRST集合和FOLLOW集合如下：FIRST(Expr)=-，(，idFIRST(ExprTail)=-，F(xiàn)IRST(Var)=idFIRST(VarTail)=(，F(xiàn)OLLOW(Expr)=)，#FOLLOW(ExprTail)=)，#FOLLOW(Var)=-，)，#FOLLOW(VarTail)=-，#構(gòu)造其預(yù)測(cè)分析表如下：-id()#ExprExpr- ExprExpr ExprExpr-( Expr)ExprTailExprTail-ExprExprT

41、ailExprTailVarVarid VarTailVarTailVarTailVarTail(Expr)VarTailVarTail（2）、句子id-id(id)的分析過程如下：步驟符號(hào)棧輸入串所用產(chǎn)生式0# Exprid-id(id) #1# ExprTail Varid-id(id) #ExprVar ExprTail2# ExprTail VarTail idid-id(id) #Varid VarTail3# ExprTail VarTail-id(id) #4# ExprTail-id(id) #VarTail5# Expr -id(id) #ExprTail-Expr6# Ex

42、pr-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) #12# ExprTail ) Expr (id) #VarTail(Expr)13# ExprTail ) Expr(id) #14# ExprTail ) ) Expr (id) #15# ExprTail ) ) Exprid) #16# ExprTail ) ) Expr

43、Tal Varid) #ExprVar ExprTail17# ExprTail ) ) ExprTail VarTail idid) #Varid VarTail18# ExprTail ) ) ExprTail VarTail) #19# ExprTail ) ) ExprTail) #VarTail20# ExprTail ) ) #ExprTail21# ExprTail ) #22# ExprTail#23#ExprTailsuc5、把下面文法改寫為L(zhǎng)L(1)的：DeclistDeclist；DeclDeclDeclIdList：TypeIdListIdList，ididTypeSc

44、alarTypearray(ScalarTypeList) of TypeScalarTypeidBound.BoundBoundSign IntLiteralidSign+-ScalarTypeListScalarTypeList，ScalarTypeScalarType分析：本題主要考察理解和運(yùn)用消除文法的左遞歸、提取公因子等算法的能力，為判斷文法是否是LL(1)文法，還要計(jì)算文法的FIRST集合和FOLLOW集合。消除文法的左遞歸的基本思想是，將文法規(guī)則中的左遞歸結(jié)構(gòu)變換成等價(jià)的右遞歸結(jié)構(gòu)。提取左公因子的算法，是對(duì)包含公共左因子的產(chǎn)生式候選，反復(fù)提取左因子，就能夠把每個(gè)非終結(jié)符（包括新引

45、進(jìn)者）的所有候選首符集變成為兩兩不相交。消除文法的左遞歸、提取左公共因子后，再計(jì)算文法的各非終結(jié)符（X）的首符集FIRST（X）和隨符集FOLLOW(X)，然后根據(jù)LL(1)文法的充分必要條件（即LL(1)文法的定義）來判斷文法是否是LL(1)文法。解：首先消除左遞歸，得到文法G(Declist)：DeclistDecl DeclistDeclist；Decl DeclistDeclIdList：TypeIdListid IdListIdList，id ListTypeScalarTypearray(ScalarTypeList) of TypeScalarTypeidBound.BoundB

46、oundSign IntLiteralidSign+-ScalarTypeListScalarType ScalarTypeListScalarTypeList，ScalarType ScalarTypeList顯然，改造后的文法沒有左公共因子，計(jì)算每個(gè)非終結(jié)符的FIRST集合和FOLLOW集合如下：FIRST(Declist)=idFIRST(Declist)=；，F(xiàn)IRST(Decl)=idFIRST(IdList)=idFIRST(IdList)=；，F(xiàn)IRST(Type)=id，+，-，IntLiteral，arrayFIRST(ScalarType)=id，+，-，IntLitera

47、lFIRST(Bound)=id，+，-，InLiteralFIRST(Sign)=+，-，F(xiàn)IRST(ScalarTypeList)=id，+，-，IntLiteral FIRST(ScalarTypeList)=，F(xiàn)OLLOW(Declist)=#FOLLOW(Declist)=#FOLLOW(Decl)=id，；FOLLOW(IdList)=：FOLLOW(IdList)=：FOLLOW(Type)=id，；FOLLOW(ScalarType)=id，；，），F(xiàn)OLLOW(Bound)=id，；，），.FOLLOW(Sign)=IntLiteralFOLLOW(ScalarTypeList)=)FOLLOW(ScalarTypeList)=)顯