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

《第三四章习题课编译原理课件.ppt》由会员分享，可在线阅读，更多相关《第三四章习题课编译原理课件.ppt（65页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第三、四章习题第三、四章习题P64：7,8,9,12,14,15,20,补充题补充题P81：1,2,3,4,5词法分析词法分析正规式自动机正规文法正规式正规式正规文法正规文法NFADFA状态最小状态最小DFA词法词法分析器分析器分分裂裂法法转转换换规规则则子子集集法法分分划划法法2正规式与正规文法的转化正规式与正规文法的转化:令令 VT=对任意正规式对任意正规式 R 选择一个非终结符选择一个非终结符 Z 生成规则生成规则ZR，并令，并令 SZ；若若 a 和和 b 都是正规式，对形如都是正规式，对形如 Aab的规则转换成的规则转换成 AaB 和和 Bb；在已转换的文法中，将形如在已转换的文法中，

2、将形如 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 XY YR R(2)分析分析 R 的语法结构，用如下规则对的语法结构，用如下规则对 R 中的每个基本符号构造中的每个基本符号构造 NFA。R，构造构造 NFA 如图：如图：R，构造构造 NFA 如图：如图：X XY YX XY Y Ra(a)，构造，构造 NFA 如图：如图：X XY Ya4正规式转化为正规式转化为NFA(2/2)若若 R 是是复合正规式，则按下图的转换规则对复合正规式，则按下图的转换规则对 R 进行分裂和加

4、进行分裂和加进新结，直至每个边上只留下一个符号（或进新结，直至每个边上只留下一个符号（或 ）为止。）为止。A AB Br1r2A AB Br1C Cr2代换为A AB Br1|r2A AB Br1r2代换为A AB Br1*A AB B C C 代换为r1整个分裂过程中，所有新结点均采用不同的名字，保留整个分裂过程中，所有新结点均采用不同的名字，保留 X，Y 为全为全图唯一初态结点和终态结点图唯一初态结点和终态结点5NFA确定化为确定化为DFA 首先将从首先将从初态初态 S 出发经过任意条出发经过任意条 弧所能到达的状态弧所能到达的状态所组成的集合作为所组成的集合作为 M 的初态的初态 S，然

5、后从然后从 S 出发，经出发，经过对输入符号过对输入符号 a 的状态转移所能到达的状态的状态转移所能到达的状态(包括包括读输入符号之前或之后所有可能的读输入符号之前或之后所有可能的 转移所能到达的转移所能到达的状态状态)所组成的集合作为所组成的集合作为 M 的的新状态新状态，如此重复，直，如此重复，直到不再有新的状态出现为止。到不再有新的状态出现为止。从从从从 NFA N=(Q,NFA N=(Q,F,S,Z),F,S,Z)构造等价的构造等价的构造等价的构造等价的DFA DFA M=(Q,M=(Q,F,S,Z),F,S,Z)的方法的方法的方法的方法6DFA的化简的化简n将将 DFA M 的状态集

6、的状态集 Q 分成两个子集：分成两个子集：终态集终态集 F 和非终和非终态集态集 F，形成初始分划，形成初始分划 。n对对 建立新的建立新的分划分划 new。对。对 的每个状态子集的每个状态子集 G 进进行如下变换行如下变换：n把把 G 分划成新的子集，使得分划成新的子集，使得 G 的两个状态的两个状态 s 和和 t 属属于同一子集，当且仅当对于同一子集，当且仅当对任何输入符号任何输入符号 a，状态，状态 s 和和 t 转换到的状态都属于转换到的状态都属于 的同一子集的同一子集。n用用 G 分划出的所有新子集替换分划出的所有新子集替换 G，形成新的分划，形成新的分划 new。n如果如果 new

