编译原理-练习.ppt

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

2、构造一个拓广的转换图,练习1.2 词法分析,(2)使用分裂规则对V进行分裂，加进新结点，直到把图转换成每条弧上标识为上的一个字符或 最后得到一个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中的某一状态结点出发经过一条a弧而到达的状态结点的全体,例：有如下一个状态转换图

3、 假定 I=1, 2，求Ia = ？ 解： Ia =_CLOSURE(J) J = _CLOSURE(J) = Ia=5, 6, 2, 4, 7, 3, 8,1,a,5,4,3,8,2,6,7,a,a,4,5,3,5,6,2,4,7,3,8,(2)用子集法把M确定化 设 = a，b 构造一张表,集合1,集合1,集合1,集合2,集合2,集合2,集合3,集合3,集合3,集合4,集合4,集合4,_CLOSURE(X),把得到的每个集合看成一个状态，得到一张状态转换表，该表的初态就是_CLOSURE(X)，它的终态是那些含有终态Y的子集，这样就得到一个DFA M 且L(M) = L(M),1.构造下列

4、正规式相应的DFA。 (1) 1(0|1)*101 (2) 0*10*10*10*, ,(1)1(0|1)*101,得到一个NFA M 且 L(M) = L(V),用子集法对M进行确定化 构造一张表,-,J=1,X,1, 2, 3,-,2, 3,2, 3,2, 3, 4,1, 2, 3,2, 3,2, 3, 4,2, 3, 5,2, 3, 4,2, 3, 4,J=2,J=2, 4,J=2,J=2, 4,J=2, 5,J=2, 4,2, 3, 5,2, 3,2, 3, 4,Y,2, 3, 4, Y,2, 3, 5,2, 3, 4,J=2,J=2, 4, Y,J=2, 5,J=2, 4,把每个子集

5、看成一个状态，得到一个DFA M， 且L(M) = L(M),0,1,2,3,2,3,3,2,4,3,4,5,1,5,3,2,4,把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,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，4,0，1，2，

6、3,J=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,2,0,1,2,1,3,0,1,2,J=2,J=3,2,1,2,3,3,所以， 最终把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),J=0,X,0,1,0,1,0,1,3,4,2,3,4,2,3,4,2,

7、3,4,0,1,3,4,3,4,5,6,7,5,6,7,J=3,J=5,J=0,J=8,J=3,J=2,5,6,7,6,7,8,9,Y,6,7,6,7,8,9,Y,J=6,J=5,J=6,J=8,J=2,8,9,Y,J=9,9,Y,9,Y,-,J=9,9,Y,-,X,0,1,0,1,0,1,3,4,2,3,4,2,3,4,2,3,4,0,1,3,4,3,4,5,6,7,5,6,7,5,6,7,6,7,8,9,Y,6,7,6,7,8,9,Y,8,9,Y,9,Y,9,Y,-,9,Y,-,把每个子集看成一个状态，得到一个DFA M， 且L(M) = L(M),0,1,2,3,4,5,6,7,1,1,

8、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,5分割为0,1,2,3和4,5,7, ,6,7,6,7,J=7,1,3,5,0,1,2,3,4,5,J=1,3,5,2,4,6,0,1,2,3,4,5,J=2,4,6,考察4,5 因为， 4,50 = 4,51 = 所以， 4,5 不可再分

9、考察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,5,4,5,6,6,7,J=1,3,J=2,4,1,3,0,1,2,3,2,4,0,1,2,3,4,5,6,7,考察2,3 因为， 2,30 = 2,31 = 所以， 2,3 不可再分 考察0,1 因为， 0,10 = 0,11 = 所以， 0,1 不可再分,J=3,J=4,3,2,3,4,4,5,J=1,J=2,1,0,1,2,2,3,所以， 最终把M分割为0,1， 2,3 ， 4,5 ， 6,7 用状态1代替状态0，把引向状态0的箭弧

