编译原理习题及答案整理后

第一章1、将编译程序分成假设干个“遍〞是为了.b.使程序的结构更加清楚2、构造编译程序应掌握.a.源程序b.目标语言c.编译方法3、变量应当.c.既持有左值又持有右值4、编译程序绝大多数时间花在上.d.治理表格5、不可能是目标代码.d.中间代码6、使用可以定义一个程序的意义.a.语义规那么7、词法分析器的输入是.b.源程序8、中间代码生成时所遵循的是-.c.语义规那么9、编译程序是对.d.高级语言的译10、语法分析应遵循.c.构词规那么二、多项选择题1、编译程序各阶段的工作都涉及到.b.表格治理c.出错处理2、编译程序工作时,通常有阶段.a.词法分析b.语法分析c.中间代码生成e.目标代码生成三、填空题1、解释程序和编译程序的区别在于是否生成目标程序.2、编译过程通常可分为5个阶段,分别是一词法分析—、语法分析中间代码生成—、代码优化和目标代码生成.3、编译程序工作过程中,第一段输入是—源程序,最后阶段的输出为标代码生成程序.4、编译程序是指将源程序程序译成目标语言程序的程序.、单项选择题1、文法G:SfxSx|y所识别的语言是.a.xyxb.(xyx)*c.xnyxn(n>0)d.x*yx*2、文法G描述的语言L(G)是指.a.L(G)={a|S?“,aCVt*}b.L(G)={a|SZa,aCVt*}C.L(G)={a|S?*a,aC(VtUVn*)}d.L(G)={a|S?a,〞C(VtUVn*)}3、有限状态自动机能识别.a.上下文无关文法b.上下文有关文法c.正规文法d.短语文法4、设G为算符优先文法,G的任意终结符对a、b有以下关系成立.a.假设f(a)>g(b),那么a>bb.假设f(a)<g(b),那么a<bc.a~b都不一定成立d.a~b一定成立5、如果文法G是无二义的,那么它的任何句子a.a.最左推导和最右推导对应的语法树必定相同b.最左推导和最右推导对应的语法树可能不同c.最左推导和最右推导必定相同d.可能存在两个不同的最左推导,但它们对应的语法树相同6、由文法的开始符经0步或多步推导产生的文法符号序列是.a.短语b.句柄c.句型d.句子7、文法G:E-E+T|TT一T*P|PP一(E)|I那么句型P+T+i的句柄和最左素短语为.a.P+T和ib.P和P+Tc.i和P+T+id.P和T8、设文法为：S-SA|AA-a|b那么对句子aba,下面是标准推导.S：SA=,SAA=AAA=,aAA=abA：abaS：SA=SAA=AAA=AAa=Aba=abaS：SA=SAA=SAa:Sba:Aba=abaS：SA=Sa：SAa=Sba:Aba：aba9、文法G:Sfb|A(T)T-T,S|S贝UFIRSTVT(T).