7、，则执行第，则执行第（4）步；否则令）步；否则令new，重复第（，重复第（2）步。）步。n分划结束，对分划中的每个状态子集，选出一个状态作代分划结束，对分划中的每个状态子集，选出一个状态作代表，而删去其它一切等价的状态，并把表，而删去其它一切等价的状态，并把射向其余状态的射向其余状态的箭弧都改为射向作为箭弧都改为射向作为“代表代表”的状态的状态。71)增加新初态增加新初态 X X，与所有原初态用与所有原初态用相连，相连，增加新终态增加新终态 Y Y，与所有原终态用与所有原终态用相连，相连，从而构成一个新的从而构成一个新的 FA M，它只有一个初态它只有一个初态 X 和一个终态和一个终态 Y。2

8、)在在X 与与 Y 之间进行弧合并：之间进行弧合并：ACBr1r2ABr1r2r2ACBr1r3ABr1r2ABr1|r2ABr1r2*r33)在在X 和和 Y之间的表达式即为所求的正规式之间的表达式即为所求的正规式 R。代之以代之以代之以代之以代之以代之以代之以代之以代之以代之以代之以代之以自动机转化为正规式自动机转化为正规式8正规文法转化为自动机正规文法转化为自动机(1/2)设给定一个设给定一个右线性正规文法右线性正规文法 G=(VN,VT,P,S)，则相应的，则相应的有穷自动机有穷自动机 M=(Q,f,q0,Z)（1）将）将VN中的每一个非终结符视作中的每一个非终结符视作 M 中的一个状

9、态，中的一个状态，并增加一并增加一个个新终态新终态 D，且，且 D VN，令令 Q=VN D,Z=D,=VT,q0=S（2）对）对 AaB（A,B VN,a VT ），令），令f(A,a)=B。构造弧构造弧（3）对）对 Aa（A VN,a VT ），令），令f(A,a)=D。构造弧构造弧ABaADa9正规文法转化为自动机正规文法转化为自动机(2/2)设给定一个设给定一个左线性正规文法左线性正规文法 G=(VN,VT,P,S)，则相应的，则相应的有穷自动机有穷自动机 M=(Q,f,q0,Z)（1）将）将VN中的每一个非终结符视作中的每一个非终结符视作 M 中的一个状态，中的一个状态，并增加一并增

10、加一个个初始状态初始状态 q0，且，且 q0 VN，令令 Q=VN q0,Z=S,=VT(将文法将文法G的开始符号的开始符号S看成终态看成终态)（2）对）对 ABa（A,B VN,a VT ）令）令f(B,a)=A。构造弧构造弧（3）对）对 Aa（A VN,a VT ），令），令f(q0,a)=A。构造弧构造弧BAaq0Aa10自动机转化为正规文法自动机转化为正规文法(1/2)设给定设给定有穷自动机有穷自动机 M=(Q,f,q0,Z)，按照下述方法可按照下述方法可以从以从 M 构造出相应的构造出相应的右线性正规文法右线性正规文法 G=(VN,VT,P,S)，使得使得L(M)=L(G)(1)令令

11、 VN=Q,VT=,S=q0(2)若若f(A,a)=B且且B Z时，时，则将规则则将规则 AaB 加到加到P中。中。(3)若若f(A,a)=B且且B Z时，则将规则时，则将规则AaB a或或 AaB,B 加到加到P中。中。(4)若文法的开始符号若文法的开始符号 S 是一个终态，是一个终态，则将规则则将规则S 加到加到P中。中。ABa注意:若终态无出弧，若终态无出弧，则去掉该非终结符则去掉该非终结符起点开始，考虑出弧！11自动机转化为正规文法自动机转化为正规文法(1/2)设给定设给定有穷自动机有穷自动机 M=(Q,f,q0,Z)，按照下述方法可按照下述方法可以从以从 M 构造出相应的构造出相应的

