编译原理_(华大学出_第二版_课后答案).docx-淘文阁

资源描述

《编译原理_(华大学出_第二版_课后答案).docx》由会员分享，可在线阅读，更多相关《编译原理_(华大学出_第二版_课后答案).docx（311页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、第1章引论第1题解释下列术语:(1)编译程序(2)源程序Ac|aBAabBbc写出L(G|S|)的全部元素。答案:L(GS)=abc第2题文法GN为:NtD|NDD-0|1|2|3|4|5|6|7|8|9GN的语肃是什么?答案:GN的语言是 V+o V=0,l,2,3,4,5,6,7,8,9N=ND=NDD. =NDDDD.D=D.D或者:允许。开头的非负整数?第3题为只包含数字、加号和减号的表达式,例如9-2 + 5, 3-1, 7等构造个文法。答案：GS:S-S+D|S-D|DD-0|l|2|3|4|5|6|7|8|9第4题已知文法G|Z|：ZaZb|ab写出L(GZ)的全部元素。答案:Z

3、n=l2答案:（5）表达式表达式=表达式+项=X表达式+v因子=X表达式+ （表达式）=x表达式+ （表达式+ 项）表达式+项=X表达式+ （表达式+因子）项因子=x表达式+ （表达式+i）=v表达式+ (项+i)=表达式+ （因子+i）烟子（表达式）=x表达式+ （i+i）=x项+(i+i)1 表达式+项=x 因子+ (i+i)=i+ (i+i)项因子因子i（6） v表达式=表达式+项=x表达式+ 项A*因子=X表达式+V项i=X表达式A+v因子i=x表达式,+i*i=x项+i*i=x 因子+i*i=i + i*i表达式表达式+项项v项* 因子因子因子i第7题证明下述文法G（表达式 |是二义

4、的。表达式）:=a|（表达式）|表达式运算符表达式运算符）:：=+|-|*|/答案:可为句子a+a*a构造两个不同的最右推导:最右推导1 表达式表达式运算符表达式表达式运算符a表达式* a表达式运算符表达式*a表达式运算符a*a表达式+ a * aa+a*a最右推导2 表达式表达式运算符表达式表达式运算符表达式运算符表达式表达式运算符表达式运算符a表达式运算符表达式a表达式运算符a*a表达式+ a * aa+a*a=n=文法GS为:SAc|aBA-abBbc该文法是否为二义的?为什么?答案:对于串abc(1 )S=Ac=abc (2)S=aB=abc即存在两不同的最右推导。所以,该文法是二义的

5、。或者:对输入字符串abc,能构造两棵不同的语法树,所以它是二义的。SSaBAbcab第9题考虑下面上卜文无关文法:sS-SS*|SS+|a(1)表明通过此文法如何生成串aa+a*,并为该串构造语法树。(2)GS|的语是什么?Ss答案:S S + a(1)此文法生成串aa+a*的最右推导如下S=SS*=SS*=Sa*=SS+a*=Sa+a*=aa+a*(2)该文法生成的语言是：和+的后缀表达式，即逆波兰式。a 第10题文法 S-S(S)S|(1)生成的语言是什么?(2)该文法是二义的吗?说明理由。答案:(1 )嵌套的括号(2 )是二义的,因为对于()()可以构造两棵不同的语法树。第11题令文法

6、G|E为:E-T|E+T|E-TT-F|T*F|T/FF-(E)|i证明E+T*F是它的个句型,指出这个句型的所有短语、宜接短语和句柄。答案:此句型对应语法树如右，故为此文法一个句型。或者：因为存在推导序歹:E=E+T=E+T*F,所以E+T*F句型此句型相对于E的短语有:E+T*F:相对于T的短语有T*F直接短语为：T*F句柄为:T*F第13题个上下文无关文法牛.成句子abbaa的推导树如下:(1)给出串abbaa最左推导、最右推导。Q僧文法的小生式集合P可能有哪些元素，S(3)找出该句子的所有短语、直接短语、句柄。ABSS B BA答案:(I)串abbaa最左推导:S=AB S=a B S

