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

一、填空题（每空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：S xSx|y 所识别的语言是_C_。A xyx B(xyx)*C xnyxn(n 0)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 AB CDB AB CD C ABCDD AB CD8.优化可生成 _D_的目标代码。A运行时间较短 B占用存储空间较小C运行时间短但占用内存空间大D运行时间短且占用存储空间小9下列 _C_优化方法不是针对循环优化进行的。A.强度削弱B删除归纳变量C删除多余运算D代码外提10编译程序使用_B_区别标识符的作用域。A.说明标识符的过程或函数名B说明标识符的过程或函数的静态层次C说明标识符的过程或函数的动态层次D.标识符的行号三、判断题（对的打，错的打，每小题1 分，共 10 分）2一个有限状态自动机中，有且仅有一个唯一的终态。x 名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 7 页 -3一个算符优先文法的每个非终结符号间都也可能存在优先关系。X 4语法分析时必须先消除文法中的左递归。X 6逆波兰表示法表示表达式时无须使用括号。R 9两个正规集相等的必要条件是他们对应的正规式等价。X 1编译程序是对高级语言程序的编译执行。X 2一个有限状态自动机中，有且仅有一个唯一的初始态。R 3一个算符优先文法的每个非终结符号间都不存在优先关系。R 4 LL（1）语法分析时必须先消除文法中的左递归。R 5LR 分析法在自左至右扫描输入串时就能发现错误，但不能准确地指出出错地点。R 6逆波兰表示法表示表达式时根据表达式会使用括号。X 7静态数组的存储空间可以在编译时确定。X 8进行代码优化时应着重考虑循环的代码优化，这对提高目标代码的效率将起更大作用。X 9两个正规集相等的必要条件是他们产生的符号串是相同的。R 10一个语义子程序描述了一个文法所对应的翻译工作。X 1什么是 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 页，共 7 页 -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 名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 7 页 -将状态集划分为两个集合：，根据、集合的情况，对集合进行划分状态输入I 0 I 1 最小 DFA 的状态转换图（分）（20 分）给定文法 GE：E E+T|T T T*F|F F (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)=*名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 7 页 -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 NV T+*i ()$E E TEE TEE E +TEE ET T FTT FTTTT *FT T TF F (E)F i 1（10 分）对于文法G：SaSbS|aS|d 证明该文法是二义性文法。答：一个文法，如果存在某个句子有不只一棵语法分析树与之对应，那么称这个文法是二义性文法。（5 分）句子 aadbd 有两棵语法树（5 分，划一棵树给3 分）。如下图：（分）(1)(2)由此可知，SaSbS|aS|d 定义的文法是二义性文法。（20 分）给定一个简单的算术表达式文法 GE：E E+T|T T T*F|F F (E)|i 该文法是 SLR(1)文法吗？（要求给出详细过程，如果是SLR文法，给出分析表）答：(1)该文法的拓广文法是：(2分)d S S a b S S a d S a S S a b S d d 名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 7 页 -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 分）（3）冲突与解决 (3分）I1状态中有移进规约冲突Follow(E )=$不含+可解决移进规约冲突 I2状态中有移进规约冲突Follow(E)=+，），$不含 *可解决移进规约冲突 I8状态中有移进规约冲突)(F T I0:E.E E .E+T E .T T .T*F T .F F .(E)F .i I1:E E.E E.+T I2:E T.T T.*F E F I3:T F.T I4:F (.E)E .E+T E .T T .T*F T .F F .(E)F .i （i I6:E E+.T T .T*F T .F F .(E)F .i +*（i i T I8:E E+T.T T.*F*I7:T T*.F F .(E)F .i F（i I9:F (E.)E E.+T E I10:F (E).+I5:F i.F I11:T T*F.名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 7 页 -Follow(E)=+，），$不含 *可解决移进规约冲突(4)SLR 分析表 (5分)ACTION GOTO+*i（）$E T F 0 S5 S4 1 2 3 1 S6 接受2 r3 S7 r3 r3 3 r5 r5 r5 R5 r5 r5 4 S5 S4 9 2 3 5 r7 r7 r7 r7 r7 r7 6 S5 S4 8 3 7 S5 S4 11 8 r2 S7 r2 r2 9 S6 S10 10 r6 r6 r6 r6 r6 r6 11 r4 r4 r4 r4 r4 r4 二、单项选择题（每小题2分，共 20分）1语言是 _C_ A 终结符与非终结符的符号串的集合 B 非终结符符号串的集合 C 终结符符号串的集合 D产生式的集合2编译程序分两阶段工作，前阶段完成的工作是_C_ A 词法分析、语法分析和代码优化 B代码生成、代码优化和词法分析C 词法分析、语法分析、语义分析和中间代码生成 D词法分析、语法分析和代码优化3一个句型中称为句柄的是该句型的最左C A句型 B短语 C直接短语 D 最左直接短语4自动机识别的语言是 D A 0 型语言 B1 型语言 C 2 型语言 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把汇编语言翻译成机器语言名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 7 页 -