12、左线性正规文法左线性正规文法 G=(VN,VT,P,S)，使得使得L(M)=L(G)(1)令令 VN=Q,VT=,S=Z(2)若若f(S,a)=A,则则Aa|Sa(3)若若f(A,a)=B,则则BAa(AS)注意:若初态无入弧，若初态无入弧，则去掉该非终结符则去掉该非终结符终点开始，考虑入弧！12习题习题7(1/4)7、构造下列正规式的相应的、构造下列正规式的相应的DFA1(0|1)*101解题步骤：解题步骤：1.由正规式由正规式R构造构造NFA N2.构造确定化后的构造确定化后的DFA的状态矩阵的状态矩阵3.生成确定化后的生成确定化后的DFA的状态转换图的状态转换图4.化简化简DFA13习题

13、习题7(2/4)n由正规式构造由正规式构造NFAn构造确定化后的构造确定化后的DFA的状态矩阵的状态矩阵Y Y2 23 34 4101X X1 110 010 Q10AX0,1,2B0,1,20,2,30,2C0,2,30,2,30,2,4D0,20,2,30,2E0,2,40,2,3,Y0,2F0,2,3,Y0,2,30,2,414n 生成确定化后的生成确定化后的DFA的状态转换图的状态转换图B BF FD DE E010C C1100A A101习题习题7(3/4)115n化简化简DFADFAA AB BlllF FE EC C00l0lB BF FD DE E01C C11100A A1

14、0100n首先首先 M的状态分成两组：终态组F，非终态组A,B,C,D,En考察考察A,B,C,D,E，由于A,B,C,D,E1 属于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。nA,B,C,D0 属于D,E,它不含在任何划分中它不含在任何划分中，因为状态 C 经 0弧到达状态 E，而状态A,B,D经 0 弧都到达 D，因此，应把 C 分出来，形成A,B,D、C、E、F。n由于A,B,D1=B,C，它不包

15、含在任何划分之中，因此，应把A,B,D一分为二。因为状态B、D经 1 弧都到达 C，经 0弧都到达 D因此，应把 A分出来，形成A、B,D、C、E、F。B,D无法再分。n至此，至此，整个分划含有四组：A、B,D、C、E、F。每个组都不可再分。习题习题7(4/4)16习题习题8(1/3)8、给出下面正规表达式、给出下面正规表达式(1)以以01结尾的二进制数串结尾的二进制数串;(2)能被能被5整除的十进制整数整除的十进制整数;(3)包含奇数个包含奇数个1或者奇数个或者奇数个0的二进制数的二进制数串串;(7)不包含子串不包含子串abb的由的由a和和b组成的符号串组成的符号串的全体。的全体。17习题习

16、题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|518习题习题8(3/3)(3)奇数个奇数个1：0*1(0|10*1)*奇数个奇数个0：1*0(1|01*0)*所以正则表达式为所以正则表达式为0*1(0|1

17、0*1)*|1*0(1|01*0)*(7)ab后只能跟后只能跟a,所以可以是所以可以是ab、a组成的任意符号串，组成的任意符号串，即即(a|ab)*。又若以又若以b开始，所以正则表达式为开始，所以正则表达式为b*(a|ab)*。19习题习题9(1/3)9、对下面的情况给出、对下面的情况给出DFA以及正规表达式。以及正规表达式。(1)0，1上的含有子串上的含有子串010的所有串。的所有串。解：首先必须含有解：首先必须含有010，然后首尾为，然后首尾为0、1组成的组成的任意字符串，所以正规式为任意字符串，所以正规式为(0|1)*010(0|1)*。X X1 15 5010Y Y2 23 34 46

18、 6 0011 20习题习题9(2/3)Q01AX,5,15,1,25,1B5,1,25,1,25,1,3C5,15,1,25,1D5,1,35,1,2,4,6,Y5,1E5,1,2,4,6,Y5,1,2,6,Y5,1,3,6,YF5,1,2,6,Y5,1,2,6,Y5,1,3,6,YG5,1,3,6,Y5,1,2,4,6,Y5,1,6,YH5,1,6,Y5,1,6,Y5,1,6,YB BH HC C01D D1100A A001G GE EF F111000,1化简后的化简后的DFA：B BA A0E ED D0,10011121习题习题9(3/3)(2)0，1上不含子串上不含子串010的所

