编译原理期末考试题目及答案.pdf

《编译原理期末考试题目及答案.pdf》由会员分享，可在线阅读，更多相关《编译原理期末考试题目及答案.pdf（8页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、实用文档一、填空题每空 2 分，共 20 分1编译程序首先要识别出源程序中每个单词单词，然后再分析每个句子句子并翻译其意义。2编译器常用的语法分析方法有自底向上有自底向上和自顶向下自顶向下两种。3通常把编译过程分为分析前端与综合后端两大阶段。词法、语法和语义分析是对源程序的 分析分析，中间代码生成、代码优化与目标代码的生成那么是对源程序的综合综合。4程序设计语言的开展带来了日渐多变的运行时存储管理方案，主要分为两大类，即 静态存储分配静态存储分配方案和动态存储分配动态存储分配方案。5对编译程序而言，输入数据是源程序源程序，输出结果是目标程序目标程序。1计算机执行用高级语言编写的程序主要有两种途

2、径：解释和编译解释和编译。2扫描器是词法词法分析器，它接受输入的源程序源程序，对源程序进行词法分析词法分析并识别出一个个单词符号，其输出结果是单词符号，供语法分析器使用。3自下而上分析法采用移进移进、归约、错误处理、接受接受等四种操作。4一个 LL1分析程序需要用到一张分析表一张分析表和符号栈符号栈。5后缀式 abc-/所代表的表达式是 a/(b-c)a/(b-c)。二、单项选择题每题2分，共20分1词法分析器的输出结果是_C。A 单词的种别编码B 单词在符号表中的位置C 单词的种别编码和自身值D 单词自身值2 正规式 M 1 和 M 2 等价是指_C_。A M1 和 M2 的状态数相等 B

3、M1 和 M2 的有向边条数相等C M1 和 M2 所识别的语言集相等D M1 和 M2 状态数和有向边条数相等3 文法 G：SxSx|y 所识别的语言是_C_。A xyxB(xyx)*C xnyxn(n0)D x*yx*4如果文法 G 是无二义的，那么它的任何句子_A_。A最左推导和最右推导对应的语法树必定相同B最左推导和最右推导对应的语法树可能不同C最左推导和最右推导必定相同D可能存在两个不同的最左推导，但它们对应的语法树相同5构造编译程序应掌握_D_。A源程序B目标语言C 编译方法D以上三项都是6四元式之间的联系是通过_B_实现的。A指示器B临时变量C符号表D程序变量7表达式(AB)(C

4、D)的逆波兰表示为_B_。A ABCDB ABCD C ABCDD ABCD8.优化可生成_D_的目标代码。A运行时间较短 B占用存储空间较小C运行时间短但占用内存空间大 D运行时间短且占用存储空间小9以下_C_优化方法不是针对循环优化进行的。A.强度削弱B删除归纳变量C删除多余运算D代码外提10编译程序使用_B_区别标识符的作用域。A.说明标识符的过程或函数名B说明标识符的过程或函数的静态层次C说明标识符的过程或函数的动态层次D.标识符的行号三、判断题对的打，错的打，每题1 分，共 10 分2一个有限状态自动机中，有且仅有一个唯一的终态。x.实用文档3一个算符优先文法的每个非终结符号间都也可

5、能存在优先关系。X4语法分析时必须先消除文法中的左递归。X6逆波兰表示法表示表达式时无须使用括号。R9两个正规集相等的必要条件是他们对应的正规式等价。X1编译程序是对高级语言程序的编译执行。X2一个有限状态自动机中，有且仅有一个唯一的初始态。R3一个算符优先文法的每个非终结符号间都不存在优先关系。R4LL1语法分析时必须先消除文法中的左递归。R5LR 分析法在自左至右扫描输入串时就能发现错误，但不能准确地指出出错地点。R6逆波兰表示法表示表达式时根据表达式会使用括号。X7静态数组的存储空间可以在编译时确定。X8进行代码优化时应着重考虑循环的代码优化，这对提高目标代码的效率将起更大作用。X9两个

