编译原理-2016-2017学年第二学期期末考试

2016-2017年广东海洋大学《编译原理》试卷注：文档及答案由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、假设G[S]是一个文法，如有S=x，则称x是该文法G的句型。二、判断题如：3型文法一定是2型文法。(√)三、问答题1、画出编译程序的结构框图。2、对下图中的DFA，要求：（1）写出对应的五元组表示形式。（2）求与该DFA等价的正规式。答：（1）DFAM=（{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，b）={U}f（V，a）={Q}f（Q，c）={Q}f（Q，d）={Q}（2）等价正规式：(a|c)(ab)*(a|b)(c|d)*3、将下图所示NFA转换为等价的DFA并最小化。答：4、给定文法G[S]：S-ABA-aB|bS|cB-AS|d（1）给出每一个产生式右部的First集；（2）给出每一个非终结符号的Follow集；（3）给出每一个产生式的Select集；（4）判断该文法是否为LL（1）文法？若是，给出该文法的预测分析表。答：5、已知文法G[S]：S-BAA-Bs|dB-aA|bS|c的预测分析表如下：（1）根据预测分析法，给出输入串adccd的分析过程步骤分析栈剩余输出串推导用到的产生式或匹配1#Sadccd#S-BA2#ABadccd#B-aA3#AAaadccd#“a”匹配4#AAdccd#A-d5#Addccd#“d”匹配6#Accd#A-BS7#SBccd#B-c8#Scccd#“c”匹配9#Scd#S-BA10#ABcd#B-c11#Accd#“c”匹配12#Ad#A-d13#dd#“d”匹配14##“#”匹配(接受)15（2）判断adccd输入串是否为文法G[S]的正确句子。答：是。abcd#SABS-BAA-BSB-aAS-BAA-BSB-bSS-BAA-BSB-cA-d