编译原理-练习

编译原理编译原理-练习练习练习练习1.1 基本概念基本概念l编译程序的结构编译程序的结构l上下文无关文法的一些概念上下文无关文法的一些概念l词法分析词法分析l语法分析语法分析l自上而下自上而下l自下而上自下而上1.填充下面编译程序总框图填充下面编译程序总框图 源程序源程序 目标程序目标程序(字符串字符串)词法分析器词法分析器语法分析器语法分析器语义分析和中间代码生成器语义分析和中间代码生成器代码优化器代码优化器目标代码生成器目标代码生成器表表格格管管理理出出错错处处理理对于对于上的每一个正规式上的每一个正规式V，存在一个，存在一个上的上的DFAM，使得，使得L(M)=L(V)问题问题：如何由一个正规式：如何由一个正规式V，构造一个，构造一个DFAM思路思路：分两步走：分两步走1.根据根据V，构造一个，构造一个NFAM，使得，使得L(M)=L(V)2.将将M确定化，变为确定化，变为DFAM第一步第一步，在，在上构造一个上构造一个NFAM(1)构造一个拓广的转换图构造一个拓广的转换图练习练习1.2词法分析词法分析(2)使用分裂规则对使用分裂规则对V进行分裂，加进新结点，直到把图进行分裂，加进新结点，直到把图转换成每条弧上标识为转换成每条弧上标识为上的一个字符或上的一个字符或最后得到一个最后得到一个NFAM且且L(M)=L(V)第二步第二步，把，把M确定化确定化(1)两个概念两个概念定义定义1：假定：假定I是是M的状态集的子集，定义的状态集的子集，定义I的的闭包闭包_CLOSURE(I)为：为：(a)若若q I，则，则q _CLOSURE(I)(b)若若q I，那么从，那么从q出发经任意条出发经任意条弧而能到达的任何弧而能到达的任何状态状态q都属于都属于_CLOSURE(I)；定义定义2：假定：假定I是是M的状态集的子集，定义的状态集的子集，定义Ia=_CLOSURE(J)其中，其中，J是所有那些可从是所有那些可从I中的某一状态结点出发经过中的某一状态结点出发经过一条一条a弧而到达的状态结点的全体弧而到达的状态结点的全体例例例例：有如下一个状态转换图：有如下一个状态转换图假定假定I=1,2，求，求Ia=？解：解：Ia=_CLOSURE(J)J=_CLOSURE(J)=Ia=5,6,2,4,7,3,81a a5438267a aa a4,5,35,6,2,4,7,3,8a aa aa a5436278(2)用子集法把用子集法把M确定化确定化设设=a，b 构造一张表构造一张表IIa=_CLOSURE(J)Ib=_CLOSURE(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集合集合1Sab0123413422431 把得到的每个集合看成一个状态，得到一张状态转换表，把得到的每个集合看成一个状态，得到一张状态转换表，该表的初态就是该表的初态就是_CLOSURE(X)，它的终态是那些含有终，它的终态是那些含有终态态Y的子集，这样就得到一个的子集，这样就得到一个DFAM且且L(M)=L(M)1.构造下列正规式相应的构造下列正规式相应的DFA。(1)1(0|1)*101(2)0*10*10*10*(1)1(0|1)*101得到一个得到一个NFAM且且L(M)=L(V)用子集法对用子集法对M进行确定化进行确定化构造一张表构造一张表II0=_CLOSURE(J)I1=_CLOSURE(J)-J=1X1,2,3-2,32,32,3,41,2,32,32,3,42,3,52,3,42,3,4J=2J=2,4J=2J=2,4J=2,5J=2,42,3,52,32,3,4,Y2,3,4,Y2,3,52,3,4J=2J=2,4,YJ=2,5J=2,4II0=_CLOSURE(J)I1=_CLOSURE(J)X1,2,32,32,3,42,3,52,3,4,Y-2,32,32,3,52,32,3,51,2,32,3,42,3,42,3,42,3,4,Y2,3,4把每个子集看成一个状态，得到一个把每个子集看成一个状态，得到一个DFAM，且且L(M)=L(M)s01012345-2242413335301232332434515324s01012345-22424133353把把DFAM进行化简进行化简解解:把把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和和32,41,3,50,1,2,3,40,1,2,3,4J=2,4J=1,3,52，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=2J=1,320,1,21,30,1,2J=2J=321,233所以，所以，最终把最终把M分割为分割为0，1,2，3，4，5用状态用状态2代替状态代替状态1，把引向状态，把引向状态1的箭弧都引向状态的箭弧都引向状态2，把，把1消去，得到一个消去，得到一个DFAM(2)0*10*10*10*得到一个得到一个NFAM且且L(M)=L(V)II0=_CLOSURE(J)I1=_CLOSURE(J)J=0X,0,10,10,13,42,3,42,3,42,3,40,13,43,45,6,75,6,7J=3J=5J=0J=8J=3J=25,6,76,78,9,Y6,76,78,9,YJ=6J=5J=6J=8J=28,9,YJ=99,Y9,Y-J=99,Y-II0=_CLOSURE(J)I1=_CLOSURE(J)X,0,10,10,13,42,3,42,3,42,3,40,13,43,45,6,75,6,75,6,76,78,9,Y6,76,78,9,Y8,9,Y9,Y9,Y-9,Y-把每个子集看成一个状态，得到一个把每个子集看成一个状态，得到一个DFAM，且且L(M)=L(M)s010123456711335577224466-0123456711335577224466s010123456711335577224466-(3)例例例例:把把DFAM进行化简进行化简解解:把把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,576,76,7J=71,3,50,1,2,3,4,5J=1,3,52,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,3J=5J=654,566,7J=1,3J=2,41,30,1,2,32,40,1,2,34,56,7考察考察2,3因为，因为，2,30=2,31=所以，所以，2,3不可再分不可再分考察考察0,1因为，因为，0,10=0,11=所以，所以，0,1不可再分不可再分J=3J=432,344,5J=1J=210,122,3所以，所以，最终把最终把M分割为分割为0,1，2,3，4,5，6,7用状态用状态1代替状态代替状态0，把引向状态，把引向状态0的箭弧都引向状态的箭弧都引向状态1，把，把0消去；消去；用状态用状态3代替状态代替状态2，把引向状态，把引向状态2的箭弧都引向状的箭弧都引向状态态3，把，把2消去；消去；用状态用状态5代替状态代替状态4，把引向状态，把引向状态4的箭弧都引向状的箭弧都引向状态态5，把，把4消去；消去；用状态用状态7代替状态代替状态6，把引向状态，把引向状态6的箭弧都引向状的箭弧都引向状态态7，把，把6消去；得到一个化简得消去；得到一个化简得DFAM2.把把(a)和和(b)分别确定化和最分别确定化和最少化少化(a)(b)(1)用子集法对用子集法对M进行确定化进行确定化构造一张表构造一张表IIa=_CLOSURE(J)Ib=_CLOSURE(J)J=0,1J=100,10,101110,1-J=0J=1J=0,1-把每个子集看成一个状态，得到一个把每个子集看成一个状态，得到一个DFAM，且且L(M)=L(M)sab01211022-IIa=_CLOSURE(J)Ib=_CLOSURE(J)0121210200,10,101110,1-sab01211022-(2)把把DFAM进行化简进行化简解解:把把M状态集分为两组状态集分为两组:终态结点终态结点0，1非终态结点非终态结点2考察考察0，1因为，因为，0，1a=0，1b=所以，所以，0，1不可再分不可再分120,12J=1J=2所以，所以，最终把最终把M分割为分割为0，1，2用状态用状态0代替状态代替状态1，把引向状态，把引向状态1的箭弧都引向状的箭弧都引向状态态0，把，把1消去，得到一个消去，得到一个DFAM(2)用子集法对用子集法对M进行确定化进行确定化构造一张表构造一张表IIa=_CLOSURE(J)Ib=_CLOSURE(J)J=1J=2011124213J=1J=4J=1J=3430532J=0J=5J=3J=2J=5J=4554(2)把把DFAM进行化简进行化简解解:把把M状态集分为两组状态集分为两组:终态结点终态结点0，1非终态结点非终态结点2，3，4，5考察考察0，1因为，因为，0，1a=0，1b=所以，所以，0，1不可再分不可再分12，40,12，3，4，5J=1J=2，4考察考察2，3，4，5因为，因为，2,3,4,5a=所以，所以，2,3,4,5可再分可再分看图，把看图，把2,3,4,5分割为分割为2,4和和3,50,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,13,50,13,5J=0,1J=3,53,52,43,52,4J=3,5J=2,4所以，最终把所以，最终把M分割为分割为0，1，2，4，3，5用状态用状态0代替状态代替状态1，把引向状态，把引向状态1的箭弧都引向状的箭弧都引向状态态0，把，把1消去；用状态消去；用状态2代替状态代替状态4，把引向状态，把引向状态4的箭弧都引向状态的箭弧都引向状态2，把，把4消去；用状态消去；用状态5代替状态代替状态3，把引向状态，把引向状态3的箭弧都引向状态的箭弧都引向状态5，把，把3消去；得消去；得到一个到一个DFAM3.设计一个设计一个DFA，它接受，它接受0，1上所有满足如下条件的字符串：上所有满足如下条件的字符串：每个每个1都有都有0直接跟在右边。直接跟在右边。解解:(1)根据题意，得到相应的正规式：根据题意，得到相应的正规式：(0|10)*(2)由以上正规式构造相应的由以上正规式构造相应的NFA为：为：(1)用子集法对用子集法对M进行确定化进行确定化构造一张表构造一张表II0=_CLOSURE(J)I1=_CLOSURE(J)J=1J=2x,1,y1,y1,y1,y2221,y-J=1J=2J=1-把每个子集看成一个状态，得到一个把每个子集看成一个状态，得到一个DFAM，且且L(M)=L(M)s0101211122-II0=_CLOSURE(J)I1=_CLOSURE(J)01212112x,1,y1,y1,y1,y2221,y-s0101211122-(2)把把DFAM进行化简进行化简解解:把把M状态集分为两组状态集分为两组:终态结点终态结点0，1非终态结点非终态结点2考察考察0，1因为，因为，0，10=0，11=所以，所以，0，1不可再分不可再分120,12J=1J=2所以，所以，最终把最终把M分割为分割为0，1，2用状态用状态1代替状态代替状态0，把引向状态，把引向状态0的箭弧都引向状的箭弧都引向状态态1，把，把0消去，得到一个消去，得到一个DFAM问题一：问题一：消除文法直接左递归方法消除文法直接左递归方法：设有产生式设有产生式PP1|P2|Pm|1|2|n其中每个其中每个i不以不以P开头，每个开头，每个i不为不为消除消除P的直接左递归性就是把这些规则改写成：的直接左递归性就是把这些规则改写成：P1P|2P|nPP1P|2P|mP|练习练习1.3自上而下的语法分析自上而下的语法分析 4.消除整个文法的左递归的算法消除整个文法的左递归的算法如果文法不含回路（形如如果文法不含回路（形如 的推导），也不含有以的推导），也不含有以为右部的产生式，则下面算法可以消除左递归为右部的产生式，则下面算法可以消除左递归(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的所有产生式的所有产生式 Endfor Endfor 消除关于消除关于P Pi i的直接左递归的直接左递归EndforEndfor(3)(3)化简由化简由(2)(2)得到的文法：除去从开始符号无法达到的得到的文法：除去从开始符号无法达到的非终结符的产生式非终结符的产生式例子例子例子例子：考虑以下文法，消除其左递归性：考虑以下文法，消除其左递归性SQc|cQRb|bRSa|a解解：(1)把该文法的非终结符排列为把该文法的非终结符排列为R、Q、S.(2)对于对于R，不存在直接左递归，不用消除，不存在直接左递归，不用消除对于对于Q，把，把R代入到代入到Q的有关候选式后，把的有关候选式后，把Q的产生式改写为的产生式改写为QSab|ab|b现在现在Q不存在直接左递归，不用消除不存在直接左递归，不用消除对于对于S，把，把Q代读到代读到S的有关候选式后，把的有关候选式后，把S的产生式改写为的产生式改写为SSabc|abc|bc|cS有直接左递归，消除有直接左递归，消除S的直接左递归为的直接左递归为SabcS|bcS|cSSabcS|得到消除左递归性的文法为得到消除左递归性的文法为SabcS|bcS|cSSabcS|QSab|ab|bRSa|a(3)显然，显然，Q和和R的产生式已经是多余的，将它们去掉的产生式已经是多余的，将它们去掉化简后的文法是：化简后的文法是：SabcS|bcS|cSSabcS|注意注意注意注意：由于对非终结符排序的不同，最后所得的文法在形式：由于对非终结符排序的不同，最后所得的文法在形式上可能不一样，但它们都是等价的上可能不一样，但它们都是等价的例如例如例如例如：考虑刚才的文法，消除其左递归性：考虑刚才的文法，消除其左递归性SQc|cQRb|bRSa|a解解：(1)把该文法的非终结符排列为把该文法的非终结符排列为S、Q、R(2)对于对于S，不存在直接左递归，不用消除，不存在直接左递归，不用消除对于对于Q，不存在直接左递归，不用消除，不存在直接左递归，不用消除对于对于R，把，把S代入到代入到R的有关候选式后，把的有关候选式后，把R的产生式改写为的产生式改写为RQca|ca|a把把Q代入到代入到R的有关候选式后，把的有关候选式后，把R的产生式改写为的产生式改写为RRbca|bca|ca|aRRbca|bca|ca|aR有直接左递归，消除有直接左递归，消除S的直接左递归为的直接左递归为RbcaR|caR|aRRbcaR|得到消除左递归性的文法为得到消除左递归性的文法为SQc|cQRb|bRbcaR|caR|aRRbcaR|问题三：问题三：证明是证明是LL(1)LL(1)文法文法(1)文法不含左递归文法不含左递归(2)对于文法中每一个非终结符对于文法中每一个非终结符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代表从左到右扫描输入串，第代表从左到右扫描输入串，第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的开始符的开始符号集满足号集满足FIRST(FIRST(i i)FIRST()FIRST(j j)=)=，则，则A A可以根可以根据所面临的第一个输入符号，准确地指派一个候选据所面临的第一个输入符号，准确地指派一个候选式式去执行任务，去执行任务，是那个是那个FIRSTFIRST集含集含a a的候选式，的候选式，即即 a a FIRST(FIRST()2.对每个文法符号对每个文法符号X V VN N V VT T构造其构造其FIRST(X)FIRST(X)连续使用以下规则，直至每个结合连续使用以下规则，直至每个结合FIRSTFIRST不再增大为止不再增大为止(1)(1)若若X X V VT T，则，则FIRST(X)=X.FIRST(X)=X.(2)(2)若若X X V VN N，且有产生式，且有产生式XaXa，则把，则把a a加入到加入到FIRST(X)FIRST(X)中；中；若若XX也是一条产生式，则把也是一条产生式，则把也加到也加到FIRST(X)FIRST(X)中。中。(3)(3)若若XYXY是一个产生式，且是一个产生式，且Y Y V VN N，则把，则把FIRST(Y)FIRST(Y)中所中所有非有非元素都加到元素都加到FIRST(X)FIRST(X)中；中；若若XYXY1 1Y Y2 2 Y Yk k是一个产生式，是一个产生式，Y Y1 1Y Y2 2 Y Yi-1i-1都是非终都是非终结符，而且，对于任何结符，而且，对于任何j j，1 1j ji-1-1，FIRST(Y FIRST(Yj j)都含有都含有(即即Y Y1 1YYi-1i-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 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，定义它的后继符号集合：，定义它的后继符号集合：特别地，如果特别地，如果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自自动匹配动匹配5.对每个文法对每个文法A V 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)FOLLOW(A)加至加至FOLLOW(B)FOLLOW(B)中中 或或ABAB是一个产生式而是一个产生式而(即即 FIRST()FIRST()，FOLLOW(A)FOLLOW(A)加至加至FOLLOW(B)FOLLOW(B)中中其中其中,(V VN N V VT T)*，B B V VN N6.构造分析表构造分析表M的算法是的算法是(1)(1)对于文法对于文法G G的每个产生式的每个产生式AA，执行，执行(2)(3)(2)(3)(2)(2)对每个终结符对每个终结符a a FIRST()FIRST()，把，把AA加至加至MA,aMA,a中；中；(3)(3)若若 FIRST()FIRST()，则对任何，则对任何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=SP:P:Sa|(T)TT,S|S(1)消除其产生式的左递归消除其产生式的左递归.然后，对每个非终结符写出不带然后，对每个非终结符写出不带回溯的递归子程序；回溯的递归子程序；(2)经改写后的文法是否是经改写后的文法是否是LL(1)的？给出它的预测分析表的？给出它的预测分析表Sa|(T)TT,S|S(1)消除其产生式的直接左递归消除其产生式的直接左递归解：对于解：对于TT,S|S(P=T，=,S，=S)变成变成TSTT,ST|所以所以Sa|(T)TSTT,ST|每个非终结符的不带回溯的递归子程序如下：每个非终结符的不带回溯的递归子程序如下：PP|-PPPP|Sa|(T)TSTT,ST|(2)经改写后的文法经改写后的文法是否是是否是LL(1)的？的？给出它的预测分析表。给出它的预测分析表。解：解：FIRST(S)=;FIRST(T)=;FIRST(T)=;(2)若若X VN，且有产生式，且有产生式Xa，则把，则把a加入到加入到FIRST(X)中；若中；若X也是一条也是一条产生式，则把产生式，则把也加到也加到FIRST(X)中。中。(3)若若XY是一个产生式，且是一个产生式，且Y VN，则把则把FIRST(Y)中所有非中所有非元素都加到元素都加到FIRST(X)中；中；若若XY1Y2Yk是一个产生式，是一个产生式，Y1Y2Yi-1都是非终结符，而且，对于任何都是非终结符，而且，对于任何j，1ji-1，FIRST(Yj)都含有都含有(即即Y1Yi-1=)，则把，则把FIRST(Yi)中的所有中的所有非非元素都加到元素都加到FIRST(X)；特别是，若所有的特别是，若所有的FIRST(Yj)均含有均含有，j=1，2，k，则把，则把加到加到FIRST(X)中。中。a,(a,(Sa|(T)TSTT,ST|解：解：FIRST(ST)=;FIRST(,ST)=;FIRST(a)=;FIRST()=;FIRST(T)=;=X1X2Xn构造构造FIRST()(1)置置FIRST()=FIRST(X1)(2)若对任何若对任何1ji-1，FIRST(Xj)，则把则把FIRST(Xj)加至加至FIRST()中中(3)特别的，若所有的特别的，若所有的FIRST(Xj)均含均含有有，1jn，则把，则把也加至也加至FIRST()中中，a,(a(Sa|(T)TSTT,ST|解：解：FOLLOW(T)=;FOLLOW(T)=;FOLLOW(S)=;(1)对于分发开始符号对于分发开始符号S，置，置#于于FOLLOW(S)中；中；(2)若若AB是一个产生式，则把是一个产生式，则把FIRST()加至加至FOLLOW(B)中；中；(3)若若AB是一个产生式，或是一个产生式，或AB是一个产生式而是一个产生式而 FIRST()，FOLLOW(A)加至加至FOLLOW(B)中。中。#,),Sa|(T)TSTT,ST|证明：证明：FIRST(a)FIRST()FIRST(T)=a(=FIRST(T)FOLLOW(T)=，,)=所以，该文法是所以，该文法是LL(1)文法文法Sa|(T)TSTT,ST|a()，#SSaS S(T)TTSTTSTTSTTTT,ST2.构造算符优先关系表构造算符优先关系表(1)通过检查产生式的每一个候选式可以找出满足通过检查产生式的每一个候选式可以找出满足a=.b（即（即Pab或或PaQb的产生式）的产生式）(2)为了满足为了满足.，需对，需对G中每个非终结符中每个非终结符P构造两个构造两个集合集合FIRSTVT(P)和和LASTVT(P)：(3)构造集合构造集合FIRSTVT(P)的算法的算法按其定义，可用下面两条规则来构造集合按其定义，可用下面两条规则来构造集合FIRSTVT(P)：若有产生式若有产生式Pa或或PQa，则则a FIRSTVT(P)；若若a FIRSTVT(Q)，且有产生式，且有产生式PQ，则则a FIRSTVT(P)。(4)同理构造构造集合同理构造构造集合LASTVT(P)的算法的算法按其定义，可用下面两条规则来构造集合按其定义，可用下面两条规则来构造集合LASTVT(P)：若有产生式若有产生式Pa或或PaQ，则则a LASTVT(P)；若若a LASTVT(Q)，且有产生式，且有产生式PQ，则则a LASTVT(P)。(5)有了这两个集合之后，就可以通过检查每个产生有了这两个集合之后，就可以通过检查每个产生式的候选式确定满足关系式的候选式确定满足关系.的所有终结符对。的所有终结符对。(1)(1)假定有个产生式的一个候选形为假定有个产生式的一个候选形为aPaP 那么，对任何那么，对任何b b FIRSTVT(P)FIRSTVT(P)，有，有a a.b b。例例例例1 1:考虑下面的文法考虑下面的文法G：SX|SaXXY|X%YYX！构造该文法构造该文法G的每个非终结符的的每个非终结符的FIRSTVT和和LASTVT集合集合解解:(1)构造构造FIRSTVT集合集合FIRSTVT(Y)=FIRSTVT(X)=FIRSTVT(S)=若有产生式若有产生式Pa或或PQa，则则a FIRSTVT(P)；若若a FIRSTVT(Q)，且有产生式，且有产生式PQ，则，则a FIRSTVT(P)。%,a,%,例例例例1 1:考虑下面的文法考虑下面的文法G：SX|SaXXY|X%YYX！构造该文法构造该文法G的每个非终结符的的每个非终结符的FIRSTVT和和LASTVT集合集合解解:(1)构造构造LASTVT集合集合LASTVT(Y)=LASTVT(X)=LASTVT(S)=!,%,!,a,%,!,若有产生式若有产生式Pa或或PaQ，则则a LASTVT(P)；若若a LASTVT(P)，且有产生式，且有产生式PQ，则，则a LASTVT(P)。例例例例2 2:G:SX|SaXXY|X%YYX！求出该文法每个终结符号的优先关系，并构造优先分析表求出该文法每个终结符号的优先关系，并构造优先分析表(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)，有，有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和和g是否与原来的关系是否与原来的关系矛盾。若没有矛盾，则矛盾。若没有矛盾，则f和和g就是要求的优先函数，就是要求的优先函数，若有矛盾，则不存在优先函数。若有矛盾，则不存在优先函数。gifif*g*g+f+f#g#例例例例:取前面文法取前面文法G(E)(1)EE+T|T(2)TT*F|F(3)F(E)|i的终结符的终结符+，*，i，#i+*#fg74662151(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)=(U|V)|Wn(3)证明 U(VW)=(UV)W 因为 L(U(VW)=L(U)L(VW)=L(U)(L(V)L(W)=(L(U)L(V)L(W)=L(UV)L(W)=L(UV)W)n(4)证明 U(V|W)=(UV)|(UW)因为 L(U)(L(V)L(W)=(L(U)L(V)(L(U)L(W)n(5)U=U=U 证：L(U)=L()L(U)=L(U)0 L(U)=L(U)n8.给出下面的正规表达式。(1)以01结尾的二进制数串;正规式 (0|1)*01(2)能被5整除的十进制整数;正规式：(0|1|2|3|4|5|6|7|8|9)*(0|5)(3)英文字母组成的所有符号串,要求符号串中的字母依照字典序排列;正规式 (a|A)*(b|B)*(c|C)*(d|D)*(z|Z)*(4)给出描述包含奇数个1或奇数个0个二进制数串的正规表达式：解题思路：本题求二进制串，并且要求包含奇数个0或奇数个1，由于0和1都可以在二进制串中任何地方出现，所以本题只需要考虑一种情况，另外一种情况也可以类似求得。考虑包含奇数个0的字符串：由于只关心0的个数的奇偶数，我们可以把二进制串分成多段来考虑，第1段为二进制串的开始到第1个0为止，这一段包含1个0，并且0的前面有0个或多个1，对于剩下的二进制串按照每段包含两个0的方式去划分，即以0开始，以0结尾，中间可以有0个或多个1，如果一个二进制串被这样划分完后，剩下的部分如果全部是全1串（这些全1串在前面划分的串之间或最后），则该二进制串就具有奇数个0，所以该二进制可以这样描述：以第1段（1*）开始，后面由全1串（1*）以及包含两个0的串（01*0）组成，所以包含奇数个0的正规表达式为：1*0（101*0）*，本题的解答则是：1*0（101*0）*0*1（010*1）*(5)没有重复出现的数字的数字符号串全体.(6)最多有一个重复出现的数字的数字符号串全体令 ri=i|,i=0,1,2,.,9 R0|R1|R2|.|R9记为 Ri i(0,1,2.,9)P(0,1,2.,9)表示0,1,2.,9的全排列 ri0ri1.ri9 i0i1.i9P(0,1,2.,9)i ri0ri1.ri9i(0,1,2.,9)i0i1.i9P(0,1,2.,9)(7)不包含子串abb的由a和b组成的符号串全体.b*(a*|(ba)*)*结束语结束语谢谢大家聆听！谢谢大家聆听！88