编译原理-练习

1、编译原理编译原理 练习练习1 王金伟 计算机与信息工程学院 天津师范大学 练习练习1.1 基本概念基本概念 l编译程序的结构编译程序的结构 l上下文无关文法的一些概念上下文无关文法的一些概念 l词法分析词法分析 l语法分析语法分析 l自上而下自上而下 l自下而上自下而上 1.填充下面编译程序总框图填充下面编译程序总框图 源程序源程序 目标程序目标程序 ( 字符串字符串) 词法分析器词法分析器 语法分析器语法分析器 语义分析和中间代码生成器语义分析和中间代码生成器 代码优化器代码优化器 目标代码生成器目标代码生成器 表表 格格 管管 理理 出出 错错 处处 理理 对于对于上的每一个正规式上的每一

2、个正规式V，存在一个，存在一个上的上的DFA M， 使得使得L(M) = L(V) 问题问题：如何由一个正规式：如何由一个正规式V，构造一个，构造一个DFA M 思路思路：分两步走：分两步走 1.根据根据V，构造一个，构造一个NFA M，使得，使得L(M) = L(V) 2.将将M确定化，变为确定化，变为DFA M 第一步第一步，在，在上构造一个上构造一个NFA M (1)构造一个拓广的转换图构造一个拓广的转换图 练习练习1.2 词法分析词法分析 (2)使用分裂规则对使用分裂规则对V进行分裂，加进新结点，直到把进行分裂，加进新结点，直到把 图转换成每条弧上标识为图转换成每条弧上标识为上的一个字

3、符或上的一个字符或 最后得到一个最后得到一个NFA M 且且L(M) = L(V) 第二步第二步，把，把M确定化确定化 (1)两个概念两个概念 定义定义1：假定：假定I是是M的状态集的子集，定义的状态集的子集，定义I的的闭包闭包 _CLOSURE(I)为：为： (a)若若qI，则，则q_CLOSURE(I) (b)若若qI，那么从，那么从q出发经任意条出发经任意条弧而能到达的任弧而能到达的任 何状态何状态q都属于都属于_CLOSURE(I) ； 定义定义2：假定：假定I是是M的状态集的子集，定义的状态集的子集，定义 Ia =_CLOSURE(J) 其中，其中，J是所有那些可从是所有那些可从I中

4、的某一状态结点出发经过中的某一状态结点出发经过 一条一条a弧而到达的状态结点的全体弧而到达的状态结点的全体 ：有如下一个状态转换图：有如下一个状态转换图 假定假定 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确定化确定化 设设 = a，b 构造一张表构造一张表 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 把得到的每个集合看成一个状态，得到一张状态转换表，把得到的每个集合看成一个状态，得到一张状态转换表， 该表的初态就是该表的初态

6、就是_CLOSURE(X)，它的终态是那些含有终，它的终态是那些含有终 态态Y的子集，这样就得到一个的子集，这样就得到一个DFA M 且且L(M) = L(M) 1.构造下列正规式相应的构造下列正规式相应的DFA。 (1) 1(0|1)*101 (2) 0*10*10*10* (1)1(0|1)*101 得到一个得到一个NFA M 且且 L(M) = L(V) 用子集法对用子集法对M进行确定化进行确定化 构造一张表构造一张表 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 把每个子集看成一个状态

8、，得到一个把每个子集看成一个状态，得到一个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进行化简进行化简 解解: 把把M状态集分为两组状态集分为两组: 终态结点终态结点5 非终态结点非终态结点0，1，2，3，4 考察考察0，1，2，3，4 因为，因为， 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 因为，因为， 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 因为，因为， 0,1,20 = 0,1,21 = 所以，所以， 0,1,2必可再分必可再分 看图，把看图，把0,1,2分割为分割为0， 1,2 考察考察1,2 因为，因为， 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 用状态用状态2代替状态代替状态1，把引向状态，把引向状态1的箭弧都引向状态的箭弧都引向状态2， 把把1消去，得到一个消去，得到一个DFA M (2) 0*10*10*10* 得到一个得到一个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- 把每个子集看成一个状态，得到一个把每个子集看成一个状态，得到一个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进行化简进行化简 解解: 把把M状态集分为两组状态集分为两组: 终态结点终态结点6,7 非终态结点非终态结点0,1,2,3,4,5 考察考察6,7 因为，因为， 6,70 = 6,71 = 所以，所以， 6,7不可再分；不可再分； 考察考察0,1,2,3,4,5 因为，因为， 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 因为，因为， 4,50 = 4,51 = 所以，所以， 4,5 不可再分不可再分 考察考察0,1,2,3 因为，因为， 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 因为，因为， 2,30