10、产生正规语言的文法为a.0型b.1型11、米用自上而卜分析,必须.c.2型d.3型a.消除左递归b.消除右递归c.消除回溯d.提取公共左因子12、在标准归约中,用来刻回可归约串.a.直接短语b.句柄c.最左素短语d.素短语a.{ba.{b,A,()b.{b,A,))c.{b,A,(,,)d.{b,A,),,)13、有文法G:E-E*T|TT-T+i|i句子1+2*8+6按该文法G归约,其值为d.17b.最右推导的逆过程d.17b.最右推导的逆过程d.最左归约的逆过程b.状态转换图是一个有向图d.DFA可以用状态转换图表示14、标准归约指.a.最左推导的逆过程c.标准推导二、多项选择题1、下面哪些说法是错误的.a.有向图是一个状态转换图c.有向图是一个DFA2、对无二义性文法来说,一棵语法树往往代表了.a.多种推导过程b.多种最左推导过程c.一种最左推导过程d.仅一种推导过程e.一种最左推导过程之一时,那么称该文法是二义文法.3、如果文之一时,那么称该文法是二义文法.a.该句子的最左推导与最右推导相同b.该句子有两个不同的最左推导c.该句子有两棵不同的最右推导d.该句子有两棵不同的语法树e.该句子的语法树只有一个4、有一文法G:S-ABAfaAb|£BfcBd|£它不产生下面集合.a.{anbmcndm|n,m>0}b.{anbncmdm|n,m>0}c.{anbmcmdn|n,m>0}d.{anbncmdm|n,m>0}e.{anbncndn|n>0}5、自下而上的语法分析中,应从开始分析.a.句型b.句子c.以单词为单位的程序d.文法的开始符e.句柄6、对正规文法描述的语言,以下有水平描述它.a.0型文法b.1型文法c.上下文无关文法d.右线性文法e.左线性文法三、填空题1、文法中的终结符和非终结符的交集是.词法分析器交给语法分析器的文法符号一定是,它一定只出现在产生式的部.2、最左推导是指每次都对句型中的非终结符进行扩展.3、在语法分析中,最常见的两种方法一定是分析法,另一是分析法.4、采用语法分析时,必须消除文法的左递归.5、树代表推导过程,树代表归约过程.6、自下而上分析法采用、归约、错误处理、等四种操作.7、Chomsky把文法分为种类型,编译器构造中采用和文法,它们分别产生和语言,并分别用和自动机识别所产生的语言.四、判断题TOC\o"1-5"\h\z1、文法S-aS|bR|e描述的语言是〔a|bc〕*〔〕RfcS2、在自下而上的语法分析中,语法树与分析树一定相同.〔〕3、二义文法不是上下文无关文法.〔〕4、语法分析时必须先消除文法中的左递归.〔〕5、标准归约和标准推导是互逆的两个过程.〔〕6、一个文法所有句型的集合形成该文法所能接受的语言.〔〕五、简做题1、句柄2、素短语3、语法树4、归约5、推导六、问做题1、给出上下文无关文法的定义.2、文法G[S]:S一aSPQ|abQQDPQbP一bbbQ一bccQ—cc〔1〕它是Chomsky哪一型文法〔2〕它生成的语言是什么3、按指定类型,给出语言的文法.L={aibj|j>i>1}的上下文无关文法.4、有文法G:SfaAcB|BdAfAaB|cB一bScA|b(1)试求句型aAaBcbbdcc和aAcbBdcc的句柄；(2)写出句子acabcbbdcc的最左推导过程.5、对于文法G[S]:S一(L)|aS|a1_一1_,S|S(1)画出句型(S,(a))的语法树.(2)写出上述句型的所有短语、直接短语、句柄和素o6、考虑文法G[T]:T-T*F|FFfFTP|PP-(T)|i证实T*PT(T*F)是该文法的一个句型,并指出直接短语和句柄.单项选择[解答]1、选Co2、选a.3、选Co4、虽然a与b没有优先关系,但构造优先函数后,a与b就一定存在优先关系了.所以,由f(a)>g)(b)或f(a)<g(b)并不能判定原来的a与b之间是否存在优先关系：应选c.5、如果文法G无二义性,那么最左推导是先生长右边的枝叶：对于d,如果有两个不同的TOC\o"1-5"\h\z是了左推导,那么必然有二义性.应选a.E6、选c./!\E+F7、由图2-8-1的语法树和优先关系可以看出应选bo।E+TPII一iP#<+>+<i>#图2-8-1句型P+T+I的语法及优先关系8、标准推导是最左推导,应选do9、由T-T,和T-(得FIRSTVT(T))={(,,)};由T-S得FIRSTVT(S)?FIRSTVT(T),而FIRSTVT(S)={b,A,(};即FIRSTVT(T)={b,A,(,,};因此选c.10、d11、c12、b13、b14、b多项选择解答1、e、a、c2、a、c、e3、b、c、d4、a、c5、b、c6、a、b、c、d、e填空解答1、空集终结符右2、最左3、自上而上自下而上4、自上而上5、语法分析6、移进接受7、42型3型上下文无关语言正规语言下推自动机有限判断解答1、对2、错3、错4、错5、错6、错简答［解答］1、句柄：一个句型的最左直接短语称为该句型的句柄.2、素短语：至少含有一个终结符的素短语,并且除它自身之外不再含任何更小的素短语.3、语法树：满足下面4个条件的树称之为文法G［S］的一棵语法树.①每一终结均有一标记,此标记为VnUVt中的一个符号；②树的根结点以文法G［S］的开始符S标记；③假设一结点至少有一个直接后继,那么此结点上的标记为Vn中的一个符号；④假设一个以A为标记的结点有K个直接后继,且按从左至右的顺序,这些结点的标记分另I为Xi,X2,,Xk,那么AXi,X2,,Xk,必然是G的一个产生式.4、归约：我们称“丫3直接归约出aA3,仅当A-丫是一个产生式,且a、3C(VnUVt)*.归约过程就是从输入串开始,反复用产生式右部的符号替换成产生式左部符号,直至文法开始符.5、推导：我们称aA3直接推出a丫3,即aA3=a丫3,仅当A一丫是一个产生式,且a、3C(VnUVt)*o如果ai=ta2=i…3an,那么我们称这个序列是从ai至a2的一'个推导.假设存在一个从…n的推导,那么称“1可推导出&no推导是归约的逆过程.问答1［解答］一个上下文无关文法G是一个四元式(Vt,Vn,S,P),其中：Vt是一个非空有限集,它的每个元素称为终结符号；Vn是一个非空有限集,它的每个元素称为非终结符号,VtAVn=①；S是一个非终结符号,称为开始符号；P是一个产生式集合(有限),每个产生式的形式是P-a,其中,PCVn,aC(VtUVn)*.开始符号S至少必须在某个产生式的左部出现一次.2［解答］(1)由于产生式左部存在终结符号,且所有产生式左部符号的长度均小于等于产生式右部的符号长度,所以文法G［S］是Chomsky1型文法,即上下文有关文法.(2)按产生式出现的顺序规定优先级由高到低(否那么无法推出句子),我们可以得到：SabQ=abcSaSPQaabQPQ=aabPQQ=aabbQQ=aabbcQaabbccSaSPQaaSPQPQ=aaabQPQPQ=aaabPQQPQ=aaabPQPQQ=aaaPPQQQ二aaabbPqqq=aaabbQQQ=-aaabbbcQQ=aaabbbccQ,:aaabbbccc……于是得到文法G[S]生成的语言L={anbncn|n>1}3【解答】(1)由L={abj|j>in1}知,所求该语言对应的上下文无关文法首先应有S-aSb型产生式,以保证b的个数不少于a的个数；其次,还需有S-Sb或S-bS型的产生式,用以保证b的个数多于a的个数；也即所求上下文无关文法G[S]为：G[S]:S-aSb|Sb|b4【解答】(1)分别画出对应两句型的语法树,如图2-8-2所示TOC\o"1-5"\h\z句柄：AaBBdSS…cB...……AaBbAct八Bdc八Bdcb(a)(b)图2-8-2语法树(2)句子acabcbbdcc的最左推导如下：S:aAcB:aAaBcB=acaBcB:acabcB:acabcbScA:acabcbBdcA=acabcbbdcAacabcbbdcc5【解答】S(1)句型(S,(a))的语法树如图2-8-3所示/।\(L)L।S/1\s(l)Sa图2-8-3句型(S,(a))的语法树

