編譯原理-練習(xí)

1、編譯原理編譯原理 練習(xí)練習(xí)1 王金偉 計(jì)算機(jī)與信息工程學(xué)院 天津師范大學(xué) 練習(xí)練習(xí)1.1 基本概念基本概念 l編譯程序的結(jié)構(gòu)編譯程序的結(jié)構(gòu) l上下文無關(guān)文法的一些概念上下文無關(guān)文法的一些概念 l詞法分析詞法分析 l語(yǔ)法分析語(yǔ)法分析 l自上而下自上而下 l自下而上自下而上 1.填充下面編譯程序總框圖填充下面編譯程序總框圖 源程序源程序 目標(biāo)程序目標(biāo)程序 ( 字符串字符串) 詞法分析器詞法分析器 語(yǔ)法分析器語(yǔ)法分析器 語(yǔ)義分析和中間代碼生成器語(yǔ)義分析和中間代碼生成器 代碼優(yōu)化器代碼優(yōu)化器 目標(biāo)代碼生成器目標(biāo)代碼生成器 表表 格格 管管 理理 出出 錯(cuò)錯(cuò) 處處 理理 對(duì)于對(duì)于上的每一個(gè)正規(guī)式上的每一

2、個(gè)正規(guī)式V，存在一個(gè)，存在一個(gè)上的上的DFA M， 使得使得L(M) = L(V) 問題問題：如何由一個(gè)正規(guī)式：如何由一個(gè)正規(guī)式V，構(gòu)造一個(gè)，構(gòu)造一個(gè)DFA M 思路思路：分兩步走：分兩步走 1.根據(jù)根據(jù)V，構(gòu)造一個(gè)，構(gòu)造一個(gè)NFA M，使得，使得L(M) = L(V) 2.將將M確定化，變?yōu)榇_定化，變?yōu)镈FA M 第一步第一步，在，在上構(gòu)造一個(gè)上構(gòu)造一個(gè)NFA M (1)構(gòu)造一個(gè)拓廣的轉(zhuǎn)換圖構(gòu)造一個(gè)拓廣的轉(zhuǎn)換圖 練習(xí)練習(xí)1.2 詞法分析詞法分析 (2)使用分裂規(guī)則對(duì)使用分裂規(guī)則對(duì)V進(jìn)行分裂，加進(jìn)新結(jié)點(diǎn)，直到把進(jìn)行分裂，加進(jìn)新結(jié)點(diǎn)，直到把 圖轉(zhuǎn)換成每條弧上標(biāo)識(shí)為圖轉(zhuǎn)換成每條弧上標(biāo)識(shí)為上的一個(gè)字

3、符或上的一個(gè)字符或 最后得到一個(gè)最后得到一個(gè)NFA M 且且L(M) = L(V) 第二步第二步，把，把M確定化確定化 (1)兩個(gè)概念兩個(gè)概念 定義定義1：假定：假定I是是M的狀態(tài)集的子集，定義的狀態(tài)集的子集，定義I的的閉包閉包 _CLOSURE(I)為：為： (a)若若qI，則，則q_CLOSURE(I) (b)若若qI，那么從，那么從q出發(fā)經(jīng)任意條出發(fā)經(jīng)任意條弧而能到達(dá)的任弧而能到達(dá)的任 何狀態(tài)何狀態(tài)q都屬于都屬于_CLOSURE(I) ； 定義定義2：假定：假定I是是M的狀態(tài)集的子集，定義的狀態(tài)集的子集，定義 Ia =_CLOSURE(J) 其中，其中，J是所有那些可從是所有那些可從I中

4、的某一狀態(tài)結(jié)點(diǎn)出發(fā)經(jīng)過中的某一狀態(tài)結(jié)點(diǎn)出發(fā)經(jīng)過 一條一條a弧而到達(dá)的狀態(tài)結(jié)點(diǎn)的全體弧而到達(dá)的狀態(tài)結(jié)點(diǎn)的全體 ：有如下一個(gè)狀態(tài)轉(zhuǎn)換圖：有如下一個(gè)狀態(tài)轉(zhuǎn)換圖 假定假定 I=1, 2，求，求Ia = ？ 解：解： Ia =_CLOSURE(J) J = _CLOSURE(J) = Ia=5, 6, 2, 4, 7, 3, 8 1 a a 5 4 38 2 6 7 a a a a 4,5,3 5,6,2,4,7,3,8 a a a a a a 5 4 3 6 2 7 8 (2)用子集法把用子集法把M確定化確定化 設(shè)設(shè) = a，b 構(gòu)造一張表構(gòu)造一張表 IIa =_CLOSURE(J)Ib =_CLOS

5、URE(J) 集合集合1 集合集合1 集合集合1 集合集合2 集合集合2 集合集合2 集合集合3 集合集合3 集合集合3 集合集合4 集合集合4 集合集合4 _CLOSURE(X) IIa =_CLOSURE(J)Ib =_CLOSURE(J) _CLOSURE(X) 集合集合1 集合集合2 集合集合3 集合集合4 集合集合1 集合集合3 集合集合4 集合集合2 集合集合2 集合集合4 集合集合3 集合集合1 Sab 0 1 2 3 4 1 3 4 2 2 4 3 1 把得到的每個(gè)集合看成一個(gè)狀態(tài)，得到一張狀態(tài)轉(zhuǎn)換表，把得到的每個(gè)集合看成一個(gè)狀態(tài)，得到一張狀態(tài)轉(zhuǎn)換表， 該表的初態(tài)就是該表的初態(tài)

