编译原理一、单选题1、将编译程序分为若干个“遍”是为了()。
BA.提高程序的执行效率B.使程序的结构更加清晰C.利用有限的机器内存并提高机器的执行效率D.利用有限的机器内存但降低了机器的执行效率2、构造编译程序应掌握()。
DA.源程序B.目标语言C.编译方法D.以上三项都是3、变量应当()。
CA.持有左值B.持有右值C.既持有左值又持有右值D.既不持有左值也不持有右值4、编译程序绝大多数时间花在()上。
DA.出错处理B.词法分析C.目标代码生成D.管理表格5、()不可能是目标代码。
DA.汇编指令代码B.可重定位指令代码C.绝对指令代码D.中间代码6、编译程序是对()。
DA.汇编程序的翻译B.高级语言程序的解释执行C.机器语言的执行D.高级语言的翻译7、正规式M1和M2等价是指()。
CA.M1和M2的状态数相等B.M1和M2的有象弧条数相等C.M1和M2所识别的语言集相等D.M1和M2状态数和有象弧条数相等8、如果文法G是无二义的,则它的任何句子()。
AA.最左推导和最右推导对应的语法树必定相同。
B.最左推导和最右推导对应的语法树可能相同。
C.最左推导和最右推导必定相同。
D.可能存在两个不同的最左推导,但它们对应的语法树相同。
9、文法G:S→S+T|TT→T*P|PP→(S)|i句型P+T+i的短语有()BA.i,P+TB. P,P+T,i,P+T +iB.P+T + i D. P,P+T,i10、产生正规语言的文法为()。
DA.0型B.1型C.2型D.3型11、文法G:S→b|˄|(T)T→T˅S|S则FIRSTVT(T)=() CA.{b,˄,(}B.{b,˄,)}C.{b,˄,(,˅}D.{b,˄,),˅}12、给定文法:A→bA | cc,下面的符号串中,为该文法句子的是()。
A①cc ②bcbc ③bcbcc ④bccbcc ⑤bbbcc可选项有:A.①B.①③④⑤C.①④D.①④⑤13、采用自上而下分析,必须()。
CA.消除左递归B.消除右递归C.消除回溯D.提取公共左因子14、由文法的开始符经0步或多步推导产生的文法符号序列是()。
CA.短语B.句柄C.句型D.句子15、后缀式ab+cd+/可用表达式()来表示。
BA.a+b/c+dB.(a+b)/(c+d)C.a+b/(c+d)D.a+b+c/d16、语法分析器则可以发现源程序中的()。
DA.语义错误B.语法和语义错误C.错误并矫正D.语法错误17、在语法分析处理中,FIRST集合、FOLLOW集合、SELECT集合均是()。
BA.非终极符集B.终极符集D.字母表 D.状态集18、四种形式语言文法中,1型文法又称为()。
CA.短语结构文法B.前后文无关文法C.前后文有关文法D.正规文法19、优化可生成()的目标代码。
DA.运行时间较短B.占用存储空间较小C.运行时间短但占用内存空间大D.运行时间短且占用内存空间小20、四元式之间的联系是通过()实现的。
BA.指示器B.临时变量C.符号表D.程序变量二、多选题1、如果在文法G中存在一个句子,当其满足下列条件(BCD )之一时,则称该文法是二义文法。
A.其最左推导和最右推导相同B.该句子有两个不同的最左推导C.该句子有两个不同的最右推导D.该句子有两棵不同的语法树E.该句子对应的语法树唯一2、下面(BCD)语法制导翻译中,采用拉链—回填技术。
A、赋值语句B、布尔表达式的计算C、条件语句D、循环语句3、一般程序设计语言的定义都涉及到(ABC)3个方面。
A、语法B、语义C、语用D、程序基本符号的确定4、程序语言一般分为(A)和(B)。
A高级语言 B低级语言 C专用程序语言 D通用程序语言5、编译程序工作时,通常有(ABCD)阶段。
A、词法分析B、语法分析C、中间代码生成D、语义检查E、目标代码生成6、编译过程中,语法分析的任务是( BCD)。
A、分析单词是怎样构成的B、分析单词是如何构成语句和说明的C、分析语句和说明是如何构成程序的D、分析程序的结构7、语法分析的常用方法有(AB)。
A、自顶向下B、自底向上C、自左向右D、自右向左8、程序设计语言常见的数据类型有:(ABCD)A、数值型数据B、逻辑数据C、字符数据D、指针类型9、构造编译程序应掌握(ABC)。
A、源程序B、目标语言C、编译方法D、以上都不是10、编译程序前三个阶段完成的工作是(ABC)A、词法分析B、语法分析C、语义分析和中间代码生成D、代码优化11、一个上下文无关文法G 包括四个组成部分:一组终结符,一组非终结符,以及(BC)。
A、一组字符串B、一组产生式C、一个开始符号D、一个文法12、描述一个语言的文法是(C、D)。
A、唯一的B、不唯一的C、可能唯一D、也可能不唯一13、设有文法G[I]:I→I1|I0|Ia|Ic|a|b|c下列符号串中是该文法句子的有(BCD)。
A、ab0B、a0c01C、aaaD、bc1014、运行阶段的存储组织与管理的目的是(CD)。
A、提高编译程序的运行速度B、节省编译程序的存储空间C、提高目标程序的运行速度D、为运行阶段的存储分配做准备15、已知文法G[E]:E→TE’E’→+TE’∣εT→FT’T’→*FT’∣εF →(E)∣id 求:FOLLOW(F)=( D ),FIRST(T’)=( B )A、{*,+}B、{*,ε}C、{+,#,)}D、{*,+,#,)}E、{#,)}F、{*,+,#,id}16、面向机器语言的特点是(ABC)。
A、程序的执行效率高B、编制效率低C、可读性差D、可读性强17、编译程序使用(AB )区别标识符的作用域。
A、说明标识符的过程B、函数的静态层次C、函数的动态层次D、标识符的行号18、词法分析器的输出结果是(AD)A、单词的种别编码B、单词在符号表中的位置C、单词的长度D、单词自身值19、优化可生成(AD)的目标代码。
A、运行时间较短B、占用存储空间较大C、运行时间短且占用内存空间大D、占用存储空间小22、编译程序各阶段的工作都涉及到(BC)A、语法分析B、表格管理C、出错处理D、语义分析 F、词法分析三、填空题1.编译程序的工作过程一般可以划分为词法分析,语法分析,语义分析,中间代码生成,代码优化等几个基本阶段,同时还会伴有__表格处理___和___出错处理__。
2.若源程序是用高级语言编写的,___目标程序__是机器语言程序或汇编程序, 则其翻译程序称为 ___编译程序__ 。
3.编译方式与解释方式的根本区别在于__是否生成目标代码___。
4.对编译程序而言,输入数据是___源程序__, 输出结果是__目标程序___。
5.产生式是用于定义___语法成分__的一种书写规则。
6.语法分析最常用的两类方法是___自上而下__和___自下而上__分析法7.设 G 是一个给定的文法,S 是文法的开始符号,如果 S->x( 其中 x∈VT*), 则称 x 是文法的一个__句子___。
8.递归下降法不允许任一非终极符是直接__左___递归的。
9.常用的参数传递方式有___传地址__,传值和传名。
10.在使用高级语言编程时,首先可通过编译程序发现源程序的全部__语法___错误和语义的部分错误。
11.一个句型中的最左简单短语称为该句型的___句柄_。
12.一个典型的编译程序中,不仅包括__词法分析___、__语法分析___、__中间代码生成___、代码优化、目标代码生成等五个部分,还应包括表格处理和出错处理。
13.从功能上说,程序语言的语句大体可分为__执行性___语句和__说明性___语句两大类。
14.语法分析是依据语言的__语法___规则进行的,中间代码产生是依据语言的__语义___规进行的。
15.产生式是用于定义___语法成分__的一种书写规则。
16.计算机执行用高级语言编写的程序主要有两种途径:___解释__和__编译___。
17.局部优化是在__基本块___范围内进行的一种优化。
18.词法分析基于__正则___文法进行,即识别的单词是该类文法的句子。
19.语法分析基于__上下文无关___文法进行,即识别的是该类文法的句子。
语法分析的有效工具是__语法树___。
20.一个文法能用有穷多个规则描述无穷的符号串集合(语言)是因为文法中存在有___递归 __定义的规则。
四、名词解释(1)2型文法(上下文无关文法)若文法G=(V N,V T,P,S)中的每一条规则的形式为A→β,其中A∈V N,β∈(V N∪V T)*,则称G是2型文法。
(2)二义性文法如果一个文法存在某个句子对应两课不同的语法树,则称这个文法是二义性文法。
(3)有穷自动机是具有离散输入与输出系统的一种抽象数学模型。
(4)算符文法设有文法G,若G中没有形如U→…VW…的规则,其中V和W为非终结符,则称G为算符文法。
(5)素短语素短语是指这样一种短语,它至少包含一个终结符,并且除自身之外,不再包含其他任何更小的素短语。
(6)语法制导翻译法在语法分析过程中,根据相应文法的每一规则所对应的语义子程序进行翻译的方法。
(7)基本块指程序中一顺序执行的语句序列,其中只有一个入口和一个出口,入口就是其中的第一个语句,出口就是其中的最后一个语句。
(8)句柄一个句型的最左直接短语称为该句型的句柄。
(9)待用信息如果在一个基本块中,四元式i对A定值,四元式j要引用A值,而从i到j之间没有A的其它定值,则称j是四元式i的变量A的待用信息。
(10)局部优化局限于基本块范围的优化称。
五、应用题1.编译过程的5个阶段是什么?第1阶段:词法分析第2阶段:语法分析第3阶段: 词义分析与中间代码产生第4阶段:代码优化第5阶段:目标代码生成2.请给出编译程序的结构框图。
3.设有文法G[A]:A—>a|b|e|Aa|Ae|A0|A1(1)试问V T 和V N是由哪些符号组成的?V N={A}V T={a,b,e,0,1}(2)下列符号串a,ab0,a0e01,0a,11,eee是否为该文法的句子?a,a0e01,eee是该文法句子。
4.证明下面的文法是二义性的。
S—>iSeS|iS|i5.目标代码有哪几种形式?生成目标代码时通常应考虑哪几个问题?目标代码通常采用三种形式:机器语言,汇编语言,待装配机器语言模块。
应着重考虑的问题:(1)如何使生成的目标代码较短;(2)如何充分利用寄存器,以减少访问内存次数;(3)如何充分利用指令系统的特点。
6.基本的优化方法有哪几种?删除多余运算,代码外提,强度削弱,变换循环控制条件,合并已知量,复写传播和删除无用赋值。
7.构造下列正规式相应的DFA(用状态转换图表示)(1)1(0|1)*1(2)0*10*10*10*1(3)letter(letter|digit)*8.给出下述文法所对应的正规式。