(2)由图2-8-3可知：①短语：S、a、(a)、S,(a)、(S,(a));②直接短语：a、S;③句柄：S;④素短语：素短语可由图2-8-3中相邻终结符之间的优先关系求得,即;#<(V,V(Va>)?)>#因此素短语为a.6【解答】首先构造T*PT(T*F)的语法树如图2-8-4所示.由图2-8-4可知,T*PT(T*F)是文法G[T]的一个句型.直接短语有两个,即P和T*F;句柄为P.、单项选择题1、词法分析所依据的是—.a.语义规、单项选择题1、词法分析所依据的是—.a.语义规那么b.构词规那么2、词法分析器的输出结果是—.a.单词的种别编码c.单词的种别编码和自身值3、正规式Mi和M2等价是指,Mi和M2的状态数相等c.Mi和M2所识别的语言集相等第三章c.语法规那么d.等价变换规那么b.单词在符号表中的位置d.单词自身值Mi和M2的有向弧条数相等d.M1和M2状态数和有向弧条数相等4、状态转换图(见图3-6-1)接受的字集为图3-6-1a.以0开头的二进制数组成的集合b.以0结尾的二进制数组成的集合c.含奇数个0的二进制数组成的集合d,含偶数个0的二进制数组成的集合5、词法分析器作为独立的阶段使整个编译程序结构更加简洁、明确,因此,a,a,词法分析器应作为独立的一遍b,词法分析器作为子程序较好c,词c,词法分析器分解为多个过程,由语法分析器选择使用d,词法分析器并不作为一个独立的阶二、多项选择题在词法分析中,能识别出a,根本在词法分析中,能识别出a,根本字b,四元式c,运算符d.逆波兰式e,常数令汇={a,b},那么汇上所有以b开头,后跟假设干个ab的字的全体对应的正规式为a,b(a,b(ab)*d,(ba)+b三、填空题+b,b(ab)e,b(a|b)c.(ba)*b1、确1、确定有限自动机DFA是的一个特例.2、2、假设二个正规式所表示的相同,那么认为二者是等价的.3、3、一个字集是正规的,当且仅当它可由所.四、判断题1、一个有限状态自动机中,有且仅有一个唯一终态.2、设r和s分别是正规式,那么有L(r|s)=L(r)|L(s).3、自动机M和M'的状态数不同,那么二者必不等价.4、确定的自动机以及不确定的自动机都能正确地识别正规集.5、对任意一个右线性文法5、对任意一个右线性文法G,都存在一个NFAM,满足L(G)=L(M).6、对任意一个右线性文法G,都存在一个DFAM,满足L(G)=L(M).7、对任何正规表达式e,都存在一个NFAM,满足L(G)=L(e).8、对任何正规表达式e,都存在一个DFAM,满足L(G)=L(e).五、基此题1、设M=({x,y},{a,b},f,x,{y})为一非确定的有限自动机,其中f定义如下:f(x,a)={x,y}f(x,b)={y}ff(y,b)={x,y}f(y,a)=(f)试构造相应确实定有限自动机M2、对给定正规式b*(d|ad)(b|ab)构造其NFAM;单项选择解答1、b2、c3、c4、d5、b多项选择解答1、a、c、e2、a、b、填空解答1、NFA正规集3、DFA(NFA)所识别判断解答1、2、3、错4、5、6、7、8、正确根本根本1解答:对照自动机的定义M=(S,2,f,S,z),由f的定义可知f(x,a)、f(y,b)均为多值函数,所以是一非确定有限自动机,先画出NFAM相应的状态图,如图3-6-2所示.将图3-6-5的将图3-6-5的DFAM'最小化.首先,将M'的状态分成终态组{1,2}与非终态组{0};其次,考察{1,2}.由于{1,2}a={1,2}b={2}?{1,2},所以不再将其划分了,也即整个划分只有两组{1,2}:令状态1代表{1,2},即把原来至沙所示化简DFAM'.b1酬除状态2.最后,得到如图{0},3-6-6图3-6-6化简后的DFAM'2解答2解答：首先用如图3-6-7所示.NFAM,用子集法构造状态转换矩阵表3-6-3所示.IIaIb{X}{x,y}{y}{y}一{x,y}{x,y}{x,y}{x,y}将转换矩阵中的所有子集重新命名而形成表3-6-4所示的状态转换矩阵.表3-6-4状态转换矩阵ab0211一22k-22k即得到M'=({0,1,2},{a,b},f,0,{1,2}),其状态转换图如图3-6-5所示.第四章1、构造下面文法的LL(1)分析表.DfTLTfint|realLfidRRf,idR|£下面文法G[S]是否为LL(1)文法说明理由.SfAB|PQxA-xyB-bcPfdP|eQ-aQ|e设有以下文法：G[S]:SfaAbDe|dAfBSD|eBfSAc|cD|£DfSe|e(1)求出该文法的每一个非终结符U的FOLLOW集(2)该文法是LL(1)文法吗?(3)构造C[S]的LL(1)分析表.将文法G[V]改造成为LL(1)的.G[V]:VfN|N[E]E-V|V+E5、文法:G[A]:A-aAa|£(1)该文法是LL(1)文法吗?为什么(2)假设采用LL(1)方法进行语法分析,如何得到该文法的LL(1)分析表?(3)假设输入符号串“aaaa〞,请给出语法分析过程.1解答：LL(1)分析表见表4-3-1分析虽然这个文法很简单,我们还是从求开始符号集合和后继符号集合开始.FIRST(D)=FIRST(T)={int,real}FOLLOW(D)=FOLLOW(L)={#}FIRST(L)={id}FOLLOW(T)={id}FIRST(R)={,,卜FOLLOW(R)={#}有了上面每个非终结符的FIRST集合,填分析表时要计算一个产生式右部a的FIRST(亦就不是件难事了.填表时唯一要小心的时,e是产生式R-e右部的一个开始符号,而#在FOLLOW(R)中,所以R-e填在输入符号#的栏目中.表4-3-1LL(1)分析表非终结符输入符号intrealid#DDfTLDfTLTT-intT一realLLTdRRRf,idRR一£2解答：该文法不是LL(1)文法,见下面分析中的说明.分析只有三个非终结符有两个选择.1、P的两个右部dP和e的开始符号肯定不相交.2、Q的两个右部aQ和£的开始符号肯定不相交.3、对S来说,由于x£FIRST(AB),同时也有x£FIRST(PQx)(由于P和Q都可能为空).所以该文法不是LL(1)文法.3解答：(1)求文法的每一个非终结符U的FOLLOW集的过程如下：由于：S是识别符号,且有AfBSD、BfSAc、DfSe,所以FOLLOW(S)应包含FIRST(D)UFIRST(Ac)UFIRST(e)U{#}={a,d}U{a,d,c,e}U{e}U{#}={a,c,d,e#}又由于AfBSD和D一s,所以FOLLOW中还包含FOLLOW(A).由于SfaAbDe和B-SAc,所以FOLLOW(A)=FIRST(bDe)UFIRST(c)={b,c}综合①、②得FOLLOW(S)={a,d,c,e,#}U{a,b,c,d,e,#}由于A-BSD,所以FOLLOW(B)=FIRST(SD)={a,d}由于SfaAbDe|d、A-BSD|e和B-SAc|cD,所以FOLLOW(D)=FIRST(e)UFOLLOW(A)UFOLLOW(B)={e}U{b,c}U{a,d}={a,b,c,d,e}(2)G[S]不是LL(1)文法.由于产生式BfSAc|cD|£中FIRST(SAc)nFOLLOW(B)={a,d}w?(3)构造G[S]的LL(1)分析表.根据LL(1)分析表的构造算法构造方法G[S]的LL(1)分析表如表4-3-2所示.表4-3-2G[S]的LL(1)分析表abcde#SaAbDedABSDBSDBSDeBSac/ecDSac/eDSe/£££Se/££4解答：对文法G[V]提取公共左因子后得到文法:G[V]:V-NAA一或E]E一VBBfH+ENfi求出文法G[V]中每一个非终结符号的FIRST集:FIRST(V)={i}FIRST(A)={[,}FIRST(E)={i}FIRST(B)={+,}FIRST(N)={i}求出文法G[V]中每一个非终结符号的FOLLOW集：FOLLOW(V)={#}UFIRST(B)\{4UFOLLOW(E)={#,+,]}FOLLOW(A)=FOLLOW(V)={+,,#}FOLLOW(E)=FIRST(])\{4UFOLLOW(B)=FIRST(])\{}UFOLLOW(E)={]}FOLLOW(B)=FOLLOW(E)={]}FOLLOW(N)=FIRST(A)\{3UFOLLOW(V)={[,],+,#}可以看到,对文法G[V]的产生式A一或E],有FIRST([E])AFOLLOW(A)={[}n{+,],#}=?对产生式B一耳+E,有FIRST(+E)AFOLLOW(B)={+}n{]}=?而文法的其他产生式都只有一个不为由勺右部,所以文法G[V]是LL(1)文法.5解答：(1)由于产生式A-aAa|e有空产生式右部,而FOLLOW(A)={#}UFIRST(a)={a,#}造成FIRST(A)nFOLLOW(A)={A,}n{a,#}w?所以该文法不是LL(1)文法.(2)假设采用LL(1)方法进行语法分析,必须修改该文法.因该文法产生偶数(可以为0)个a,所以得到文法G[A]:A-aaA|日此时对产生式A-aaA|e,有FOLLOW(A)={#}UFOLLOW(A)={#},因而FIRST(A)nFOLLOW(A)={a,}n{#}=?所以文法G[A]是LL(1)文法,按LL(1)分析表构造算法构造该文法的LL(1)分析表如表4-3-3所不.表4-3-3文法G'[A]的LL(1)分析表A#AA-aaAA一日(3)假设采用LL(1)方法进行语法分析,对符号串“aaaa〞的分析过程如表4-3-4所示.表4-3-4对符号串“aaaa〞的分析过程步骤分析栈输入串产生式/动作1#Aaaaa#A-aaA2#Aaaaaaa#匹配3#Aaaaa#匹配4#Aaa#A-aaA5#Aaaaa#匹配6#Aaa#匹配7#A#A一日8##接受第五章.设有文法G[S]为:S一a|b|(A)AfSdA|S(1)完成以下算符优先关系表,见表5-7-1,并判断G[S]是否为算符优先文法.表5-7-1算符优先关系表ab()d#a??b??(????)??d#????(2)给出句型(SdSdS)的短语、简单短语、句柄、素短语和最左素短语.(3)给出输入串(adb)#的分析过程.解答：(1)先求文法G[S]的FIRSTVT集和LASTVT集:由S-a|b|(A)得：FIRSTVT(S)={a,b,();由AfSd得：FIRSTVT(A)={d};又由A-S得：FIRSTVT(S)?FIRSTVT(A),即FIRSTVT(A)={d,a,b,(};由S-a|b|(A)得；LASTVT(S)={a,b,}};由A一dA得：LASTVT(A)={d},又由A-S得：LASTVT(S)?LASTVT(A),即LASTVT(A)={d,a,b,)}.构造优先关系表方法如下：①对Pf…ab…,或Pf…aQb…,有a?b;②对P—aR,而bCFIRSTVT(R),有a?b;③对PfRb,而aCFIRSTVT(R),有a?b.由此得到：①由S一(A)得：(?);②由S一(A得：(?FIRSTVT(A),即：(?d,(?a,(?b,(?(油A-dA得：d?FIRSTVT(A),即：d?d,d?a,d?b,d?(;③由S-A)得,LASTVT(A)?),即：d?),a?),b?),)?);由A-Sd得：LASTVT(S)?d,即：a?d,b?d,)?d;此外,由#S#导:#?#;由#?FIRSTVT(S)得：#?a,#?b,#?(;月旨由LASTVT(S)?#得：d?#,a?#,b?#,)?#.最后得到算符优先关系表,见表5-7-2.