6、就是_CLOSURE(X)，它的終態(tài)是那些含有終，它的終態(tài)是那些含有終 態(tài)態(tài)Y的子集，這樣就得到一個(gè)的子集，這樣就得到一個(gè)DFA M 且且L(M) = L(M) 1.構(gòu)造下列正規(guī)式相應(yīng)的構(gòu)造下列正規(guī)式相應(yīng)的DFA。 (1) 1(0|1)*101 (2) 0*10*10*10* (1)1(0|1)*101 得到一個(gè)得到一個(gè)NFA M 且且 L(M) = L(V) 用子集法對(duì)用子集法對(duì)M進(jìn)行確定化進(jìn)行確定化 構(gòu)造一張表構(gòu)造一張表 II0 =_CLOSURE(J)I1 =_CLOSURE(J) -J=1 X 1, 2, 3 - 2, 32, 3 2, 3, 4 1, 2, 3 2, 3 2, 3,

7、42, 3, 5 2, 3, 4 2, 3, 4 J=2 J=2, 4J=2 J=2, 4 J=2, 5J=2, 4 2, 3, 52, 32, 3, 4,Y 2, 3, 4, Y2, 3, 52, 3, 4 J=2J=2, 4, Y J=2, 5J=2, 4 II0 =_CLOSURE(J)I1 =_CLOSURE(J) X 1, 2, 3 2, 3 2, 3, 4 2, 3, 5 2, 3, 4, Y - 2, 3 2, 3 2, 3, 5 2, 3 2, 3, 5 1, 2, 3 2, 3, 4 2, 3, 4 2, 3, 4 2, 3, 4, Y 2, 3, 4 把每個(gè)子集看成一個(gè)狀態(tài)

8、，得到一個(gè)把每個(gè)子集看成一個(gè)狀態(tài)，得到一個(gè)DFA M， 且且L(M) = L(M) s01 0 1 2 3 4 5 - 2 2 4 2 4 1 3 3 3 5 3 0 1 2 3 23 32 4 3 4 5 1 5 3 2 4 s01 0 1 2 3 4 5 - 2 2 4 2 4 1 3 3 3 5 3 把把DFA M進(jìn)行化簡(jiǎn)進(jìn)行化簡(jiǎn) 解解: 把把M狀態(tài)集分為兩組狀態(tài)集分為兩組: 終態(tài)結(jié)點(diǎn)終態(tài)結(jié)點(diǎn)5 非終態(tài)結(jié)點(diǎn)非終態(tài)結(jié)點(diǎn)0，1，2，3，4 考察考察0，1，2，3，4 因?yàn)?，因?yàn)椋?0，1，2，3，40 = 0，1，2，3，41 = 所以，所以， 0，1，2，3，4可再分，分成可再分，分成0,

9、1,2,3和和4 考察考察0，1，2, 3 因?yàn)?，因?yàn)椋?0,1,2,30 = 所以，所以， 0,1,2,3必可再分必可再分 看圖，把看圖，把0,1,2,3分割為分割為0,1,2和和3 2,4 1,3,5 0,1,2,3,4 0,1,2,3,4 J=2,4 J=1,3,5 2，40，1，2，3J=2,4 考察考察0,1,2 因?yàn)?，因?yàn)椋?0,1,20 = 0,1,21 = 所以，所以， 0,1,2必可再分必可再分 看圖，把看圖，把0,1,2分割為分割為0， 1,2 考察考察1,2 因?yàn)?，因?yàn)椋?1,20 = 1,21 = 所以所以1,2不可再分不可再分 J=2 J=1,3 20,1,2 1,3

10、0,1,2 J=2 J=3 21,2 33 所以，所以， 最終把最終把M分割為分割為0， 1,2 ， 3 ， 4 ， 5 用狀態(tài)用狀態(tài)2代替狀態(tài)代替狀態(tài)1，把引向狀態(tài)，把引向狀態(tài)1的箭弧都引向狀態(tài)的箭弧都引向狀態(tài)2， 把把1消去，得到一個(gè)消去，得到一個(gè)DFA M (2) 0*10*10*10* 得到一個(gè)得到一個(gè)NFA M 且且 L(M) = L(V) II0 =_CLOSURE(J)I1 =_CLOSURE(J) J=0X,0,1 0,1 0,1 3,42,3,4 2,3,4 2,3,4 0,1 3,43,4 5,6,7 5,6,7 J=3J=5 J=0 J=8 J=3 J=2 5,6,76,

11、78,9,Y 6,76,78,9,Y J=6 J=5 J=6J=8 J=2 8,9,YJ=99,Y 9,Y - J=99,Y- II0 =_CLOSURE(J)I1 =_CLOSURE(J) X,0,1 0,1 0,1 3,42,3,4 2,3,4 2,3,4 0,1 3,43,4 5,6,7 5,6,7 5,6,76,78,9,Y 6,76,78,9,Y 8,9,Y9,Y 9,Y - 9,Y- 把每個(gè)子集看成一個(gè)狀態(tài)，得到一個(gè)把每個(gè)子集看成一個(gè)狀態(tài)，得到一個(gè)DFA M， 且且L(M) = L(M) s01 0 1 2 3 4 5 6 7 1 1 3 3 5 5 7 7 2 2 4 4 6 6

12、 - - 0 1 2 3 4 5 6 7 1 1 3 3 5 5 7 7 2 2 4 4 6 6 s01 0 1 2 3 4 5 6 7 1 1 3 3 5 5 7 7 2 2 4 4 6 6 - - (3) :把把DFA M進(jìn)行化簡(jiǎn)進(jìn)行化簡(jiǎn) 解解: 把把M狀態(tài)集分為兩組狀態(tài)集分為兩組: 終態(tài)結(jié)點(diǎn)終態(tài)結(jié)點(diǎn)6,7 非終態(tài)結(jié)點(diǎn)非終態(tài)結(jié)點(diǎn)0,1,2,3,4,5 考察考察6,7 因?yàn)?，因?yàn)椋?6,70 = 6,71 = 所以，所以， 6,7不可再分；不可再分； 考察考察0,1,2,3,4,5 因?yàn)椋驗(yàn)椋?0,1,2,3,4,50 = 0,1,2,3,4,51 = 看圖，把看圖，把0,1,2,3,4,