19、有串。的所有串。解：解：1*(0|111*)*1*X X1 13 3 Y Y4 42 25 56 6 116 66 610 11A AC CB BE EG GD DF FH H10000000111111A AB BD D01110化简后的化简后的DFADFANFA22习题习题12(1/3)12、将图、将图3.18的的(a)和和(b)分别确定化和最分别确定化和最少化。少化。a,baa0 01 15 50 04 42 2a3 3ba1 1abaaabbbb(b)(b)(a)23习题习题12(2/3)a,baa0 01 1(a)(a)QabA00,11B0,10,11C10ababaC CB BA

20、 AbaaA AB B245 50 04 42 2a3 3ba1 1abaaabbbb(b)(b)已经是确定化，对其最小化。已经是确定化，对其最小化。1:0,1,2,3,4,50,1a=0,10,1b=2,42,3,4,5a=1,3,0,52:0,1,2,4,3,52,4b=3,53,5b=2,4baa0 02 2bb3 3a习题习题12(3/3)25习题习题14(1/2)1414、构造、构造DFA,DFA,接收接收0，1上所有满足每个上所有满足每个1 1都有都有0 0直接跟在后面的字符串。直接跟在后面的字符串。解：正规表达式为解：正规表达式为(10|0)*26(10|0)*X XY Y1 1

21、012 2 0Q01AX,1,Y1,Y2B1,Y1,Y2C21,Y01010A AB BC C100A AC C习题习题14(2/2)27习题习题15(1/3)15、给定右线性文法、给定右线性文法G：S0S|1S|1A|0B A1C|1 B0C|0 C0C|1C|1|0求出求出一个与一个与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 SA A10,1B

22、 B00,1100D DC C0,1129习题习题15(3/3)与文法与文法G等价的左线性文法等价的左线性文法GL=(S,A,B,C,D,0,1,f,D)DA1|B0|C0|C1 CA1|B0|C0|C1 B0|S0 A1|S1 S0|1|S0|S130习题习题20(1/3)20、假定有正规定义式、假定有正规定义式 A0a|b A1A0A0 AnAn-1An-1考虑词形考虑词形An(1)把把An中所有简名都换掉，最终所得的正规式的长度是中所有简名都换掉，最终所得的正规式的长度是多少；多少；(2)字集字集An的元素是什么？把它们非形式地表示成的元素是什么？把它们非形式地表示成n的函的函数；数；(

23、3)证明识别证明识别An的的DFA只需要用只需要用2n+1个状态就足够了。个状态就足够了。31习题习题20(2/3)解解:(1)AnAn-1An-1 An-2An-2An-2An-2 An-3An-3An-3An-3An-3An-3An-3An-3 即 ，所以长度为2n。(2)f(n)=32习题习题20(3/3)(3)用归纳法证明。用归纳法证明。当当n=0时，只需要时，只需要1个状态，即个状态，即假设当假设当n=k时成立，需要时成立，需要2k+1个状态个状态；Ak+1=(a|b)(a|b)S SabS SA AB BC Caabb.第第2k+1个状态个状态D DE Eaabb所以所以Ak+1需

24、要需要2(k+1)+1个状态，即个状态，即n=k+1时成立。综上所述，识别时成立。综上所述，识别An的的DFA只需要用只需要用2n+1个状态。个状态。33补充题补充题构造构造a,b上的含有偶数个上的含有偶数个a且奇数个且奇数个b的的正规文法。正规文法。解：左线性文法解：左线性文法GL=(S,A,B,C,0,1,f,S)S识别偶数个a,偶数个b;A识别奇数个a,偶数个b;B识别奇数个a,奇数个b;C识别偶数个a,奇数个b.S SaA AabbC CB BaabbSaA|bC|AaS|bBBaC|bACaB|bS34语法分析语法分析自上而下分析自上而下分析(1/5)自上而下分析法自上而下分析法确定

