编译原理下载试题-copy.docx

历年试题及答案一选择题1将编译程序分成若干个“遍”是为了_。a.提高程序的执行效率b.使程序的结构更加清晰c.利用有限的机器内存并提高机器的执行效率d.利用有限的机器内存但降低了机器的执行效率2构造编译程序应掌握_。a.源程序 b.目标语言c.编译方法 d.以上三项都是3编译程序绝大多数时间花在_上。a.出错处理 b.词法分析c.目标代码生成 d.管理表格4词法分析器的输出结果是_。a.单词的种别编码 b.单词在符号表中的位置c.单词的种别编码和自身值 d.单词自身值5正规式MI和M2等价是指_。a. MI和M2的状态数相等 b.Ml和M2的有向弧条数相等。C.M1和M2所识别的语言集相等 d. Ml和M2状态数和有向弧条数相等6中间代码生成时所依据的是_。 a语法规则 b词法规则 c语义规则 d等价变换规则7程序所需的数据空间在程序运行前就可确定，称为_ 管理技术。 a.动态存储 b.栈式存储 c.静态存储 d.堆式存储二、简答题1.画出编译程序的总体结构图，简述各部分的主要功能。2.已知文法GE: EET+|TTTF* | FFF | a 试证：FF*是文法的句型，指出该句型的短语、简单短语和句柄. 3为正规式(a|b) *a(a|b)构造一个确定的有限自动机。4设文法G(S)： S(L)|a S|a LL，S|S (1) 消除左递归和回溯； (2) 计算每个非终结符的FIRST和FOLLOW； (3) 构造预测分析表。5已知文法A-aAd| aAb| ，判断该文法是否SLR（1）文法，若是构造相应分析表，并对输入串ab#给出分析过程。6已构造出文法G（S）（1）S- BB（2）B -aB（3）B - b1）。给出DFA图2）.给出LR分析表3）假定输入串为abaab，请给出LR分析过程（即状态，符号，输入串的变化过程）。4 【解答】(1) S(L)|aS SS| LSL LSL| 评分细则：消除左递归2分，提公共因子2分。 5 【解答】 (1)拓广文法 (0)S-A(1) A-aAd(2)A- aAb(3)A- (2)构造识别活前缀的DFA FOLLOW(A)=d,b,# 对于状态I0：FOLLOW(A)a= 对于状态I1：FOLLOW(A)a= 因为，在DFA中无冲突的现象，所以该文法是SLR(1)文法。 6 【解答】（1）LR分析表如下：（2）分析表 一、简答题（60分）1编译程序在逻辑上由哪几部分组成？2编译程序和解释程序有哪些区别？ 解释程序是源程序的一个执行系统，而编译程序是源程序的一个转换系统；解释器直接由源程序得到运行结果，而编译器是生成等价于源程序的某种目标机程序。 3. 给出识别正则表达式(（a|bc）*d)+的NFA 。 4已知文法GS：S S；GG G G(T) HH a (S)T T+S S找出句型：a(T+S)；H；(S)的短语、简单短语和句柄。 5已知文法GS为：SAB | bC Ab | BaD | CAD | b DaS | c 对其每一个非终级符求First集和Follow集。 二、（10分）设有文法GA: A iB*e B SB|e S eC|.i C eC|e判定该文法是否为LL(1)文法？若是则给出它的LL(1)分析表，否则说明理由。 三、（15分）设有文法GS: S LaR|RL bR|cR L 判断该文法是否为LR(1)文法。若是则给出它的LR(1)状态机以及LR分析表。 LR(1)状态机如下： 因为状态机中没有冲突，所以是LR(1)文法。 LR(1)分析表如下： (1) S LaR (2) S R (3) L bR (4) L c (5) R L a b c # S L R 1 S6 S4 2 5 3 2 Acc 3 R2 4 R4 R4 5 S7 R5