13、5分割為分割為0,1,2,3和和4,5 7 6,7 6,7 J=7 1,3,50,1,2,3,4,5J=1,3,5 2,4,60,1,2,3,4,5J=2,4,6 考察考察4,5 因?yàn)?，因?yàn)椋?4,50 = 4,51 = 所以，所以， 4,5 不可再分不可再分 考察考察0,1,2,3 因?yàn)椋驗(yàn)椋?0,1,2,30 = 0,1,2,31 = 所以所以0,1,2,3可再分可再分 看圖，把看圖，把0,1,2,3分割為分割為0,1和和2,3 J=5 J=6 54,5 66,7 J=1,3 J=2,4 1,30,1,2,3 2,40,1,2,3 4,5 6,7 考察考察2,3 因?yàn)?，因?yàn)椋?2,30

14、= 2,31 = 所以，所以， 2,3 不可再分不可再分 考察考察0,1 因?yàn)?，因?yàn)椋?0,10 = 0,11 = 所以，所以， 0,1 不可再分不可再分 J=3 J=4 32,3 44,5 J=1 J=2 10,1 22,3 所以，所以， 最終把最終把M分割為分割為0,1， 2,3 ， 4,5 ， 6,7 用狀態(tài)用狀態(tài)1代替狀態(tài)代替狀態(tài)0，把引向狀態(tài)，把引向狀態(tài)0的箭弧都引向狀態(tài)的箭弧都引向狀態(tài)1， 把把0消去；消去； 用狀態(tài)用狀態(tài)3代替狀態(tài)代替狀態(tài)2，把引向狀態(tài)，把引向狀態(tài)2的箭弧都引向狀的箭弧都引向狀 態(tài)態(tài)3，把，把2消去；消去； 用狀態(tài)用狀態(tài)5代替狀態(tài)代替狀態(tài)4，把引向狀態(tài)，把引向狀態(tài)

15、4的箭弧都引向狀的箭弧都引向狀 態(tài)態(tài)5，把，把4消去；消去； 用狀態(tài)用狀態(tài)7代替狀態(tài)代替狀態(tài)6，把引向狀態(tài)，把引向狀態(tài)6的箭弧都引向狀的箭弧都引向狀 態(tài)態(tài)7，把，把6消去；得到一個(gè)化簡(jiǎn)得消去；得到一個(gè)化簡(jiǎn)得DFA M 2.把把(a)和和(b)分別確定化和最分別確定化和最 少化少化 (a)(b) (1)用子集法對(duì)用子集法對(duì)M進(jìn)行確定化進(jìn)行確定化 構(gòu)造一張表構(gòu)造一張表 IIa =_CLOSURE(J)Ib =_CLOSURE(J) J=0,1J=1 0 0,1 0,1 01 1 1 0,1 - J=0 J=1J=0,1 - 把每個(gè)子集看成一個(gè)狀態(tài)，得到一個(gè)把每個(gè)子集看成一個(gè)狀態(tài)，得到一個(gè)DFA M

16、， 且且L(M) = L(M) sab 0 1 2 1 1 0 2 2 - IIa =_CLOSURE(J)Ib =_CLOSURE(J) 0 1 2 1 21 0 2 0 0,1 0,1 01 1 1 0,1 - sab 0 1 2 1 1 0 2 2 - (2) 把把DFA M進(jìn)行化簡(jiǎn)進(jìn)行化簡(jiǎn) 解解: 把把M狀態(tài)集分為兩組狀態(tài)集分為兩組: 終態(tài)結(jié)點(diǎn)終態(tài)結(jié)點(diǎn)0，1 非終態(tài)結(jié)點(diǎn)非終態(tài)結(jié)點(diǎn)2 考察考察0，1 因?yàn)椋驗(yàn)椋?0，1a = 0，1b = 所以，所以， 0，1不可再分不可再分 1 2 0,1 2 J=1 J=2 所以，所以， 最終把最終把M分割為分割為0，1， 2 用狀態(tài)用狀態(tài)0代替狀

17、態(tài)代替狀態(tài)1，把引向狀態(tài)，把引向狀態(tài)1的箭弧都引向狀的箭弧都引向狀 態(tài)態(tài)0，把，把1消去，得到一個(gè)消去，得到一個(gè)DFA M (2)用子集法對(duì)用子集法對(duì)M進(jìn)行確定化進(jìn)行確定化 構(gòu)造一張表構(gòu)造一張表 IIa =_CLOSURE(J)Ib =_CLOSURE(J) J=1J=2 0 1 1 12 4 2 1 3 J=1 J=4J=1 J=3 4 3 05 32 J=0J=5 J=3J=2 J=5J=4 554 (2) 把把DFA M進(jìn)行化簡(jiǎn)進(jìn)行化簡(jiǎn) 解解: 把把M狀態(tài)集分為兩組狀態(tài)集分為兩組: 終態(tài)結(jié)點(diǎn)終態(tài)結(jié)點(diǎn)0，1 非終態(tài)結(jié)點(diǎn)非終態(tài)結(jié)點(diǎn)2，3，4，5 考察考察0，1 因?yàn)?，因?yàn)椋?0，1a = 0

18、，1b = 所以，所以， 0，1不可再分不可再分 1 2，4 0,1 2，3，4，5 J=1 J=2，4 考察考察2，3，4，5 因?yàn)?，因?yàn)椋?2,3,4,5a = 所以，所以， 2,3,4,5可再分可再分 看圖，把看圖，把2,3,4,5分割為分割為2,4和和3,5 0,1,3,52,3,4,5J=0,1,3,50,1 考察考察2，4 因?yàn)?，因?yàn)椋?2，4a = 2，4b = 所以，所以， 2，4不可再分不可再分 考察考察3，5 因?yàn)?，因?yàn)椋?3，5a = 3，5b = 所以，所以， 3，5不可再分不可再分 0,1 3,5 0,1 3,5 J=0,1 J=3,5 3,5 2,4 3,5 2,4

