广东海洋大学20162017学年第二学期 编译原理课程试题题号一二三四五六总分阅卷教师各题分数20 10 70 100 实得分数注：文档及答案由Adao 完善上传提供，如有疑问或不妥之处，请自行解决。一、填空题1、编译程序的基本任务是将源程序翻译成等价的目标程序。编译器的各个阶段的工作都涉及表格处理和 出错处理。2、将非 LL（1）文法转换为等价的LL（1）文法的两种方法是消除左递归 和提取左公共因子。3、编译和解释程序的根本区别是是否生成目标代码。4、文法 G 产生的 句子的全体是该文法描述的语言。5、文法 G 定义为四元组（Vn，Vt，P，S），其中，Vn为非终结符集，Vt 为终结符集，P为产生式集合，S称作 开始符号。6、2 型文法又称为 上下文无关 文法，3 型文法又称为正规文法。3 型文法可用作词法分析，2 型文法可用作语法分析。7、通常用于描述词法规则的工具有四种，NFA，DFA，正规文法，正规式。8、假设 GS是一个文法，如有S=x，则称 x 是该文法 G 的句型。二、判断题如：并不是每个文法都能改写成LL(1)文法。()三、问答题1、画出编译程序的结构框图。课程号：考试A 卷闭卷考查 B 卷 开卷班级：姓名：学号：试题共页加白纸张密封线GDOU-B-11-302名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 5 页 -2、对下图中的DFA，要求：（1）写出对应的五元组表示形式。（2）求与该DFA等价的正规式。答：（1）DFA M=（S，U，V，Q，a，b，c，d，f，S，Q）其中：f（S，a）=U f（S，c）=V f（U，a）=V f（U，b）=Q f（V，a）=Q f（V，b）=U f（Q，c）=Qf（Q，d）=Q（2）等价正规式：(a|c)(ab)*(a|b)(c|d)*名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 5 页 -3、将下图所示NFA转换为等价的DFA并最小化。答：名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 5 页 -4、给定文法GS：S-AB A-aB|bS|c B-AS|d（1）给出每一个产生式右部的First 集；（2）给出每一个非终结符号的Follow 集；（3）给出每一个产生式的Select 集；（4）判断该文法是否为LL（1）文法？若是，给出该文法的预测分析表。答：5、已知文法GS：S-BA A-Bs|d B-aA|bS|c 的预测分析表如下：a b c d#S A B S-BA A-BS B-aA S-BA A-BS B-bS S-BA A-BS B-c A-d 名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 5 页 -（1）根据预测分析法，给出输入串adccd 的分析过程步骤分析栈剩余输出串推导用到的产生式或匹配1#S adccd#S-BA2#AB adccd#B-aA 3#AAa adccd#“a”匹配4#AA dccd#A-d 5#Ad dccd#“d”匹配6#A ccd#A-BS 7#SB ccd#B-c 8#Sc ccd#“c”匹配9#S cd#S-BA 10#AB cd#B-c 11#Ac cd#“c”匹配12#A d#A-d 13#d d#“d”匹配14#“#”匹配(接受)15（2）判断 adccd 输入串是否为文法GS的正确句子。答：是。名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 5 页 -