25、的自上而下分析法确定的自上而下分析法非确定的自上而下分析法非确定的自上而下分析法(带回溯的自上而下分析法带回溯的自上而下分析法)递归下降分析法递归下降分析法预测分析法预测分析法35语法分析语法分析自上而下分析自上而下分析(2/5)nLL(1)文法要求文法要求：（1）文法不含左递归。）文法不含左递归。（2）对文法中的每一个非终极符）对文法中的每一个非终极符 A，若若 A 1|2|.|n，则则 FIRST（i）FIRST（j）=（3）对文法中的每一个非终极符对文法中的每一个非终极符 A，若它存在某，若它存在某个候选首符集包含个候选首符集包含，则则 FIRST（A）FOLLOW（A）=左递归的消除：

26、左递归的消除：PP|改为：改为：PP P P|FIRST集：集：FIRST()=a|a,a VT 若若，FIRST()FOLLOW集：集：FOLLOW(A)=a|S.Aa.，aVT 若若S.A，则规定，则规定#FOLLOW（A）*非非LL(1)文法改写为文法改写为LL(1)文法：文法：消除左递归和反复提取公共左因子。消除左递归和反复提取公共左因子。提取公共左因子提取公共左因子：A 1|2|.|n|1|2|.|m 修改成：修改成：A A|1|2|.|m A 1|2|.|n36语法分析语法分析自上而下分析自上而下分析(3/5)n递归下降分析程序的构造：递归下降分析程序的构造：n当遇到终结符当遇到终