19、 J=3,5 J=2,4 所以，最終把所以，最終把M分割為分割為0，1， 2，4 ， 3，5 用狀態(tài)用狀態(tài)0代替狀態(tài)代替狀態(tài)1，把引向狀態(tài)，把引向狀態(tài)1的箭弧都引向狀的箭弧都引向狀 態(tài)態(tài)0，把，把1消去；用狀態(tài)消去；用狀態(tài)2代替狀態(tài)代替狀態(tài)4，把引向狀態(tài)，把引向狀態(tài)4 的箭弧都引向狀態(tài)的箭弧都引向狀態(tài)2，把，把4消去；用狀態(tài)消去；用狀態(tài)5代替狀態(tài)代替狀態(tài)3， 把引向狀態(tài)把引向狀態(tài)3的箭弧都引向狀態(tài)的箭弧都引向狀態(tài)5，把，把3消去；得到消去；得到 一個(gè)一個(gè)DFA M 3.設(shè)計(jì)一個(gè)設(shè)計(jì)一個(gè)DFA，它接受，它接受0，1上所有滿足如下條件的字符串：上所有滿足如下條件的字符串： 每個(gè)每個(gè)1都有都有0直接

20、跟在右邊。直接跟在右邊。 解解: (1)根據(jù)題意，得到相應(yīng)的正規(guī)式：根據(jù)題意，得到相應(yīng)的正規(guī)式： (0|10)* (2)由以上正規(guī)式構(gòu)造相應(yīng)的由以上正規(guī)式構(gòu)造相應(yīng)的NFA為：為： (1)用子集法對(duì)用子集法對(duì)M進(jìn)行確定化進(jìn)行確定化 構(gòu)造一張表構(gòu)造一張表 II0 =_CLOSURE(J)I1 =_CLOSURE(J) J=1J=2 x,1,y 1,y 1,y 1,y2 2 2 1,y - J=1 J=2J=1 - 把每個(gè)子集看成一個(gè)狀態(tài)，得到一個(gè)把每個(gè)子集看成一個(gè)狀態(tài)，得到一個(gè)DFA M， 且且L(M) = L(M) s01 0 1 2 1 1 1 2 2 - II0 =_CLOSURE(J)I1

21、 =_CLOSURE(J) 0 1 2 1 21 1 2x,1,y 1,y 1,y 1,y2 2 2 1,y - s01 0 1 2 1 1 1 2 2 - (2) 把把DFA M進(jìn)行化簡(jiǎn)進(jìn)行化簡(jiǎn) 解解: 把把M狀態(tài)集分為兩組狀態(tài)集分為兩組: 終態(tài)結(jié)點(diǎn)終態(tài)結(jié)點(diǎn)0，1 非終態(tài)結(jié)點(diǎn)非終態(tài)結(jié)點(diǎn)2 考察考察0，1 因?yàn)?，因?yàn)椋?0，10 = 0，11 = 所以，所以， 0，1不可再分不可再分 1 2 0,1 2 J=1 J=2 所以，所以， 最終把最終把M分割為分割為0，1， 2 用狀態(tài)用狀態(tài)1代替狀態(tài)代替狀態(tài)0，把引向狀態(tài)，把引向狀態(tài)0的箭弧都引向狀的箭弧都引向狀 態(tài)態(tài)1，把，把0消去，得到一個(gè)消去

22、，得到一個(gè)DFA M 問題一：?jiǎn)栴}一：消除文法直接左遞歸方法消除文法直接左遞歸方法： 設(shè)有產(chǎn)生式設(shè)有產(chǎn)生式 PP1|P2|Pm|1|2|n 其中每個(gè)其中每個(gè)i不以不以P開頭，每個(gè)開頭，每個(gè)i不為不為 消除消除P的直接左遞歸性就是把這些規(guī)則改寫成：的直接左遞歸性就是把這些規(guī)則改寫成： P1P|2P|nP P1P| 2P|mP| 練習(xí)練習(xí)1.3 自上而下的語(yǔ)法分析自上而下的語(yǔ)法分析 4.消除整個(gè)文法的左遞歸的算法消除整個(gè)文法的左遞歸的算法 如果文法不含回路（形如如果文法不含回路（形如 的推導(dǎo)），也不含有以的推導(dǎo)），也不含有以 為右部的產(chǎn)生式，則下面算法可以消除左遞歸為右部的產(chǎn)生式，則下面算法可以消

23、除左遞歸 (1)(1)把文法把文法G G的所有非終結(jié)符按任一種順序排列成的所有非終結(jié)符按任一種順序排列成 P P1 1,P,P2 2,P,Pn n；按此順序執(zhí)行；按此順序執(zhí)行 (2)for i = 1 to n do(2)for i = 1 to n do for j = 1 to i-1 do for j = 1 to i-1 do 把形如把形如P Pi iPPj j的規(guī)則改寫成的規(guī)則改寫成: : P Pi i 1 1|2 2|k k。 其中其中P Pj j1 1|2 2|k k是關(guān)于是關(guān)于P Pj j的所有產(chǎn)生式的所有產(chǎn)生式 EndforEndfor 消除關(guān)于消除關(guān)于P Pi i的直接左遞

24、歸的直接左遞歸 EndforEndfor (3)(3)化簡(jiǎn)由化簡(jiǎn)由(2)(2)得到的文法：除去從開始符號(hào)無法達(dá)到的得到的文法：除去從開始符號(hào)無法達(dá)到的 非終結(jié)符的產(chǎn)生式非終結(jié)符的產(chǎn)生式 PP ：考慮以下文法，消除其左遞歸性：考慮以下文法，消除其左遞歸性 SQc | c QRb | b RSa | a 解解：(1)把該文法的非終結(jié)符排列為把該文法的非終結(jié)符排列為R、Q、S. (2)對(duì)于對(duì)于R，不存在直接左遞歸，不用消除，不存在直接左遞歸，不用消除 對(duì)于對(duì)于Q，把，把R代入到代入到Q的有關(guān)候選式后，把的有關(guān)候選式后，把Q的產(chǎn)生式改寫為的產(chǎn)生式改寫為 QSab| ab | b 現(xiàn)在現(xiàn)在Q不存在直接左