ab()d#a???b???(????)???d??????#????表5-7-2算符优先关系表由表5-7-2可以看出,任何两个终结符之间至少只满足、、三种优先关系之一,故G[S]为算符优先文法.S〔2〕为求出句型〔SdSdS〕的短语、简单短语、句柄,我们先画出该句型对应的语法树,如图5-7-3所示.由图5-7-3得到：S短语：S,SdS,SdSdS,〔SdSdS〕简单短语〔即直接短语〕：S句柄〔即最左直接短语〕：S素短语：SdS,它同时也是该句型的最左素短语.图5-7-3句型〔SdSdS〕的语法树〔3〕输入串〔adb〕#的分析过程见表5-7-4表5-7-4输入串〔adb〕#的分析过程符号栈输入串说明#(adb)#移进#(adb)#移进#(adb)#用S-a归约#(Sdb)#移进#(Sdb)#移进#(Sdb)#用S-b归约#(SdS)#用A-S归约#(SdA)#用A-SdA归约#(A)#移进#(A)#用S-(A)归约#S#分析成功第六章一、单项选择题1、假设a为终结符,那么A-a・a3为工程a.归约b.移进c.接受d.待约2、假设工程集Ik含有A-a-,那么在状态k时,仅当面临的输入符号a»OLLOW(A)时,才采取“A-动作的一定是.a.LALR文法b.LR(0)文法c.LR(1)文法d.SLR(1)文法3、就文法的描述水平来说,有—.a.SLR(1)?LR(0)b.LR(1)?LR(0)c.SLR(1)?LR(1)d.无二义文法LR4、在LR(0)的ACTION子表中,如果某一行中存在标记"j’的栏,那么.a.该行必定填满rjb.该行未填满rjc.其他行也有rjd.goto子表中也有rj5、一个指明了在分析过程中的某时刻所能看到产生式多大一局部.a.活前缀b.前缀c.工程d.工程集二、多项选择题1、一个LR分析器包括.a.一个总控程序b.一个工程集c.一个活前缀d.一张分析表e.一个分析栈2、LR分析器核心局部是一张分析表,该表包括等子表.a.LL(1)分析b.优先关系c.GOTOd.LRe.ACTION3、每一项ACTION[S,a]所规定的动作包括.a.移进b.比拟c.接受d.归约e.报错4、对LR分析表的构造,有可能存在动作冲突.

