编译原理课后作业参考答案

1作业参考答案第二章高级语言及其语法描述6、（1）L（G6）={0,1,2,......,9}+（2）最左推导：N=ND=NDD=NDDD=DDDD=0DDD=01DD=012D=0127N=ND=DD=3D=34N=ND=NDD=DDD=5DD=56D=568最右推导：N=ND=N7=ND7=N27=ND27=N127=D127=0127N=ND=N4=D4=34N=ND=N8=ND8=N68=D68=5687、Ｇ：S→ABC|AC|CA→1|2|3|4|5|6|7|8|9B→BB|0|1|2|3|4|5|6|7|8|9C→1|3|5|7|98、（1）最左推导：E=E+T=T+T=F+T=i+T=i+T*F=i+F*F=i+i*F=i+i*iE=T=T*F=F*F=i*F=i*(E)=i*(E+T)=i*(T+T)=i*(F+T)=i*(i+T)=i*(i+F)=i*(i+i)最右推导：E=E+T=E+T*F=E+T*i=E+F*i=E+i*i=T+i*i=F+i*i=i+i*iE=T=T*F=T*(E)=T*(E+T)=T*(E+F)=T*(E+i)=T*(T+i)=T*(F+i)=T*(i+i)=F*(i+i)=i*(i+i)(2)9、证明：该文法存在一个句子iiiei有两棵不同语法分析树，如下所示，因此该文法是二义的。E+TTFiEE+TFiFiE+TFiET*FiFiTE-TTFiEE-TFiFiSSeiSiSiiSeiSiSiSi211、第3章词法分析7、构造下列正规式相应的DFA：1(0|1)*101解：（1）构造NFA：（2）确定化：构造状态转换矩阵如下：重命名：II0I1{X}_{1}{1}{1}{1,2}{1,2}{1,3}{1,2}{1,3}{1}{1,2,Y}{1,2,Y}{1,3}{1,2}画出状态转换图：（注：已是最简）8、（1）（0|1）*01（2）（0|1|2|3|4|5|6|7|8|9）(1|2|3|4|5|6|7|8|9)*(0|5)|0|5（3）（10*1|0）*10*|（01*0|1）*01*（4）a*b*c*......z*9、（1）正规式（0|1）*（010）（0|1）*NFA:S010111223231443201210130104101X123Y10,1101X01Y0,10,1001G1:S→ABA→aAb|abB→cB|εG2:S→ABA→aA|εB→bBc|bcG3:S→AAA→aAb|εG4:S→1S0|AA→0A1|ε3构造状态转换矩阵：重命名：画出DFA：最少化后：12、（a）构造状态转换矩阵：重命名：IIaIb{0}{0，1}{1}{0，1}{0，1}{1}{1}{0}——重命名：画出确定化后的有限自动机：（b）最少化：首先分为终态集和非终态集：{0，1}{2，3，4，5}{0，1}a={1}{0，1}b={2，4}II0I1{X}{X,0}{X}{X,0}{X,0}{X,1}{X,1}{X,0,Y}{X}{X,0,Y}{X,0,Y}{X,1,Y|{X,1,Y}{X,0,Y}{X,Y}{X,Y}{X,0,Y}{X,Y}S01010112230334435535Sab01211220_0011201010，13001120101010154301ababa1204{2，3，4，5}a={1，3，0，5}可分为{2，4}和{3，5}{2，4}b={3，5}{3，5}b={2，4}形成划分：{0，1}{2，4}{3，5}最少化后的DFA：14、每个1都有0直接跟在右边：（10|0）*15、画出NFA：等价的左线性正规文法：F→A1|B0|C0|C1S→0|1|S0|S1A→1|S1B→0|S0C→A1|B0|C0|C10a12babab10100SBA0,110C1F1000,10,15第4章语法分析——自上而下分析1、S→a|^|(T)T→T,S|S(1)消除左递归S→a|^|(T)T→ST’T’→,ST’|ε递归下降子程序：(2)FIRSTFOLLOWS{a,^,(}{#,,,）}T{a,^,(}{）}T’{,,ε}{）}该文法是LL(1)的：方法一（利用概念）：a.不含左递归；b.候选终结首符集没有交集；c.ε∈first(T’),follow(T’)∩first(T’)={}方法二（指出预测分析表没有多重入口）预测分析表如下：a^(),#SS→aS→^S→(T)TT→ST’T→ST’T→ST’T’T’→εT’→,ST’2、：FIRSTFOLLOWE{（，a，b，^}{#,)}E’{+，ε}{#,)}T{（，a，b，^}{+,#,)}T’{ε，（，a，b，^}{+,#,)}voidS(){if(sym==’a’)advanced();elseif(sym==’^’)advanced();elseif(sym==’(‘){advanced();T();if(sym==’)’)advanced();elseerror();}elseerror();}voidT(){S();T’();}voidT’(){if(sym==’,’){advanced();S();T’();}elseif(syminfollow(T’))elseerror();}6F{（，a，b，^}{(,a,b,^,+,#,)}F’{*，ε}{(,a,b,^,+,#,)}P{（，a，b，^}{*,(,a,b,^,+,#,)}(2)略(3)构造预测分析表+*（）^ab#EE→TE’E→TE’E→TE’E→TE’E’E’→+EE’→εE’→εTT→FT’T→FT’T→FT’T→FT’T’T’→εT’→TT’→εT’→TT’→TT’→TT’→εFF→PF’F→PF’F→PF’F→PF’F’F’→εF’→*F’F’→εF’→εF’→εF’→εF’→εF’→εPP→(E)P→^P→aP→b(4)略4、文法：Expr→-Expr|(Expr)|VarExprTailExprTail→-Expr|εVar→idVarTailVarTail→(Expr)|ε(1)构造LL(1)分析表：FIRST和FOLLOW集合如下：FIRSTFOLLOWExpr{-,(,id}{#,)}ExprTail{-,ε}{#,)}Var{id}{-,#,)}VarTail{(,ε){-,#,)}LL(1)分析表：-()id#ExprExpr→-ExprExpr→(Expr)Expr→VarExprTailExprTailExprTail→-ExprExprTail→εExprTail→εVarVar→idVarTailVarTailVarTail→εVarTail→(Expr)VarTail→εVarTail→ε(2)句子id—id((id))的分析过程：步骤分析栈输入串所用产生式（略）1#Exprid--id((id))#2#ExprTailVarid--id((id))#3#ExprTailVarTailidid--id((id))#4#ExprTailVarTail--id((id))#5#ExprTail--id((id))#76#Expr---id((id))#7#Expr-id((id))#8#Expr--id((id))#9#Exprid((id))#10#ExprTailVarid((id))#11#ExprTailVarTailidid((id))#12#ExprTailVarTail((id))#13#ExprTail)Expr(((id))#14#ExprTail)Expr(id))#15#ExprTail))Expr((id))#16#ExprTail))Exprid))#17#ExprTail))ExprTailVarid))#18#ExprTail))ExprTailVarTailidid))#19#ExprTail))ExprTailVarTail))#20#ExprTail))ExprTail))#21#ExprTail))))#22#ExprTail))#23#ExprTail#24##8第5章语法分析——自下而上分析1、文法：E→E+T|TT→T*F|FF→(E)|i证明E+T*F是它的一个句型，并指出该句型所有短语、直接短语和句柄。解：E+T*F是它的一个句型，因为存在下面语法树：短语：T*F,E+T*F直接短语：T*F句柄：T*F2、文法：S→a|^|(T)T→T,S|S(1)给出(a,(a,a))和(((a,a),^,(a)),a)的最左和最右推导；(2)指出(((a,a),^,(a)),a)的规范归约以及每一步的句柄，根据这个规范归约，给出“移进-归约”过程，并给出它的语法树自下而上构造过程。解：(1)略(2)①规范句型及每一步的句柄（用下划线标示）：②“移进-规约”过程：步骤分析栈输入串动作（1）#(((a,a),^,(a)),a)#预备（2）#(((a,a),^,(a)),a)#移进（3）#(((a,a),^,(a)),a)#移进（4）#(((a,a),^,(a)),a)#移进（5）#(((a,a),^,(a)),a)#移进（6）#(((S,a),^,(a)),a)#归约（7）#(((T,a),^,(a)),a)#归约EE+TT*F1）(((a,a),^,(a)),a)2）(((S,a),^,(a)),a)3）(((T，a),^,(a)),a)4）(((T,S),^,(a)),a)5）(((T),^,(a)),a)6）((S,^,(a)),a)7）((T,^,(a)),a)8）((T,S,(a)),a)9）((T,(a)),a)10）((T,(S)),a)11）((T,(T)),a)12）((T,S),a)13）((T),a)14）(S,a)15）(T,a)16）(T,S)17）(T)18）S9（8）#(((T,a),^,(a)),a)#移进（9）#(((T,a),^,(a)),a)#移进（10）#(((T,S),^,(a)),a)#归约（11）#(((T),^,(a)),a)#归约（12）#(((T),^,(a)),a)#移进（13）#((S,^,(a)),a)#归约（14）#((T,^,(a)),a)#归约（15）#((T,^,(a)),a)#移进（16）#((T,^,(a)),a)#移进（17）#((T,S,(a)),a)#归约（18）#((T,(a)),a)#归约（19）#((T,(a)),a)#移进（20）#((T,(a)),a)#移进（21）#((T,(a)),a)#移进（22）#((T,(S)),a)#归约（23）#((T,(T)),a)#归约（24）#((T,(T)),a)#移进（25）#((T,S),a)#归约（26）#((T),a)#归约（27）#((T),a)#移进（28）#(S,a)#归约（29）#(T,a)#归约（30）#(T,a)#移进（31）#(T,a)#移进（32）#(T,S)#归约（33）#(T)#归约（34）#(T)#移进（35）#S#归约（36）#S#接受③语法树的自下而上的构造过程：103、（1）计算练习2文法G2的FIRSTVT和LASTVT；（2）计算G2的优先关系，G2是一个算符优先文法吗？（3）给出输入串(a,(a,a))的算符优先分析过程。解：（1）FIRSTVTLASTVTS{a,^,(}{a,^,)}T{,,a,^,(}{,,a,^,)}（2）优先关系表如下：a^(),#a^(=),#=因为：1）该文法不含ε产生式；2）该文法是算符文法；3）由优先关系表可以看出，任何终结符之间的优先关系之多满足一种优先关系；所以该文法是算符优先文法。（3）步骤分析栈输入串动作原因0#(a,(a,a))#预备1#(a,(a,a))#移进#(2#(a,(a,