当前位置:文档之家› 编译原理习题及答案(整理后)

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

第一章1、将编译程序分成若干个“遍”就是为了。

a.提高程序得执行效率b.使程序得结构更加清晰c.利用有限得机器内存并提高机器得执行效率d.利用有限得机器内存但降低了机器得执行效率2、构造编译程序应掌握。

a.源程序b.目标语言c.编译方法d.以上三项都就是3、变量应当。

a.持有左值b.持有右值c.既持有左值又持有右值d.既不持有左值也不持有右值4、编译程序绝大多数时间花在上。

a.出错处理b.词法分析c.目标代码生成d.管理表格5、不可能就是目标代码。

a.汇编指令代码b.可重定位指令代码c.绝对指令代码d.中间代码6、使用可以定义一个程序得意义。

a.语义规则b.语法规则c.产生规则d.词法规则7、词法分析器得输入就是。

a.单词符号串b.源程序c.语法单位d.目标程序8、中间代码生成时所遵循得就是- 。

a.语法规则b.词法规则c.语义规则d.等价变换规则9、编译程序就是对。

a.汇编程序得翻译b.高级语言程序得解释执行c.机器语言得执行d.高级语言得翻译10、语法分析应遵循。

a.语义规则b.语法规则c.构词规则d.等价变换规则二、多项选择题1、编译程序各阶段得工作都涉及到。

a.语法分析b.表格管理c.出错处理d.语义分析e.词法分析2、编译程序工作时,通常有阶段。

a.词法分析b.语法分析c.中间代码生成d.语义检查e.目标代码生成三、填空题1、解释程序与编译程序得区别在于。

2、编译过程通常可分为5个阶段,分别就是、语法分析、代码优化与目标代码生成。

3、编译程序工作过程中,第一段输入就是,最后阶段得输出为程序。

4、编译程序就是指将程序翻译成程序得程序。

单选解答1、将编译程序分成若干个“遍”就是为了使编译程序得结构更加清晰,故选b。

2、构造编译程序应掌握源程序、目标语言及编译方法等三方面得知识,故选d。

3、对编译而言,变量既持有左值又持有右值,故选c。

4、编译程序打交道最多得就就是各种表格,因此选d。

5、目标代码包括汇编指令代码、可重定位指令代码与绝对指令代码3种,因此不就是目标代码得只能选d。

6、词法分析遵循得就是构词规则,语法分析遵循得就是语法规则,中间代码生成遵循得就是语义规则,并且语义规则可以定义一个程序得意义。

因此选a。

7、b 8、c 9、d 10、c多选解答1.b、c 2、a、b、c、e填空解答就是否生成目标程序2、词法分析中间代码生成3、源程序目标代码生成4、源程序目标语言第二章一、单项选择题1、文法G:S→xSx|y所识别得语言就是。

a、xyxb、(xyx)*c、x n yx n(n≥0)d、x*yx*2、文法G描述得语言L(G)就是指。

a、L(G)={α|S+⇒α , α∈V T*}b、L(G)={α|S*⇒α, α∈V T*}c、L(G)={α|S*⇒α,α∈(V T∪V N*)}d、L(G)={α|S+⇒α, α∈(V T∪V N*)}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、最左推导与最右推导对应得语法树必定相同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,下面就是规范推导。

a、S⇒SA⇒SAA⇒AAA⇒aAA⇒abA⇒abab、S⇒SA⇒SAA⇒AAA⇒AAa⇒Aba⇒abac、S⇒SA⇒SAA⇒SAa⇒Sba⇒Aba⇒abad、S⇒SA⇒Sa⇒SAa⇒Sba⇒Aba⇒aba9、文法G:S→b|∧(T)T→T,S|S则FIRSTVT(T) 。

a、{b,∧,(}b、{b,∧,)}c、{b,∧,(,,}d、{b,∧,),,}10、产生正规语言得文法为。

a、0型b、1型c、2型d、3型11、采用自上而下分析,必须。

a、消除左递归b、消除右递归c、消除回溯d、提取公共左因子12、在规范归约中,用来刻画可归约串。

a、直接短语b、句柄c、最左素短语d、素短语13、有文法G:E→E*T|TT→T+i|i句子1+2*8+6按该文法G归约,其值为。

a、23 B、42 c、30 d、1714、规范归约指。

a、最左推导得逆过程b、最右推导得逆过程c、规范推导d、最左归约得逆过程二、多项选择题1、下面哪些说法就是错误得。

a、有向图就是一个状态转换图b、状态转换图就是一个有向图c、有向图就是一个DFAd、DFA可以用状态转换图表示2、对无二义性文法来说,一棵语法树往往代表了。

a、多种推导过程b、多种最左推导过程c、一种最左推导过程d、仅一种推导过程e、一种最左推导过程3、如果文法G存在一个句子,满足下列条件之一时,则称该文法就是二义文法。

a、该句子得最左推导与最右推导相同b、该句子有两个不同得最左推导c、该句子有两棵不同得最右推导d、该句子有两棵不同得语法树e、该句子得语法树只有一个4、有一文法G:S→ABA→aAb|εB→cBd|ε它不产生下面集合。