a.移a.移进b.归约c.移进/归约d.移进/移进e.归约/归约5、就文法的描述水平来说,有LR(1)?SLR(1)e.SLR(1)?SLR(1)e.SLR(1)?无二义文法一等分析表的构造方法.c.SLR(1)d.SLR(0)ob.LL(1)分析法e.LALR(1)分析法LR(0)?LR(1)e.LR(1)c.SLR(1)分析法.LR(1)?无二义文法6、对LR分析器来说,存在a.LALRb.LR(0)7、自上而下的语法分析方法有a.算符优先分析法d.LR(0)分析法三、填空题1、对于一个文法,如果能够构造.使得它的均是唯一确定的,那么称该文法为LR文法.2、字的前缀是指该字的.3、活前缀是指的一个前缀,这种前缀不含之后的任何符号.4、在LR分析过程中,只要的已扫描局部保持可归约成一个—,那么扫描过的局部正确.5、将识别的NFA确定化,使其成为以为状态的DFA,这个DFA就是建立的根底.6、A->a,称为工程；对文法开始符S>a•为工程；假设a为终结符,那么称A一a,a3为工程；假设B为非终结符,那么称A-"a3为工程.7、LR(0)分析法的名字中“L〞表示,“R〞表示,“0"表示.四、综合题1、对于文法G[S]:S-AS|bA一SA|a(1)列出所有LR(0)工程(2)列出构成文法LR(0)工程集标准族.单项解答：1、A->a•称为归约工程,对文法开始符S'的归约工程,如S>a•称为接受工程,A->a,a3(a为终结符)称为移进工程.在此选b.2、当用产生式Af“归约时,LR(0)无论面临什么输入符号都进行归约；SLR(1)那么仅当面临的输入符号aCFOLLOW(A)时进行归约；LR(1)那么当在把“归约为A的标准句型的前缀阳a前提下,当“后跟终结符a时,才进行归约；因此选do3、由于LR(0)?SLR(1)?LR(1)?无二义文法,应选c.4、选a.

