编译原理及实现课后习题答案.doc_第1页
编译原理及实现课后习题答案.doc_第2页
编译原理及实现课后习题答案.doc_第3页
编译原理及实现课后习题答案.doc_第4页
编译原理及实现课后习题答案.doc_第5页
已阅读5页,还剩11页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

2.3 设有文法GS:S=SS*|SS+|a,写出符号串aa+a*规范推导,并构造语法树。S = SS* = Sa* = SS+a* = Sa+a* = aa+a*SSS*SS+aaa2.5 已知文法GS: S=AB A=aA B=bBcbc , 写出该文法描述的语言。A=aA描述的语言: an|n=0B=bBcbc描述的语言:bncn|n=1L(GS)=anbmcm|n=0,m=1ETE+FTE+iFT*T2.7 对2.6题的文法,写出句型T+T*F+i的短语、简单短语以及句柄。短语:T+T*F+i T+T*F i i T T*F简单短语:i T*F T句柄:T 2.8 设有文法GS:S=S*S|S+S|(S)|a,该文法是二义性文法吗?SSS*S+SaaaSSS+S*Saaa根据所给文法推导出句子a+a*a,画出了两棵不同的语法树,所以该文法是二义性文法。2.10给出语言anbm|n,m1的文法。 GS: S:=AB A:=aA|a B:=bB|b3.1 有正则文法GZ:Z:=Ua|Vb,U:=Zb|b,V:=Za|a ,画出该文法的状态图,并检查句子abba是否合法。解:该文法的状态图如下:SUVZaaabbb句子abba合法。3.2 状态图如图3.35所示,S为开始状态,Z为终止状态。写出相应的正则文法以及V,Vn和Vt。SAZabab图3-35状态图 解: 左线性文法GZ: 右线性文法GS:Z:=Ab|bS:=aA|b A:=Aa|aA:=aA|bV=Z,A,a,bV=S,A,a,bVn=Z,AVn=S,AVt=a,bVt=a,b3.3 构造下列正则表达式相应的NFA: 1(1|0)*|0 1(1010*|1(010)*1)*0解:正则表达式:1(1|0)*|01、SZ1(1|0)*|02、SZ1(1|0)*03、SAZ01014、q0q1010,1q2正则表达式:1(1010*|1(010)*1)*00135462101010780101101a,baa3.4 将图3.36的NFA M确定化图3.36 状态图 解:aBq0=00,11q1=0,10,11q2=10DFA:q0q1q2ababa3.5 将图3.37的DFA化简。014253aaaaaabbbbbb图3.37 DFA状态图 解:划分aB0,112,42,3,4,51,0,3,53,5,2,4划分aB0,112,42,40,13,53,53,52,4q0=0,1q1=2,4q2=3,5化简后的DFA:q0q1q2baaabb4.1 对下面文法,设计递归下降分析程序。 SaAS|(A) , AAb|c解:首先将左递归去掉,将规则AAb|c 改成 Acb4.4 有文法GA:A:=aABe|,B:=Bb|b(1)求每个非终结符号的FOLLOW集。(2)该文法是LL(1)文法吗?(3)构造LL(1)分析表。解:(1) FOLLOW(A)=First(B)#=b,# FOLLOW(B)=e,b(2) 该文法中的规则B:=Bb|b为左递归,因此该文法不是LL(1)文法(3) 先消除文法的左递归(转成右递归),文法变为:A:=aABe|,B:=bB,B=bB|,该文法的LL(1)分析表为:aeb#APOP ,PUSH(eBAa)POPPOPBPOP ,PUSH(Bb)BPOPPOP ,PUSH(Bb)aPOP,NEXTSYMePOP,NEXTSYMbPOP,NEXTSYM#ACCEPT更常用且简单的LL(1)分析表:aeb#AAaABeAABBbBBBBbB4.5 若有文法A(A)A|(1)为非终结符A构造FIRST集合和FOLLOW集合。(2)说明该文法是LL(1)的文法。解:(1)FIRST(A)(, FOLLOW(A),#(2)该文法不含左递归;FIRST((A)A)=(,FIRST()=,FIRST((A)A)FIRST()=,且FOLLOW(A),#,FIRST((A)A) FOLLOW(A) =,因此,该文法满足LL(1)文法的条件,是LL(1)文法。4.6 利用分析表4-1,识别以下算术表达式,请写出分析过程。(1)i+i*i+i(2)i*(i+i+i)解:(1)i+i*i+i步骤分析栈余留输入串分析表元素所用产生式1#Ei+i*i+i#POP,PUSH(ET)ETE2#ETi+i*i+i#POP,PUSH(TF)TFT3#ETFi+i*i+i#POP,PUSH(i)Fi4#ETii+i*i+i#POP,NEXTSYM5#ET+i*i+i#POPT6#E+i*i+i#POP,PUSH(ET+)E+TE7#ET+i*i+i#POP,NEXTSYM8#ETi*i+i#POP,PUSH(TF)TFT9#ETFi*i+i#POP,PUSH(i)Fi10#ETii*i+i#POP,NEXTSYM11#ET*i+i#POP,PUSH(TF*)T*FT12#ETF*i+i#POP,NEXTSYM13#ETFi+i#POP,PUSH(i)Fi14#ETii+i#POP,NEXTSYM15#ET+i#POPT16#E+i#POP,PUSH(ET+)E+TE17#ET+i#POP,NEXTSYM18#ETi#POP,PUSH(TF)TFT19#ETFi#POP,PUSH(i)Fi20#ETii#POP,NEXTSYM21#ET#POPT22#E#POPE23#ACCEPT(2)i*(i+i+i)步骤分析栈余留输入串分析表元素所用产生式1#Ei*(i+i+i)#POP,PUSH(ET)ETE2#ETi*(i+i+i)#POP,PUSH(TF)TFT3#ETFi*(i+i+i)#POP,PUSH(i)Fi4#ETii*(i+i+i)#POP,NEXTSYM5#ET*(i+i+i)#POP,PUSH(TF*)T*FT6#ETF*(i+i+i)#POP,NEXTSYM7#ETF(i+i+i)#POP, PUSH()E()F(E)8#ET )E(i+i+i)#POP,NEXTSYM9#ET )Ei+i+i)#POP,PUSH(ET)ETE10#ET ) ETi+i+i)#POP,PUSH(TF)TFT11#ET ) E TFi+i+i)#POP,PUSH(i)Fi12#ET ) E Tii+i+i)#POP,NEXTSYM13#ET ) E T+i+i)#POPT14#ET ) E +i+i)#POP,PUSH(ET+)E+TE15#ET ) ET+i+i)#POP,NEXTSYM16#ET ) ETi+i)#POP,PUSH(TF)TFT17#ET ) ETFi+i)#POP,PUSH(i)Fi18#ET ) ETii+i)#POP,NEXTSYM19#ET ) ET+i)#POPT20#ET ) E+i)#POP,PUSH(ET+)E+TE21#ET ) E T+i)#POP,NEXTSYM22#ET ) E Ti)#POP,PUSH(TF)TFT23#ET ) E TFi)#POP,PUSH(i)Fi24#ET ) E Tii)#POP,NEXTSYM25#ET ) E T)#POPT26#ET ) E)#POPE27#ET )#POP,NEXTSYM28#ET #POPT29#E#POPE30#ACCEPT4.7 考虑下面简化了的C声明文法:;int|float|charID,|ID(1) 在该文法中提取左因子。(2) 为所得的文法的非终结符构造FIRST集合和FOLLOW集合。(3) 说明所得的文法是LL(1)文法。(4) 为所得的文法构造LL(1)分析表。(5) 假设有输入串为“char x,y,z;”,写出相对应的LL(1)分析过程。解:(1) 规则ID,|ID提取公因子如下:ID(,|)增加新的非终结符,规则变为:ID,| C声明文法改变为: ;int|float|charID,|(2) FIRST()FIRST()int,float,charFIRST()IDFIRST(),FOLLOW()#FOLLOW()FIRST()IDFOLLOW()FOLLOW();(3) 所得文法无左递归,且FIRST(int)FIRST(float)FIRST(char)FIRST(,)FIRST()FIRST(,)FOLLOW()因此,所得文法为LL(1)文法。(4) 所得的文法构造LL(1)分析表如下所示:;intfloatcharID,#POP ,PUSH(;)POP ,PUSH(;)POP ,PUSH(;)POP ,PUSH(int)POP ,PUSH(float)POP ,PUSH(char)POP ,PUSH(ID)POPPOP ,PUSH(,);POP,NEXTSYMintPOP,NEXTSYMfloatPOP,NEXTSYMcharPOP,NEXTSYMIDPOP,NEXTSYM,POP,NEXTSYM#ACCEPT更常用且简单的LL(1)分析表:;intfloatcharID,#;intfloatcharID,(5) 输入串“char x,y,z;”相对应的LL(1)分析过程如下:步骤分析栈余留输入串分析表元素所用产生式1#char x,y,z;#POP ,PUSH(;);2#;char x,y,z;#POP ,PUSH(char)char3#; charchar x,y,z;#POP,NEXTSYM4#;x,y,z;#POP ,PUSH(ID)ID5#;xx,y,z;#POP,NEXTSYM6#;,y,z;#POP ,PUSH(,),7#;,y,z;#POP,NEXTSYM8#;y,z;#POP ,PUSH(ID)ID9#;yy,z;#POP,NEXTSYM10#;,z;#POP ,PUSH(,),11#;,z;#POP,NEXTSYM12#;z;#POP ,PUSH(ID)ID13#;zz;#POP,NEXTSYM14#;#POP15#;#POP,NEXTSYM16#ACCEPT5.1 考虑以下的文法:SS;T|TTa(1) 为这个文法构造LR(0)的项目集规范族。(2) 这个文法是不是LR(0)文法?如果是,则构造LR(0)分析表。(3) 对输入串“a;a”进行分析。解:(1)拓广文法GS: 0:SS 1:SS;T 2:ST 3:Ta构造LR(0)项目集规范族状态项目集转换函数0SSSS;TSTTaGO0,S1GO0,S1GO0,T2GO0,a31SSSS;TACCEPTGO1,;42STR23TaR34SS;TTaGO4,T5GO4,a35SS;TR1(2)该文法不存在“归约归约”和“归约移进”冲突,因此是LR(0)文法。LR(0)分析表如下:状态ACTIONGOTO;a#ST0S3121S4ACCEPT2R2R2R23R3R3R34S355R1R1R1(3)对输入串“a;a”进行分析如下:步骤状态栈符号栈输入符号栈ACTIONGOTO00#a;a#S3103#a;a#R32302#T;a#R21401#S;a#S45014#S;a#S360143#S;a#R3570145#S;T#R11801#S#ACCEPT5.2 证明下面文法是SLR(1)文法,但不是LR(0)文法。SAAAb|bBaBaAc|a|aAb解:文法GS:0:SA1:AAb2:AbBa3:BaAc4:Ba5:BaAb构造LR(0)项目集规范族:状态项目集转换函数0SAAAbAbBaGO0,A1GO0,A1GO0,b21SAAAbACCEPTGO1,b32AbBaBaAcBaBaAbGO2,B4GO2,a5GO2,a5GO2,a53AAbR14AbBaGO4,a65BaAcBaBaAbAAbAbBaGO5,A7R4GO5,A7GO5,A7GO5,b26AbBaR27BaAcBaAbAAbGO7,c8GO7,b9GO7,b98BaAcR39BaAbAAbR5R1状态5存在“归约移进”冲突,状态9存在“归约归约”冲突,因此该文法不是LR(0)文法。状态5:FOLLOW(B)a,因此,FOLLOW(B)b状态9:FOLLOW(B)a,FOLLOW(A)#,b,c,因此FOLLOW(B)FOLLOW(A)状态5和状态9的冲突均可用SLR(1)方法解决,构造SLR(1)分析表如下:状态ACTIONGOTOabc#AB0S211S3ACCEPT2S543R1R1R14S65R4S276R2R2R27S9S88R39R5R1R1R1该SLR(1)分析表无重定义,因此该文法是SLR(1)文法,不是LR(0)文法。5.3 证明下面文法是LR(1)文法,但不是SLR(1)文法。SAaAb|BbBaAB解:拓广文法GS:0:SS1:SAaAb2:SBbBa3:A4:B构造LR(0)项目集规范族:状态项目集转换函数0SSSAaAbSBbBaABGO0,S1GO0,A2GO0,B3R3R41SSACCEPT2SAaAbGO2,a43SBbBaGO3,b54SAaAbAGO4,A6R35SBbBaBGO5,B7R46SAaAbGO6,b87SBbBaGO7,a98SAaAbR19SBbBaR2状态0存在“归约归约”冲突,且FOLLOW(A) a,b,FOLLOW(B)a,b,即FOLLOW(A)FOLLOW(B)a,b,所以该文法不是SLR(1)文法。构造LR(

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论