14、= 2,31 = 所以，所以， 2,3 不可再分不可再分 考察考察0,1 因为，因为， 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 用状态用状态1代替状态代替状态0，把引向状态，把引向状态0的箭弧都引向状态的箭弧都引向状态1， 把把0消去；消去； 用状态用状态3代替状态代替状态2，把引向状态，把引向状态2的箭弧都引向状的箭弧都引向状 态态3，把，把2消去；消去； 用状态用状态5代替状态代替状态4，把引向状态，把引向状态

15、4的箭弧都引向状的箭弧都引向状 态态5，把，把4消去；消去； 用状态用状态7代替状态代替状态6，把引向状态，把引向状态6的箭弧都引向状的箭弧都引向状 态态7，把，把6消去；得到一个化简得消去；得到一个化简得DFA M 2.把把(a)和和(b)分别确定化和最分别确定化和最 少化少化 (a)(b) (1)用子集法对用子集法对M进行确定化进行确定化 构造一张表构造一张表 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 - 把每个子集看成一个状态，得到一个把每个子集看成一个状态，得到一个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进行化简进行化简 解解: 把把M状态集分为两组状态集分为两组: 终态结点终态结点0，1 非终态结点非终态结点2 考察考察0，1 因为，因为， 0，1a = 0，1b = 所以，所以， 0，1不可再分不可再分 1 2 0,1 2 J=1 J=2 所以，所以， 最终把最终把M分割为分割为0，1， 2 用状态用状态0代替状

17、态代替状态1，把引向状态，把引向状态1的箭弧都引向状的箭弧都引向状 态态0，把，把1消去，得到一个消去，得到一个DFA M (2)用子集法对用子集法对M进行确定化进行确定化 构造一张表构造一张表 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进行化简进行化简 解解: 把把M状态集分为两组状态集分为两组: 终态结点终态结点0，1 非终态结点非终态结点2，3，4，5 考察考察0，1 因为，因为， 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 因为，因为， 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 因为，因为， 2，4a = 2，4b = 所以，所以， 2，4不可再分不可再分 考察考察3，5 因为，因为， 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 用状态用状态0代替状态代替状态1，把引向状态，把引向状态1的箭弧都引向状的箭弧都引向状 态态0，把，把1消去；用状态消去；用状态2代替状态代替状态4，把引向状态，把引向状态4 的箭弧都引向状态的箭弧都引向状态2，把，把4消去；用状态消去；用状态5代替状态代替状态3， 把引向状态把引向状态3的箭弧都引向状态的箭弧都引向状态5，把，把3消去；得到消去；得到 一个一个DFA M 3.设计一个设计一个DFA，它接受，它接受0，1上所有满足如下条件的字符串：上所有满足如下条件的字符串： 每个每个1都有都有0直接

20、跟在右边。直接跟在右边。 解解: (1)根据题意，得到相应的正规式：根据题意，得到相应的正规式： (0|10)* (2)由以上正规式构造相应的由以上正规式构造相应的NFA为：为： (1)用子集法对用子集法对M进行确定化进行确定化 构造一张表构造一张表 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 - 把每个子集看成一个状态，得到一个把每个子集看成一个状态，得到一个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进行化简进行化简 解解: 把把M状态集分为两组状态集分为两组: 终态结点终态结点0，1 非终态结点非终态结点2 考察考察0，1 因为，因为， 0，10 = 0，11 = 所以，所以， 0，1不可再分不可再分 1 2 0,1 2 J=1 J=2 所以，所以， 最终把最终把M分割为分割为0，1， 2 用状态用状态1代替状态代替状态0，把引向状态，把引向状态0的箭弧都引向状的箭弧都引向状 态态1，把，把0消去，得到一个消去