a、{a n b m c n d m|n,m≥0}b、{a n b n c m d m|n,m>0}c、{a n b m c m d n|n,m≥0}d、{a n b n c m d m|n,m≥0}e、{a n b n c n d n|n≥0}5、自下而上得语法分析中,应从开始分析。

a、句型b、句子c、以单词为单位得程序d、文法得开始符e、句柄6、对正规文法描述得语言,以下有能力描述它。

a、0型文法b、1型文法c、上下文无关文法d、右线性文法e、左线性文法三、填空题1、文法中得终结符与非终结符得交集就是。

词法分析器交给语法分析器得文法符号一定就是,它一定只出现在产生式得部。

2、最左推导就是指每次都对句型中得非终结符进行扩展。

3、在语法分析中,最常见得两种方法一定就是分析法,另一就是分析法。

4、采用语法分析时,必须消除文法得左递归。

5、树代表推导过程,树代表归约过程。

6、自下而上分析法采用、归约、错误处理、等四种操作。

7、Chomsky把文法分为种类型,编译器构造中采用与文法,它们分别产生与语言,并分别用与自动机识别所产生得语言。

四、判断题1、文法S→aS|bR|ε描述得语言就是(a|bc)* ( )R→c S2、在自下而上得语法分析中,语法树与分析树一定相同。

()3、二义文法不就是上下文无关文法。

()4、语法分析时必须先消除文法中得左递归。

()5、规范归约与规范推导就是互逆得两个过程。

()6、一个文法所有句型得集合形成该文法所能接受得语言。

()五、简答题1、句柄2、素短语3、语法树4、归约5、推导六、问答题1、给出上下文无关文法得定义。

2、文法G[S]:S→aSPQ|abQQP→PQbP→bbbQ→bccQ→cc(1)它就是Chomsky哪一型文法?(2)它生成得语言就是什么?3、按指定类型,给出语言得文法。

L={a i b j|j>i≥1}得上下文无关文法。

4、有文法G:S→aAcB|BdA→AaB|cB→bScA|b(1)试求句型aAaBcbbdcc与aAcbBdcc得句柄;(2)写出句子acabcbbdcc得最左推导过程。

5、对于文法G[S]:S→(L)|aS|a L→L, S|S(1)画出句型(S,(a))得语法树。

(2)写出上述句型得所有短语、直接短语、句柄与素短语。

6、考虑文法G[T]:T→T*F|FF→F↑P|PP→(T)|i证明T*P↑(T*F)就是该文法得一个句型,并指出直接短语与句柄。

单选[解答]1、选c。

2、选a。

3、选c。

4、虽然a与b没有优先关系,但构造优先函数后,a与b就一定存在优先关系了。

所以,由f(a)>g)(b)或f(a)<g(b)并不能判定原来得a与b之间就是否存在优先关系:故选c。

5、如果文法G无二义性,则最左推导就是先生长右边得枝叶:对于d,如果有两个不同得就是了左推导,则必然有二义性。

故选a。

6、选c。

7、由图2-8-1得语法树与优先关系可以瞧出应选b。

8、规范推导就是最左推导,故选d。

9、由T→T,…与T→(…得FIRSTVT(T))={(,,)};由T→S得FIRSTVT(S)⊂FIRSTVT(T),而FIRSTVT(T)={b,∧,(,,};因此选c。

10、d 11、c 12、b 13、b 14、b多选解答1、e、a、c 2、a、c、e 3、b、c、d 4、a填空解答1、空集终结符右2、最左3、自上而上自下而上4、自上而上5、语法分析6、移进接受7、4 2 型3型上下文无关语言正规语言下推自动机有限判断解答1、对2、错3、错4、错5、错6、错简答[解答]1、句柄:一个句型得最左直接短语称为该句型得句柄。

2、素短语:至少含有一个终结符得素短语,并且除它自身之外不再含任何更小得素短语。

3、语法树:满足下面4个条件得树称之为文法G[S]得一棵语法树。

①每一终结均有一标记,此标记为V N∪V T中得一个符号;②树得根结点以文法G[S]得开始符S标记;③若一结点至少有一个直接后继,则此结点上得标记为V N中得一个符号;④若一个以A为标记得结点有K个直接后继,且按从左至右得顺序,这些结点得标记分别为X1,X2,…,X K,则A→X1,X2,…,X K,必然就是G得一个产生式。

4、归约:我们称αγβ直接归约出αAβ,仅当A→γ就是一个产生式,且α、β∈(V N∪V T)*。

归约过程就就是从输入串开始,反复用产生式右部得符号替换成产生式左部符号,直至文法开始符。

5、推导:我们称αAβ直接推出αγβ,即αAβ⇒αγβ,仅当A→γ就是一个产生式,且α、β∈(V N∪V T)*。

如果α1⇒α2⇒…⇒αn,则我们称这个序列就是从α1至α2得一个推导。

若存在一个从α1αn得推导,则称α1可推导出αn。

推导就是归约得逆过程。

问答1[解答]一个上下文无关文法G就是一个四元式(V T,V N,S, P),其中:●V T就是一个非空有限集,它得每个元素称为终结符号;●V N就是一个非空有限集,它得每个元素称为非终结符号,V T∩V N=Φ;●S就是一个非终结符号,称为开始符号;●P就是一个产生式集合(有限),每个产生式得形式就是P→α,其中,P∈V N,α∈(V T∪V N)*。

相关主题