6、正规集相等的必要条件是他们产生的符号串是相同的。R10一个语义子程序描述了一个文法所对应的翻译工作。X1什么是 S-属性文法？什么是 L-属性文法？它们之间有什么关系？S-S-属性文法是只含有综合属性的属性文法。属性文法是只含有综合属性的属性文法。2 2 分分L-L-属性文法要求对于每个产生式属性文法要求对于每个产生式A AX1X2X1X2XnXn，其每个语义规那么中的每个属性或者是综合属性，其每个语义规那么中的每个属性或者是综合属性，或者是或者是XjXj的一个继的一个继承属性，且该属性仅依赖于：承属性，且该属性仅依赖于：（1 1）产生式产生式XjXj的左边符号的左边符号X1,X2X1,X2X

7、j-1Xj-1的属性；的属性；（2 2）A A的继承属性。的继承属性。2 2分分S-S-属性文法是属性文法是 L-L-属性文法的特例。属性文法的特例。分什么是 L分析器什么是 L分析器所谓 LR()分析，是指从左至右扫描和自底向上的语法分析，且在分析的每一步，只须根据分析栈当前已移进和归约出的全部文法符号，并至多再向前查看 0 个输入符号，就能确定相对于某一产生式左部符号的句柄是否已在分析栈的顶部形成，从而也就可以确定当前所应采取的分析动作(是移进还是按某一产生式进行归约等)。五、综合题共 40 分1 10 分对于文法 GS：S 1A|0B|A 0S|1AAB 1S|0BB(3 分)请写出三个

8、关于 GS 的句子；(4 分)符号串 11A0S 是否为 G S 的句型？试证明你的结论。(3 分)试画出 001B 关于 G S 的语法树。答：1 三个 0 和 1 数量相等的串每个 1 分2 S=1A=11AA=11A 0S3.实用文档2.10 分设有语言 L=|0,1+，且不以 0 开头，但以 00 结尾 。分试写出描述 L 的正规表达式；分构造识别 L 的 DFA 要求给出详细过程，并画出构造过程中的 NFA、DFA 的状态转换图，以及最小DFA 的状态转换图)。答：1 分正规表达式：1(0|1)*00 2 分第一步分：将正规表达式转换为 NFA第二步分：将 NFA 确定化为 DFA：

9、分状态 输入I 0I 1SA,D,BA,D,BD,B,CD,B重新命名D,B,CD,B,C,ZD,BD,BD,B,CD,BD,B,C,ZD,B,C,ZD,BDFA 的状态转换图分tq0q1q20q2q41q1q3q3q3q4q2q4q3q3第三步分：将 DFA 最小化：分将状态划分终态与非终态两个集合：，根据、集合的情况，对集合进行划分状态 输入I 0I 1.将状态集划分为两个集合：，根据、集合的情况，对集合进行划分状态 输入I 0I 1将状态集划分为两个集合：，根据、集合的情况，对集合进行划分状态 输入I 0I 1最小 DFA 的状态转换图分 20 分给定文法 GE：E E+T|TT T*F

