《习题课编译原理》PPT课件.ppt

第三、四章习题,P64：7,8,9,12,14,15,20,补充题 P81：1,2,3,4,5,2,词法分析,正规式,自动机,正规文法,3,正规式与正规文法的转化,: 令 VT = 对任意正规式 R 选择一个非终结符 Z 生成规则ZR，并令 SZ； 若 a 和 b 都是正规式，对形如 Aab的规则转换成 AaB 和 Bb； 在已转换的文法中，将形如 Aa*b 的规则进一步转换成 A aA | b； 不断利用上上面后两条规则进行转换，直到每条规则最多含有一个 终结符为止。,: 将每个非终结符表示成关于它的正规式方程，获得一个联立方程组。 依照求解规则： 若 x = x | (或x = x+)，则解为x = * 若 x = x | (或x = x+)，则解为x = * 以及正规式的分配率、交换率和结合率求关于文法开始符号的正规式 方程组的解。,4,正规式转化为NFA(1/2),(1)引进初始结点 X 和终止结点 Y，把 R 表示成拓广转换图。如图,(2)分析 R 的语法结构，用如下规则对 R 中的每个基本符号构造 NFA。 R，构造 NFA 如图： R，构造 NFA 如图：,Ra(a)，构造 NFA 如图：,5,正规式转化为NFA(2/2),若 R 是复合正规式，则按下图的转换规则对 R 进行分裂和加进新结，直至每个边上只留下一个符号（或 ）为止。,整个分裂过程中，所有新结点均采用不同的名字，保留 X，Y 为全图唯一初态结点和终态结点,6,NFA确定化为DFA,首先将从初态 S 出发经过任意条 弧所能到达的状态所组成的集合作为 M 的初态 S，然后从 S 出发，经过对输入符号 a 的状态转移所能到达的状态(包括读输入符号之前或之后所有可能的 转移所能到达的状态)所组成的集合作为 M 的新状态，如此重复，直到不再有新的状态出现为止。,从 NFA N=(Q,F,S,Z)构造等价的DFA M=(Q,F,S,Z)的方法,7,DFA的化简,将 DFA M 的状态集 Q 分成两个子集：终态集 F 和非终态集 F，形成初始分划 。 对 建立新的分划 new。对 的每个状态子集 G 进行如下变换： 把 G 分划成新的子集，使得 G 的两个状态 s 和 t 属于同一子集，当且仅当对任何输入符号 a，状态 s 和 t 转换到的状态都属于 的同一子集。 用 G 分划出的所有新子集替换 G，形成新的分划 new 。 如果 new，则执行第（4）步；否则令new，重复第（2）步。 分划结束，对分划中的每个状态子集，选出一个状态作代表，而删去其它一切等价的状态，并把射向其余状态的箭弧都改为射向作为“代表”的状态。,8,增加新初态 X，与所有原初态用相连， 增加新终态 Y，与所有原终态用相连， 从而构成一个新的 FA M， 它只有一个初态 X 和一个终态 Y。 在X 与 Y 之间进行弧合并：,在X 和 Y之间的表达式即为所求的正规式 R。,代之以,代之以,代之以,自动机转化为正规式,9,正规文法转化为自动机(1/2),设给定一个右线性正规文法 G=(VN,VT,P,S)，则相应的有穷自动机 M=(Q,f,q0,Z) （1）将VN中的每一个非终结符视作 M 中的一个状态， 并增加一个新终态 D，且 DVN， 令 Q=VND,Z=D,=VT,q0=S （2）对 AaB（A,BVN,aVT ），令f(A,a)=B。 构造弧 （3）对 Aa（AVN,aVT ），令f(A,a)=D。 构造弧,10,正规文法转化为自动机(2/2),设给定一个左线性正规文法 G=(VN,VT,P,S)，则相应的有穷自动机 M=(Q,f,q0,Z) （1）将VN中的每一个非终结符视作 M 中的一个状态， 并增加一个初始状态 q0，且 q0VN， 令 Q=VNq0,Z=S,=VT (将文法G的开始符号S看成终态) （2）对 ABa（A,BVN,aVT ）令f(B,a)=A。 构造弧 （3）对 Aa（AVN,aVT ），令f(q0,a)=A。 构造弧,11,自动机转化为正规文法(1/2),设给定有穷自动机 M=(Q,f,q0,Z)，按照下述方法可 以从 M 构造出相应的右线性正规文法 G=(VN,VT,P,S)， 使得L(M)=L(G) (1)令 VN=Q,VT=,S=q0 (2)若f(A,a)=B且BZ时， 则将规则 AaB 加到P中。 (3)若f(A,a)=B且BZ时，则将规则 AaBa 或 AaB, B 加到P中。 (4)若文法的开始符号 S 是一个终态，则将规则 S 加到P中。,注意: 若终态无出弧，则去掉该非终结符,起点开始，考虑出弧！,12,自动机转化为正规文法(1/2),设给定有穷自动机 M=(Q,f,q0,Z)，按照下述方法可 以从 M 构造出相应的左线性正规文法 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),注意: 若初态无入弧，则去掉该非终结符,终点开始，考虑入弧！,13,习题7(1/4),7、构造下列正规式的相应的DFA 1(0|1)*101 解题步骤： 1.由正规式R构造NFA N 2.构造确定化后的DFA的状态矩阵 3.生成确定化后的DFA的状态转换图 4.化简DFA,14,习题7(2/4),由正规式构造NFA 构造确定化后的DFA的状态矩阵,15,生成确定化后的DFA的状态转换图,B,F,D,E,0,1,0,C,1,1,0,0,A,1,0,1,习题7(3/4),1,16,化简DFA,0,首先 M的状态分成两组：终态组F，非终态组A,B,C,D,E 考察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。 A,B,C,D0 属于D,E,它不含在任何划分中，因为状态 C 经 0弧到达状态 E，而状态A,B,D经 0 弧都到达 D，因此，应把 C 分出来，形成A,B,D、C、E、F。 由于A,B,D1=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),17,习题8(1/3),8、给出下面正规表达式 (1)以01结尾的二进制数串; (2)能被5整除的十进制整数; (3)包含奇数个1或者奇数个0的二进制数串; (7)不包含子串abb的由a和b组成的符号串的全体。,18,习题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,19,习题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)*。,20,习题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,21,习题9(2/3),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,22,习题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,23,习题12(1/3),12、将图3.18的(a)和(b)分别确定化和最少化。,(a),24,习题12(2/3),(a),25,已经是确定化，对其最小化。 1:0,1,2,3,4,5 0,1a=0,1 0,1b=2,4 2,3,4,5a=1,3,0,5 2:0,1,2,4,3,5 2,4b=3,5 3,5b=2,4,习题12(3/3),26,习题14(1/2),14、构造DFA,接收0，1上所有满足每个1都有0直接跟在后面的字符串。 解：正规表达式为(10|0)*,27,(10|0)*,X,Y,1,0,1,2,0,0,1,0,1,0,A,B,C,习题14(2/2),28,习题15(1/3),15、给定右线性文法G： S0S|1S|1A|0B A1C|1 B0C|0 C0C|1C|1|0 求出一个与G等价的左线性文法。,29,习题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,30,习题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|S1,31,习题20(1/3),20、假定有正规定义式 A0a|b A1A0A0 AnAn-1An-1 考虑词形An (1)把An中所有简名都换掉，最终所得的正规式的长度是多少； (2)字集An的元素是什么？把它们非形式地表示成n的函数； (3)证明识别An的DFA只需要用2n+1个状态就足够了。,32,习题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)=,33,习题20(3/3),(3)用归纳法证明。 当n=0时，只需要1个状态，即 假设当n=k时成立，需要2k+1个状态； Ak+1= (a|b)(a|b),S,a,b,S,A,B,C,a,a,b,b,.,第2k+1个状态,D,E,a,a,b,b,所以Ak+1需要2(k+1)+1个状态，即n=k+1 时成立。综上所述，识别An的DFA只需要用 2n+1个状态。,34,补充题,构造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,a,A,a,b,b,C,B,a,a,b,b,SaA|bC| AaS|bB BaC|bA CaB|bS,35,语法分析自上而下分析(1/5),自上而下分析法,确定的自上而下分析法 非确定的自上而下分析法 (带回溯的自上而下分析法),递归下降分析法 预测分析法,36,语法分析自上而下分析(2/5),LL(1)文法要求： （1）文法不含左递归。 （2）对文法中的每一个非终极符 A， 若 A 1|2|.|n， 则 FIRST（i） FIRST（j）= （3）对文法中的每一个非终极符 A，若它存在某个候选首符集包含 ， 则 FIRST（A） FOLLOW（A）=,左递归的消除： 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)文法： 消除左递归和反复提取公共左因子。 提取公共左因子： A1|2|.|n|1|2|.|m 修改成： A A|1|2|.|m A1|2|.|n,37,语法分析自上而下分析(3/5),递归下降分析程序的构造： 当遇到终结符 a 时，则编写语句 if (当前读到的输入符号=a) 读入下一个输入符号。 当遇到非终结符 A 时，则编写语句调用 A. 当遇到 A 规则时，则编写语句 if (当前读到的输入符号 FOLLOW(A) ERROR。 当某个非终结符的规则有多个候选式时，按LL(1)文法的条件唯一现在一个候选式进行推导。,38,实验二：预测分析算法的设计与实现,预测分析器 预测分析表 分析栈 总控程序,Tj,分 析 栈 Sk,总控程序,预测分析表,输出,39,预测分析表的构造,1、构造文法 G 的每一个非终结符的FIRST集和FOLLOW集 2、构造分析表 MA，a （1）对文法G的每个规则A，执行第二步和第三步； （2）对每个终极符aFIRST(）,则置MA,a=A； （3）若FIRST(）,则对任何bFOLLOW（A）, 则置MA,bA； （4）把所有无定义的 MA,a 标上“出错标志” (表中用空格表示)。,40,FIRST集的构造,若XVT，则 FIRST(X)=X。 若XVN，且有规则Xa，aVT，则aFIRST(X)。 若XVN，且有规则X，则FIRST(X)中。 若有规则XY1Y2Yn，对任意的i(1in)， 当Y1Y2Yi-1都是非终极符且Y1Y2Yi-1= (即对任何j(1ji-1)，FIRST(YJ)都含有)， 则把 FIRST(Yi)中的所有非-元素加到 FIRST(X)中； 特别地，若Y1Y2Yn=(即所有的FIRST(Yj)中均含有，1jn)，则FIRST（X）。 反复使用上面的规则，直到每个FIRST集不再增大为止,41,FOLLOW集的构造,(1)对文法的开始符号 S，置#于FOLOOW（S）中； (2)若AB 是一个规则，则把FIRST()-加到FOLLOW(B)中； (3)若AB 是一个规则， 或AB 是一个规则，而 =，即FIRST(),则把FOLLOW(A)加至FOLLOW(B)中。 (4)反复使用上面的规则，直到每个非终结符的FOLLOW集 不再增大为止。,42,总控程序,43,预测分析的过程,若X=a=#，则宣布分析成功； 若X=a#，则将栈顶符号 X（终极符）弹出，让 IP 指针指向下一个输入符号； 若 X 是一个非终极符，则查看分析表 M。如果分析表的 MA,a 中是一条产生式，则先将栈顶符号 X（非终极符）弹出，然后把该产生式右端符号串按反序（从右到左）压入栈中（串不入栈）。,44,习题1(1/4),1、考虑下面文法G1： Sa|(T) TT,S|S （1）消去G1的左递归，然后对每个非终结符写出不带回溯的递归子程序。 （2）经过改写的文法是否是LL（1）的？给出它的预测分析表。,45,习题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集,46,习题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）文法。,47,习题1(4/4),预测分析表如下：,48,习题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)构造它的递归下降分析程序。,49,习题2(2/6),解： (1)FIRST和FOLLOW集如下表：,50,习题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)文法。,51,习题2(4/6),(3)预测分析表为：,52,习题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,53,习题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,54,习题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,55,习题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)文法。,56,习题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)文法。,57,习题4(1/3),4、对下面文法： Expr_Expr Expr(Expr)| Var ExprTail ExprTail_ Expr| Varid VarTail VarTail(Expr)| (1)构造LL（1）分析表 (2)给出对句子id_ _id(id) 的分析过程,58,习题4(2/3),解： (1)FIRST集和FOLLOW集如下表：,LL(1)分析表为：,59,习题4(3/3),(2) 步骤 符号栈 输入串 所用产生式,反序压入栈,60,习题5(1/5),5、把下面文法改写为LL(1)的： DeclistDeclist；Decl|Decl DeclIdList:Type IdListIdList,id|id TypeScalarType|array(ScalarTypeList) of Type ScalarTypeid|BoundBound BoundSign IntLiteral|id Sign+|-| ScalarTypeListScalarTypeList,ScalarType|ScalarType,61,习题5(2/5),解：消除左递归： DeclistDeclDeclist Declist;DeclDeclist| DeclIdList:Type IdListidIdList IdList,idIdList| TypeScalarType|array(ScalarTypeList) of Type ScalarTypeid|BoundBound BoundSign IntLitera