《编译原理期末考试题目及答案》由会员分享，可在线阅读，更多相关《编译原理期末考试题目及答案（17页珍藏版）》请在金锄头文库上搜索。
1、、填空题（每空 2 分，共 20分）1编译程序首先要识别出源程序中每个单词，然后再分析每个 句子 并翻译其意义。2编译器常用的语法分析方法 有自底向上 和 自顶向下 两种。3通常把编译过程分为分析前端与综合后端两大阶段。词法、语法和语义分析是对源程序的分析 ，中间代码生成、代码优化与目标代码的生成则是对源程序的 综合 。4程序设计语言的发展带来了日渐多变的运行时存储管理方案，主要分为两大类，即静态存储分配 方案和 动态存储分配5对编译程序而言，输入数据是 源程序 ，输出结果是 目标程序 。 1计算机执行用高级语言编写的程序主要有两种途径：解释和编译 。2扫描器是 词法分析器，它接受输入的 源程
2、序，对源程序进行 词法分析 并识别出一个个单词符号，其输出结果是单词符 号，供语法分析器使用。3自下而上分析法采用 移进 、归约、错误处理、 接受 等四种操作。4一个 LL（ 1）分析程序需要用到 一张分析表 和符号栈 。5后缀式 abc-/ 所代表的表达式是 a/（b-c） 。二、单项选择题（每小题 2分，共 20分）1. 词法分析器的输出结果是 _C。A 单词的种别编码B 单词在符号表中的位置C. 单词的种别编码和自身值D 单词自身值2. 正规式 M 1 和 M 2 等价是指C_。A M1 和 M2 的状态数相等B. M1和M2的有向边条数相等C. M1和M2所识别的语言集相等D. M1和
3、M2状态数和有向边条数相等3. 文法G StxSx|y所识别的语言是 _C。A. xyxB . (xyx)* Cxnyxn(n 0)D . x*yx*4. 如果文法 G是无二义的，则它的任何句子A. 最左推导和最右推导对应的语法树必定相同B. 最左推导和最右推导对应的语法树可能不同C.最左推导和最右推导必定相同D.可能存在两个不同的最左推导，但它们对应的语法树相同5.构造编译程序应掌握D_。A.源程序B.目标语言C . 编译方法D .以上三项都是6.四元式之间的联系是通过 _B_实现的。A.指示器B.临时变量C.符号表D .程序变量7. 表达式(AV B) A (C V D)的逆波兰表示为 _
4、B.A. n ABVA CDVB. A BV CDVA8. 优化可生成 _D_的目标代码。A.运行时间较短C. ABVn CDVAB.占用存储空间较小D.& BVA CDVC. 运行时间短但占用内存空间大D .运行时间短且占用存储空间小C.删除多余运算D .代码外提9下列_C_优化方法不是针对循环优化进行的。A. 强度削弱B 删除归纳变量10.编译程序使用_BJ区别标识符的作用域。B.说明标识符的过程或函数的静态层次D. 标识符的行号1 分，共 10 分)A. 说明标识符的过程或函数名C.说明标识符的过程或函数的动态层次三、判断题(对的打，错的打X,每小题2一个有限状态自动机中，有且仅有一个唯
5、一的终态。x3一个算符优先文法的每个非终结符号间都也可能存在优先关系。X4语法分析时必须先消除文法中的左递归。 X6逆波兰表示法表示表达式时无须使用括号。R9两个正规集相等的必要条件是他们对应的正规式等价。X1编译程序是对高级语言程序的编译执行。X2一个有限状态自动机中，有且仅有一个唯一的初始态。R3一个算符优先文法的每个非终结符号间都不存在优先关系。R4. LL (1)语法分析时必须先消除文法中的左递归。R5. LR分析法在自左至右扫描输入串时就能发现错误，但不能准确地指出出错地点。R6逆波兰表示法表示表达式时根据表达式会使用括号。X7静态数组的存储空间可以在编译时确定。X8进行代码优化时应
6、着重考虑循环的代码优化，这对提高目标代码的效率将起更大作用。X9两个正规集相等的必要条件是他们产生的符号串是相同的。R10一个语义子程序描述了一个文法所对应的翻译工作。X1.什么是S-属性文法什么是L-属性文法它们之间有什么关系S-属性文法是只含有综合属性的属性文法。2 分）L-属性文法要求对于每个产生式A X1X2Xn,其每个语义规则中的每个属性或者是综合属性,或者是Xj的一个继承属性，且该属性仅依赖于：（1）产生式Xj的左边符号X1,X2Xj-1的属性；（2）A的继承属性。（2分）S-属性文法是L-属性文法的特例。（1分）2 什么是L L（1）分析器2 .什么是L R（0）分析器所谓LR（
7、 0 ）分析，是指从左至右扫描和自底向上的语法分析，且在分析的每一步，只须根据分析栈当前已移进和归约出的全部文法符号，并至多再向前查看0个输入符号，就能确定相对于某一产生式左部符号的句柄是否已在分析栈的顶部形成，从而也就可以确定当前所应采取的分析动作（是移进还是按某一产生式进行归约等）五、综合题（共40分）1. （10分）对于文法 GS:S t 1A | 0B |At 0S | 1AAB 宀 1S | 0BB（3分）请写出三个关于GS的句子；（4分）符号串11A0S是否为G S的句型试证明你的结论。（3 分）试画出001B关于G S的语法树。答：（1）三个0和1数量相等的串（每个1 分）(2)
8、 S = 1A = 11AA = 11A 0S(3)2. （10分）设有语言L= a | a 0,1 + ，且a不以0开头，但以00结尾3分）试写出描述 L的正规表达式;（7分）构造识别 L的DFA （要求给出详细过程，并画出构造过程中的NFA、DFA的状态转换图，以及最小DFA的状态转换图）答:（1）（3分）正规表达式:1(0|1) * 00（2 ）（7分）第一步（3分）：将正规表达式转换为NFANFA确定化为DFA :(1分)状态输入I 0I 1S一A,D,BA,D,BD,B,CD,BD,B,CD,B,C,ZD,BD,BD,B,CD,BD,B,C,ZD,B,C,ZD,BFA的状态转换图（1
9、分）第二步（2分）：将重新命名第三步（2分）：将DFA最小化：（1分）将状态划分终态与非终态两个集合：A=qO,q1,q2.q3,E =q4根据A、E集合的情况,对A集合进行划分状态输入将状态集A划分为两个集合：A=q0,q1,q3,E=2根据A、E集合的情况，对A集合进行划分状态输入 I0I 1qOAqlBAq3BA将状态集A划分为两个集合：A=qO,C=ql,q3根据A、C集合的情况，对C集合进行划分状态输入 I0I 1qlBAq3BA最小DFA的状态转换图(l分)3. (20分)给定文法GE:E t E+T | TT t T*F | FF t (E) | i该文法是LL(1)文法吗(要求
10、给出详细过程，如果是LL (1),给出分析表)答：(1)该文法不是LL (1)文法，因为有左递归，消除左递归可获得一个LL (1)文法 (2 分)(2)消除左递归，得新文法(3分)E t TEEt +TE|T t FTTt *FT | F t (E) | i(3) 求产生式右部的First集分)First(TE ) = First(T)= First(F)=(,iFirst(+TE ) = +T Tt & T t *FT Tt Tt First(*FT ) = *First(E) = (First(i) = i4)求所有非终结符的 Follow 集分)Follow(E) = $,)Follow
11、(E ) = Follow(E) = $,)Follow(T) = First(E ) U Follow(E)=+ U $,)=$,+,)Follow(T ) = Follow( T) =$,*,)Follow(F) = First(T)UFollow(T) UFollow(T )= $,*,)5)求所有产生式的 Select 集 分)Select(E tTE)=First(TE )=(,iSelect(Et+TE) =First(+TE)= +Select(Et)= Follow(E )= $,)Select(T tFT)=First(FT )=(,iSelect(Tt *FT)=First
12、(*FT)= *Select(Tt)= Follow(T )=$,+,)Select(F t(E) )=First(E)= (Select(F ti )=First(i)= i(6)对相同左部的所有Select 即求交集分 )Select (Et +TE)n Select (Et )=Select (T*FT )n Select (T ) =QSelect (F (E)n Select (F i ) =Q所以，改造后的文法是 LL (1)文法，其分析表如下7) LL(1) 分析表( 5 分)V N+EEEt +TETV Ti(E t TE E t TET t FT T t FT Et Et 1
13、. （10分）对于文法G:S aSbS|aS|d证明该文法是二义性文法。(5分)答：一个文法，如果存在某个句子有不只一棵语法分析树与之对应，那么称这个文法是二义性文法。句子aadbd有两棵语法树（5分，划一棵树给3分）。如下图:(6分)ddd(1)由此可知，S aSbS|aS|d定义的文法是二义性文法。3. （20分）给定一个简单的算术表达式文法 GEE t E+T | TT t T*F | FF t （E） | i该文法是SLR（1）文法吗（要求给出详细过程，如果是SLR文法，给出分析表） 答：（1）该文法的拓广文法是： （2分）Et E(1)E te+t(2)E tt(3)T tt*f(4)(6)(5)(7)(2) 相应的LR ( 0)的DFA (10分)(3)冲突与解决(3