27、结符 a 时时，则编写语句，则编写语句if(当前读到的输入符号当前读到的输入符号=a)读入下一个输入符读入下一个输入符号。号。n当遇到非终结符当遇到非终结符 A 时时，则编写语句调用，则编写语句调用 A.n当遇到当遇到 A 规则时规则时，则编写语句，则编写语句if(当前读到的输入符号当前读到的输入符号 FOLLOW(A)ERROR。n当某个非终结符的规则有多个候选式时当某个非终结符的规则有多个候选式时，按，按LL(1)文法的条件唯一现在一个候选式进行推导。文法的条件唯一现在一个候选式进行推导。37实验二：预测分析算法的设计与实现实验二：预测分析算法的设计与实现预测分析器预测分析器n预测分析表预

28、测分析表n分析栈分析栈n总控程序总控程序a a1 1a a2 2 a ai i a an n$X X$TjTj分分析析栈栈SkSk总控程序总控程序预测分析表预测分析表输出38预测分析表的构造预测分析表的构造1、构造文法、构造文法 G 的每一个非终结符的的每一个非终结符的FIRST集和集和FOLLOW集集2、构造分析表、构造分析表 MA，a（1）对文法）对文法G的每个规则的每个规则A，执行第二步和第三步；，执行第二步和第三步；（2）对每个终极符）对每个终极符aFIRST(）,则置则置MA,a=A；（3）若）若FIRST(）,则对任何则对任何bFOLLOW（A）,则置则置MA,bA；（4）把所有无

29、定义的）把所有无定义的 MA,a 标上标上“出错标志出错标志”(表中用空格表示表中用空格表示)。39FIRST集的构造集的构造若若XVT，则，则 FIRST(X)=X。若若XVN，且有规则，且有规则Xa，aVT，则，则aFIRST(X)。若若XVN，且有规则，且有规则X，则，则FIRST(X)中。中。若有规则若有规则XY1Y2Yn，对任意的，对任意的i(1 i n)，当当Y1Y2Yi-1都是非终极符且都是非终极符且Y1Y2Yi-1=(即对任何即对任何j(1 j i-1)，FIRST(YJ)都含有都含有)，则把则把 FIRST(Yi)中的所有非中的所有非-元素加到元素加到 FIRST(X)中；中

30、；特别地，若特别地，若Y1Y2Yn=(即所有的即所有的FIRST(Yj)中均中均含有含有，1 j n)，则，则FIRST（X）。）。反复使用上面的规则，直到每个反复使用上面的规则，直到每个FIRST集不再增大为止集不再增大为止40FOLLOW集的构造集的构造(1)对文法的开始符号对文法的开始符号 S，置，置#于于FOLOOW（S）中；）中；(2)若若AB 是一个规则，则把是一个规则，则把FIRST()-加到加到FOLLOW(B)中；中；(3)若若AB 是一个规则，是一个规则，或或AB 是一个规则，而是一个规则，而 =，即，即FIRST(),则把则把FOLLOW(A)加至加至FOLLOW(B)中

31、。中。(4)反复使用上面的规则，直到每个非终结符的反复使用上面的规则，直到每个非终结符的FOLLOW集集 不再增大为止。不再增大为止。41总控程序总控程序42预测分析的过程预测分析的过程n若若X=a=#，则宣布分析成功；，则宣布分析成功；n若若X=a#，则将栈顶符号，则将栈顶符号 X（终极（终极符）弹出，让符）弹出，让 IP 指针指向下一个输入符指针指向下一个输入符号；号；n若若 X 是一个非终极符是一个非终极符，则查看分析表，则查看分析表 M。如果分析表的如果分析表的 MA,a 中是一条产生式，中是一条产生式，则先将栈顶符号则先将栈顶符号 X（非终极符）弹出，（非终极符）弹出，然后把该产生式

32、右端符号串按然后把该产生式右端符号串按反序反序（从（从右到左）压入栈中（右到左）压入栈中（串不入栈）。串不入栈）。43习题习题1(1/4)1、考虑下面文法、考虑下面文法G1：Sa|(T)TT,S|S（1）消去消去G1的左递归的左递归，然后对每个非终，然后对每个非终结符写出不带回溯的递归子程序。结符写出不带回溯的递归子程序。（2）经过改写的文法是否是）经过改写的文法是否是LL（1）的？）的？给出它的预测分析表。给出它的预测分析表。44习题习题1(2/4)解：（解：（1）消去）消去G1的左递归的左递归：Sa|(T)TST T,ST|递归子程序：递归子程序：PROCEDURE S;IF SYM=a

33、THEN ADVANCEELSE IF SYM=THEN ADVANCEELSE IF SYM=(THEN BEGIN ADVANCE T;IF SYM=)THEN ADVANCE ELSE ERROR ENDELSE ERROR;PROCEDURE T;BEGINS;TEND;PROCEDURE T;IF SYM=,THEN BEGIN ADVANCE S;T END;ELSE IF SYM)THEN ERROR判断输入符号是否判断输入符号是否属于属于FOLLOW集集45习题习题1(3/4)（2）FIRST(a)=a FIRST()=FIRST(T)=(FIRST(,ST)=,FIRST()

34、=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(4/4)预测分析表预测分析表如下：如下：47习题习题2(1/6)2、对下面的文法、对下面的文法G：ETE E+E|TFT TT|FPF F*F|P(E)|a|b|(1)计算这个文法的每个非终结符的计算这个文法的每个非终结符的FIRST和和FOLLOW。(2)证明这个

35、文法是证明这个文法是LL(1)的。的。(3)构造它的预测分析表。构造它的预测分析表。(4)构造它的递归下降分析程序。构造它的递归下降分析程序。48习题习题2(2/6)解解：(1)FIRST和和FOLLOW集如下表集如下表：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

36、(4/6)(3)预测分析表为：预测分析表为：51习题习题2(5/6)(4)递归下降分析程序为：PROCEDURE E;BEGIN T;EEND;PROCEDURE T;BEGIN F;TEND;PROCEDURE E;IF SYM=+THENBEGIN ADVANCE;EEND;ELSE IF SYM)AND SYM#THEN ERRORPROCEDURE F;BEGIN P;FEND;PROCEDURE T;IF SYM=a OR SYM=b OR SYM=OR SYM=(THENBEGIN ADVANCE;TEND;ELSE IF SYM)AND SYM+AND SYM#THEN ERRO

37、R52习题习题2(6/6)PROCEDURE P;IF SYM=(THENBEGIN ADVANCE;E;IF SYM!=)THEN ADVANCE;ELSE ERRORENDELSE IF SYM=a OR SYM=b OR SYM=THEN ADVANCE;ELSE ERRORPROCEDURE F;IF SYM=*THENBEGIN ADVANCE;F;ENDELSE IF SYM(AND SYMa AND SYMb AND SYM AND SYM+SYM)AND SYM#THEN ERROR53习题习题3(1/3)3、下面文法那些是、下面文法那些是LL(1)文法？文法？(1)S Abc

38、 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(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(3/3)(3)文法无左递归文法无左递归 FIRST(a)FIRST()=a =F

39、IRST(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习题习题4(1/3)4、对下面文法：、对下面文法：Expr_Expr Expr(Expr)|Var ExprTail ExprTail_ Expr|Varid VarTail VarTail(Expr)|(1)构造构造LL（1）分析表）分析表(2)给出对句子给出对句子id_

40、_id(id)的分析过程的分析过程57习题习题4(2/3)解：解：(1)FIRST集和集和FOLLOW集如下表：集如下表：LL(1)分析表为：分析表为：58习题习题4(3/3)(2)步骤步骤 符号栈符号栈 输入串输入串 所用产生式所用产生式反序压入栈反序压入栈59习题习题5(1/5)5、把下面文法改写为、把下面文法改写为LL(1)的的：DeclistDeclist；Decl|DeclDeclIdList:TypeIdListIdList,id|idTypeScalarType|array(ScalarTypeList)of TypeScalarTypeid|Bound.BoundBoundSi

41、gn IntLiteral|idSign+|-|ScalarTypeListScalarTypeList,ScalarType|ScalarType60习题习题5(2/5)解：消除左递归：解：消除左递归：DeclistDeclDeclistDeclist;DeclDeclist|DeclIdList:TypeIdListidIdListIdList,idIdList|TypeScalarType|array(ScalarTypeList)of TypeScalarTypeid|Bound.BoundBoundSign IntLiteral|idSign+|-|ScalarTypeListSca

42、larTypeScalarTypeListScalarTypeList,ScalarTypeScalarTypeList|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,+,-,IntLiteralFIRST(Sign IntLiteral)FIRST(

43、id)=+,-,IntLiteralid=FIRST(+)FIRST(-)FIRST()=+-=FIRST(,ScalarTypeScalarTypeList)FIRST()=,=FIRST(Declist)FOLLOW(Declist)=;,#=62习题习题5(4/5)FIRST(IdList)FOLLOW(IdList)=,:=FIRST(Sign)FOLLOW(Sign)=+,-,IntLiteral=FIRST(ScalarTypeList)FOLLOW(ScalarTypeList)=,)=所以该文法不是所以该文法不是LL(1)文法。文法。不是不是LL(1)文法是由文法是由Scala

44、rTypeid|Bound.Bound存在公共左因子存在公共左因子id引起的，提取左因子得：引起的，提取左因子得：63习题习题5(5/5)DeclistDeclDeclistDeclist;DeclDeclist|DeclIdList:TypeIdListidIdListIdList,idIdList|TypeScalarType|array(ScalarTypeList)of TypeScalarTypeidScalarType|Sign IntLiteral.BoundScalarType|.BoundBoundSign IntLiteral|idSign+|-|ScalarTypeListScalarTypeScalarTypeListScalarTypeList,ScalarTypeScalarTypeList|该文法是该文法是LL(1)文法。文法。64问题？