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

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

3、所识别的语言集相等 D M1和M2状态数和有向边条数相等 3 文法G：SxSx|y所识别的语言是_C_。A xyx  B (xyx)* C xnyxn(n0)     D x*yx* 4假如文法G是无二义的，则它的任何句子_A_。A最左推导和最右推导对应的语法树必定相同 B最左推导和最右推导对应的语法树可能不同 C最左推导和最右推导必定相同   D可能存在两个不同的最左推导，但它们对应的语法树相同 5构造编译程序应把握_D_。A源程序   B目标语言       C 编译方法

4、      D以上三项都是 6四元式之间的联系是通过_B_实现的。 A指示器         B临时变量 C符号表              D程序变量 7表达式(AB)(CD)的逆波兰表示为_B_。A ABCD B ABCD      C ABCD        &#

5、160; D ABCD 8. 优化可生成_D_的目标代码。A运行时间较短               B占用存储空间较小C运行时间短但占用内存空间大 D运行时间短且占用存储空间小9下列_C_优化方法不是针对循环优化进行的。A. 强度减弱     B删除归纳变量     C删除多余运算   D代码外提10编译程序使用_B_区分标识符的作用域。 A. 说明标识符的过程或函数名 B说

6、明标识符的过程或函数的静态层次C说明标识符的过程或函数的动态层次 D. 标识符的行号三、推断题（对的打，错的打×，每小题1分，共10分）2一个有限状态自动机中，有且仅有一个唯一的终态。x3一个算符优先文法的每个非终结符号间都也可能存在优先关系。X4语法分析时必需先消退文法中的左递归 。X6逆波兰表示法表示表达式时无须使用括号。R9两个正规集相等的必要条件是他们对应的正规式等价。 X1编译程序是对高级语言程序的编译执行。X2一个有限状态自动机中，有且仅有一个唯一的初始态。R3一个算符优先文法的每个非终结符号间都不存在优先关系。R4LL（1）语法分析时必需先消退文法中的左递归 。 R5L

7、R分析法在自左至右扫描输入串时就能发觉错误，但不能精确地指出出错地点。 R6逆波兰表示法表示表达式时依据表达式会使用括号。 X7静态数组的存储空间可以在编译时确定。X8进行代码优化时应着重考虑循环的代码优化，这对提高目标代码的效率将起更大作用。X9两个正规集相等的必要条件是他们产生的符号串是相同的。 R10一个语义子程序描述了一个文法所对应的翻译工作。 X1什么是S-属性文法？什么是L-属性文法？它们之间有什么关系？S-属性文法是只含有综合属性的属性文法。 （2分）L-属性文法要求对于每个产生式AàX1X2Xn，其每个语义规章中的每个属性或者是综合属性，或者是Xj的一个继承属性，且该

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

9、 分 ) 请写出三个关于 GS 的句子； (4 分 ) 符号串 11A0S 是否为 G S 的句型？试证明你的结论。 (3 分 ) 试画出 001B 关于 G S 的语法树。 答：（1） 三个 0 和 1 数量相等的串 （每个1分）（2） S => 1A => 11AA => 11A 0S （3）  2.（10分）设有语言 L= | 0,1 + ，且不以 0 开头，但以 00 结尾 。 2 分）试写出描述 L 的正规表达式； （分）构造识别 L 的 DFA （要求给出具体过程，并画出构造过程中的 NFA 、 DFA 的状态转换图，以及最小DFA的状态转换图 ) 。

10、答：（ 1 ）（分）正规表达式： 1(0|1) * 00 （ 2 ）（分）第一步（分）：将正规表达式转换为 NFA 其次步（分）：将 NFA 确定化为 DFA ：（分） 状态 输入 I 0 I 1   t 0 1 S A,D,B   q 0 q 1 A,D,B D,B,C D,B 重新命名 q 1 q 2 q 3 D,B,C D,B,C,Z D,B q 2 q 4 q 3 D,B D,B,C D,B   q 3 q 2 q 3 D,B,C,Z D,B,C,Z D,B   q 4 q 4 q 3 DFA 的状态转换图（分） 第三步（分）：将DFA 最小化

11、：（分） 将状态划分终态与非终态两个集合：，依据、集合的状况，对集合进行划分状态 输入 I 0 I 1 将状态集划分为两个集合：，依据、集合的状况，对集合进行划分状态 输入 I 0 I 1 将状态集划分为两个集合：，依据、集合的状况，对集合进行划分状态 输入 I 0 I 1 最小DFA 的状态转换图（分） （20分）给定文法 GE ： E E+T | T T T*F | FF (E) | i 该文法是 LL(1) 文法吗？（要求给出具体过程，假如是LL（1），给出分析表）答：（1）该文法不是LL（1）文法，由于有左递归，消退左递归可获得一个LL（1）文法 （2分）（2） 消退左递归，得新文法

