编译原理期末考试题库.doc

装订线 装订线PAGE 2 PAGE 1华南农业大学期末考试题库（含参考答案） 考试科目：　编译原理 　　 考试时间：　120　分钟学号 姓名 年级专业 题号一二三四五总分得分评阅人得分得分一、本题共6小题，每小题5分，共30分。1、写出下面右线性正规文法所对应的正规式。文法所对应的正规式为： 文法所对应的正规式为： a(b|aa)*bS → aDD → bD | aA | bA → aD 2、给出下面语言集合的上下文无关文法。（2010 2014）文法： S → aS | DD → aDb | ab L1={ an文法： S → aS | DD → aDb | ab2、为正规集L2={anbm ck | n≥1,m≥1,k≥1}构造一右线性正规文法。（2010）S S → aS | aAA → bA | bBB → cB | c3、按照编译过程的5个阶段得到编译程序的逻辑结构框图如下：4、简述编译过程的5个阶段及各阶段的主要功能。（多年必考）编译过程即编译程序的工作过程，是指从输入源程序开始到输出目标程序为止的整个过程，是非常复杂的，就其过程而言，一般可以划分为五个工作阶段：编译过程即编译程序的工作过程，是指从输入源程序开始到输出目标程序为止的整个过程，是非常复杂的，就其过程而言，一般可以划分为五个工作阶段：①词法分析，对构成源程序的字符串进行扫描和分解，识别出一个个的单词；②语法分析，根据语言的语法规则，把单词符号串组合成各类语法单位；③语义分析与中间代码产生，即对各类语法单位，分析其含义并进行初步翻译；④代码优化，对代码进行等价变换，以期产生更高效的代码；⑤目标代码生成，把中间代码变换成特定机器上的低级语言指令形式。5、“含有优化部分的编译程序的执行效率更高。”这句话对吗？为什么？。这句话是错的。优化不是编译程序必须的一个部分，含有优化的编译程序功能更强、算法更复杂，因而开发效率和执行效率低些，但得到的目标代码的效率通常更高。这句话是错的。优化不是编译程序必须的一个部分，含有优化的编译程序功能更强、算法更复杂，因而开发效率和执行效率低些，但得到的目标代码的效率通常更高。6、简述语法制导翻译技术的基本思想。（2013）语法制导翻译技术的语法制导翻译技术的基本思想是，对文法中的每个产生式都附加一个语义动作或语义子程序，在执行语法分析的过程中，当运用该产生式进行推导或归约时，就执行相应的语义动作，从而完成预定的翻译工作。7、简述算符优先分析方法。（2013）算符优先分析方法是一种移进-归约的语法分析方法，这种分析方法首先要根据文法来确定终结符之间的优先关系，然后借助这种优先关系，在移进-归约过程中通过比较算符优先分析方法是一种移进-归约的语法分析方法，这种分析方法首先要根据文法来确定终结符之间的优先关系，然后借助这种优先关系，在移进-归约过程中通过比较相邻终结符之间的优先关系来确定句型的可归约串（最左素短语）并进行归约。它不是一种规范归约的分析方法，只适用于分析算符优先文法。8、简要说明翻译程序与编译程序的异同、编译程序与解释程序的异同。（2011）翻译程序是将一种语言程序（源）转换成另一种语言程序（目标），对源语言和目标语言没特别要求，编译程序特指将高级语言的源程序转换成低级语言程序翻译程序是将一种语言程序（源）转换成另一种语言程序（目标），对源语言和目标语言没特别要求，编译程序特指将高级语言的源程序转换成低级语言程序，是翻译程序的一种。编译程序与解释程序都是将高级语言翻译成低级语言，但编译程序要先编译生成目标代码、再执行目标代码，解释程序边转换边执行，不生成目标代码。9、判断下图FA是NFA还是DFA，并用正规式来描述它所识别的语言。是DFA(1分)，对应的正规式为： 是DFA(1分)，对应的正规式为： 1*01*(01*01*)* (4分)1AB00110、判断下图FA是NFA还是DFA，并用正规式来描述它所识别的语言。（2011）00AB0,10是NFA,因为A状态输入0可以转换到A或B两状态。是NFA,因为A状态输入0可以转换到A或B两状态。等价正规式：0*(0|1)(00*(0|1))*11、有文法及其语义子程序如下：S →T { print(T.h) }T→ T 1*E { T.h= T 1.h +E.h }T→ E { T.h=E.h }E→（T） {E.h= T.h}E→ a { E.h= 1 } 采用移进归约的分析方法，当分析器的输入为(a)*(a*a) 时，画出其语法树（可以带注释、也可以不带注释），并求输出的结果。语法树（略），语