22、，得到一个DFA M 问题一：问题一：消除文法直接左递归方法消除文法直接左递归方法： 设有产生式设有产生式 PP1|P2|Pm|1|2|n 其中每个其中每个i不以不以P开头，每个开头，每个i不为不为 消除消除P的直接左递归性就是把这些规则改写成：的直接左递归性就是把这些规则改写成： P1P|2P|nP P1P| 2P|mP| 练习练习1.3 自上而下的语法分析自上而下的语法分析 4.消除整个文法的左递归的算法消除整个文法的左递归的算法 如果文法不含回路（形如如果文法不含回路（形如 的推导），也不含有以的推导），也不含有以 为右部的产生式，则下面算法可以消除左递归为右部的产生式，则下面算法可以消

23、除左递归 (1)(1)把文法把文法G G的所有非终结符按任一种顺序排列成的所有非终结符按任一种顺序排列成 P P1 1,P,P2 2,P,Pn n；按此顺序执行；按此顺序执行 (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的规则改写成的规则改写成: : P Pi i 1 1|2 2|k k。 其中其中P Pj j1 1|2 2|k k是关于是关于P Pj j的所有产生式的所有产生式 EndforEndfor 消除关于消除关于P Pi i的直接左递

24、归的直接左递归 EndforEndfor (3)(3)化简由化简由(2)(2)得到的文法：除去从开始符号无法达到的得到的文法：除去从开始符号无法达到的 非终结符的产生式非终结符的产生式 PP ：考虑以下文法，消除其左递归性：考虑以下文法，消除其左递归性 SQc | c QRb | b RSa | a 解解：(1)把该文法的非终结符排列为把该文法的非终结符排列为R、Q、S. (2)对于对于R，不存在直接左递归，不用消除，不存在直接左递归，不用消除 对于对于Q，把，把R代入到代入到Q的有关候选式后，把的有关候选式后，把Q的产生式改写为的产生式改写为 QSab| ab | b 现在现在Q不存在直接左

25、递归，不用消除不存在直接左递归，不用消除 对于对于S，把，把Q代读到代读到S的有关候选式后，把的有关候选式后，把S的产生式改写为的产生式改写为 SSabc | abc | bc | c S有直接左递归，消除有直接左递归，消除S的直接左递归为的直接左递归为 SabcS | bcS | cS SabcS | 得到消除左递归性的文法为得到消除左递归性的文法为 SabcS | bcS | cS SabcS | QSab| ab | b RSa | a (3)显然，显然，Q和和R的产生式已经是多余的，将它们去掉的产生式已经是多余的，将它们去掉 化简后的文法是：化简后的文法是： SabcS | bcS |

26、 cS SabcS | ：由于对非终结符排序的不同，最后所得的文法在形式：由于对非终结符排序的不同，最后所得的文法在形式 上可能不一样，但它们都是等价的上可能不一样，但它们都是等价的 ：考虑刚才的文法，消除其左递归性：考虑刚才的文法，消除其左递归性 SQc | c QRb | b RSa | a 解解： (1)把该文法的非终结符排列为把该文法的非终结符排列为S、Q、R (2)对于对于S，不存在直接左递归，不用消除，不存在直接左递归，不用消除 对于对于Q，不存在直接左递归，不用消除，不存在直接左递归，不用消除 对于对于R，把，把S代入到代入到R的有关候选式后，把的有关候选式后，把R的产生式改写为

27、的产生式改写为 RQca| ca | a 把把Q代入到代入到R的有关候选式后，把的有关候选式后，把R的产生式改写为的产生式改写为 RRbca| bca | ca | a RRbca| bca | ca | a R有直接左递归，消除有直接左递归，消除S的直接左递归为的直接左递归为 RbcaR | caR | aR RbcaR | 得到消除左递归性的文法为得到消除左递归性的文法为 SQc | c QRb | b RbcaR | caR | aR RbcaR | 问题三：问题三：证明是证明是LL(1)LL(1)文法文法 (1)文法不含左递归文法不含左递归 (2)对于文法中每一个非终结符对于文法中每一

28、个非终结符A的各个产生式的候选式的各个产生式的候选式 的的FIRST集两两不相交。即，若集两两不相交。即，若 A1|2|n 则则FIRST(FIRST(i i)FIRST()FIRST(j j)=)= (i (ij) ) (3)对于文法中的每个非终结符对于文法中的每个非终结符A，若它的某个候选首符，若它的某个候选首符 集包含集包含,则则 FIRST(A)FOLLOW(A)=FIRST(A)FOLLOW(A)= 如果一个文法如果一个文法G G满足以上条件，则称该文法满足以上条件，则称该文法G G为为LL(1)LL(1)文文 法法( (第第1 1个个L L代表从左到右扫描输入串，第代表从左到右扫描

29、输入串，第2 2个个L L代表最左代表最左 推导，推导，1 1表示分析时每一步只看表示分析时每一步只看1 1个符号个符号) ) 问题四问题四：预测分析表：预测分析表M(xm ，ai )的构造方法的构造方法 1. 定义定义FIRSTFIRST集集 令文法令文法G G是不含左递归的文法，对是不含左递归的文法，对G G的非终结符的候选的非终结符的候选， 定义它的开始符号（终结首符）集合：定义它的开始符号（终结首符）集合： 特别地，如果特别地，如果，则，则FIRST(FIRST() ) 如果非终结符如果非终结符A A的任意两个候选式的任意两个候选式i i和和j j的开始符的开始符 号集满足号集满足FI

30、RST(FIRST(i i)FIRST()FIRST(j j)=)=，则，则A A可以根可以根 据所面临的第一个输入符号，准确地指派一个候选据所面临的第一个输入符号，准确地指派一个候选 式式去执行任务，去执行任务，是那个是那个FIRSTFIRST集含集含a a的候选式，的候选式， 即即 a a FIRST(FIRST() ) * T FIRST( )a | a.,aV * 2.对每个文法符号对每个文法符号XV VN NV VT T构造其构造其FIRST(X)FIRST(X) 连续使用以下规则，直至每个结合连续使用以下规则，直至每个结合FIRSTFIRST不再增大为止不再增大为止 (1)(1)若

31、若X XV VT T，则，则FIRST(X)=X.FIRST(X)=X. (2)(2)若若X XV VN N，且有产生式，且有产生式XaXa，则把，则把a a加入到加入到FIRST(X)FIRST(X)中；中； 若若XX也是一条产生式，则把也是一条产生式，则把也加到也加到FIRST(X)FIRST(X)中。中。 (3)(3)若若XYXY是一个产生式，且是一个产生式，且Y YV VN N，则把，则把FIRST(Y)FIRST(Y)中所中所 有非有非元素都加到元素都加到FIRST(X)FIRST(X)中；中； 若若XYXY1 1Y Y2 2 Y Yk k是一个产生式，是一个产生式， Y Y1 1Y

32、 Y2 2 Y Yi-1 i-1都是非终 都是非终 结符，而且，对于任何结符，而且，对于任何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. 对于文法的任意符号串对于文法的任意符号串=X=X1 1X X2

33、 2 X Xn n构造集合构造集合FIRST()FIRST() (1)(1)置置FIRST()= FIRST(XFIRST()= FIRST(X1 1) (2)(2)若对任何若对任何1 1j ji-1-1，FIRST(XFIRST(Xj j) )，则把，则把FIRST(XFIRST(Xi i) 加至加至FIRST()FIRST()中中 (3)(3)特别的，若所有的特别的，若所有的FIRST(XFIRST(Xj j) )均含有均含有，1 1j jn，则把，则把 也加至也加至FIRST()FIRST()中中 4.定义定义FOLLOW集集 对文法对文法G G的任何非终结符的任何非终结符A A，定义它

34、的后继符号集合：，定义它的后继符号集合： 特别地，如果特别地，如果S SA，则，则#FOLLOW(A)FOLLOW(A) FOLLOW(A)FOLLOW(A)集合是所有句型中出现在紧接集合是所有句型中出现在紧接A A之后的之后的 终结符号或终结符号或# #所组成的集合所组成的集合 当非终结符当非终结符A A面临输入符号面临输入符号a a，且，且a a不属于不属于A A的任意的任意 候选式的候选式的FIRSTFIRST集但集但A A的某个候选式的的某个候选式的FIRSTFIRST集包集包 含含时，只有当时，只有当a FOLLOW(A)FOLLOW(A)，才可能允许，才可能允许A A自自 动匹配动

35、匹配 Va.Aa.,S | aFOLLOW(A) T * * 5.对每个文法对每个文法AV VN N构造其构造其FOLLOW(A)FOLLOW(A) 连续使用一下规则，直至每个集合连续使用一下规则，直至每个集合FOLLOWFOLLOW不再增大为止不再增大为止 (1)(1)对于分发开始符号对于分发开始符号S S，置，置# #与与FOLLOW(S)FOLLOW(S)中；中； (2)(2)若若ABAB是一个产生式，则把是一个产生式，则把FIRST()FIRST()加至加至 FOLLOW(B)FOLLOW(B)中；中； (3)(3)若若ABAB是一个产生式，是一个产生式， FOLLOW(A)FOLLO

36、W(A)加至加至FOLLOW(B)FOLLOW(B)中中 或或ABAB是一个产生式而是一个产生式而 ( (即即FIRST()FIRST()， FOLLOW(A)FOLLOW(A)加至加至FOLLOW(B)FOLLOW(B)中中 其中其中,(V VN NV VT T)*，B BV VN N * 6.构造分析表构造分析表M的算法是的算法是 (1)(1)对于文法对于文法G G的每个产生式的每个产生式AA，执行，执行(2)(3)(2)(3) (2)(2)对每个终结符对每个终结符a aFIRST()FIRST()，把，把AA加至加至MA,aMA,a中；中； (3)(3)若若FIRST()FIRST()，

37、则对任何，则对任何b b FOLLOW(A)FOLLOW(A)把把AA加加 至至MA,bMA,b中；中； (4)(4)把所有无定义的把所有无定义的MA,aMA,a标上标上”出错标志出错标志” 1. 设有文法设有文法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)消除其产生式的左递归消除其产生式的左递归.然后，对每个非终结符写出不带然后，对每个非终结符写出不带 回溯的递归子程序；回溯的递归子程序； (2)经改写后的文法是否是经改写后的文法是否是LL(1

38、)的？给出它的预测分析表的？给出它的预测分析表 S a | | (T) T T,S | S (1)消除其产生式的直接左递归消除其产生式的直接左递归 解：对于解：对于T T,S | S (P=T，=,S ，=S)变成变成 TST T,ST| 所以所以 S a | | (T) TST T,ST| 每个非终结符的不带回溯的递归子程序如下：每个非终结符的不带回溯的递归子程序如下： PP| - PP PP| S a | | (T) TST T,ST| (2)经改写后的文法经改写后的文法 是否是是否是LL(1)的？的？ 给出它的预测分析表。给出它的预测分析表。 解：解：FIRST( S )= ; FIRS

39、T( T )= ; FIRST( T)= ; (2)若若XVN，且有产生式，且有产生式Xa，则，则 把把a加入到加入到FIRST(X)中；若中；若X也是一也是一 条产生式，则把条产生式，则把也加到也加到FIRST(X)中。中。 (3)若若XY是一个产生式，且是一个产生式，且YVN， 则把则把FIRST(Y)中所有非中所有非元素都加到元素都加到 FIRST(X)中；中； 若若XY1Y2 Yk是一个产生式，是一个产生式， Y1Y2 Yi-1都是非终结符，而且，对于都是非终结符，而且，对于 任何任何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 构造构造FIRST() (1)置置FIRST()= FIRST(X1) (2)若对任何若对任何1ji-1，FIRST(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)对于分发开始符号对于分发开始符号S，置，置#于于 FOLLOW(S)中；中； (2)若若AB是一个产生式，则把是一个产生式，则把 FIRST()加至加至FOLLOW(B)中；中； (3)若若AB是一个产生式，或是一个产生式，或 AB是一个产生式而是一个产生式而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.构造算符优先关系表构造算符优先关系表 (1)通过检查产生式的每一个候选式可以找出满足通过检查产生式的每一个候选式可以找出满足a=.b （即（即Pab或或PaQb的产生式）的产生式） (2)为了满足为了满足.，需对，

43、需对G中每个非终结符中每个非终结符P构造两构造两 个集合个集合FIRSTVT(P)和和LASTVT(P)： FIRSTVT Pa PaPQaaVQV TN ( ) |, 或而 ,|)( NT VQVaaQPaPaPLASTVT 而或 (3)构造集合构造集合FIRSTVT(P)的算法的算法 按其定义，可用下面两条规则来构造集合按其定义，可用下面两条规则来构造集合FIRSTVT(P)： 若有产生式若有产生式Pa或或PQa， 则则a FIRSTVT(P)； 若若a FIRSTVT(Q)，且有产生式，且有产生式PQ， 则则a FIRSTVT(P)。 (4)同理构造构造集合同理构造构造集合LASTVT(

44、P)的算法的算法 按其定义，可用下面两条规则来构造集合按其定义，可用下面两条规则来构造集合LASTVT(P)： 若有产生式若有产生式P a或或P aQ ， 则则a LASTVT(P)； 若若a LASTVT(Q)，且有产生式，且有产生式P Q ， 则则a LASTVT(P)。 (5)有了这两个集合之后，就可以通过检查每个产生有了这两个集合之后，就可以通过检查每个产生 式的候选式确定满足关系式的候选式确定满足关系.的所有终结符对。的所有终结符对。 (1)(1)假定有个产生式的一个候选形为假定有个产生式的一个候选形为 aPaP 那么，对任何那么，对任何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的每个非终结符的的每个非终结符的FIRSTVT和和LASTVT集合集合 解解: (1)构造构造FIRSTVT集合集合 FIRSTVT(Y)= FIRSTVT(X)= FIRSTVT(S)= 若有产生式若有产生式Pa或或PQa， 则则a FIRSTVT(P)； 若若a FIRSTVT(Q)，且有产生式，且有产生式 PQ，则，则a FI

46、RSTVT(P)。 %, a,%, :考虑下面的文法考虑下面的文法G： S X | SaX X Y | X%Y Y X！ 构造该文法构造该文法G的每个非终结符的的每个非终结符的FIRSTVT和和LASTVT集合集合 解解: (1)构造构造LASTVT集合集合 LASTVT(Y)= LASTVT(X)= LASTVT(S)= !, %,! , a,%,!, 若有产生式若有产生式P a或或P aQ ， 则则a LASTVT(P)； 若若a LASTVT(P)，且有产生式，且有产生式 P Q ，则，则a LASTVT(P)。 :G: S X | SaX X Y | X%Y Y X！ 求出该文法每个终

47、结符号的优先关系，并构造优先分析表求出该文法每个终结符号的优先关系，并构造优先分析表 (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)假定有个产生式的一个候选形为假定有个产生式的一个候选形为 aP 那么，对任何那么，对任何b FIRSTVT(P

48、)，有，有a . b。 a%! a. . . . . 构造分析表如下：构造分析表如下： 其中，空白为错误其中，空白为错误 2.优先函数的构造方法优先函数的构造方法 如果优先函数存在，则可以通过以下三个步骤从优如果优先函数存在，则可以通过以下三个步骤从优 先表构造优先函数先表构造优先函数: (1)对于每个终结符对于每个终结符a，令其对应两个符号，令其对应两个符号fa和和ga， 画一张以所有符号画一张以所有符号fa和和ga为结点的方向图。为结点的方向图。 如果如果a.=.b，则从，则从fa画一条弧至画一条弧至gb 如果如果a.=.b，则从，则从gb画一条弧至画一条弧至fa 。 (2)对每个结点都赋予一个数，此数等于从该结点对每个结点都赋予一个数，此数等于从该结点 出发所能到达的结点出发所能到达的结点(包括出发点自身包括出发点自身)。 赋给赋给fa的数作为的数作为f(a) 赋给赋给ga的数作为的数作为g(a)。 (3)检查所构造出来的函数检查所构造出来的函数f和和