25、遞歸，不用消除不存在直接左遞歸，不用消除 對(duì)于對(duì)于S，把，把Q代讀到代讀到S的有關(guān)候選式后，把的有關(guān)候選式后，把S的產(chǎn)生式改寫為的產(chǎn)生式改寫為 SSabc | abc | bc | c S有直接左遞歸，消除有直接左遞歸，消除S的直接左遞歸為的直接左遞歸為 SabcS | bcS | cS SabcS | 得到消除左遞歸性的文法為得到消除左遞歸性的文法為 SabcS | bcS | cS SabcS | QSab| ab | b RSa | a (3)顯然，顯然，Q和和R的產(chǎn)生式已經(jīng)是多余的，將它們?nèi)サ舻漠a(chǎn)生式已經(jīng)是多余的，將它們?nèi)サ?化簡(jiǎn)后的文法是：化簡(jiǎn)后的文法是： SabcS | bcS |

26、 cS SabcS | ：由于對(duì)非終結(jié)符排序的不同，最后所得的文法在形式：由于對(duì)非終結(jié)符排序的不同，最后所得的文法在形式 上可能不一樣，但它們都是等價(jià)的上可能不一樣，但它們都是等價(jià)的 ：考慮剛才的文法，消除其左遞歸性：考慮剛才的文法，消除其左遞歸性 SQc | c QRb | b RSa | a 解解： (1)把該文法的非終結(jié)符排列為把該文法的非終結(jié)符排列為S、Q、R (2)對(duì)于對(duì)于S，不存在直接左遞歸，不用消除，不存在直接左遞歸，不用消除 對(duì)于對(duì)于Q，不存在直接左遞歸，不用消除，不存在直接左遞歸，不用消除 對(duì)于對(duì)于R，把，把S代入到代入到R的有關(guān)候選式后，把的有關(guān)候選式后，把R的產(chǎn)生式改寫為

27、的產(chǎn)生式改寫為 RQca| ca | a 把把Q代入到代入到R的有關(guān)候選式后，把的有關(guān)候選式后，把R的產(chǎn)生式改寫為的產(chǎn)生式改寫為 RRbca| bca | ca | a RRbca| bca | ca | a R有直接左遞歸，消除有直接左遞歸，消除S的直接左遞歸為的直接左遞歸為 RbcaR | caR | aR RbcaR | 得到消除左遞歸性的文法為得到消除左遞歸性的文法為 SQc | c QRb | b RbcaR | caR | aR RbcaR | 問題三：?jiǎn)栴}三：證明是證明是LL(1)LL(1)文法文法 (1)文法不含左遞歸文法不含左遞歸 (2)對(duì)于文法中每一個(gè)非終結(jié)符對(duì)于文法中每一

28、個(gè)非終結(jié)符A的各個(gè)產(chǎn)生式的候選式的各個(gè)產(chǎn)生式的候選式 的的FIRST集兩兩不相交。即，若集兩兩不相交。即，若 A1|2|n 則則FIRST(FIRST(i i)FIRST()FIRST(j j)=)= (i (ij) ) (3)對(duì)于文法中的每個(gè)非終結(jié)符對(duì)于文法中的每個(gè)非終結(jié)符A，若它的某個(gè)候選首符，若它的某個(gè)候選首符 集包含集包含,則則 FIRST(A)FOLLOW(A)=FIRST(A)FOLLOW(A)= 如果一個(gè)文法如果一個(gè)文法G G滿足以上條件，則稱該文法滿足以上條件，則稱該文法G G為為L(zhǎng)L(1)LL(1)文文 法法( (第第1 1個(gè)個(gè)L L代表從左到右掃描輸入串，第代表從左到右掃描

29、輸入串，第2 2個(gè)個(gè)L L代表最左代表最左 推導(dǎo)，推導(dǎo)，1 1表示分析時(shí)每一步只看表示分析時(shí)每一步只看1 1個(gè)符號(hào)個(gè)符號(hào)) ) 問題四問題四：預(yù)測(cè)分析表：預(yù)測(cè)分析表M(xm ，ai )的構(gòu)造方法的構(gòu)造方法 1. 定義定義FIRSTFIRST集集 令文法令文法G G是不含左遞歸的文法，對(duì)是不含左遞歸的文法，對(duì)G G的非終結(jié)符的候選的非終結(jié)符的候選， 定義它的開始符號(hào)（終結(jié)首符）集合：定義它的開始符號(hào)（終結(jié)首符）集合： 特別地，如果特別地，如果，則，則FIRST(FIRST() ) 如果非終結(jié)符如果非終結(jié)符A A的任意兩個(gè)候選式的任意兩個(gè)候選式i i和和j j的開始符的開始符 號(hào)集滿足號(hào)集滿足FI

30、RST(FIRST(i i)FIRST()FIRST(j j)=)=，則，則A A可以根可以根 據(jù)所面臨的第一個(gè)輸入符號(hào)，準(zhǔn)確地指派一個(gè)候選據(jù)所面臨的第一個(gè)輸入符號(hào)，準(zhǔn)確地指派一個(gè)候選 式式去執(zhí)行任務(wù)，去執(zhí)行任務(wù)，是那個(gè)是那個(gè)FIRSTFIRST集含集含a a的候選式，的候選式， 即即 a a FIRST(FIRST() ) * T FIRST( )a | a.,aV * 2.對(duì)每個(gè)文法符號(hào)對(duì)每個(gè)文法符號(hào)XV VN NV VT T構(gòu)造其構(gòu)造其FIRST(X)FIRST(X) 連續(xù)使用以下規(guī)則，直至每個(gè)結(jié)合連續(xù)使用以下規(guī)則，直至每個(gè)結(jié)合FIRSTFIRST不再增大為止不再增大為止 (1)(1)若

