编译原理自测题2014.doc

注：1、章节不完全按照陈意云教材的章节； 2、不公布标准答案； 3、题目中标注的页码如P6图1.3均为陈意云教材的页码。 第一章 一．填空题 1．编译程序的工作过程一般可以划分为______、_______、_______、_______和_______等几个基本阶段，同时还伴有_______和_______。 2．若源程序是用高级语言编写的，目标程序是_______或_______，则其翻译程序称为编译程序。 3．编译方式与解释方式的根本区别在于_______。 4．_______是这样一种程序，它能将用甲种语言书写的程序转换成与其等价的乙种语言书写的程序。 5．对编译程序而言，输入数据是_______，输出结果是_______。 6．运行编译程序的计算机称宿主机，运行编译程序所产生目标代码的计算机称_______。 7．当把编译程序划分成编译前端和编译后端时，_______主要由与_______有关但与目标机无关的部分组成，编译后端包括编译程序中与目标机有关的部分，编译后端不依赖于源语言而仅仅依赖于_______。 8．描述词法规则的有效工具是_______，通常使用_______来描述语法规则，使用_______描述语义规则。 二 简答题 1．什么是编译程序 2. 什么是解释程序 3. 什么是翻译程序 4. 以上3种程序的区别 三 综合题 1、编译过程的几个阶段的输入输出及相关技术（P6图1.3） 第二章 一 综合题 1．构造与正规式(a|b)*a(a|b)等价的状态最少的确定有限自动机。 2．构造与正规式(0|1)*0(0|1)等价的状态最少的确定有限自动机。 3．构造与正规式(a|ba)*等价的状态最少的确定有穷自动机。 4．构造与正规式(a|b)* aa等价的状态最少的确定有穷自动机。 5．构造与正规式a (a|b)*b等价的状态最少的确定有穷自动机。 注意：以上4题要分别写出构造NFA、NFA确定化为DFA（子集法）、DFA的最小化过程 二 简答题 1、当给出有限自动机的状态转换图时，写出有限自动机的五元式定义，并判断它能识别何种字符串。 第三章 一．填空题 1．上下文无关文法包括以下四个组成部分：一组______符号，一组______符号，一个______符号，以及一组_______。 2．如果一个文法存在某个句子对应两棵不同的语法树，则这个文法是_______文法。 3．消除文法的二义性的方法主要有：_______二义文法为非二义文法；为文法符号规定_______和_______。 二 简答题 1．有文法G：E→E+E│E*E│(E)│id （1）给出(id* id)+ id的最左推导； （2）并给出该推导过程中的所有句型； （3）给出该文法的2个句子； （4）这个文法产生的是什么语言。 2. 有文法G：S→aSbS│bSaS│ε （1）为句子abab构造最左推导； （2）给出该推导过程中的所有句型； （3）证明该文法是二义文法； （4）这个文法产生的是什么语言。 3. 什么是LL（1）文法。 4. 预测分析器模型由哪些部分组成。 5. LR分析器模型由哪些部分组成。 第四章 一．填空题 1．自上而下语法分析中存在的主要问题是由左递归引起的 问题和左公共因子引起的 问题。 2．LL（1）文法是即不含左递归，也没有左公共因子的文法。要避免回溯，第一，需要文法中每一个非终结符A的各个产生式的候选首符集两两不相交，即，若A→(1|(2|…|(n，则 ＝(，(i(j)；第二，若A存在某个候选首符集包含(，则 =(，i=1,2,...,n。 3．自上而下语法分析的基本思想是，对任何输入串，从文法的 符号，即根结点出发，自上而下地为输入串建立一颗语法树。递归下降分析器采用的是自上而下语法分析方法，非递归的预测分析器采用的是 语法分析方法，LR分析器采用的是 语法分析方法。 4．预测分析器模型是由输入、输出、 ， 和 组成。 5．自下而上语法分析的基本思想是，从 开始，逐步进行 ，直至规约到文法的开始符号，即从语法树的 开始，步步向上规约，直到 。 6．LR分析器模型包括输入、输出、 、 和含有 与 两部分的分析表。 二、简答题 1．将以下文法G（S）改写成LL(1)文法，该文法能识别哪一类语言。 S→ (L)│a L→ L，S│S 2．将以下表达式文法G（E）改写成LL(1)（无左递归的）文法，该文法能识别哪一类语言。 E→E+T│T T→T*F│F F→ (E)│id 3．