编译原理试题
一、单项选择题
1.将编译程序分成若干个“遍”是为了( B ) A.提高程序的执行效率 B. 使程序的结构更加清晰
C.利用有限的机器内存并提高机器的执行效率
D.利用有限的机器内存但降低了机器的执行效率 2.不可能是目标代码的是( D )
A.汇编指令代码 B.可重定位指令代码 C.绝对指令代码 D.中间代码 3.词法分析器的输入是( B ) A.单词符号串 B.源程序 C.语法单位 D.目标程序 4.中间代码生成时所遵循的是( C ) A.语法规则 B.词法规则 C.语义规则 D.等价变换规则 5.编译程序是对( D )
A.汇编程序的翻译 B.高级语言程序的解释执行 C.机器语言的执行 D.高级语言的翻译 6.词法分析应遵循( C )
A.语义规则 B.语法规则 C.构词规则 D.等价变换规则 7.词法分析器的输出结果是( C )
A.单词的种别编码 B.单词在符号表中的位置 C.单词的种别编码和属性值 D.单词属性值 8.正规式M1和M2等价是指( C )
A.M1和M2的状态数相等 B.M1和M2的有向弧条数相等
C.M1和M2所识别的语言集相等 D.M1和M2状态数和有向弧条数相等
9.词法分析器作为独立的阶段使整个编译程序结构更加简洁、明确,因此,( B ) A.词法分析器应作为独立的一遍 B.词法分析器作为子程序较好
C.词法分析器分解为多个过程,由语法分析器选择使用 . D.词法分析器并不作为一个独立的阶段 10.如果L(M1)=L(M2),则M1与M2( A ) A.等价 B.都是二义的
1
C.都是无二义的 D.它们的状态数相等 11.文法G:S→xSx|y所识别的语言是( C )
*nn**
A.xyx B.(xyx) c.xyx(n≥0) d.xyx 12.文法G描述的语言L(G)是指( A )
?????*? A.L(G)???|S??,??VT? B.L(G)???|S??,??(VT?VN)*? ????**???*? C.L(G)???|S??,??VT? D.L(G)???|S??,??(VT?VN)*? ????13.有限状态自动机能识别( C )
A.上下文无关文法 B.上下文有关文法 C.正规文法 D.短语文法
14.如果文法G是无二义的,则它的任何句子( A ) A.最左推导和最右推导对应的语法树必定相同 B.最左推导和最右推导对应的语法树可能不同 C.最左推导和最右推导必定相同
D.可能存在两个不同的最左推导,但它们对应的语法树相同 15.由文法的开始符经0步或多步推导产生的文法符号序列是( C ) A.短语 B.句柄 C.句型 D.句子 16.文法G:E→E+T|T T→T*P|P P→(E)|i
则句型P+T+i的句柄为( B )
A.P+T B.P C.P+T+i D.i 17.文法G:S→b|∧|(T) T→T∨S|S 则FIRSTVT(T)=( C )
A.{ b,∧,( } B.{ b,∧,) } C.{ b,∧,(,∨ } D.{ b,∧,),∨ } 18.产生正规语言的文法为( D )
A.0型 B.1型 C.2型 D.3型 19.任何算符优先文法( D )优先函数。
A.有一个 B.没有 C.有若干个 D.可能有若干个 20.采用自上而下分析,必须( A ) A.消除左递归 B.消除右递归 C.消除回溯 D.提取公共左因子
2
21.在规范归约中,用( B )来刻画可归约串。
A.直接短语 B.句柄 C.最左素短语 D.素短语 22.有文法G:E→E*T|T T→T+i|i
句子1+2*8+6按该文法G归约,其值为( B ) A.23 B.42 C.30 D.17
23.如果文法是无二义的,那么规范归约是指( B ) A.最左推导的逆过程 B.最右推导的逆过程 C.规范推导 D.最左归约的逆过程 24.文法G:S→S+T|T T→T*P|P P→(S)|i 句型P+T+i的短语有( B )
A.i,P+T B.P,P+T,i,P+T+i C.P+T+i D.P,P+T,i 25.四元式之间的联系是通过( B )实现的。
A.指示器 B.临时变量 C.符号表 D.程序变量 26.后缀式ab+cd+/可用表达式( B )来表示。
A.a+b/c+d B.(a+b)/(c+d) C.a+b/(c+d) D.a+b+c/d 27.使用间接三元式表示法的主要目的( A ) A.便于优化处理 B.便于表的修改
C.节省存储空间 D.生成中间代码更容易 28.表达式(┐A∨B)∧(C∨D)的逆波兰表示为( B ) A.┐AB∨∧CD∨ B.A┐B∨CD∨∧ C.AB∨┐CD∨∧ D.A┐B∨∧CD∨
二、判断题
1.一个确定有限状态自动机中,有且仅有一个唯一的终态。 (╳) 2.设R和S分别是字母表∑上的正规式,则有L(R|S)=L(R)∪L(S)。 (√) 3.自动机M1和M2的状态数不同,则二者必不等价。 (╳)
4.确定有限自动机以及非确定有限自动机都能正确地识别正规集。 (√)5.对任意一个右线性正规文法G,都存在一个NFA M,满足L(G)=L(M)。 (√) 6.对任意一个右线性正规文法G,都存在一个DFA M,满足L(G)= L(M)。(√) 7.对任何正规式e,都存在一个NFA M,满足L(M)=L(e)。(√) 8.对任何正规式e,都存在一个DFA M,满足L(M)=L(e)。(√) 9.从一个句型到另一个句型的推导过程是唯一的。(╳) 10.词法分析作为单独的一遍来处理较好。 (╳)
3
11.一张转换图只包含有限个状态,其中有一个被认为是初态,最多只有一个终态。(╳) 12.二义文法不是上下文无关文法。(╳)
13.自上而下分析法是一种“移进—归约”法。(╳) 14.文法是描述语言的语法结构的形式规则。(√) 15.产生式是定义语法范畴的一种书写规则。(√)
16.要构造行之有效的自上而下的分析器,则必须消除左递归。(╳)
17.如果文法G是无二义的,那么规范归约和规范推导是互逆的两个过程。(√) 18.自下而上的分析法是一种“移进—归约”法。(√)
19.如果文法G是二义的,那么规范归约和规范推导是互逆的两个过程。(╳)
三、填空题
1.解释程序和编译程序的区别在于(是否生成目标代码)。 2.编译过程通常可分为5个阶段,分别是(词法分析)、(语法分析)、语义分析与中间代码产生、代码优化和目标代码生成。
3.编译程序工作过程中,第一阶段输入是(源程序),最后阶段的输出为(目标代码)程序。
4.把语法范畴翻译成中间代码所依据的是(语义规则)。
5.目标代码可以是(汇编)指令代码或(可重定位)指令代码或绝对机器指令代码。 6.词法分析的任务是:输入源程序,对构成源程序的(字符串)进行扫描和分解。 7.源程序中的错误通常分为(语法错误)和(语义错误)两大类。 8.(编译程序)是将源程序翻译成目标程序的程序。 9.一个上下文无关文法G包括四个部分:(终结符号)、(非终结符号)、(开始符号)和一组(产生式)。
10.若?1??2????n,则称这个序列是从?1到?n的一个(推导)。 11.设文法G的开始符号为S,如果S??则称?是L(G)的一个(句型)。
12.文法G所产生的句子的全体是文法G所定义的(语言)。
13.若一个文法存在某个句子对应的两棵不同的语法树,则称这个文法是(二义文法)。 14.程序语言的单词符号一般可分为五种:(关键字)、(标识符)、常数、(运算符)和界符。
15.(确定有限自动机DFA)是非确定有限自动机NFA的一个特例。
16.对于正规文法G和有限自动机M,若L(G)=L(M),则称G和M是(等价)的。 17.若两个正规式所表示的正规集相等,则认为二者是(等价)的。 18.按照语法分析树的建立方法,语法分析可分为两类:(自上而下分析)和(自下而上分析)。
18.规范归约中的可归约串是指(句柄)。
4
*