《编译原理精华总结--计算题》由会员分享，可在线阅读，更多相关《编译原理精华总结--计算题（28页珍藏版）》请在金锄头文库上搜索。
1、1练习：给出i+i*i的规范推导，并画出语法树。iii最左推导过程：E=E + E=i + E=i + E * E=i + i * E=i + i * i文法GE如下：EE+E EE*E E( E ) Ei 课堂练习2（1）转换函数；（3）状态转换图DFA三种表示的转换（2）状态转换矩阵；DFA M=(0,1,2,3,a,b,f,0,3)f(0,a)=1 f(0,b)=2 f(1,a)=3 f(1,b)=2f(2,a)=2 f(2,b)=3 f(3,a)=2 f(3,b)=1 ab 0120 1320 2230 3211a103 2aabbbba3课堂练习4f35621iaaaabbbbsta
2、rtNFA转变为DFA4等价的DFA aCDBAEFSbaaaaabbbbbabFstartNFA转变为DFA5DFA最小化课堂练习：把下图最小化6（1）将所有状态分成两个子集：终态集0和非终态集1,2,3,4,5；（2）当输入a时可判断1,2,3,4,5可再拆分，拆分后：41,2,3, 5；（3）当输入b时可判断1,2,3,5可再拆分，拆分后：1, 52,3；（4）当输入a时可判断2,3可再拆分，拆分后：23；1, 5在输入a或b时指向相同，不可再拆。得：最小DNF为：DFA最小化课堂练习构造a(b*c|c*b)的NFAa(b*c|c*b)SZSAZab*c|c*bSAZa c*bb*cBS
3、AZa bbcCc正规式构造NFA课堂练习43521aaaabbbb求以下NFA的正规式第一步64aaz3521saabbbb6NFA构造正规式第二步第三步第四步zs(a|b)*(aa|bb)(a|b)*aa|bbz52s（a|b）*（a|b）*aaz521sa|ba|bbb6NFA构造正规式例:给出如图NFA等价的正规文法GABCDaaabbbbG=（A，B，C，D，a，b，P，A）其中P：A aBA bDB bCC aAC bDC D aBD bDD NFA构造正规文法课堂练习求GS:SaS|bS|aA|bBAaC|a, BbC|bCaC|bC的等价的NFABASaaaabbbbC正规文法
4、构造NFA12课堂练习文法GE：EE+T| E-T|TTT*F| T/F|F F(E)|I消除方法左递归ETEE+TE|-TE|TFTT*FT| /FT| F(E)|i消除左递归13【例】文法：（1）SQc|c（2）QRb|b（3）RSa|a该文法的每个非终结符为间接左递归，消除方法：l 非终结符排序为：S、Q、Rl 把（1）右部代入（3）得：（4）RQca|ca|a 再将（2）的右部代入（4）得：（5）RRbca|bca|ca|a 对（5）消除直接左递归得：R(bca|ca|a)RR bcaR|SQc|cQRb|bR(bca|ca|a)RRbcaR|最终文法变为：消除左递归 14FIRST(
5、F)=(,iFIRST(T)=*,FIRST(T) =(,iFIRST(E)=+,FIRST(E)=(,i判断方法是否是LL(1)方法【例】判断文法GE是否为LL(1)文法。ETE E+TE T FTT*FT F(E)i【解】文法不含左递归E+TE| FIRST(+TE)=+， FOLLOW(E)=),FIRST(+TE)FOLLOW(E)=T*FT| FIRST(*FT)=*,FOLLOW(T)=+,),FIRST(*FT)FOLLOW(T)=F(E)|i FIRST(E)=(,FIRST(i)=iFIRST(E)FIRST(i)=所以GE是LL(1)文法。15【例】文法G：ETEE+TE|
6、TFTT*FT|F(E)|i 构造文法G的分析表i+*()# EETEETE EE+TEEE TTFTTFT TTT*FTTT FFiF(E)构造方法分析表16例:文法GE:E:=E+T|TT:=T*F|FF:=(E)|i求句型T+T+i的短语、简单短语、 句柄、素短语、最左素短语短语：T+T+i, T+T, T, i简单短语：T, I句柄：T 素短语：T+T和i最左素短语：T+T短语、简单短语、句柄、素短语、最左素短语TE+TFiEE+T17【例】试构造FIRSTVT集和LASTVT集 E#E# EE+T ET TT*F TF F(E) Fi方法一：根据定义FIRSTVT(E)=#FIRST
7、VT(E)=+,*,i,(FIRSTVT(T)=*,i,(FIRSTVT(F)=i,(LASTVT(E)=#LASTVT(E)=+,*,i,)LASTVT(T)=*,i,)LASTVT(F)=i,)构造FIRSTVT集和LASTVT集18构造算符优先关系表【例4】试构造文法GE的优先关系表E#E# EE+T ET TT*F TF F(E) Fi+*i()# + * i #=可根据优先关系表判断该文法是否为算符优先文法如果表中元素不存在冲突，即文法的任何终结符至多只存在一种优先关系，则该文法是一个算符优先文法19GS：SaAcBe AbAAbBd1) 通过项目集规范族构造识别活前缀的DFA 2)
8、 构造它的LR(0)分析表 练习构造LR(0)分析表20GS拓广为:SSSa A c B eAbAA bBdI0:S SS a A c B e I1:SS I2 : Sa A c B eA bA AbI3:Sa A c B eAA bI4:Ab I5:S a A c B eB dI7:Sa A c B eI8:Bd I9:Sa A c B e I6:AA b aAbbcBed构造LR(0)分析表S21构造LR(0)分析表状 态ACTIONGOTO acebd#SAB 0S21 1acc 2S43 3S5S6 4r2r2r2r2r2r2 5S87 6r3r3r3r3r3r3 7S9 8r4r4r
9、4r4r4r4 9r1r1r1r1r1r122(a+b)*c-(a+b)/e (a+b)*c)(a+b)/e)- (a+b)c*)(a+b)e/)- (ab+c*)(ab+e/)- ab+c*ab+e/-逆波兰式练习：写出算术表达式(a+b)*c-(a+b)/e的逆波兰式23三元式序列：三元式序列：(1) (-,C,D)(1) (-,C,D)(2) (*,B,(1) (2) (*,B,(1)(3) (+,A,(2) (3) (+,A,(2)(4) (-,C,D) (4) (-,C,D)(5) (*,(4),N) (5) (*,(4),N)(6) (/,E,(5) (6) (/,E,(5)(7)
10、 (+,(3),(6) (7) (+,(3),(6)三元式练习：写出算术表达式A+B*(C-D)+E/(C-D)*N的三元式表示24四元式练习：写出算术表达式A+B*(C-D)+E/(C-D)*N的四元式表示四元式序列：四元式序列：(1) (-,C,D,T1)(1) (-,C,D,T1)(2) (*,B,T1,T2) (2) (*,B,T1,T2)(3) (+,A,T2,T3) (3) (+,A,T2,T3)(4) (-,C,D,T4) (4) (-,C,D,T4)(5) (*,T4,N,T5) (5) (*,T4,N,T5)(6) (/,E,T5,T6) (6) (/,E,T5,T6)(7)
11、 (+,T3,T6,T7) (7) (+,T3,T6,T7)251346201011211.FACTOR=22.EXP 1=3.IF ( )GOTO 104.BASE=2.05.FACTOR=FACTOR*26.GOTO 2010. BASE=11. FACTOR20. Q=21. RETURN划分基本块及流程图26课堂练习求流程图中各结点的必经结点集D(n)。D(1)= 1 D(2)= 1, 2 D(3)= 1, 2, 3 D(4)= 1, 2, 4 D(5)= 1, 2, 4, 5 D(6)= 1, 2, 4, 6 D(7)= 1, 2, 4, 7 必经结点与必经结点集123456727课堂练习求流程图中所有回边。由回边的定义知66 是回边，因为 D(6)=1,2,4,6，故 6 DOM 6。74 是回边，因为 D(7)=1,2,4,7，故4 DOM 7。42 是回边，因为 D(4)=1,2,4，故 2 DOM 4。回边123456728课堂练习求回边 74 组成的循环。解：首先，确定循环出口为7，然后求7的前驱是5和6，它们都不是4，再分别求5的前驱(=4)，6的前驱(=4)，此时算法终止，得到循环7，6，5，4。由回边求循环1234567