10、都引向状态1，把0消去；,用状态3代替状态2，把引向状态2的箭弧都引向状态3，把2消去；,用状态5代替状态4，把引向状态4的箭弧都引向状态5，把4消去；,用状态7代替状态6，把引向状态6的箭弧都引向状态7，把6消去；得到一个化简得DFA M,2.把(a)和(b)分别确定化和最少化,(a),(b),(1)用子集法对M进行确定化 构造一张表,J=0,1,J=1,0,0,1,0,1,0,1,1,1,0,1,-,J=0,J=1,J=0,1,-,把每个子集看成一个状态，得到一个DFA M， 且L(M) = L(M),0,1,2,1,2,1,0,2,0,0,1,0,1,0,1,1,1,0,1,-,(2)

11、把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代替状态1，把引向状态1的箭弧都引向状态0，把1消去，得到一个DFA M,(2)用子集法对M进行确定化 构造一张表,J=1,J=2,0,1,1,1,2,4,2,1,3,J=1,J=4,J=1,J=3,4,3,0,5,3,2,J=0,J=5,J=3,J=2,J=5,J=4,5,5,4,(2) 把DFA M进行化简 解: 把M状态集分为两组: 终态结点0，1 非终态结点

12、2，3，4，5 考察0，1 因为， 0，1a = 0，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,5,2,3,4,5,J=0,1,3,5,0,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,J=3,5,J=2,4,所以，最终把M分

13、割为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直接跟在右边。 解: (1)根据题意，得到相应的正规式： (0|10)* (2)由以上正规式构造相应的NFA为：,(1)用子集法对M进行确定化 构造一张表,J=1,J=2,x,1,y,1,y,1,y,1,y,2,2,2,1,y,-,J=1,J=2,J=1,-,把每个子集看成一个状态，得到