5、选c.多项选择解答:1、一个LR分析器包括一个总控程序和一张分析表,选a、do2、选c、e°3、选a、c、d、e.4、在LR分析表的构造中有可能存在“移进〞/“归约〞和“归约〞/“归约〞冲突；应选c、e.5、选a、b、c、d、e.6、选a、b、c、e.7、选a、c、d、e.填空解答：1、一张分析表每个入口2、任意首部3、标准句型句柄4、输入串活前缀5、活前缀工程集合LR分析算法6、归约接受移进待约7、自左至右分析采用最右推导的逆过程即最左归约向右查看0个字符综合解答：首先将文法G拓广为G[S]:SfSSfAS|bAfSA|a1)文法G[S]的LR(0)工程是:1、S1、SfS2、SfS3、SfAS4、SfAS5、SfAS6、Sfb7、S-b,8、AfSA9、AfSA10、AfSA11、Afa12、Afa2、列出构成文法LR(0)工程集标准族.用e-CLOSURE(闭包)方法构造文法G'的LR(0)工程集标准族如下：Io：1、SfSI3：9、AfSA"12、A-a3、S-AS8、AfSAI7：7、S-b8、AfSA3、SfAS11、Afa6、Sfb6、Sfb11、Afa

9、A-SA4、S-AS8、A一SA3、S一AS11、A一a6、S-b3、S—,AS8、A一SA6、S—>,b11、A一aI2：4、S一A,SI5:5、S一AS,3、S—,AS9、A-SA6、S—>,b8、A一SA8、A一SA11、A一a11、A一a3、S一AS6、S-b注思：11中的S-,S•和A一•SA是由状态I.中的1和3读入一个S字符后得到的下一个工程;而I4中的A-SA和A-A-S那么是由I3中的9和3读入一个A字符后得到的下一个工程；中的SfAS•和A-S・A那么是由I4中的4和8读入一个S字符后得到的下一个工程.状态全体构成了文法G'的LR(0)标准族.11:2、S'一S,14：10、A-SAI5第七章、单项选择题1、中间代码生成所依据的是.d.等价变换规那么d.程序变量d.a+bd.等价变换规那么d.程序变量d.a+b+c/d2、四元式之间的联系是通过实现的.a.指示器b.临时变量c.符号表3、后缀式ab+cd+/可用表达式来表示.a.a+b/c+db.(a+b)/(c+d)c.a+b/(c+d)4、4、表达式3AVB)A(CVD)的逆波兰表示为rArABVACDVArBVCDVAABABVnCDVAArBVACDV।O।人入5、中间代码的树型表示ABCD所对应的表达式为a.A+B+C+Db.A+(B+C)+Dc.(A+B)+C+Dd.(A+B)+(C+D)6、四元式表示法的优点为a.不便于优化处理,a.不便于优化处理,但便于表的更动b.不便于优化处理,但节省存储空间c.便于优化处理,也便于表的更动d.便于表的更动,也节省存储空间7、终结符具有属性.a.传递b.继承c.抽象d.综合二、多顶选择题1、中间代码主要有a.四元式a.四元式d.后缀式e.间接三元2、下面中间代码形式中,能正确表示算术表达式a+b+c的有d.e.ad.e.a+b+cbca.ab+c+b.abc++c.+bc

