电子科技大学编译原理

《计算机编译原理》试卷A2参考答案一、单项选择题(每小题1分，共25分)构造编译程序应掌握—源程序8、目标语言变量应当一、单项选择题(每小题1分，共25分)构造编译程序应掌握—源程序8、目标语言变量应当C持有左值既持有左值又持有右值1、A、2、A、C、3、A、4、A、C、5、A、6、A、7、A、8、A、C、9、A、_D 。C、编译方法D、以上三项都是B、D、持有右值既不持有左值也不持有右值D编译程序绝大多数时间花在出错处理B、词法分析。、目标代码生成D、管理表格D不可能是目标代码。汇编指令代码B、可重定位指令代码绝对指令代码D、中间代码使用A可以定义一个程序的意义。语义规则 B、词法规则 C、产生规则词法分析器的输入是B。单词符号串 B、源程序 C、语法单位中间代码生成时所遵循的是C。语法规则B、词法规则C、语义规则D、编译程序是对D。汇编程序的翻译 B、高级语言程序的解释执行机器语言的执行D、高级语言的翻译文法G：S—xSx|y所识别的语言是CxyxB、(xyx)*C、xnyxn(n>0)D、x*yx*上。D、词法规则。、目标程序等价变换规则10、文法G描述的语言L(G)是指AA、A、L(G)={a|S方a,aEVT*}B、L(G)={a|S当a,aEVT*}C、L(G)={a|S当a,aE(VTUVN*)}D、L(G)={a|SEa,aE(VtUVn*)}11、有限状态自动机能识别C。A、上下文无关文法 B、上下文有关文法C、正规文法 D、短语文法12、 设G为算符优先文法，G的任意终结符对a、b有以下关系成立.A、若f(a)>g(b),则a>bB、若f(a)<g(b),则a<bC、A~B都不一定成立 D、A〜B一定成立13、 如果文法G是无二义的，则它的任何句子aA、A、B、C、D、最左推导和最右推导对应的语法树可能不同最左推导和最右推导必定相同可能存在两个不同的最左推导，但它们对应的语法树相同14、 由文法的开始符经0步或多步推导产生的文法符号序列是.A、短语B、句柄C、句型 D、句子15、 文法G：E—E+T|TT—T*P|P