14、一个DFA M， 且L(M) = L(M),0,1,2,1,2,1,1,2,x,1,y,1,y,1,y,1,y,2,2,2,1,y,-,(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消去，得到一个DFA M,问题一：消除文法直接左递归方法： 设有产生式 PP1|P2|Pm|1|2|n 其中每个i不以P开头，每个i不为 消除P的直接左递归性就是把这些规则改写

15、成： P1P|2P|nP P1P| 2P|mP| ,练习1.3 自上而下的语法分析,4.消除整个文法的左递归的算法 如果文法不含回路（形如 的推导），也不含有以为右部的产生式，则下面算法可以消除左递归 (1)把文法G的所有非终结符按任一种顺序排列成P1,P2,Pn；按此顺序执行 (2)for i = 1 to n do for j = 1 to i-1 do 把形如PiPj的规则改写成: Pi 1|2|k。 其中Pj1|2|k是关于Pj的所有产生式 Endfor 消除关于Pi的直接左递归 Endfor (3)化简由(2)得到的文法：除去从开始符号无法达到的非终结符的产生式,例子：考虑以下文法，

16、消除其左递归性 SQc | c QRb | b RSa | a 解：(1)把该文法的非终结符排列为R、Q、S. (2)对于R，不存在直接左递归，不用消除 对于Q，把R代入到Q的有关候选式后，把Q的产生式改写为 QSab| ab | b 现在Q不存在直接左递归，不用消除 对于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的产生

17、式已经是多余的，将它们去掉 化简后的文法是： SabcS | bcS | cS SabcS | 注意：由于对非终结符排序的不同，最后所得的文法在形式上可能不一样，但它们都是等价的,例如：考虑刚才的文法，消除其左递归性 SQc | c QRb | b RSa | a 解： (1)把该文法的非终结符排列为S、Q、R (2)对于S，不存在直接左递归，不用消除 对于Q，不存在直接左递归，不用消除 对于R，把S代入到R的有关候选式后，把R的产生式改写为 RQca| ca | a 把Q代入到R的有关候选式后，把R的产生式改写为 RRbca| bca | ca | a,RRbca| bca | ca | a

18、 R有直接左递归，消除S的直接左递归为 RbcaR | caR | aR RbcaR | 得到消除左递归性的文法为 SQc | c QRb | b RbcaR | caR | aR RbcaR | ,问题三：证明是LL(1)文法 (1)文法不含左递归 (2)对于文法中每一个非终结符A的各个产生式的候选式的FIRST集两两不相交。即，若 A1|2|n 则FIRST(i)FIRST(j)= (ij) (3)对于文法中的每个非终结符A，若它的某个候选首符集包含,则 FIRST(A)FOLLOW(A)= 如果一个文法G满足以上条件，则称该文法G为LL(1)文法(第1个L代表从左到右扫描输入串，第2个L

19、代表最左推导，1表示分析时每一步只看1个符号),问题四：预测分析表M(xm ，ai )的构造方法,1. 定义FIRST集 令文法G是不含左递归的文法，对G的非终结符的候选，定义它的开始符号（终结首符）集合： 特别地，如果，则FIRST() 如果非终结符A的任意两个候选式i和j的开始符号集满足FIRST(i)FIRST(j)=，则A可以根据所面临的第一个输入符号，准确地指派一个候选式去执行任务，是那个FIRST集含a的候选式，即 a FIRST(),2.对每个文法符号XVNVT构造其FIRST(X) 连续使用以下规则，直至每个结合FIRST不再增大为止 (1)若XVT，则FIRST(X)=X.

20、(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)中的所有非元素都加到FIRST(X)； 特别是，若所有的FIRST(Yj)均含有，j=1，2，k，则把加到FIRST(X)中。,3. 对于文法的任意符号串=X1X2 Xn构造集合FIRST() (1)置FIRST()= F

21、IRST(X1) (2)若对任何1ji-1，FIRST(Xj)，则把FIRST(Xi)加至FIRST()中 (3)特别的，若所有的FIRST(Xj)均含有，1jn，则把 也加至FIRST()中,4.定义FOLLOW集 对文法G的任何非终结符A，定义它的后继符号集合： 特别地，如果SA，则#FOLLOW(A) FOLLOW(A)集合是所有句型中出现在紧接A之后的终结符号或#所组成的集合 当非终结符A面临输入符号a，且a不属于A的任意候选式的FIRST集但A的某个候选式的FIRST集包含时，只有当a FOLLOW(A)，才可能允许A自动匹配,5.对每个文法AVN构造其FOLLOW(A) 连续使用一

22、下规则，直至每个集合FOLLOW不再增大为止 (1)对于分发开始符号S，置#与FOLLOW(S)中； (2)若AB是一个产生式，则把FIRST()加至FOLLOW(B)中； (3)若AB是一个产生式， FOLLOW(A)加至FOLLOW(B)中 或AB是一个产生式而 (即FIRST()，FOLLOW(A)加至FOLLOW(B)中 其中,(VNVT)*，BVN,6.构造分析表M的算法是 (1)对于文法G的每个产生式A，执行(2)(3) (2)对每个终结符aFIRST()，把A加至MA,a中； (3)若FIRST()，则对任何b FOLLOW(A)把A加至MA,b中； (4)把所有无定义的MA,a

23、标上”出错标志”,1. 设有文法G(VT，VN，S，P)，其中 VT=a， ，, ，(，) ；VN=S,T；S = S P: S a | | (T) T T,S | S (1)消除其产生式的左递归.然后，对每个非终结符写出不带回溯的递归子程序； (2)经改写后的文法是否是LL(1)的？给出它的预测分析表,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

24、) TST T,ST| (2)经改写后的文法 是否是LL(1)的？ 给出它的预测分析表。 解：FIRST( S )= ; FIRST( 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)中的所有非元素都加到FIRST(X)； 特别是