7、=aS B B S=aB BS=abBS=abbS=abbAa=abbaa 最右推导:S=ABS=ABAa=ABaa=ASBBaa=ASBbaa=ASbbaa=Abbaa=abbaa(2)产生式有:SABS |Aa|e A-a B-SBB|b可能兀素有:e aa ab abbaa aaabbaa(3)该句子的短语有：a是相对A的短语是相对S的短语b是相对B的短语Ebb是相对B的短语aa是相对S的短语asbbaa是相对S的短语直接短语有:a Eb句柄是:a第14题给出生成下述语言的上下文无关文法：(1 ) anbnambm| ri, m=0(2 ) 1 nOm 1 mOn| 11, IT1=O(

9、字母表中的元素。句子:如果Zx,xDV *T 则称x是文法G的个句子。(3 )语言:它是由句子组成的集合,是由一组记号所构成的集合。程序设计的语言就是所有该语言的程序的全体。语言可以看成在个基本符号集上定义的,按一定规则构成的一切基本符号串组成的集合。语法:表示构成语言句子的各个记号之间的组合规律。程序的结构或形式。语义:表示按照各种表示方法所表示的各个记号的特定含义。语言所代表的含义。附加题问题1:给出下述文法所对应的正规式:S-OA|1BA 一 1S|1B-OS|O答案:R = (01 I 10)( 01 I 10 )问题2：已知文法G|A1,写出它定义的语言描述G|A: A-OB|1

10、CBt 1|1A|OBBC - 0|0A|lCC答案:GA定义的语言由、1符号串组成,串中和1的个数相同.问题3：给出语描述,构造文法.构造文法,其定义的语,是由算符+,*,(,)和运算对象a构成的算术表达式的集合.答案:GE E-E+T|TT-T* F|F F-(E)|a答案：GE E-E+E|E* E|(E)|a问题4：已知文法G|S|:S-dAB10A-*aA|aB-8|bB相应的正规式是什么? G能否改写成为等价的正规文法?答案:正规式是daa*b*：相应的正规文法为(由自动机化简来)：GS:S-dA A-a|aB B-aB|a|b|bC C-bC|b也可为(观察得来):GS:SdA

11、A - a|aA|aB B-bB|c问题5：已知文法G：E-E+T|E-T|TT-T*F|T/F|FF 一 (E)|i试给出卜.述表达式的推导及语法树(l)i；(2) i*i+i(3) i+i*i(4) i+(i+i)答案:(l)E=T=F=i(2)E=E+T=T+T=T*F+T=F*F+T=i*F+T=i*i+T=i*i+F=i*i+i(3)E=E+T=T+T=F+T=i+T=i+T*F=i4-F*F=i+i*F=i4-i*i(4)E=E+T=T+T=F+T=i+T=i+F=i+(E)=i+(E+T)=i4-(T+T)=i+(F+T)=i+(i+T)=i+(i+F)=i+(i+i)EEETE

12、 +TE+ TE + TFTT * FFTTFiFiiFF.iF( E(1)iiE + T(4)11问题6：已知文法G|E|:E-ET+|TT-TF* | FF-FA I a试证:FF人人是文法的句型,指出该句型的短语、简单短语和句柄.答案:该句型对应的语法树如下:该句型相对于E的短语有FF人人相对于T的短语有FF人人,F 相对于F的短语有F人;F人人简单短语有F;F人句柄为F.问题7：适当变换文法,找到下列文法所定义语言的一个无二义的文法:S SaS N SbS Z ScS Z d答案：该文法的形式很典型,可以先采用优先级联规则变换文法，然后再规定结合性对文法做进步变换,即可消除二义性

13、。设a、和c的优先级别依次增高，根据优先级联规则将文法变换为：S SaS Z AA AbA Z CC CcC Z d规定结合性为左结合,进一步将文法变换为：5 SaAZAA AbC ZCC CcF Z FF d该文法为非二义的。EI丄t F * F问题8：构造产生如语言的上卜文无关文法:(1 ) anbinCm | ,m 0(2 ) anhmC2m H， m 0(3) amhn Z. ni e n (4) ，力，cp dq Z. i+ = p+q (5) uawb / w “* 3 I I = I 冊 I答案:(1)根据上下文无关文法的特点,要产生形如。的串,可以分别产生形如anb2n和形如

14、Cm的串。设计好的文法是否就是该语言的文法?严格地说,应该给出证明。但若不是特别指明,通常可以忽略这一点。对于该语言,存在个由以下产生式定义的上下文无关文法GS：S ABA L Z a AbbB Z/cB(2)同样,要产生形如。”加的串,可以分别产生形如an和形如bmC2m的串。对于该语言,存在个由以下产生式定义的上下文无关文法GS:S ABA E /。B Z N bBcc(3)考虑在先产生同样数目的a,b,然后再生成多余的a0以下GS是种解法：S aSb ZaS NZ(4)以下GS是种解法：S aSdZAZDA bAd ZBD aDc Z BB bBc Z Z注：a不多于d时,b不少于c

15、:反之,a不少于d时,b不多于co前种情形通过对应A,后种情形对应Do(5)以下GS是种解法：S AbA BAB Z a13B aZh问题9：下面的文法G（S）描述由命题变量p、q 联结词（合取）、（析取）、（否定）构成的命题公式集合:S S（TZTT T?FZ FF 4-FZpZq试指出句型F（ qp的直接短语（全部）以及句柄。答案:直接短语:p, q, -F句柄:UO=Z 10=U010=1010Z=UO=Z 10=V 110=0110Z=V 1 =ZOO=UOOO= 1000Z=V 1 =Z00=V 100=0100问题13：已知文法GS： S：=AB A：：=aA I B：：=

17、aa问题16：写文法,使其语言是奇正整数集合。答案:A:=1|3|5|7|9|NAN:=NO|N 1 |N2|N3|N4|N5|N6|N7|N8|N9|N:=0|l|2|3|4|5|6|7|8|9第4章词法分析第1题构造下列正规式相应的DFA.(1 ) 1(0|1) *101(2 )1 (1010*|1(010)*1) *0(3 ) a(a|b)*|ab*a)*b(4 ) b(ab)*|bb)*ab答案:(1)先构造NFA：用子集法将NFA确定化除X, A,重新命名其他状态,令AB为B、AC为C、ABY为D,因为D含有丫（NFA 的终态）,所以D为终态。DFA的状态闇:.01X.AAAABA