P-(E)|I则句型P+T+i的句柄和最左素短语为B。A、P+T和iB、P和P+TC、i和P+T+iD、P和T16、 设文法为：S—SAIAA、B、C、D、A—a|bA、B、C、D、SnSAnSAAnAAAnaAAnabAnabaSnSAnSAAnAAAnAAanAbanabaSnSAnSAAnSAanSbanAbanabaSnSAnSanSAanSbanAbanaba17、 文法G：S—b|A(T)T—T,S|S则FIRSTVT(T)C。A、{b,A,(} B、{b,A,)}C、{b,A,(,,}D、{b,A,),,}18、产生正规语言的文法为DA、0型B、1型 C、2型D、3型19、 采用自上而下分析，必须C。A、消除左递归B、消除右递归C、消除回溯D、提取公共左因子20、在规范归约中，用B来刻画可归约串。A、直接短语B、句柄C、最左素短语D、素短语21、若一个文法是递归的，则它所产生的语言的句子 A。A、是无穷多个B、是有穷多个C、是可枚举的D、个数是常量22、词法分析器用于识别C。A、句子B、句型C、单词D、产生式23、 在语法分析处理中，FIRST集合、FOLLOW集合、SELECT集合均是.A、非终极符集B、终极符集C、字母表D、状态集24、编译程序中语法分析器接收以 A 为单位的输入。A、单词B、表达式C、产生式D、句子的DFA状态。25、 在LR分析法中，分析栈中存放的状态是识别规范句型A、句柄B、前缀C、活前缀D、LR(0)项目的DFA状态。二、判断题(每小题1分，共10分)(V)26、文法S—aS|bR|eR—cS描述的语言是(a|bc)*(X)27、在自下而上的语法分析中，语法树与分析树一定相同。(X)28、二义文法不是上下文无关文法。(X)29、语法分析时必须先消除文法中的左递归。(X)30、规范归约和规范推导是互逆的两个过程。(X)31、一个文法所有句型的集合形成该文法所能接受的语言。(X)32、一个有限状态自动机中，有且仅有一个唯一终态。(X)33、设r和s分别是正规式，则有L(r|s)=L(r)|L(s)。(X)34、自动机M和M'的状态数不同，则二者必不等价。(V)35、确定的自动机以及不确定的自动机都能正确地识别正规集。三、名词解释题(每小题4分，共8分)36、短语设G[Z]是给定文法，w=xuyEV+,为该文法的句型，如果满足下面两个条件:xUy；u；则称句型xuy中的子串u是句型xuy的短语。37、简单短语设G[Z]是给定文法，w=xuyEV+,为该文法的句型，如果满足下面两个条件:Z xUy；Uu；则称句型xuy中的子串u是句型xuy的简单短语（或直接短语）。四、 简答题（每小题4分，共8分）38、 给出上下文无关文法的定义。答：一个上下文无关文法G是一个四元式（VT,VN,S,P），其中：•VT是一个非空有限集，它的每个元素称为终结符号；•vn是一个非空有限集，它的每个元素称为非终结符号，vTnvN=o；•S是一个非终结符号，称为开始符号；•P是一个产生式集合（有限），每个产生式的形式是P—a，其中，PEVn，a£（VTUVN）*o开始符号S至少必须在某个产生式的左部出现一次。39、 简述DFA与NFA有何区别？答：DFA与NFA的区别表现为两个方面:一是NFA可以若干个开始状态，而DFA仅只一个开始状态。另一方面，DFA的映象M是从KXE到K,而NFA的映象M是从KXE到K的子集，即映象M将产生一个状态集合（可能为空集），而不是单个状态。五、 应用题（每小题5分，共25分）40、 已知文法G[E]为：e—tie+tie-tt—fit*fit/ff—（e）li该文法的开始符号（识别符号）是什么？请给出该文法的终结符号集合vt和非终结符号集合vn。找出句型T+T*F+i的所有短语、简单短语和句柄。解：①该文法的开始符号（识别符号）是Eo该文法的终结符号集合vt={+、-、*、/、（、）、i}。非终结符号集合Vn={E、T、F}o句型T+T*F+I的短语为i、T*F、第一个T、T+T*F+i;简单短语为i、T*F、第一个T;句柄为第一个T。41、已知文法G[S]为:S-dABA—aAlaB—BbleG[S]产生的语言是什么？G[S]能否改写为等价的正规文法？解：①G[S]产生的语言是L(G[S])={danbm|nN1,mN0}。②G[S]能改写为等价的正规文法,其改写后的等价的正规文法G[S']为:S'—dAA—aA|aB|aB—bB|b42、 按指定类型，给出语言的文法。L={aibj|j>iN1}的上下文无关文法。答：由L={abj|j>iN1}知，所求该语言对应的上下文无关文法首先应有S—aSb型产生式，以保证b的个数不少于a的个数；其次，还需有S—Sb或S—bS型的产生式，用以保证b的个数多于a的个数；也即所求上下文无关文法G[S]为：G[S]：S—aSb|Sb|b43、 有文法G：S—aAcB|BdA—AaB|cB—bScA|b试求句型aAaBcbbdcc和aAcbBdcc的句柄;写出句子acabcbbdcc的最左推导过程。(1)分别画出对应两句型的语法树，如下图所示句柄:AaB Bdb(2)句子acabcbbdcc的最左推导如下:SnaAcBnaAaBcBnacaBcBnacabcBnacabcbScAnacabcbBdcAnacabcbbdcAnacabcbbdcc44、考虑文法G[T]：T—T*F|FF—FfP|PP—(T)|i证明T*Pf(T*F)是该文法的一个句型，并指出直接短语和句柄。答：首先构造T*Pf(T*F)的语法树如下图所示。T*F由上图可知，T*Pf(T*F)是文法G[T]的一个句型。直接短语有两个，即P和T*F；句柄为P。六、综合题(每小题8分，共24分)45、构造下面文法的LL(1)分析表。D一TLT一int|realL一idRR一，idRI£答：求开始符号集合和后继符号集合：FIRST(D)=FIRST(T)={int,real}FOLLOW(D)=FOLLOW(L)={#}FIRST(L)={id} FOLLOW(T)={id}FIRST(R)={，,£} FOLLOW(R)={#}£是产生式R-£右部的一个开始符号，而#在FOLLOW(R)中，所以R-£填在输入符号#的栏目中。LL(1)分析表如下表所示非终结符输入符号intrealid，#DD—TLD—TLTT—intT—realLL—idRRR—,idRR—£46、已知文法：G[A]：A—aAaM该文法是LL(1)文法吗？为什么？若采用LL(1)方法进行语法分析，如何得到该文法的LL(1)分析表?若输入符号串“aaaa”，请给出语法分析过程。答：(1)因为产生式A—aAaM有空产生式右部，而FOLLOW(A)={#}UFIRST(a)={a,#}造成FIRST(A)nFOLLOW(A)={A,£}n{a,#}/0所以该文法不是LL(1)文法。