ab3、在下面的语法制导译中,采用拉链-回填技术.a.赋值语句b.goto语句c.条件语句d.循环语句4、以下中间代码形式有益于优化处理.a.三元式b.四元式c.间接三元式d.逆波兰表示法e.树形表示法5、在编译程序中安排中间代码生成的目的是.a.便于进行存储空间的组织b.利于目标代码的优化c.利于编译程序的移植d.利于目标代码的移植e.利于提升目标代码的质量能正确表示算术表达式a+b*c能正确表示算术表达式a+b*c.题〕a.ab+c*b.abc*+7、三地址代码语句具体实现通常有表示方法.a.逆波兰表示b.三元式c.间接三元式d.树形表示e.四元式三、填空题1、中间代码有等形式,生成中间代码主要是为了使.2、语法制导译既可以用来产生代码,也可以用来产生指令,甚至可用来对输入串进行.3、当源程序中的标号出现“先引用后定义〞时,中间代码的转移地址须持时才能确定,因而要进行.4、文法符号的属性有两种,一种称为,另一种称为.5、后缀式abc-/所代表的表达式是,表达式(a-b)*c可用后缀式表示.6、用一张辅以的方法来表示中间代码,这种表示法称为间接三元式.四、综合题1、给出以下表达式的逆波兰表示(后缀式)：①a*(-b+c)②(AVB)A(CVrDAE)2、写出算术表达式：A+B*(C-D)+E/(C-D)TN的①四元式序列；②三元式序列；③间接三元式序列单项选择解答1、选Co2、四元式之间的联系是通过临时变量实现的,应选bo3、选bo4、选bo5、选do6、四元式表示法的优点与间接三元式相同,应选Co7、选do多项选择解答1、选a、c、d、e.2、b、d的中间代码不能正确表示a+b+c,而e不是中间代码：应选a、c.3-凡涉及到跳转的语句都需要采用拉链一一回填技术,应选b、c、d.4、选b、c.5、选b、do6、选b、e.7、选b、c、e.填空解答1、逆波兰记号、树形表示、三元式、四元式目标代码的优化容易实现2、中间目标解释执行3、标号定义回填4、继承属性综合属性5、a/(b-c)ab-c*6、间接码表三兀式表综合解答1、ab@c+*;ABVCDrEAVA