10、|FF (E)|i该文法是 LL(1)文法吗？要求给出详细过程，如果是LL1，给出分析表答：1该文法不是 LL1文法，因为有左递归，消除左递归可获得一个LL1文法2 消除左递归，得新文法 (3 分)E TEE+TE|T FTT *FT|F (E)|i(3)求产生式右部的 First 集 (2.5 分)First(TE)=First(T)=First(F)=(,iFirst(+TE)=+First(FT)=First(F)=(,iFirst(*FT)=*First(E)=(First(i)=i4 求所有非终结符的Follow 集(2.5 分)Follow(E)=$,)Follow(E)=Foll

11、ow(E)=$,)Follow(T)=First(E)Follow(E)=+$,)=$,+,)Follow(T)=Follow(T)=$,*,).实用文档2 分实用文档Follow(F)=First(T)Follow(T)Follow(T)=$,*,)5 求所有产生式的 Select 集 (2.5 分)SelectE TE=First(TE)=(,iSelectE+TE=First(+TE)=+SelectE=Follow(E)=$,)SelectT FT=First(FT)=(,iSelectT *FT=First(*FT)=*SelectT=Follow(T)=$,+,)SelectF (

12、E)=First(E)=(SelectF i=First(i)=i6对相同左部的所有Select 即求交集(2.5 分)SelectE+TESelectE=SelectT *FTSelectT=SelectF (E)SelectF i=所以，改造后的文法是 LL1文法，其分析表如下7 LL(1)分析表 5 分VTVN+*i()$EE TEE TEEE+TEE E TT FTT FTTT T *FTT T FF (E)F i1 10 分对于文法 G：SaSbS|aS|d证明该文法是二义性文法。答：一个文法，如果存在某个句子有不只一棵语法分析树与之对应，那么称这个文法是二义性文法。5 分句子 aa

13、dbd 有两棵语法树5 分，划一棵树给 3 分。如以下图：分由此可知，SaSbS|aS|d 定义的文法是二义性文法。.SSdaSSSdaaSbSdaSdb(1)(2)实用文档 20 分给定一个简单的算术表达式文法 GE：E E+T|TT T*F|FF (E)|i该文法是 SLR(1)文法吗？要求给出详细过程，如果是SLR 文法，给出分析表答：(1)该文法的拓广文法是：(2 分)E E1E E+T2E T3T T*F4T F5F (E)6F i72 相应的 LR0的 DFA：10 分E+I6:E E+.TT .T*FT .FF .(E)F .iTI7:T T*.FF .(E)F .iiFI11:

14、T T*F.*I8:E E+T.T T.*FI0:E.EE .E+TE .TT .T*FT .FF .(E)F .iiI5:F i.I1:E E.E E.+TiFTI3:T F.FI2:E T.T T.*FTF*iE(I4:F (.E)E .E+TE .TT .T*FT .FF .(E)F .iI9:F (E.)E E.+T.+I10:F (E).)实用文档3 冲突与解决 (3 分 I1 状态中有移进规约冲突Follow(E)=$不含+可解决移进规约冲突 I2 状态中有移进规约冲突Follow(E)=+，$不含*可解决移进规约冲突 I8 状态中有移进规约冲突Follow(E)=+，$不含*可解

15、决移进规约冲突(4)SLR 分析表 (5 分)01234567891011+S6r3r5r7r2S6r6r4*S7r5r7S7r6r4ACTIONiS5S4r5R5S5S4r7r7S5S4S5S4r6r6r4r4r3r5r7r2S10r6r4$接受r3r5r7r2r6r4E19GOTOT228F33311二、单项选择题每题2分，共20分1语言是_C_A终结符与非终结符的符号串的集合 B 非终结符符号串的集合 C终结符符号串的集合 D产生式的集合2编译程序分两阶段工作，前阶段完成的工作是_C_A词法分析、语法分析和代码优化 B代码生成、代码优化和词法分析C词法分析、语法分析、语义分析和中间代码生

16、成 D词法分析、语法分析和代码优化3一个句型中称为句柄的是该句型的最左C A句型 B短语 C直接短语 D最左直接短语4自动机识别的语言是 DA0 型语言 B1 型语言 C2 型语言 D3 型语言5自动机所完成的任务是从字符串形式的源程序中识别出一个个具有独立含义的最小语法单位即 B A 字符 B单词 C句子 D句型6对应 Chomsky 四种文法的四种语言之间的关系是B AL0 L1 L2 L3 BL3 L2 L1 L0 CL3=L2 L1 L0 DL0 L1 L2=L37词法分析的任务是 A A识别单词 B分析句子的含义 C识别句子 D生成目标代码8常用的中间代码形式不含D A三元式 B四元式 C逆波兰式 D语法树9 代码优化的目的是 C.实用文档 A节省时间 B节省空间 C节省时间和空间 D把编译程序进行等价交换10代码生成阶段的主要任务是C A把高级语言翻译成汇编语言 B把高级语言翻译成机器语言 C把中间代码变换成依赖具体机器的目标代码 D把汇编语言翻译成机器语言.