编译原理期末考试选择题汇总.doc

一、单项选择题 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、高级语言编译程序常用的语法分析方法中,递归下降分析法属于 b 分析方法。可选项有：a、自左至右 b、自顶向下 c、自底向上 d、自右向左 6、已知文法GE： ETE E +TE TFT T FT F（E）id 求：FOLLOW（F）=（1） d , FIRST(T）=(2） b 可选项有： a、*,+ b、*, c、+，#，） d、*,+,，） e、#，） f、，+，#,id 7、中间代码生成时所遵循的是( C ) A语法规则 B词法规则 C语义规则 D等价变换规则8、编译程序是对( D ） A汇编程序的翻译 B高级语言程序的解释执行 C机器语言的执行 D高级语言的翻译9、词法分析应遵循（ C ) A语义规则 B语法规则 C构词规则 D等价变换规则10、词法分析器的输出结果是（ C ) A单词的种别编码 B单词在符号表中的位置 C单词的种别编码和属性值 D单词属性值11、正规式M1和M2等价是指（ C ) AM1和M2的状态数相等 BM1和M2的有向弧条数相等 CM1和M2所识别的语言集相等 DM1和M2状态数和有向弧条数相等12、词法分析器作为独立的阶段使整个编译程序结构更加简洁、明确，因此，( A ） A词法分析器应作为独立的一遍 B词法分析器作为子程序较好 C词法分析器分解为多个过程，由语法分析器选择使用 D词法分析器并不作为一个独立的阶段13、如果L（M1）=L(M2），则M1与M2( A ) A等价 B都是二义的 C都是无二义的 D它们的状态数相等14、文法G:SxSx|y所识别的语言是（ C ） Axyx B(xyx） cxnyxn（n0) dxyx15、文法G描述的语言L（G）是指（ A ) A B C D16、有限状态自动机能识别( C ) A上下文无关文法 B上下文有关文法 C正规文法 D短语文法17、编译过程中扫描器的任务包括 d 。组织源程序的输入 按词法规则分割出单词,识别出其属性，并转换成属性字的形式输出 删除注解 删除空格及无用字符 行计数、列计数 发现并定位词法错误 建立符号表可选项有：a、 b、 c、 d、18、正则式的“读作（1） b ，“读作（2) c ，“”读作(3） d 。可选项有:a、并且 b、或者 c、连接 d、闭包19 、 b 这样一些语言,它们能被确定的有穷自动机识别，但不能用正则表达式表示。可选项有：a、存在 b、不存在 c、无法判定是否存在20、编译过程中，语法分析的任务是 c 。分析单词是怎样构成的 分析单词是如何构成语句和说明的分析语句和说明是如何构成程序的 分析程序的结构可选项有：a、和 b、 c、 d、 21、语法分析的常用方法有 b 。自顶向下 自底向上 自左向右 自右向左可选项有：a、 b、 c、 d、 22、如果文法G是无二义的，则它的任何句子( A ) A最左推导和最右推导对应的语法树必定相同 B最左推导和最右推导对应的语法树可能不同 C最左推导和最右推导必定相同 D可能存在两个不同的最左推导，但它们对应的语法树相同23、由文法的开始符经0步或多步推导产生的文法符号序列是( C ） A短语 B句柄 C句型 D句子24、文法G：EE+TT TTPP P（E）|i则句型P+T+i的句柄为（ B ) AP+T BP CP+T+i Di25、文法G：Sb(T) TTS|S则FIRSTVT(T)=（ C ） A b，( B b，） C b，(， D b，）， 26、产生正规语言的文法为（ D ) A0型 B1型 C2型 D3型27、任何算符优先文法（ D ）优先函数。 A有一个 B没有 C有若干个 D可能有若干个28、采用自上而下分析，必须（ C ) A消除左递归 B消除右递归 C消除回溯 D提取公共左因子29、素短语是指 D 的短语。至少包含一个符号 至少包含一个终结符号 至少包含一个非终结符号 除自身外不再包含其他终结符号 除自身外不再包含其他非终结符号 除自身外不再包含其他短语 除自身外不再包含其他素短语可选项有:A、 B、 C、 D、30、给定文法AbAcc，下面的符号串中，为该文法句子的是 A 。cc bcbc bcbcc bccbcc bbbcc可选项有：A、 B、 C、 D、 31、已知文法 GS： SeTRT TDR RdR Dabd则FOLLOW（T)= D .可选项有:A、d B、a，b C、a,b,# D、# E、d，#32、正则式中的 “”读作 D 。可选项有：A、并且 B、或者 C、连接 D、闭包33、在规范归约中,用（ B )来刻画可归约串. A直接短语 B句柄 C最左素短语 D素短语34、有文法G:EE*TT TT+ii句子1+2*8+6按该文法G归约，其值为（ B ) A23 B42 C30 D1735、如果文法是无二义的,那么规范归约是指( B ) A最左推导的逆过程 B最右推导的逆过程 C规范推导 D最左归约的逆过程36、文法G:SS+T|T TT*P|P P（S）|i句型P+T+i的短语有( B ) Ai，P+T BP，P+T,i,P+T+i CP+T+i DP，P+T，i37、高级语言编译程序常用的语法分析方法中，递归下降分析法属于 b 分析方法。可选项有：A、自左至右 B、自顶向下 C、自底向上 D、自右向左 38、一般程序设计语言的定义都涉及 A 三个方面。语法 语义 语用 程序基本符号的确定可选项有：A、 B、 C、 D、39、编译过程中,语法分析器的任务是 B 。分析单词是怎样构成的 分析单词串是如何构成语句和说明的 分析语句和说明是如何构成程序的 分析程序的结构可选项有:A、 B、 C、 D、40、编译程序生成的目标程序 B 是机器语言的程序.可选项有：A、一定 B、不一定 C、无法判断 D、一定不 一、单项选择题（将正确答案的字母填入括号，每题1。5分，共30分）1、一般程序设计语言的定义都涉及到（ 1.2.3)3个方面。（1)语法 （2）语义 （3）语用 (4)程序基本符号的确定2、程序语言一般分为（ 1 ）和( 2 )。(1)高级语言；（2）低级语言；（3）专用程序语言;(4)通用程序语言3、面向机器语言指的是( B ）。A用于解决机器硬件设计问题的语言B特定计算机系统所固有的语言C各种计算机系统都通用的语言D只能在一台计算机上使用的语言4面向机器语言的特点是（ D )。A程序的执行效率低，编制效率低,可读性差B程序的执行效率高，编制效率高，可读性强C程序的执行效率低,编制效率高，可读性强D程序的执行效率高，编制效率低，可读性差5、程序设计语言常见的数据类型有:1。2.3.4（1)数值型数据 （2）逻辑数据 （3）字符数据 （4）指针类型6、下列程序设计语言中是应用式语言的是：BA、PASCAL B、LISP C、VB D、PROLOG7、任何语法结构都可以用（ C )来表示.A、语法树 B、树 C、抽象语法树 D、二义文法树8、字母表是符号的有穷集合,由（ C ）组成词和句子。A、字符串 B、字符 C、符号 D、语言9、下列符号是终结符的是（ A)。A、c B、A C、S D、10、语法树用（ C )关系说明了句子中以操作符为核心的操作顺序，同时也说明了每一个操作符的操作对象.A、上下 B、先后 C、层次 D、关联11、循环语句的语法树为（ D ）A、 B、 C、 D、12、表达式中间代码的生成可采用（ B ）。A、三地址代码 B、四元式 C、三元式 D、间接三元式13、下列文法中，赋值语句的文法是（ C ）。A、 B、 C、 D、EE op E 14、词法分析的任务是（ A ）A、识别单词 B、分析句子的含义 C、识别句子 D、生成目标代码15、常用的中间代码形式中不含( D )A、三元式 B、四元式 C、 逆波兰式 D、语法树16、代码优化的目的是（ C ）A、节省时间 B、节省空间 C、节省时间和空间 D、把编译程序进行等价转换17、代码生成阶段的主要任务是（ C ）A、把高级语言翻译成汇编语言 B、把高级语言翻译成机器语言 C、把中间代码变换成依赖具体机器的目标代码 D、把汇编语言翻译成机器语言18、词法分析器的输入是（ B )A、单词符号串 B、源程序 C、语法单位 D、目标程序19、中间代码的生成所遵循的是（ C ）A、语法规则 B、词法规则 C、语义规则 D、等价变换规则20、编译程序是对（ D )A、汇编程序的翻译 B、高级语言程序的解释并执行 C、机器语言的执行 D、高级语言的翻译21、语法分析应遵循（ C ）A、语义规则 B、语法规则 C、构词规则 D、等价变换规则 22、编译程序各阶段的工作都涉及到（ B ）A、语法分析 B、表格管理、出错处理 C、语义分析 D、词法分析23、编译程序工作时,通常有（ 1.2.3.4 ）阶段。（1）词法分析 （2）语法分析 （3)中间代码生成 （4)语义检查 （5）目标代码生成24、由文法的开始符经0步或多步推导产生的文法符号序列是 C 。A、短语 B、句柄 C、句型D、句子25、产生正规语言的文法为 D 。A、0型 B、1型 C、 2型D、3型26、对无二义性文法来说,一棵语法树往往代表了 D .（1） 多种推导过程（2） 多种最左推导过程（3)一种最左推导过程（4）仅一种推导过程（5）一种最左推导过程A、 B、(1）(3）（5) C、 D27、如果文法G存在一个句子,满足下列条件 之一时,则称该文法是二义文法。BCDa。 该句子的最左推导与最右推导相同 b. 该句子有两个不同的最左推导c。 该句子有两棵不同的最右推导 d. 该句子有两棵不同的语法树 e。该句子的语法树只有一个28、优化可生成( D ）的目标代码。A、运行时间较短 B、占用存储空间较小 C、运行时间短且占用内存空间大 D、运行时间短且存储空间小29、构造编译程序应掌握（ D )A、源程序 B、目标程序 C、编译方法 D、以上三项都是30、赋值语句x=a+b*cd的逆波兰式为（ B）A、xab+c*d-= B、xabc+d= C、xabcd*+= D、x=abc+d-31、词法分析器的输出结果是（ C )A、单词的种别编码 B、单词在符号表中的位置 C、单词的种别编码和自身值 D、单词自身值编译原理期末试题（一）一、是非题（请在括号内，正确的划，错误的划)(每个2分，共20分）1编译程序是对高级语言程序的解释执行。（ )2一个有限状态自动机中，有且仅有一个唯一的终态。()3一个算符优先文法可能不存在算符优先函数与之对应。 ( ）4语法分析时必须先消除文法中的左递归 。 （）5LR分析法在自左至右扫描输入串时就能发现错误，但不能准确地指出出错地点。 (）6逆波兰表示法表示表达式时无须使用括号。 （ )7静态数组的存储空间可以在编译时确定。 ()8进行代码优化时应着重考虑循环的代码优化，这对提高目标代码的效率将起更大作用。 ()9两个正规集相等的必要条件是他们对应的正规式等价。 ( )10一个语义子程序描述了一个文法所对应的翻译工作。 (）二、选择题（请在前括号内选择最确切的一项作为答案划一个勾，多划按错论）(每个4分，共40分）1词法分析器的输出结果是_.A( ) 单词的种别编码 B( ) 单词在符号表中的位置 C( ) 单词的种别编码和自身值 D（ ） 单词自身值2 正规式 M 1 和 M 2 等价是指_. A( ） M1和M2的状态数相等 B（ ） M1和M2的有向边条数相等C( ） M1和M2所识别的语言集相等 D（ ) M1和M2状态数和有向边条数相等 3 文法G：SxSxy所识别的语言是_。A（ ） xyx B（ ) （xyx） C( ) xnyxn（n0) D（ ） xyx* 4如果文法G是无二义的，则它的任何句子_.A（ ）最左推导和最右推导对应的语法树必定相同 B( ） 最左推导和最右推导对应的语法树可能不同 C（ ) 最左推导和最右推导必定相同 D（ ）可能存在两个不同的最左推导，但它们对应的语法树相同 5构造编译程序应掌握_。A（ ）源程序B（ ） 目标语言 C( ) 编译方法 D( ) 以上三项都是 6四元式之间的联系是通过_实现的。 A( ) 指示器 B（ ) 临时变量 C( ) 符号表 D( ） 程序变量 7表达式(AB）(CD)的逆波兰表示为_。A. （ ） ABCD B（ ） ABCD C( ） ABCD D( ) ABCD 8。 优化可生成_的目标代码。A( ) 运行时间较短 B（ ） 占用存储空间较小C( ） 运行时间短但占用内存空间大 D( ） 运行时间短且占用存储空间小9下列_优化方法不是针对循环优化进行的。A. ( ) 强度削弱 B( ） 删除归纳变量 C（ ） 删除多余运算 D( ) 代码外提10编译程序使用_区别标识符的作用域. A。 ( ) 说明标识符的过程或函数名B（ ） 说明标识符的过程或函数的静态层次C( ） 说明标识符的过程或函数的动态层次 D. ( ) 标识符的行号编译原理期末试题（二）1、描述由正规式b(abb*)*(a e)定义的语言，并画出接受该语言的最简DFA。2、证明文法E E + id | id是SLR(1)文法。5、下面C语言程序经非优化编译后,若运行时输入2，则结果是area=12.566360, addr=1073743076经优化编译后，若运行时输入2，则结果是area=12.566360, addr=-1073743068请解释为什么输出结果有区别。main（） float s， pi, r; pi=3。14159; scanf（f”, r）； printf（area=%f, addr=dn, s=pi*rr, r）;6、描述由正规式b*a(bb*a) *b*定义的语言，并画出接受该语言的最简DFA。7、下面的文法产生代表正二进制数的0和1的串集：B B 0 B 1 | 1下面的翻译方案计算这种正二进制数的十进制值：B B1 0B。val ：= B1。val 2 | B1 1B.val ：= B1。val 2 +1 1 B.val ：= 1 请消除该基础文法的左递归，再重写一个翻译方案，它仍然计算这种正二进制数的十进制值.8、在C语言中,如果变量i和j都是long类型，请写出表达式&i和表达式&i-j的类型表达式.为帮助你回答问题，下面给出一个程序作为提示，它运行时输出1。main（） long i, j；printf（“%dn”, i-&j)；9、一个C语言的函数如下：func（i) long i； long j；j = i 1;func(j);下面左右两边的汇编代码是两个不同版本GCC编译器为该函数产生的代码。左边的代码在调用func之前将参数压栈,调用结束后将参数退栈.右边代码对参数传递的处理方式没有实质区别。请叙述右边代码对参数传递的处理方式并推测它带来的优点。func：|func：pushlebp|pushlebpmovlesp, ebpmovlesp, %ebpsubl4, %espsubl8， espmovl8(ebp), %edx|movl8(%ebp）, %eaxdecledx|decleaxmovl%edx， 4（ebp）movleax, -4（%ebp）movl4(ebp)， %eaxmovl4（ebp)， %eaxpushl%eaxmovl%eax， （esp）callfunccallfuncaddl4， espleaveleave|retret编译原理试卷八答案start1abb21、由正规式b*(abb*）(a e）定义的语言是字母表a， b上不含子串aa的所有串的集合。最简DFA如下：2、先给出接受该文法活前缀的DFA如下:E EE E + idE idI0E EE E+ idI1E idI2Eid+E E +idI3E E + idI4idI0和I3都只有移进项目,肯定不会引起冲突；I2和I4都无移进项目并仅含一个归约项目，也肯定不会引起冲突;在I1中，E的后继符号只有$，同第2个项目的展望符号“+不一样，因此I1也肯定不会引起冲突。由此可以断定该文法是SLR(1）的。3、语法制导定义如下。S id := E S.type ：= if (id.type = bool and E.type = bool） or (id。type = int and E.type = int)then type_ok else type_error E E1 and E2 E。type := if E1。type = bool and E2.type = bool then bool else type_error E E1 + E2 E.type ：= if E1。type = int and E2.type = int then int else type_error E E1 = E2 E.type := if E1。type = int and E2.type = int then bool else type_error E id E。type := lookup（id。entry） 4、对于函数f1，局部变量x声明的作用域是整个函数体，导致在函数体中不可能访问形式参数x。由于这是一个合法的C语言函数，因此编译器给出警告错误。对于函数f2,由于局部变量x的作用域只是函数体的一部分，不会出现上述问题，因而编译器不报错。5、使用非优化编译时,变量s， pi, r在局部数据区都分配4个字节的空间。使用优化编译时，由于复写传播，pir*r 变成3.14159*r*r,pi=3.14159成为无用赋值而删去，函数中不再有pi的引用，因此不必为pi分配空间。类似地,s=3。14159r*r也是一个无用赋值(表达式要计算,但赋值是无用的），也不必为s分配空间。这样,和非优化情况相比，局部数据区少了8个字节， 因此r的地址向高地址方向移动了8个字节。6、正规式b*a（bb*a) *b*体现的特点是，每个a的左边都有若干b，除非a是第一个字母。该正规式定义的语言是：至少含一个a，但不含子串aa的所有a和b的串集。最简DFA如下：start2abb10ab7、消除左递归后的文法：B 1 BB 0 B 1 B e相应的翻译方案如下：B 1 B。i := 1 BB。val := B.valB 0 B1。i := B。i 2 B1 B.val := B1.val| 1 B1。i ：= B.i 2 +1 B1 B.val ：= B1。val| e B。val := B.i8、表达式i的类型表达式是pointer（long），表达式i-&j的类型表达式是long。按照C语言的规定，指向同一个类型的两个指针可以相加减,它们值的差是它们之间的元素个数。9、左边的编译器版本：一般只为局部变量分配空间.调用函数前，用若干次pushl指令将参数压栈，返回后用addl $n， %esp一次将所有参数退栈（常数n根据调用前做了多少次pushl来决定）.右边的编译器版本：除了为局部变量分配空间外,同时还为本函数中出现的函数调用的参数分配空间，并且参数所用空间靠近栈顶。调用函数前，用movl指令将参数移入栈顶，调用结束后无需参数退栈指令。优点是每次函数调用结束后不需要执行addl $n, %esp指令，另外增加优化的可能性。编译原理期末试题（三）1、 从优化的范围的角度，优化可以分哪两类？对循环的优化可以有哪三种？ 答：从优化的范围的角度，优化可以分为局部优化和全局优化两类；对循环的优化有三种：循环不变表达式外提、归纳变量删除与计算强度削减。2、写出表达式a=b*c+bd对应的逆波兰式、四元式序列和三元式序列。 答：逆波兰式： abc*bd*+：= 四元式序列：三元式序列： OP ARG1 ARG2（1) （*， b， c, t1) （1) （ b， c ）（2） (， b， d, t2) (2） （ b, d )(3) （+， t1， t2,t3) （3） （+ （1）， (2）(4) （:=, t3， /， a）(4) (:= (3)， a)3、对于文法G(S)： SbM(TMabL)答：1) 2） 短语: Ma), （Ma）， b(Ma)b直接短语： Ma） 句柄: Ma）三、 设有字母表a,b上的正规式R=（ab|a）。 解：（1)0123baa-+(2）将（1）所得的非确定有限自动机确定化ab01131221+3ab-+013123+12312313+13123012aaba-+（3)对(2）得到的DFA化简，合并状态0和2 为状态2：12aab-+（4）令状态1和2分别对应非终结符B和AG： AaB|a|； BaBbA|ab|；可化简为:G: AaB|；BaBbA四、 设将文法G改写成等价的LL(1）文法，并构造预测分析表。 G：SS*aT|aTaT； T+aT|+a 解：消除左递归后的文法G： SaTSaTSS*aTS|T+aT+a 提取左公因子得文法G：SaTS|aTSS*aTST+aTTT Select(SaTS)=aSelect(S*aTS）=Select（SaTS)Select（S*aTS）=Select（SaTS）=Select（S）=Follow（s)=Select（S*aTS)Select（S)= Select（T+aT）=+Select(TT)=First（T) =+Select(T ）=Follow（T）=*，Select（TT）Select(T)= 所以该文法是LL（1）文法.预测分析表： +a#SaTSaTSSaTST+aTT T 6设文法G 为: SA；ABA；BaBb解：（1）拓广文法G:(0） SS （1） SA (2） ABA(3) A(4) BaB (5) Bb ； FIRST(A) = ， a， b;FIRST(B) = a， b构造的DFA 如下:项目集规范族看出，不存在冲突动作。该文法是LR（1)文法。（2） LR(1）分析表如下: (3)输入串abab 的分析过程为：简答题 3、设有文法GS: SS(S)S,该文法是否为二义文法？说明理由. 答：是二义的,因为对于（）(）可以构造两棵不同的语法树。 S S S （ S ） S S ( S ） S S ( S ) S S （ S ) S 五、 给定文法GS： SaAbQ； AaA|bB|b;BbD|aQ ；QaQ|bD|b；DbB|aA ；EaB|bF FbDaEb构造相应的最小的DFA 。 解：先构造其NFA： 用子集法将NFA确定化： abSAQAABZQQDZBZQDDZABDABBQD将S、A、Q、BZ、DZ、D、B重新命名，分别用0、1、2、3、4、5、6表示。因为3、4中含有z，所以它们为终态。ab012113224325416516625令P0(0,1，2，5,6，3,4）用b进行分割： P1(0，5， 6,1,2,3,4）再用b进行分割： P2（0，5, 6，1，2，3,4)再用a、b 进行分割,仍不变。 再令为A，1,2为B，3,4为C,5,6为D。 最小化为右上图。六、 对文法G(S）：S a | | （T）;T T，S | S 答：（1) a（)，a（=）,#=（2） 是算符优先文法，因为任何两个终结符之间至多只有一种优先关系.(2分）(3) 给出输入串(a，a）#的算符优先分析过程.步骤 栈当前输入字符剩余输入串动作1#(a,a#( 移进2(a,a）（, 归约4#(N,a）（, 移进5#（N，a）#，) 归约7#（N,N），） 归约8#（N）#(=) 移进9#(N）) 归约10N#接受编译原理期末试题(四）二、构造下列正规式相应的DFA(用状态转换图表示）(15)（1） 1（0 1）10,1（2） 01010101（3） letter（letter | digit）31021（1）0051（2)104130211letter(3）2letter1digit三、给出下面语言的相应文法:（15）L1=an bn | n1 L2=anbm+nam n1，m0 G1： SAB AaAb | ab BbBa | G1： AaAb |ab 四、对下面的文法G: Sa b （T）TT，S S（1) 消去文法的左递归,得到等价的文法G2；(2） 判断文法G2是否LL(1）文法，如果是，给出其预测分析表。(15）G2: Sa b （T) T ST T，S T G2是LL（1）文法.ab（）,SSa Sb S（T)TT STT STT STTT T，S T