(1)(-,C,D,T1)(1)(-,C,D)⑴(1)(-CD)(2)(*,B,T1,T2)(2)(*,B,(1))⑵(2)(*,B,(1))(3)(+,A,T2,T3)(3)(+,A,(2))⑶(3)(+,A,(2))(4)(-,C,D,T4)(4)(-,C,D)⑴(4)(T,(1),N)(5)(T,T4,N,T5)(5)("(4),N)(4)⑸(/,E,(4))(6)(/,E,T5,T6)⑹(/,E,(5))⑸(6)(+,(3),(5))⑺(+,T3,T6,T7)⑺(+,(3),(6))(6)②表达式的二兀式序列③间接三元式序列2、①表达式的2、①表达式的四元式序列:一、单项选择题1、编译程序使用区别标识符的作用域.a.说明标识符的过程或函数名b.说明标识符的过程或函数的静态层次c.说明标识符的过程或函数的动态层次d.标识符的行号2、在目标代码生成阶段,符号表用于.a.目标代码生成b.语义检查c.语法检查d.地址分配3、过程信息表不包含.a.过程入口地址b.过程的静态层次c.过程名d.过程参数信息4、以下关于标识符和名字表达中,正确的选项是.a.标识符有一定的含义b.名字是一个没有意义的字符序列c.名字有确切的属性d.a~c都不正确二、多项选择题1、符号表的每一项均包含.a.名字栏b.类型栏c.信息栏d.值栏e.a~d均包含2、对编译程序所用到的符号表,涉及的操作有.a.填写或更新信息栏内容b.填入新名c.给定名字,访问它的有关信息d.杂凑技术e.线性表和排序二叉树3、源程序中的错误一般有.a.词法错误b.语法错误c.语义错误d.编译错误e.违反环境限制的错误三、填空题1、符号表中名字栏内容有两种填写方式,它们是填写和填写.

2、词法分析阶段的错误主要是,可通过的方法纠正错误.3、符号表中名字的有关信息在和过程中陆续填入.4、在目标代码生成阶段,符号表是的依据.四、问做题：1、在编译过程中为什么要建立符号表单项选择解答：1、b2、d3、b4、c多项选择解答：1、a、c2、a、b、c3、a、b、c、e填空解答：1、标识符标识符地址及长度2、拼写错误最小距离匹配3、词法分析语法语义分析4、地址分配问做题解答：在编译过程中始终要涉及到对一些语法符号的处理,这就需要用到语法符号的相关属性.为了在需要时能找到这些语法成分及其相关属性,就必须使用一些表格来保存这些语法成分及其属性,这些表格就是符号表.第九章一、单项选择题1、程序所需的数据空间在程序运行前可确定,称为治理技术.a.动态存储b.栈式存储c.静态存储d.堆式存储2、堆式动态分配申请和释放存储空间遵守原那么.a.先请先放b.先请后放c.后请先放d.任意3、静态分配允许程序出现.a.递归过程b.可变体积的数据工程c.静态变量d.待定性质的名字4、在编译方法中,动态存储分配的含义是.a.在运行阶段对源程序中的数组、变量、参数等进行分配b.在编译阶段对源程序中的数组、变量、参数进行分配c.在编译阶段对源程序中的数组、变量、参数等进行分配,在运行时这些数组、变量、参数的地址可根据需要改变d.以上都不正确5、在编译时有传名功能的高级程序语言是.a.Fortranb.Basicc.Pascald.ALGOL6、栈式动态分配与治理在过程返回时应做的工作有.a.保护SPb.恢复SPc.保护TOPd.恢复TOP二、多项选择题1、下面需要在运行阶段分配存储空间.a.数a.数组d.静态变量b.指针变量e.动态变量c.动态数组2、栈式动态分配允许a.递a.递归过程b.分程序结构c.动态变量d.d.动态数组e.静态数组3、动态存储分配可采用的分配方案有a.队a.队式存储分配b.栈式存储分配c.链式存储分配d.堆式存储分配e.线性存储分配4、栈式动态分配与治理因调用而进入过程之后,要做的工作是.a.定义新的活动记录的SP