25、，若所有的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)特别的，若所有的FIRST(Xj)均含有，1jn，则把 也加至FIRST()中,，,a, ,(,a,(,S a | | (T) TST T,ST|

26、 解： FOLLOW(T)= ; FOLLOW (T)= ; FOLLOW (S)= ;,(1)对于分发开始符号S，置#于FOLLOW(S)中； (2)若AB是一个产生式，则把FIRST()加至FOLLOW(B)中； (3)若AB是一个产生式，或AB是一个产生式而FIRST()，FOLLOW(A)加至FOLLOW(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|,2.构造算符优先

27、关系表 (1)通过检查产生式的每一个候选式可以找出满足a=.b （即Pab或PaQb的产生式） (2)为了满足.，需对G中每个非终结符P构造两个集合FIRSTVT(P)和LASTVT(P)：,(3)构造集合FIRSTVT(P)的算法 按其定义，可用下面两条规则来构造集合FIRSTVT(P)： 若有产生式Pa或PQa， 则aFIRSTVT(P)； 若aFIRSTVT(Q)，且有产生式PQ， 则aFIRSTVT(P)。,(4)同理构造构造集合LASTVT(P)的算法 按其定义，可用下面两条规则来构造集合LASTVT(P)： 若有产生式P a或P aQ ， 则a LASTVT(P)； 若a LAST

28、VT(Q)，且有产生式P Q ， 则a LASTVT(P)。,(5)有了这两个集合之后，就可以通过检查每个产生式的候选式确定满足关系.的所有终结符对。 (1)假定有个产生式的一个候选形为 aP 那么，对任何bFIRSTVT(P)，有a . b。,例1:考虑下面的文法G： S X | SaX X Y | X%Y Y X！ 构造该文法G的每个非终结符的FIRSTVT和LASTVT集合 解: (1)构造FIRSTVT集合 FIRSTVT(Y)= FIRSTVT(X)= FIRSTVT(S)= , 若有产生式Pa或PQa，则aFIRSTVT(P)； 若aFIRSTVT(Q)，且有产生式PQ，则aFIR

29、STVT(P)。,%,a,%,例1:考虑下面的文法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)。,例2:G: S X | SaX X Y | X%Y Y X！ 求出该文法每个终结符号的优先关系，并构造优先分析表 (1)SSaX，且%, FIRSTVT(X)

30、 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 那么，对任何bFIRSTVT(P)，有a . b。,构造分析表如下： 其中，空白为错误,2.优先函数的构造方法 如果优先函数存在，则可以通过以下三个步骤从优先表构造优先函数: (1)对于每个终结符a，令其对应两个符号fa和ga，画一张

31、以所有符号fa和ga为结点的方向图。如果a.=.b，则从fa画一条弧至gb如果a.=.b，则从gb画一条弧至fa 。 (2)对每个结点都赋予一个数，此数等于从该结点出发所能到达的结点(包括出发点自身)。赋给fa的数作为f(a)赋给ga的数作为g(a)。 (3)检查所构造出来的函数f和g是否与原来的关系矛盾。若没有矛盾，则f和g就是要求的优先函数，若有矛盾，则不存在优先函数。,gi,fi,f*,g*,g+,f+,f#,g#,例:取前面文法G(E) (1) EE+T | T (2) TT*F | F (3) F (E) | i 的终结符+，*，i，#,7,4,6,6,2,1,5,1,(1) U | V = V | U或的交换律 证明：因为，L(U|V) = L(U)L(V) 又因为，L(V|U) = L(V)L(U) = L(U)L(V) 因为， L(U|V) = L(V|U) 所以，U | V = V | U,(2) U | ( V|W ) = ( U|V ) | W或的结合律 证明： 因为，L(U|(V|W)=L(U)L(V|W) =L(U)L(V)L(W) 又因为，L( U|V ) | W) = L(U|V)L(W) = L(U)L(V)L(W) 因此， L(U|(V|W) = L( U|V ) | W) 所以， U | ( V|W