31、若X XV VT T，則，則FIRST(X)=X.FIRST(X)=X. (2)(2)若若X XV VN N，且有產(chǎn)生式，且有產(chǎn)生式XaXa，則把，則把a(bǔ) a加入到加入到FIRST(X)FIRST(X)中；中； 若若XX也是一條產(chǎn)生式，則把也是一條產(chǎn)生式，則把也加到也加到FIRST(X)FIRST(X)中。中。 (3)(3)若若XYXY是一個(gè)產(chǎn)生式，且是一個(gè)產(chǎn)生式，且Y YV VN N，則把，則把FIRST(Y)FIRST(Y)中所中所 有非有非元素都加到元素都加到FIRST(X)FIRST(X)中；中； 若若XYXY1 1Y Y2 2 Y Yk k是一個(gè)產(chǎn)生式，是一個(gè)產(chǎn)生式， Y Y1 1Y

32、 Y2 2 Y Yi-1 i-1都是非終 都是非終 結(jié)符，而且，對(duì)于任何結(jié)符，而且，對(duì)于任何j j，1 1j ji-1-1， FIRST(YFIRST(Yj j) )都含有都含有 (即即Y Y1 1YYi-1 i-1=) =)，則把，則把FIRST(YFIRST(Yi i) )中的所有非中的所有非元素都元素都 加到加到FIRST(X)FIRST(X)； 特別是，若所有的特別是，若所有的FIRST(YFIRST(Yj j) )均含有均含有，j=1j=1，2 2，k k， 則把則把加到加到FIRST(X)FIRST(X)中。中。 3. 對(duì)于文法的任意符號(hào)串對(duì)于文法的任意符號(hào)串=X=X1 1X X2