12、(3分)E TEE +TE| T FTT *FT |F (E) | i (3)求产生式右部的First集 (2.5分)First(TE) = First(T)= First(F)=(,i First(+TE) = + First(FT) = First(F)=(,i First(*FT) = * First(E) = ( First(i) = i （4） 求全部非终结符的Follow集(2.5分)Follow(E) = $,) Follow(E) = Follow(E) = $,) Follow(T) = First(E)Follow(E)=+ $,)=$,+,) Follow(T) = Fo

13、llow(T) =$,*,) Follow(F) = First(T)Follow(T) Follow(T)= $,*,) （5） 求全部产生式的Select集 (2.5分)Select（E TE）=First(TE)= (,i Select（E +TE）=First(+TE)= + Select（E ）= Follow(E) = $,) Select（T FT）=First(FT)= (,i Select（T *FT）=First(*FT)= *Select（T ）= Follow(T) =$,+,) Select（F (E)）=First(E)= ( Select（F i）=First(i

14、)= i （6）对相同左部的全部Select即求交集(2.5分)Select（E +TE）Select（E ）= Select（T *FT）Select（T ）= Select（F (E)）Select（F i）= 所以，改造后的文法是LL（1）文法，其分析表如下（7） LL(1) 分析表（ 5 分） V N V T + * i ( )$E E TE E TE    E E +TE    E E TT FTT FT  TT T *FTT T FF (E)F i1（10分）对于文法G：S®aSbS|aS|d证明该文法是二义性文法。答：一

15、个文法，假如存在某个句子有不只一棵语法分析树与之对应，那么称这个文法是二义性文法。（5分）句子aadbd有两棵语法树（5分，划一棵树给3分）。如下图：（分）SaSSabSdddSSabSSad(1) (2)由此可知，S®aSbS|aS|d定义的文法是二义性文法。（20分）给定一个简洁的算术表达式文法 GE ： E E+T | T T T*F | FF (E) | i 该文法是 SLR(1) 文法吗？（要求给出具体过程，假如是SLR文法，给出分析表）答：(1) 该文法的拓广文法是： (2分)E E （1）E E+T （2）E T （3）T T*F （4）T F （5）F (E) （6）

16、F i （7）（2） 相应的LR（0）的DFA：（10分）)(FTI0:E .EE .E+T E . T T .T*FT .FF .(E)F .i I1:E E.E E.+T I2:E T. T T.*FEFI3:T F.TI4:F (.E)E .E+T E . T T .T*FT .FF .(E)F .i （iI6:E E+.TT .T*FT .FF .(E)F .i +*（iiTI8:E E+T.T T.*F*I7:T T*.FF .(E)F .i F（iI9:F (E.)E E.+T EI10:F (E) .+I5:F i.FI11:T T*F.（3） 冲突与解决 (3分） I1状态中有

17、移进规约冲突Follow(E)= $ 不含 + 可解决移进规约冲突 I2状态中有移进规约冲突Follow(E)= +，），$ 不含 * 可解决移进规约冲突 I8状态中有移进规约冲突Follow(E)= +，），$ 不含 * 可解决移进规约冲突(4) SLR分析表 (5分)ACTIONGOTO+*i（）$ETF0S5S41231S6接受2r3S7r3r33r5r5r5R5r5r54S5S49235r7r7r7r7r7r76S5S4837S5S4118r2S7r2r29S6S1010r6r6r6r6r6r611r4r4r4r4r4r4二、单项选择题（每小题2分，共20分）1语言是_C_A终结符与非

18、终结符的符号串的集合 B 非终结符符号串的集合 C终结符符号串的集合 D产生式的集合2编译程序分两阶段工作，前阶段完成的工作是_C_A词法分析、语法分析和代码优化 B代码生成、代码优化和词法分析C词法分析、语法分析、语义分析和中间代码生成 D词法分析、语法分析和代码优化3一个句型中称为句柄的是该句型的最左C A句型 B短语 C直接短语 D最左直接短语4自动机识别的语言是 DA0型语言 B1型语言 C2型语言 D3型语言5自动机所完成的任务是从字符串形式的源程序中识别出一个个具有独立含义的最小语法单位即 B A 字符 B单词 C句子 D句型6对应Chomsky四种文法的四种语言之间的关系是B AL0ÌL1