18、BACABACAABYABYACAB.01XAAABBCBCADDCB(2)先构造NFA：0B 1 C 0 D 1 E60LX 1 A EF 1 G 0 H 1 I 0 J 1( c用子集法将NFA确定化01XXTo=XAAABFLTi= ABFLYCGYYCGCGJT2=YT3= cgjDHKDHDHKABFKLT4=DHEIEIABEFILT5= abfklYCGT6= abefilEJYCGEJYABEFGJLYT7= abefgjlyEHYCGKEHYABEFHLYCGKABCFGJKLT8= abefhlyEYCGIEYABEFLYCGICGJIT9= abcfgjklDHYCGKD

19、HYDHYTio= ABEFLYEYCGTn= CGJIDHJKDHJDHJTi2= DHYEIT13= DHJEIKEIKABEFIKLTi4= abefiklEJYCG将To、Tk T2 T3、T4 T5、T6、T7、T8、T9、T10 T1K Tl2、T13 T14重新命名,分别用、 1、2、3、4、5、6、7、8、9、10、11、12、13、!4 表示。因为 2、7、8、10、12 中含有Y, 所以它们都为终态。011021 013 151 t 11I4161011210790001011131401011232345465236737898101191291010311135126

20、13141473(3)先构造NFA：先构造NFA：a,bPBC 用子集法将NFA确定化将To、Tl、T2、T3、T4、Ts重新命名,分别用、所以它们都为终态。1、2、3、4、5表示。因为3、5中含有Y,0 a 1 b 3a aa2 a 4bb8abXXTo=XAAABCDTi=ABCDBEBYBEABCDEBYABCDYT2=ABCDEBEFBEYBEFABCDEFBEYABCDEYT3=ABCDYBEBYT4=ABCDEFBEFBEYT5=ABCDEYBEFBEYab01123245323445545(4)先构造NFA：用/集法将NFA确定化:将To、Ti、T2, T3、T4、T5重新命名

21、,分别用。、1、2、3、4, 5表示。因为4中含有Y, 所以它为终态。DFA的状态闇:abXXTo=XAAABDEFTi=ABDEFCIGCICIGGT2=CIDYDYABDEFYT3=GHHABEFHT4=ABDEFYCIGT5=ABEFHCIGab011232435423523M(y,0)=x,yb ,M(z,0)=x,z,F表示。因为B、C、F第2题已知 NFA= ( x,y,z ,O,l,M,x,z),其中:M(x,O)=z, M(x,l)=x, M(y,l)=(p, M(z,l)=y,构造相应的 DFAo答案:先构造其矩阵用集法将NFA确定化:将x、z、xz y、xy、xyz重新命名

22、,分别用A、B、C、D、中含有z,所以它为终态。DFA的状态图:1! DAB01C00101XzXyx,yzx,zy01XzXzxzyxzxzxyyxyxyxyzXxyzxyzxy01ABABCDcCEDEEFAF1E第3题将图确定化:答案:用/集法将NFA确定化:重新命名状态子集,令VQ为A、QU为B、VZ为C、V为D、QUZ为E、Z为F。DFA的状态图:01SVQQUVQVZQUQUVQUZVZZZVZQUZVZQUZZZZ01SABACBBDECFFDFECEFFF第4题将下图的(a)和(b)分别确定化和最小化:答案:初始分划得no：终态组,非终态组1,2,3,4,5对非终态组进行审査：l,2,3,4,5a0,1,3,5)而0,1,3,5既不属于,也不属于1,2,3,4,5V 4 a ,所以得到新分划E：

展开阅读全文