第三四章习题课编译原理课件

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,第三、四章习题,P64：7,8,9,12,14,15,20,补充题,P81：1,2,3,4,5,1,第三、四章习题P64：7,8,9,12,14,15,20,补,词法分析,正规式,自动机,正规文法,正规式,正规文法,NFA,DFA,状态最小DFA,词法分析器,分裂法,转换规则,子集法,分划法,2,词法分析正规式自动机正规文法正规式正规文法NFA,正规式与正规文法的转化,:,令 VT = ,对任意正规式 R 选择一个非终结符 Z 生成规则Z,R，并令 SZ；,若 a 和 b 都是正规式，对形如 A,ab的规则转换成 AaB 和 Bb；,在已转换的文法中，将形如 Aa*b 的规则进一步转换成 A aA | b；,不断利用上上面后两条规则进行转换，直到每条规则最多含有一个,终结符为止。,:,将每个非终结符表示成关于它的正规式方程，获得一个联立方程组。,依照求解规则：,若 x =,x | (或,x =,x+)，则解为,x =,*,若 x = x, | (或,x = x,+)，则解为,x =,*,以及正规式的分配率、交换率和结合率求关于文法开始符号的正规式,方程组的解。,3,正规式与正规文法的转化:3,正规式转化为NFA(1/2),(1)引进初始结点 X 和终止结点 Y，把 R 表示成,拓广转换图,。如图,X,Y,R,(2)分析 R 的语法结构，用如下规则对 R 中的每个基本符号构造 NFA。,R,，构造 NFA 如图：,R,，构造 NFA 如图：,X,Y,X,Y,Ra(a,),，构造 NFA 如图：,X,Y,a,4,正规式转化为NFA(1/2)(1)引进初始结点 X 和终止结,正规式转化为NFA(2/2),若 R 是复合正规式，则按下图的转换规则对 R 进行分裂和加进新结，直至每个边上只留下一个符号（或,）为止。,A,B,r,1,r,2,A,B,r,1,C,r,2,代换为,A,B,r,1,|r,2,A,B,r,1,r,2,代换为,A,B,r,1,*,A,B,C,代换为,r,1,整个分裂过程中，所有新结点均采用不同的名字，保留 X，Y 为全图唯一初态结点和终态结点,5,正规式转化为NFA(2/2)若 R 是复合正规式，则按下图的,NFA确定化为DFA,首先将从,初态 S,出发经过任意条,弧所能到达的状态所组成的集合作为,M 的初态,S，然后从 S 出发，经过对输入符号 a, 的状态转移所能到达的状态(包括读输入符号之前或之后所有可能的 转移所能到达的状态)所组成的集合作为 M 的,新状态,，如此重复，直到不再有新的状态出现为止。,从 NFA N=(Q,F,S,Z)构造等价的DFA M=(Q,F,S,Z)的方法,6,NFA确定化为DFA 首先将从初态 S 出发经过任意条,DFA的化简,将 DFA M 的状态集 Q 分成两个子集：,终态集 F 和非终态集,F,，形成初始分划 ,。,对,建立新的,分划 new,。对, 的每个状态子集 G 进行如下变换,：,把 G,分划成新的子集，使得 G 的两个状态 s 和 t 属于同一子集，当且仅当对,任何输入符号 a，状态 s 和 t 转换到的状态都属于 的同一子集,。,用 G 分划出的所有新子集替换 G，形成新的分划 new 。,如果,new,，则执行第,（4）步；否则令,new,，重复第（2）步。,分划结束，对分划中的每个状态子集，选出一个状态作代表，而删去其它一切等价的状态，并把,射向其余状态的箭弧都改为射向作为“代表”的状态,。,7,DFA的化简将 DFA M 的状态集 Q 分成两个子集：终态,增加新初态,X,，与所有原初态用,相连，增加新终态,Y,，与所有原终态用,相连，从而构成一个新的 FA M，它只有一个初态 X 和一个终态 Y。,在X 与 Y 之间进行弧合并：,A,C,B,r,1,r,2,A,B,r,1,r,2,r,2,A,C,B,r,1,r,3,A,B,r,1,r,2,A,B,r,1,|r,2,A,B,r,1,r,2,*,r,3,在X 和 Y之间的表达式即为所求的正规式 R。,代之以,代之以,代之以,自动机转化为正规式,8,增加新初态 X，与所有原初态用相连，增加新终态 Y，与所,正规文法转化为自动机(1/2),设给定一个,右线性正规文法 G=(V,N,V,T,P,S),，则相应的,有穷自动机 M=(Q,f,q0,Z,),（1）将VN中的每一个非终结符视作 M 中的一个状态，并增加一个,新终态 D,，且 D,V,N,，令 Q=,V,N,D,Z=D,=,V,T,q0,=S,（2）对,A,aB,（A,BV,N,a,V,T,），令,f(A,a)=B,。构造弧,（3）对,A,a,（AV,N,aV,T,），令,f(A,a)=,D,。构造弧,A,B,a,A,D,a,9,正规文法转化为自动机(1/2)设给定一个右线性正规文法 G=,正规文法转化为自动机(2/2),设给定一个,左线性正规文法 G=(VN,VT,P,S),，则相应的,有穷自动机 M=(Q,f,q0,Z,),（1）将VN中的每一个非终结符视作 M 中的一个状态，并增加一个,初始状态 q0,，且,q0,VN,，令 Q=,VN,q0,Z=S,=,VT,(将文法G的开始符号S看成终态),（2）对,A,Ba,（A,BVN,a,VT ,）令,f(B,a)=A,。构造弧,（3）对,A,a,（AVN,aVT ,），令,f(q0,a)=A,。构造弧,B,A,a,q,0,A,a,10,正规文法转化为自动机(2/2)设给定一个左线性正规文法 G=,自动机转化为正规文法(1/2),设给定,有穷自动机 M=(Q,f,q0,Z,)，,按照下述方法可,以从 M 构造出相应的,右线性正规文法,G=(V,N,V,T,P,S),，,使得L(M)=L(G),(1)令,V,N,=Q,V,T,=,S=q0,(2)若f(A,a)=B且B,Z时，则将规则,A,aB,加到P中。,(3)若f(A,a)=B且B,Z时，则将规则,A,aBa或,A,aB, B,加到P中。,(4)若文法的开始符号 S 是一个终态，,则将规则,S,加到P中。,A,B,a,注意:,若终态无出弧，则去掉该非终结符,起点开始，考虑出弧！,11,自动机转化为正规文法(1/2)设给定有穷自动机 M=(Q,自动机转化为正规文法(1/2),设给定,有穷自动机 M=(Q,f,q0,Z,)，,按照下述方法可,以从 M 构造出相应的,左线性正规文法,G=(V,N,V,T,P,S),，,使得L(M)=L(G),(1)令,V,N,=Q,V,T,=,S=Z,(2)若f(S,a)=A,则,A,a|Sa,(3),若f(A,a)=B,则,B,Aa,(AS),注意:,若初态无入弧，则去掉该非终结符,终点开始，考虑入弧！,12,自动机转化为正规文法(1/2)设给定有穷自动机 M=(Q,习题7(1/4),7、构造下列正规式的相应的DFA,1(0|1)*101,解题步骤：,1.由正规式R构造NFA N,2.构造确定化后的DFA的状态矩阵,3.生成确定化后的DFA的状态转换图,4.化简DFA,13,习题7(1/4)7、构造下列正规式的相应的DFA13,习题7(2/4),由正规式构造NFA,构造确定化后的DFA的状态矩阵,Y,2,3,4,1,0,1,X,1,1,0,1,0,Q,1,0,A,X,0,1,2,B,0,1,2,0,2,3,0,2,C,0,2,3,0,2,3,0,2,4,D,0,2,0,2,3,0,2,E,0,2,4,0,2,3,Y,0,2,F,0,2,3,Y,0,2,3,0,2,4,14,习题7(2/4)由正规式构造NFAY234101X11010,生成确定化后的DFA的状态转换图,B,F,D,E,0,1,0,C,1,1,0,0,A,1,0,1,习题7(3/4),1,15,生成确定化后的DFA的状态转换图BFDE010C1100A,化简DFA,A,B,l,l,l,F,E,C,0,0,l,0,l,B,F,D,E,0,1,C,1,1,1,0,0,A,1,0,1,0,0,首先,M,的状态分成两组：终态组,F,，非终态组,A,B,C,D,E,考察,A,B,C,D,E,，由于,A,B,C,D,E,1,属于,B,C,F,它既不包含在,A,B,C,D,E,中也不包含在,F,之中，因此，应把,A,B,C,D,E,一分为二。因为状态 E 经 1 弧到达状态 F，而状态A,、B,C,D,经 1 弧都到达 B,C，因此，应把 E 分出来，形成,A,B,C,D、E、F,。,A,B,C,D,0,属于,D,E,它不含在任何划分中,，因为状态 C 经 0弧到达状态 E，而状态,A,B,D,经 0 弧都到达 D，因此，应把 C 分出来，形成,A,B,D、C、E、F,。,由于,A,B,D,1,=B,C,，它不包含在任何划分之中，因此，应把,A,B,D,一分为二。因为状态B,、D,经 1 弧都到达 C，经 0弧都到达 D因此，应把 A分出来，形成,A、B,D、C、E、F,。B,D无法再分。,至此，,整个分划含有四组：,A、B,D、C、E、F,。每个组都不可再分。,习题7(4/4),16,化简DFAABlllFEC00l0lBFDE01C11100,习题8(1/3),8、给出下面正规表达式,(1)以01结尾的二进制数串;,(2)能被5整除的十进制整数;,(3)包含奇数个1或者奇数个0的二进制数串;,(7)不包含子串abb的由a和b组成的符号串的全体。,17,习题8(1/3)8、给出下面正规表达式17,习题8(2/3),解：,(1)末两位是01，其他位为0、1组成的任意的字符串。,(a|b)*表示a、b组成的任意字符串。,所以正规表达式为(0|1)*01。,(2),若是一位数，为0或5,若是多于一位的数，为,(1|2|3|9)(0|1|2|9),*,(0|5),所以正规表达式为(1|2|3|9)(0|1|2|9),*,(0|5)|0|5,18,习题8(2/3)解：18,习题8(3/3),(3) 奇数个1：0*1(0|10*1)*,奇数个0：1*0(1|01*0)*,所以正则表达式为,0*1(0|10*1)*| 1*0(1|01*0)*,(7)ab后只能跟a,所以可以是ab、a组成的任意符号串，即(a|ab)*。,又若以b开始，所以正则表达式为,b* (a|ab)*。,19,习题8(3/3)(3) 奇数个1：0*1(0|10*1)*1,习题9(1/3),9、对下面的情况给出DFA以及正规表达式。,(1)0，1上的含有子串010的所有串。,解：首先必须含有010，然后首尾为0、1组成的任意字符串，所以正规式为(0|1),*,010(0|1),*,。,X,1,5,0,1,0,Y,2,3,4,6,0,0,1,1,20,习题9(1/3)9、对下面的情况给出DFA以及正规表达式。X,习题9(2/3),Q,0,1,A,X,5,1,5,1,2,5,1,B,5,1,2,5,1,2,5,1,3,C,5,1,5,1,2,5,1,D,5,1,3,5,1,2,4,6,Y,5,1,E,5,1,2,4,6,Y,5,1,2,6,Y,5,1,3,6,Y,F,5,1,2,6,Y,5,1,2,6,Y,5,1,3,6,Y,G,5,1,3,6,Y,5,1,2,4,6,Y,5,1,6,Y,H,5,1,6,Y,5,1,6,Y,5,1,6,Y,B,H,C,0,1,D,1,1,0,0,A,0,0,1,G,E,F,1,1,1,0,0,0,1,化简后的DFA：,B,A,0,E,D,0,1,0,0,1,1,1,21,习题9(2/3)Q01AX,5,15,1,25,习题9(3/3),(2),0，1上不含子串010的所有串。,解：1,*,(0|111,*,),*,1,*,X,1,3,Y,4,2,5,6,1,1,6,6,1,0,1,1,A,C,B,E,G,D,F,H,1,0,0,0,0,0,0,0,1,1,1,1,1,1,A,B,D,0,1,1,1,0,化简后的DFA,DFA,NFA,22,习题9(3/3)(2) 0，1上不含子串010的所有串。,习题12(1/3),12、将图3.18的(a)和(b)分别确定化和最少化。,a,b,a,a,0,1,5,0,4,2,a,3,b,a,1,a,b,a,a,a,b,b,b,b,(b),(a),23,习题12(1/3)12、将图3.18的(a)和(b)分别确定,习题12(2/3),a,b,a,a,0,1,(a),Q,a,b,A,0,0,1,1,B,0,1,0,1,1,C,1,0,a,b,a,b,a,C,B,A,b,a,a,A,B,24,习题12(2/3)a,baa01(a)QabA00,5,0,4,2,a,3,b,a,1,a,b,a,a,a,b,b,b,b,(b),已经是确定化，对其最小化。,1:0,1,2,3,4,5,0,1,a,=0,1,0,1,b,=2,4,2,3,4,5,a,=,1,3,0,5,2:0,1,2,4,3,5,2,4,b,=3,5,3,5,b,=2,4,b,a,a,0,2,b,b,3,a,习题12(3/3),25,5042a3ba1abaaabbbb(b)已经是确定化，对其,习题14(1/2),14、构造DFA,接收,0，1,上所有满足每个1都有0直接跟在后面的字符串。,解：正规表达式为,(10|0)*,26,习题14(1/2)14、构造DFA,接收0，1上所有满足,(10|0)*,X,Y,1,0,1,2,0,Q,0,1,A,X,1,Y,1,Y,2,B,1,Y,1,Y,2,C,2,1,Y,0,1,0,1,0,A,B,C,1,0,0,A,C,习题14(2/2),27,(10|0)*XY10120Q01AX,1,Y,习题15(1/3),15、给定右线性文法G：,S0S|1S|1A|0B,A1C|1,B0C|0,C0C|1C|1|0,求出,一个与G等价的左线性文法。,28,习题15(1/3)15、给定右线性文法G： 28,习题15(2/3),解：与文法G等价的自动机,M=(S,A,B,C,D,0,1,f,S,D),f(S,0)=S,B f(S,1)=S,A f(A,1)=C,D,f(B,0)=C,D f(C,0)=C,D f(C,1)=C,D,S,A,1,0,1,B,0,0,1,1,0,0,D,C,0,1,1,29,习题15(2/3)解：与文法G等价的自动机M=(S,A,B,习题15(3/3),与文法G等价的左线性文法,G,L,=(S,A,B,C,D,0,1,f,D),DA1|B0|C0|C1,CA1|B0|C0|C1,B0|S0,A1|S1,S0|1|S0|S1,30,习题15(3/3)与文法G等价的左线性文法GL=(S,A,习题20(1/3),20、假定有正规定义式,A,0,a|b,A,1,A,0,A,0,A,n,A,n-1,A,n-1,考虑词形A,n,(1)把A,n,中所有简名都换掉，最终所得的正规式的长度是多少；,(2)字集A,n,的元素是什么？把它们非形式地表示成n的函数；,(3)证明识别A,n,的DFA只需要用2n+1个状态就足够了。,31,习题20(1/3)20、假定有正规定义式31,习题20(2/3),解,:,(1)A,n,A,n-1,A,n-1,A,n-2,A,n-2,A,n-2,A,n-2,A,n-3,A,n-3,A,n-3,A,n-3,A,n-3,A,n-3,A,n-3,A,n-3,即 ，所以长度为2,n,。,(2)f(n)=,32,习题20(2/3)解:32,习题20(3/3),(3)用归纳法证明。,当n=0时，只需要1个状态，即,假设当n=k时成立，需要2k+1个状态,；,A,k+1,= (a|b)(a|b),S,a,b,S,A,B,C,a,a,b,b,.,第2k+1个状态,D,E,a,a,b,b,所以A,k+1,需要2(k+1)+1个状态，即n=k+1,时成立。综上所述，识别A,n,的DFA只需要用,2n+1个状态。,33,习题20(3/3)(3)用归纳法证明。SabSABCaabb,补充题,构造a,b上的含有偶数个a且奇数个b的,正规文法。,解：左线性文法,G,L,=(S,A,B,C,0,1,f,S),S识别偶数个a,偶数个b; A识别奇数个a,偶数个b;,B识别奇数个a,奇数个b; C识别偶数个a,奇数个b.,S,a,A,a,b,b,C,B,a,a,b,b,S,aA|bC|,AaS|bB,BaC|bA,CaB|bS,34,补充题构造a,b上的含有偶数个a且奇数个b的SaAabb,语法分析自上而下分析(1/5),自上而下分析法,确定的自上而下分析法,非确定的自上而下分析法(带回溯的自上而下分析法),递归下降分析法,预测分析法,35,语法分析自上而下分析(1/5)自上而下分析法确定的自上而,语法分析自上而下分析(2/5),LL(1),文法要求,：,（1）文法不含左递归。,（2）对文法中的每一个非终极符 A，,若 A 1|2|.|n，,则 FIRST（i）,FIRST（j）=,（3）,对文法中的每一个非终极符 A，若它存在某个候选首符集包含 ，,则 FIRST（A）,FOLLOW（A）=,左递归的消除：,PP,| 改为：,P,P,P,P|,FIRST集：,FIRST(,)= a |,a, a V,T,若,， FIRST(,),FOLLOW集：,FOLLOW(A)=a |S,.,Aa.，aV,T,若S,.,A，则规定 #FOLLOW（A）,*,*,非LL(1)文法改写为LL(1)文法：,消除左递归和反复提取公共左因子。,提取公共左因子,： A,1|,2|.|,n|,1|,2|.|,m,修改成：,A ,A,|,1|,2|.|,m,A,1|,2|.|,n,36,语法分析自上而下分析(2/5)LL(1)文法要求：左递归,语法分析自上而下分析(3/5),递归下降分析程序的构造：,当遇到终结符 a 时,，则编写语句if (当前读到的输入符号=a) 读入下一个输入符号。,当遇到非终结符 A 时,，则编写语句调用 A.,当遇到 A, 规则时,，则编写语句,if (当前读到的输入符号,FOLLOW(A) ERROR。,当某个非终结符的规则有多个候选式时,，按LL(1)文法的条件唯一现在一个候选式进行推导。,37,语法分析自上而下分析(3/5)递归下降分析程序的构造：3,实验二：预测分析算法的设计与实现,预测分析器,预测分析表,分析栈,总控程序,a,1,a,2,a,i,a,n,$,X,$,Tj,分析栈Sk,总控程序,预测分析表,输出,38,实验二：预测分析算法的设计与实现预测分析器a1a2aia,预测分析表的构造,1、构造文法 G 的每一个非终结符的FIRST集和FOLLOW集,2、构造分析表 MA，a,（1）对文法G的每个规则A，执行第二步和第三步；,（2）对每个终极符aFIRST(）,则置MA,a=A,；,（3）若FIRST(）,则对任何bFOLLOW（A）, 则置MA,bA；,（4）把所有无定义的 MA,a 标上“出错标志”,(表中用空格表示),。,39,预测分析表的构造1、构造文法 G 的每一个非终结符的FIRS,FIRST集的构造,若XV,T,，则 FIRST(X)=X。,若XV,N,，且有规则X,a，aV,T,，则aFIRST(X)。,若XV,N,，且有规则X,，则FIRST(X)中。,若有规则XY,1,Y,2,Y,n,，对任意的i(1,i,n)，当Y,1,Y,2,Y,i-1,都是非终极符且Y,1,Y,2,Y,i-1,=(,即对任何j(1,j,i-1)，FIRST(Y,J,)都含有,)，则把 FIRST(Y,i,)中的所有非-元素加到 FIRST(X)中；特别地，若Y,1,Y,2,Y,n,=(即所有的FIRST(Y,j,)中均含有，1,j,n)，则FIRST（X）。,反复使用上面的规则，直到每个FIRST集不再增大为止,40,FIRST集的构造若XVT，则 FIRST(X)=X。,FOLLOW集的构造,(1)对文法的开始符号 S，置#于FOLOOW（S）中；,(2)若,AB,是一个规则，则把,FIRST(,),-加到FOLLOW(B)中；,(3)若,AB,是一个规则，或,AB, 是一个规则，而 =,，即FIRST(,),则把FOLLOW(A)加至FOLLOW(B)中。,(4)反复使用上面的规则，直到每个非终结符的FOLLOW集 不再增大为止。,41,FOLLOW集的构造(1)对文法的开始符号 S，置#于F,总控程序,42,总控程序42,预测分析的过程,若X=a=#,，则宣布分析成功；,若X=a,#,，则将栈顶符号 X（终极符）弹出，让 IP 指针指向下一个输入符号；,若 X 是一个非终极符,，则查看分析表 M。如果分析表的 MA,a 中是一条产生式，则先将栈顶符号 X（非终极符）弹出，然后把该产生式右端符号串按,反序,（从右到左）压入栈中（串不入栈）。,43,预测分析的过程若X=a=#，则宣布分析成功；43,习题1(1/4),1、考虑下面文法G1：,Sa|(T),TT,S|S,（1）,消去G1的左递归,，然后对每个非终结符写出不带回溯的递归子程序。,（2）经过改写的文法是否是LL（1）的？给出它的预测分析表。,44,习题1(1/4)1、考虑下面文法G1：44,习题1(2/4),解：（1）消去G1的左递归,：Sa|(T),TST,T ,ST|,递归子程序：,PROCEDURE S;,IF SYM=a THEN ADVANCE,ELSE IF SYM= THEN ADVANCE,ELSE IF SYM= ( THEN,BEGIN,ADVANCE,T;,IF SYM= ) THEN ADVANCE,ELSE ERROR,END,ELSE ERROR;,PROCEDURE T;,BEGIN,S;T,END;,PROCEDURE T;,IF SYM= , THEN,BEGIN,ADVANCE,S;T,END;,ELSE,IF SYM) THEN,ERROR,判断输入符号是否,属于FOLLOW集,45,习题1(2/4)解：（1）消去G1的左递归：Sa|(T,习题1(3/4),（2）,FIRST(a)=a FIRST()= FIRST(T)= ( ,FIRST(,ST)=, FIRST()=,FIRST(S)= a,( FOLLOW(S)= #, , , , ) ,FIRST(T)= a,( FOLLOW(T)= ) ,FIRST(T)= , FOLLOW(T)= ) ,FIRST(a)FIRST(),FIRST(T)=,FIRST(,ST) ,FIRST()= ,FIRST(T) FOLLOW(T)= ,所以改写后的文法是,LL（1）,文法。,46,习题1(3/4)（2）FIRST(a)=a FIRS,习题1(4/4),预测分析表,如下：,47,习题1(4/4)预测分析表如下：47,习题2(1/6),2、对下面的文法G：,ETE,E+E|,TFT,TT|,FPF,F*F|,P(E)|a|b|,(1)计算这个文法的每个非终结符的FIRST和FOLLOW。,(2)证明这个文法是LL(1)的。,(3)构造它的预测分析表。,(4)构造它的递归下降分析程序。,48,习题2(1/6)2、对下面的文法G：48,习题2(2/6),解,：,(1)FIRST和FOLLOW集如下表,：,49,习题2(2/6)解：49,习题2(3/6),(2),FIRST(+E)FIRST()= + =,FIRST(T) FIRST()= (,a,b, =,FIRST(*F)FIRST()= * =,FIRST(E)FIRST(a) FIRST(b) FIRST()= ( a b =,FIRST(E) FOLLOW(E)= ,FIRST(T) FOLLOW(T)= ,FIRST(F) FOLLOW(F)= ,所以该文法是LL(1)文法。,50,习题2(3/6)(2)FIRST(+E)FIRST()=,习题2(4/6),(3)预测分析表为：,51,习题2(4/6)(3)预测分析表为：51,习题2(5/6),(4)递归下降分析程序为：,PROCEDURE E;,BEGIN,T;E,END;,PROCEDURE T;,BEGIN,F;T,END;,PROCEDURE E;,IF SYM=+ THEN,BEGIN,ADVANCE;,E,END;,ELSE,IF SYM) AND SYM# THEN,ERROR,PROCEDURE F;,BEGIN,P;F,END;,PROCEDURE T;,IF SYM=a OR SYM=b OR SYM= OR SYM=( THEN,BEGIN,ADVANCE;,T,END;,ELSE IF SYM) AND SYM+ AND SYM#,THEN,ERROR,52,习题2(5/6)(4)递归下降分析程序为：52,习题2(6/6),PROCEDURE P;,IF SYM=( THEN,BEGIN,ADVANCE;,E;,IF SYM!=) THEN,ADVANCE;,ELSE ERROR,END,ELSE IF SYM=a OR SYM=b OR SYM= THEN,ADVANCE;,ELSE ERROR,PROCEDURE F;,IF SYM=* THEN,BEGIN,ADVANCE;,F;,END,ELSE IF SYM( AND SYMa AND SYMb AND SYM AND SYM+ SYM) AND SYM# THEN,ERROR,53,习题2(6/6)PROCEDURE P;PROCEDURE,习题3(1/3),3、下面文法那些是LL(1)文法？,(1)S Abc A a| Bb|,(2)S Ab A a|B| Bb|,(3)S ABBA A a | Bb|,(4)S aSe|B B bBe |C CcCe|d,54,习题3(1/3)3、下面文法那些是LL(1)文法？54,习题3(2/3),解：,(1)文法无左递归,FIRST(a)FIRST()= a =,FIRST(b)FIRST()= b =,FIRST(A)FOLLOW(A)= a, b=,FIRST(B)FOLLOW(B)= b, =,所以该文法是LL(1)文法。,(2)文法无左递归,FIRST(a)FIRST(B)FIRST()= ab, ,所以该文法不是LL(1)文法。,55,习题3(2/3)解：55,习题3(3/3),(3)文法无左递归,FIRST(a)FIRST()= a =,FIRST(b)FIRST()= b =,FIRST(A)FOLLOW(A)= a, a,b, #,所以该文法不是LL(1)文法。,(4)文法无左递归,FIRST(aSe)FIRST(B)= a b,=,FIRST(bBe)FIRST(C)= b c,d=,FIRST(cCe)FIRST(d)= c d=,所以该文法是LL(1)文法。,56,习题3(3/3)(3)文法无左递归56,习题4(1/3),4、对下面文法：,Expr_Expr,Expr(Expr)| Var ExprTail,ExprTail_ Expr|,Varid VarTail,VarTail(Expr)| ,(1),构造LL（1）分析表,(2)给出对句子id_ _id(id) 的分析过程,57,习题4(1/3)4、对下面文法：57,习题4(2/3),解：,(1)FIRST集和FOLLOW集如下表：,LL(1)分析表为：,58,习题4(2/3)解：LL(1)分析表为：58,习题4(3/3),(2) 步骤 符号栈 输入串 所用产生式,反序压入栈,59,习题4(3/3)(2) 步骤 符号栈,习题5(1/5),5、把下面文法改写为LL(1)的,：,DeclistDeclist；Decl|Decl,DeclIdList:Type,IdListIdList,id|id,TypeScalarType|array(ScalarTypeList) of Type,ScalarTypeid|Bound.Bound,BoundSign IntLiteral|id,Sign+|-|,ScalarTypeListScalarTypeList,ScalarType|ScalarType,60,习题5(1/5)5、把下面文法改写为LL(1)的：60,习题5(2/5),解：消除左递归：,DeclistDeclDeclist,Declist;DeclDeclist|,DeclIdList:Type,IdListidIdList,IdList,idIdList|,TypeScalarType|array(ScalarTypeList) of Type,ScalarTypeid|Bound.Bound,BoundSign IntLiteral|id,Sign+|-|,ScalarTypeListScalarTypeScalarTypeList,ScalarTypeList,ScalarTypeScalarTypeList|,61,习题5(2/5)解：消除左递归：61,习题5(3/5),判断是否为LL(1)文法：,FIRST(;DeclDeclist)FIRST(,) =;=,FIRST(,idIdList )FIRST() =,=,FIRST(ScalarType)FIRST(array(ScalarTypeList) of Type)=id,+,-,IntLiteralarray=,FIRST(id)FIRST(Bound.Bound) =idid,+,-, IntLiteral,FIRST(Sign IntLiteral)FIRST(id) =+,-, IntLiteralid=,FIRST(+ )FIRST(-)FIRST()=+-=,FIRST(,ScalarTypeScalarTypeList)FIRST() =,=,FIRST(Declist) FOLLOW(Declist)=;,#=,62,习题5(3/5)判断是否为LL(1)文法：62,习题5(4/5),FIRST(IdList) FOLLOW(IdList)=,:=,FIRST(Sign) FOLLOW(Sign)=+,-,IntLiteral=,FIRST(ScalarTypeList) FOLLOW(ScalarTypeList)=,)=,所以该文法不是LL(1)文法。,不是LL(1)文法是由,ScalarTypeid|Bound.Bound,存在公共左因子id,引起的，提取左因子得：,63,习题5(4/5)FIRST(IdList) FOLLOW,习题5(5/5),DeclistDeclDeclist,Declist;DeclDeclist|,DeclIdList:Type,IdListidIdList,IdList,idIdList|,TypeScalarType|array(ScalarTypeList) of Type,ScalarTypeidScalarType | Sign IntLiteral.Bound,ScalarType|.Bound,BoundSign IntLiteral|id,Sign+|-|,ScalarTypeListScalarTypeScalarTypeList,ScalarTypeList,ScalarTypeScalarTypeList|,该文法是LL(1)文法。,64,习题5(5/5)DeclistDeclDeclist64,问题？,65,问题？65,