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

(完整word版)编译原理期末考试题目及答案一、填空题（每空2分，共20分）1编译程序首先要识别出源程序中每个单词，然后再分析每个句子并翻译其意义。 2编译器常用的语法分析方法有自底向上和自顶向下两种。3通常把编译过程分为分析前端与综合后端两大阶段。词法、语法和语义分析是对源程序的分析，中间代码生成、代码优化与目标代码的生成则是对源程序的综合。4程序设计语言的发展带来了日渐多变的运行时存储管理方案，主要分为两大类，即静态存储分配方案和动态存储分配方案。5对编译程序而言，输入数据是源程序，输出结果是目标程序。1计算机执行用高级语言编写的程序主要有两种途径：解释和编译。 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和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 编译方法 D以上三项都是 6四元式之间的联系是通过_B_实现的。 A指示器 B临时变量 C符号表 D程序变量 7表达式(AB)(CD)的逆波兰表示为_B_。A ABCD B ABCD C ABCD D ABCD 8. 优化可生成_D_的目标代码。A运行时间较短 B占用存储空间较小C运行时间短但占用内存空间大 D运行时间短且占用存储空间小9下列_C_优化方法不是针对循环优化进行的。A. 强度削弱 B删除归纳变量 C删除多余运算 D代码外提10编译程序使用_B_区别标识符的作用域。 A. 说明标识符的过程或函数名 B说明标识符的过程或函数的静态层次C说明标识符的过程或函数的动态层次 D. 标识符的行号三、判断题（对的打，错的打，每小题1分，共10分）2一个有限状态自动机中，有且仅有一个唯一的终态。x3一个算符优先文法的每个非终结符号间都也可能存在优先关系。X4语法分析时必须先消除文法中的左递归 。X6逆波兰表示法表示表达式时无须使用括号。R9两个正规集相等的必要条件是他们对应的正规式等价。 X1编译程序是对高级语言程序的编译执行。X2一个有限状态自动机中，有且仅有一个唯一的初始态。R3一个算符优先文法的每个非终结符号间都不存在优先关系。R4LL（1）语法分析时必须先消除文法中的左递归 。 R5LR分析法在自左至右扫描输入串时就能发现错误，但不能准确地指出出错地点。 R6逆波兰表示法表示表达式时根据表达式会使用括号。 X7静态数组的存储空间可以在编译时确定。X8进行代码优化时应着重考虑循环的代码优化，这对提高目标代码的效率将起更大作用。X9两个正规集相等的必要条件是他们产生的符号串是相同的。 R10一个语义子程序描述了一个文法所对应的翻译工作。 X1什么是S-属性文法？什么是L-属性文法？它们之间有什么关系？S-属性文法是只含有综合属性的属性文法。 （2分）L-属性文法要求对于每个产生式AX1X2Xn，其每个语义规则中的每个属性或者是综合属性，或者是Xj的一个继承属性，且该属性仅依赖于：（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 分 ) 请写出三个关于 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 结尾 。 分）试写出描述 L 的正规表达式； （分）构造识别 L 的 DFA （要求给出详细过程，并画出构造过程中的 NFA 、 DFA 的状态转换图，以及最小DFA的状态转换图 ) 。 答：（ 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 最小化 ：（分） 将状态划分终态与非终态两个集合：，根据、集合的情况，对集合进行划分状态 输入 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） 消除左递归，得新文法 (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) = Follow(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)= 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：SaSbS|aS|d证明该文法是二义性文法。答：一个文法，如果存在某个句子有不只一棵语法分析树与之对应，那么称这个文法是二义性文法。（5分）句子aadbd有两棵语法树（5分，划一棵树给3分）。如下图：（分）SaSSabSdddSSabSSad(1) (2)由此可知，SaSbS|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）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状态中有移进规约冲突Follow(E)= $ 不含 + 可解决移进规约冲突 I2状态中有移进规约冲突Follow(E)= +，），$ 不含 * 可解决移进规约冲突 I8状态中有移进规约冲突Follow(E)= +，），$ 不含 * 可解决移进规约冲突(4) SLR分析表 (5分)ACTIONGOTO+*i（）$ETF0S5S41231S6接受2r3S7r3r33r5r5r5R5r5r54S5S49235r7r7r7r7r7r76S5S4837S5S4118r2S7r2r29S6S1010r6r6r6r6r6r611r4r4r4r4r4r4二、单项选择题（每小题2分，共20分）1语言是_C_A终结符与非终结符的符号串的集合 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 AL0L1L2L3 BL3L2L1L0 CL3=L2L1L0 DL0L1L2=L37词法分析的任务是A A识别单词 B分析句子的含义 C识别句子 D生成目标代码8常用的中间代码形式不含D A三元式 B四元式 C逆波兰式 D语法树9 代码优化的目的是C A节省时间 B节省空间 C节省时间和空间 D把编译程序进行等价交换10代码生成阶段的主要任务是C A把高级语言翻译成汇编语言 B把高级语言翻译成机器语言 C把中间代码变换成依赖具体机器的目标代码 D把汇编语言翻译成机器语言