33、 2 X Xn n構(gòu)造集合構(gòu)造集合FIRST()FIRST() (1)(1)置置FIRST()= FIRST(XFIRST()= FIRST(X1 1) (2)(2)若對(duì)任何若對(duì)任何1 1j ji-1-1，F(xiàn)IRST(XFIRST(Xj j) )，則把，則把FIRST(XFIRST(Xi i) 加至加至FIRST()FIRST()中中 (3)(3)特別的，若所有的特別的，若所有的FIRST(XFIRST(Xj j) )均含有均含有，1 1j jn，則把，則把 也加至也加至FIRST()FIRST()中中 4.定義定義FOLLOW集集 對(duì)文法對(duì)文法G G的任何非終結(jié)符的任何非終結(jié)符A A，定義它

34、的后繼符號(hào)集合：，定義它的后繼符號(hào)集合： 特別地，如果特別地，如果S SA，則，則#FOLLOW(A)FOLLOW(A) FOLLOW(A)FOLLOW(A)集合是所有句型中出現(xiàn)在緊接集合是所有句型中出現(xiàn)在緊接A A之后的之后的 終結(jié)符號(hào)或終結(jié)符號(hào)或# #所組成的集合所組成的集合 當(dāng)非終結(jié)符當(dāng)非終結(jié)符A A面臨輸入符號(hào)面臨輸入符號(hào)a a，且，且a a不屬于不屬于A A的任意的任意 候選式的候選式的FIRSTFIRST集但集但A A的某個(gè)候選式的的某個(gè)候選式的FIRSTFIRST集包集包 含含時(shí)，只有當(dāng)時(shí)，只有當(dāng)a FOLLOW(A)FOLLOW(A)，才可能允許，才可能允許A A自自 動(dòng)匹配動(dòng)

35、匹配 Va.Aa.,S | aFOLLOW(A) T * * 5.對(duì)每個(gè)文法對(duì)每個(gè)文法AV VN N構(gòu)造其構(gòu)造其FOLLOW(A)FOLLOW(A) 連續(xù)使用一下規(guī)則，直至每個(gè)集合連續(xù)使用一下規(guī)則，直至每個(gè)集合FOLLOWFOLLOW不再增大為止不再增大為止 (1)(1)對(duì)于分發(fā)開始符號(hào)對(duì)于分發(fā)開始符號(hào)S S，置，置# #與與FOLLOW(S)FOLLOW(S)中；中； (2)(2)若若ABAB是一個(gè)產(chǎn)生式，則把是一個(gè)產(chǎn)生式，則把FIRST()FIRST()加至加至 FOLLOW(B)FOLLOW(B)中；中； (3)(3)若若ABAB是一個(gè)產(chǎn)生式，是一個(gè)產(chǎn)生式， FOLLOW(A)FOLLO

36、W(A)加至加至FOLLOW(B)FOLLOW(B)中中 或或ABAB是一個(gè)產(chǎn)生式而是一個(gè)產(chǎn)生式而 ( (即即FIRST()FIRST()， FOLLOW(A)FOLLOW(A)加至加至FOLLOW(B)FOLLOW(B)中中 其中其中,(V VN NV VT T)*，B BV VN N * 6.構(gòu)造分析表構(gòu)造分析表M的算法是的算法是 (1)(1)對(duì)于文法對(duì)于文法G G的每個(gè)產(chǎn)生式的每個(gè)產(chǎn)生式AA，執(zhí)行，執(zhí)行(2)(3)(2)(3) (2)(2)對(duì)每個(gè)終結(jié)符對(duì)每個(gè)終結(jié)符a aFIRST()FIRST()，把，把AA加至加至MA,aMA,a中；中； (3)(3)若若FIRST()FIRST()，

37、則對(duì)任何，則對(duì)任何b b FOLLOW(A)FOLLOW(A)把把AA加加 至至MA,bMA,b中；中； (4)(4)把所有無定義的把所有無定義的MA,aMA,a標(biāo)上標(biāo)上”出錯(cuò)標(biāo)志出錯(cuò)標(biāo)志” 1. 設(shè)有文法設(shè)有文法G(V(VT T，V VN N，S S，P)P)，其中，其中 V VT T=a， ，, ，(，) ；V VN N=S,T；S = S P:P: S a | | (T) T T,S | S (1)消除其產(chǎn)生式的左遞歸消除其產(chǎn)生式的左遞歸.然后，對(duì)每個(gè)非終結(jié)符寫出不帶然后，對(duì)每個(gè)非終結(jié)符寫出不帶 回溯的遞歸子程序；回溯的遞歸子程序； (2)經(jīng)改寫后的文法是否是經(jīng)改寫后的文法是否是LL(1

38、)的？給出它的預(yù)測(cè)分析表的？給出它的預(yù)測(cè)分析表 S a | | (T) T T,S | S (1)消除其產(chǎn)生式的直接左遞歸消除其產(chǎn)生式的直接左遞歸 解：對(duì)于解：對(duì)于T T,S | S (P=T，=,S ，=S)變成變成 TST T,ST| 所以所以 S a | | (T) TST T,ST| 每個(gè)非終結(jié)符的不帶回溯的遞歸子程序如下：每個(gè)非終結(jié)符的不帶回溯的遞歸子程序如下： PP| - PP PP| S a | | (T) TST T,ST| (2)經(jīng)改寫后的文法經(jīng)改寫后的文法 是否是是否是LL(1)的？的？ 給出它的預(yù)測(cè)分析表。給出它的預(yù)測(cè)分析表。 解：解：FIRST( S )= ; FIRS

39、T( T )= ; FIRST( T)= ; (2)若若XVN，且有產(chǎn)生式，且有產(chǎn)生式Xa，則，則 把把a(bǔ)加入到加入到FIRST(X)中；若中；若X也是一也是一 條產(chǎn)生式，則把條產(chǎn)生式，則把也加到也加到FIRST(X)中。中。 (3)若若XY是一個(gè)產(chǎn)生式，且是一個(gè)產(chǎn)生式，且YVN， 則把則把FIRST(Y)中所有非中所有非元素都加到元素都加到 FIRST(X)中；中； 若若XY1Y2 Yk是一個(gè)產(chǎn)生式，是一個(gè)產(chǎn)生式， Y1Y2 Yi-1都是非終結(jié)符，而且，對(duì)于都是非終結(jié)符，而且，對(duì)于 任何任何j，1ji-1， FIRST(Yj)都含有都含有(即即 Y1Yi-1=)，則把，則把FIRST(Yi)

40、中的所有中的所有 非非元素都加到元素都加到FIRST(X)； 特別是，若所有的特別是，若所有的FIRST(Yj)均含有均含有， j=1，2，k，則把，則把加到加到FIRST(X)中。中。 a, , , , ,(a, ( S a | | (T) TST T,ST| 解：解：FIRST(ST)= ; FIRST(,ST)= ; FIRST(a)= ; FIRST()= ; FIRST(T)= ; =X1X2 Xn 構(gòu)造構(gòu)造FIRST() (1)置置FIRST()= FIRST(X1) (2)若對(duì)任何若對(duì)任何1ji-1，F(xiàn)IRST(Xj)， 則把則把FIRST(Xj)加至加至FIRST()中中 (3

41、)特別的，若所有的特別的，若所有的FIRST(Xj)均含均含 有有，1jn，則把，則把 也加至也加至FIRST() 中中 ， a, ,( a ( S a | | (T) TST T,ST| 解：解： FOLLOW(T)= ; FOLLOW (T)= ; FOLLOW (S)= ; (1)對(duì)于分發(fā)開始符號(hào)對(duì)于分發(fā)開始符號(hào)S，置，置#于于 FOLLOW(S)中；中； (2)若若AB是一個(gè)產(chǎn)生式，則把是一個(gè)產(chǎn)生式，則把 FIRST()加至加至FOLLOW(B)中；中； (3)若若AB是一個(gè)產(chǎn)生式，或是一個(gè)產(chǎn)生式，或 AB是一個(gè)產(chǎn)生式而是一個(gè)產(chǎn)生式而FIRST()， FOLLOW(A)加至加至FOLL

42、OW(B)中。中。 #, ) ) ) , S a | | (T) TST T,ST| 證明：證明： FIRST(a)FIRST() FIRST(T)=a (= FIRST( T)FOLLOW (T)= ，, ) = 所以，該文法是所以，該文法是LL(1)文法文法 S a | | (T) TST T,ST| a()，# SS aS S (T) TTSTTSTTST TT T,ST 2.構(gòu)造算符優(yōu)先關(guān)系表構(gòu)造算符優(yōu)先關(guān)系表 (1)通過檢查產(chǎn)生式的每一個(gè)候選式可以找出滿足通過檢查產(chǎn)生式的每一個(gè)候選式可以找出滿足a=.b （即（即Pab或或PaQb的產(chǎn)生式）的產(chǎn)生式） (2)為了滿足為了滿足.，需對(duì)，

43、需對(duì)G中每個(gè)非終結(jié)符中每個(gè)非終結(jié)符P構(gòu)造兩構(gòu)造兩 個(gè)集合個(gè)集合FIRSTVT(P)和和LASTVT(P)： FIRSTVT Pa PaPQaaVQV TN ( ) |, 或而 ,|)( NT VQVaaQPaPaPLASTVT 而或 (3)構(gòu)造集合構(gòu)造集合FIRSTVT(P)的算法的算法 按其定義，可用下面兩條規(guī)則來構(gòu)造集合按其定義，可用下面兩條規(guī)則來構(gòu)造集合FIRSTVT(P)： 若有產(chǎn)生式若有產(chǎn)生式Pa或或PQa， 則則a FIRSTVT(P)； 若若a FIRSTVT(Q)，且有產(chǎn)生式，且有產(chǎn)生式PQ， 則則a FIRSTVT(P)。 (4)同理構(gòu)造構(gòu)造集合同理構(gòu)造構(gòu)造集合LASTVT(

44、P)的算法的算法 按其定義，可用下面兩條規(guī)則來構(gòu)造集合按其定義，可用下面兩條規(guī)則來構(gòu)造集合LASTVT(P)： 若有產(chǎn)生式若有產(chǎn)生式P a或或P aQ ， 則則a LASTVT(P)； 若若a LASTVT(Q)，且有產(chǎn)生式，且有產(chǎn)生式P Q ， 則則a LASTVT(P)。 (5)有了這兩個(gè)集合之后，就可以通過檢查每個(gè)產(chǎn)生有了這兩個(gè)集合之后，就可以通過檢查每個(gè)產(chǎn)生 式的候選式確定滿足關(guān)系式的候選式確定滿足關(guān)系.的所有終結(jié)符對(duì)。的所有終結(jié)符對(duì)。 (1)(1)假定有個(gè)產(chǎn)生式的一個(gè)候選形為假定有個(gè)產(chǎn)生式的一個(gè)候選形為 aPaP 那么，對(duì)任何那么，對(duì)任何b b FIRSTVT(P)FIRSTVT(P

45、)，有，有a a . b b。 FIRSTVT Pa PaPQaaVQV TN ( ) |, 或而 ,|)( NT VQVaaQPaPaPLASTVT 而或 :考慮下面的文法考慮下面的文法G： S X | SaX X Y | X%Y Y X！ 構(gòu)造該文法構(gòu)造該文法G的每個(gè)非終結(jié)符的的每個(gè)非終結(jié)符的FIRSTVT和和LASTVT集合集合 解解: (1)構(gòu)造構(gòu)造FIRSTVT集合集合 FIRSTVT(Y)= FIRSTVT(X)= FIRSTVT(S)= 若有產(chǎn)生式若有產(chǎn)生式Pa或或PQa， 則則a FIRSTVT(P)； 若若a FIRSTVT(Q)，且有產(chǎn)生式，且有產(chǎn)生式 PQ，則，則a FI

46、RSTVT(P)。 %, a,%, :考慮下面的文法考慮下面的文法G： S X | SaX X Y | X%Y Y X！ 構(gòu)造該文法構(gòu)造該文法G的每個(gè)非終結(jié)符的的每個(gè)非終結(jié)符的FIRSTVT和和LASTVT集合集合 解解: (1)構(gòu)造構(gòu)造LASTVT集合集合 LASTVT(Y)= LASTVT(X)= LASTVT(S)= !, %,! , a,%,!, 若有產(chǎn)生式若有產(chǎn)生式P a或或P aQ ， 則則a LASTVT(P)； 若若a LASTVT(P)，且有產(chǎn)生式，且有產(chǎn)生式 P Q ，則，則a LASTVT(P)。 :G: S X | SaX X Y | X%Y Y X！ 求出該文法每個(gè)終

47、結(jié)符號(hào)的優(yōu)先關(guān)系，并構(gòu)造優(yōu)先分析表求出該文法每個(gè)終結(jié)符號(hào)的優(yōu)先關(guān)系，并構(gòu)造優(yōu)先分析表 (1)SSaX，且，且%, FIRSTVT(X) aP 所以所以a 小于小于 %, (2) SSaX，且，且a, %, !, LASTVT(S) Pb 所以所以a, %, !, 大于大于 a 以下略。以下略。 FIRSTVT(S)=a, %, FIRSTVT(X)= %, FIRSTVT(Y)= LASTVT(S)=a, %, !, LASTVT(X)= %, !, LASTVT(Y)= !, (1)假定有個(gè)產(chǎn)生式的一個(gè)候選形為假定有個(gè)產(chǎn)生式的一個(gè)候選形為 aP 那么，對(duì)任何那么，對(duì)任何b FIRSTVT(P

48、)，有，有a . b。 a%! a. . . . . 構(gòu)造分析表如下：構(gòu)造分析表如下： 其中，空白為錯(cuò)誤其中，空白為錯(cuò)誤 2.優(yōu)先函數(shù)的構(gòu)造方法優(yōu)先函數(shù)的構(gòu)造方法 如果優(yōu)先函數(shù)存在，則可以通過以下三個(gè)步驟從優(yōu)如果優(yōu)先函數(shù)存在，則可以通過以下三個(gè)步驟從優(yōu) 先表構(gòu)造優(yōu)先函數(shù)先表構(gòu)造優(yōu)先函數(shù): (1)對(duì)于每個(gè)終結(jié)符對(duì)于每個(gè)終結(jié)符a，令其對(duì)應(yīng)兩個(gè)符號(hào)，令其對(duì)應(yīng)兩個(gè)符號(hào)fa和和ga， 畫一張以所有符號(hào)畫一張以所有符號(hào)fa和和ga為結(jié)點(diǎn)的方向圖。為結(jié)點(diǎn)的方向圖。 如果如果a.=.b，則從，則從fa畫一條弧至畫一條弧至gb 如果如果a.=.b，則從，則從gb畫一條弧至畫一條弧至fa 。 (2)對(duì)每個(gè)結(jié)點(diǎn)都賦予一個(gè)數(shù)，此數(shù)等于從該結(jié)點(diǎn)對(duì)每個(gè)結(jié)點(diǎn)都賦予一個(gè)數(shù)，此數(shù)等于從該結(jié)點(diǎn) 出發(fā)所能到達(dá)的結(jié)點(diǎn)出發(fā)所能到達(dá)的結(jié)點(diǎn)(包括出發(fā)點(diǎn)自身包括出發(fā)點(diǎn)自身)。 賦給賦給fa的數(shù)作為的數(shù)作為f(a) 賦給賦給ga的數(shù)作為的數(shù)作為g(a)。 (3)檢查所構(gòu)造出來的函數(shù)檢查所構(gòu)造出來的函數(shù)f和和