(2)若采用LL(1)方法进行语法分析，必须修改该文法。因该文法产生偶数(可以为0)个a,所以得到文法G'[A]：A—aaAle此时对产生式A—aaAlE，有FOLLOW(A)={#}UFOLLOW(A)={#}，因而FIRST(A)nFOLLOW(A)={a,e}n{#}=0所以文法G'[A]是LL(1)文法，按LL(1)分析表构造算法构造该文法的LL(1)分析表如下表所示。ab()d#a>>b>>(<<<互)>>d#<<<豆(2)((2)(3)答：(1)A#AA—aaAA—e(3)若采用LL(1)方法进行语法分析，对符号串“aaaa”的分析过程如下表所示。对符号串“aaaa”的分析过程步骤分析栈输入串产生式/动作1#Aaaaa#A—aaA2#Aaaaaaa#匹配3#Aaaaa#匹配4#Aaa#A—aaA5#Aaaaa#匹配6#Aaa#匹配7#A#A—e8##接受47、设有文法G[S]为：S—a|b|(A)A—SdA|S(1)完成下列算符优先关系表，并判断G[S]是否为算符优先文法。算符优先关系表给出句型(SdSdS)的短语、简单短语、句柄、素短语和最左素短语。给出输入串(adb)#的分析过程。先求文法G[S]的FIRSTVT集和LASTVT集：由S—a|b|(A)得：FIRSTVT(S)={a,b,();由A—Sd…得：FIRSTVT(A)={d};又由A—S…得：FIRSTVT(S)CFIRSTVT(A)，即FIRSTVT(A)={d,a,b,(};由S—a|b|(A)得；LASTVT(S)={a,b,}};由A—-dA得：LASTVT(A)={d}又由A—S得：LASTVT(S)CLASTVT(A),即LASTVT(A)={d,a,b,)}。构造优先关系表方法如下：对P—・・・ab…，或P—・・・aQb…，有a豆b;对P—•・aR…，而beFIRSTVT(R)，有a<b;对P—-Rb-，WaeFIRSTVT(R)，有a>bo由此得到：由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)A)，即：d>),a>),b>),)>);由A-Sd…得：LASTVT(S)X即：a>d,b>d,)>d;此外，由#S#得:#殍；由#<FIRSTVT(S)得：#<a,#<b,#<(；脂由LASTVT(S)>#得：d>#,a>#,b>#,)>#o最后得到算符优先关系表，如下表所示。算符优先关系表ab()d#a>>>b>>>(<<<豆)>>>d<<<><>#<<<豆由上表可以看出，任何两个终结符之间至少只满足-、＜、A三种优先关系之一，故G[S]^算符优先