1、编译 原理期末 测试题专业班级：_学号：_姓名：_总分 一、单项选择题(共 10 小题，每小题 2 分) （题分 20 分）1语言是A句子的集合 B产生式的集合 C符号串的集合 D句型的集合2编译程序前三个阶段完成的工作是A词法分析、语法分析和代码优化 B代码生成、代码优化和词法分析C词法分析、语法分析、语义分析和中间代码生成 D词法分析、语法分析和代码优化3一个句型中称为句柄的是该句型的最左A非终结符号 B短语 C句子 D直接短语4下推自动机识别的语言是A0 型语言 B1 型语言 C2 型语言 D3 型语言5扫描器所完成的任务是从字符串形式的源程序中识别出一个个具有独立含义的最小语法单位即A
2、 字符 B单词 C句子 D句型6对应 Chomsky 四种文法的四种语言之间的关系是AL 0L1L2L3 BL 3L2L1L0CL 3=L2L1L0 DL 0L1L2=L37词法分析的任务是A识别单词 B分析句子的含义C识别句子 D生成目标代码8常用的中间代码形式不含A三元式 B四元式 C逆波兰式 D语法树9 代码优化的目的是A节省时间 B节省空间 C节省时间和空间 D把编译程序进行等价交换10代码生成阶段的主要任务是A把高级语言翻译成汇编语言装订线得分B把高级语言翻译成机器语言C把中间代码变换成依赖具体机器的目标代码D把汇编语言翻译成机器语言二、填空题（本大题共 5 小题，每小题 2 分）
3、（题分 10 分）1编译程序首先要识别出源程序中每个( )，然后再分析每个( )并翻译其意义。 2编译器常用的语法分析方法有( )和( )两种。3通常把编译过程分为分析前端与综合后端两大阶段。词法、语法和语义分析是对源程序的( )，中间代码生成、代码优化与目标代码的生成则是对源程序的( )。4程序设计语言的发展带来了日渐多变的运行时存储管理方案，主要分为两大类，即：( )方案和( )方案。5对编译程序而言，输入数据是( )，输出结果是 ( )。三、名词解释题(共 5 小题，每小题 4 分) （题分 20 分）1词法分析2LL(1)文法3语法树4LR(0)分析器5语言和文法四、简答题(共 4 小
4、题，每小题 5 分) （题分 20 分）1编译程序和高级语言有什么区别?2编译程序的工作分为那几个阶段?3简述自下而上的分析方法。4简述代码优化的目的和意义。五、综合应用题(共 3 小题，每小题 10 分) （题分 30 分）1证明下述文法 G：SaSbS|aS|d是二义性文法。2对于文法 GS：SAB ， AAa|bB，Ba|Sb 求句型 baSb 的全部短语、直接短得分得分得分得分语和句柄？句型 baSb 的语法树如图五(2)所示。图五(2) 句型 baSb 的的语法树3设有非确定的有自限动机 NFA M=(A，B ，C，0，1， ，A，C)，其中： (A，0)=C (A，1)=A，B (
5、B，1)=C (C，1)=C。请画出状态转换距阵和状态转换图。参考答案一、单项选择题(共 10 小题，每小题 2 分，共 20 分)ASBb B Sab1语言是A句子的集合 B产生式的集合 C符号串的集合 D句型的集合2编译程序前三个阶段完成的工作是A词法分析、语法分析和代码优化 B代码生成、代码优化和词法分析C词法分析、语法分析、语义分析和中间代码生成 D词法分析、语法分析和代码优化3一个句型中称为句柄的是该句型的最左A非终结符号 B短语 C句子 D直接短语4下推自动机识别的语言是A0 型语言 B1 型语言 C2 型语言 D3 型语言5扫描器所完成的任务是从字符串形式的源程序中识别出一个个具
6、有独立含义的最小语法单位即A 字符 B单词 C句子 D句型6对应 Chomsky 四种文法的四种语言之间的关系是AL 0L1L2L3 BL 3L2L1L0CL 3=L2L1L0 DL 0L1L2=L37词法分析的任务是A识别单词 B分析句子的含义C识别句子 D生成目标代码8常用的中间代码形式不含A三元式 B四元式 C逆波兰式 D语法树9 代码优化的目的是A节省时间 B节省空间 C节省时间和空间 D把编译程序进行等价交换10代码生成阶段的主要任务是A把高级语言翻译成汇编语言B把高级语言翻译成机器语言C把中间代码变换成依赖具体机器的目标代码D把汇编语言翻译成机器语言二、填空题（本大题共 5 小题，
7、每小题 2 分，共 10 分）1编译程序首先要识别出源程序中每个(单词) ，然后再分析每个 (句子)并翻译其意义。 2编译器常用的语法分析方法有(自底向上) 和(自顶向下)两种。3通常把编译过程分为分析前端与综合后端两大阶段。词法、语法和语义分析是对源程序的(分析) ，中间代码生成、代码优化与目标代码的生成则是对源程序的(综合)。4程序设计语言的发展带来了日渐多变的运行时存储管理方案，主要分为两大类，即(静态存储分配)方案和( 动态存储分配) 方案。5对编译程序而言，输入数据是(源程序) ，输出结果是(目标程序)。三、名词解释题(共 5 小题，每小题 4 分，共 20 分)1词法分析词法分析的
8、主要任务是从左向右扫描每行源程序的符号，按照词法规则从构成源程序的字符串中识别出一个个具有独立意义的最小语法单位，并转换成统一的内部表示(token)，送给语法分析程序。2LL(1)文法若文法的任何两个产生式 A | 都满足下面两个条件：（1）FIRST( ) FIRST( ) = ；（2）若 * ，那么 FIRST( ) FOLLOW( A ) = 。我们把满足这两个条件的文法叫做 LL(1)文法，其中的第一个 L 代表从左向右扫描输入，第二个 L 表示产生最左推导，1 代表在决定分析器的每步动作时向前看一个输入符号。除了没有公共左因子外，LL(1) 文法还有一些明显的性质，它不是二义的，也
9、不含左递归。3语法树句子的树结构表示法称为语法树(语法分析树或语法推导树) 。给定文法 G=(VN，V T，P，S)，对于 G 的任何句型都能构造与之关联的语法树。这棵树具有下列特征：(1)根节点的标记是开始符号 S。(2)每个节点的标记都是 V 中的一个符号。(3)若一棵子树的根节点为 A，且其所有直接子孙的标记从左向右的排列次序为 A1A2AR，那么 AA1A2AR 一定是 P 中的一条产生式。(4)若一标记为 A 的节点至少有一个除它以外的子孙，则 A VN。(5)若树的所有叶节点上的标记从左到右排列为字符串 w，则 w 是文法 G的句型；若 w 中仅含终结符号，则 w 为文法 G 所产
10、生的句子。4LR(0)分析器所谓 LR(0)分析，是指从左至右扫描和自底向上的语法分析，且在分析的每一步，只须根据分析栈当前已移进和归约出的全部文法符号，并至多再向前查看 0 个输入符号，就能确定相对于某一产生式左部符号的句柄是否已在分析栈的顶部形成，从而也就可以确定当前所应采取的分析动作 (是移进还是按某一产生式进行归约等)。5语言和文法文法就是语言结构的定义和描述，是有穷非空的产生式集合。文法 G 定义为四元组的形式：G=(VN，V T，P ，S)其中：V N 是非空有穷集合，称为非终结符号集合；V T 是非空有穷集合，称为终结符号集合；P 是产生式的集合( 非空)；S 是开始符号( 或识
11、别符号)。这里，V NVT=，S VN。V=V NV T，称为文法 G 的字母表，它是出现文法产生式中的一切符号的集合。文法 G 所描述的语言用 L(G)表示，它由文法 G 所产生的全部句子组成，即L(G)=x| S*x，其中 S 为文法开始符号，且 TVx简单的说，文法描述的语言是该文法一切句子的集合。四、简答题(共 4 小题，每小题 5 分，共 20 分)1编译程序和高级语言有什么区别?用汇编语言或高级语言编写的程序，必须先送入计算机，经过转换成用机器语言表示的目标程序（这个过程即编译），才能由计算机执行。执行转换过程的程序叫编译程序。汇编程序是指没有编译过的汇编语言源文件。编译程序转换过
12、的叫目标程序，也就是机器语言。编译程序的工作情况有三种：汇编型、解释型和编译型。汇编型编译程序用来将汇编语言编写的程序，按照一一对应的关系，转换成用机器语言表示的程序。解释型编译程序将高级语言程序的一个语句，先解释成为一组机器语言的指令，然后立即执行，执行完了，取下一组语句解释和执行，如此继续到完成一个程序止。用解释型编译程序，执行速度很慢，但可以进行人和计算机的“对话“ ，随时可以修改高级语言的程序。BASIC 语言就是解释型高级语言。编译型编译程序将级语言编写的程序，一次就会部翻译成机器语言表示的程序，而且过程进行很快，在过程中，不能进行人机对话修改。FORTRAN 语言就是编译型高级语言
13、。2编译程序的工作分为那几个阶段?词法分析、语法分析和语义分析是对源程序进行的分析(称为编译程序的前端) ，而中间代码生成、代码优化和代码生成三个阶段合称为对源程序进行综合(称为编译程序的后端)，它们从源程序的中间表示建立起和源程序等价的目标程序。3简述自下而上的分析方法。所谓自下而上分析法就是从输入串开始，逐步进行“归约”，直至归约到文法的开始符号；或者说从语法树的末端开始，步步向上“归约”，直到根节点。4简述代码优化的目的和意义。代码优化是尽量生成“好”的代码的编译阶段。也就是要对程序代码进行一种等价变换，在保证变换前后代码执行结果相同的前提下，尽量使目标程序运行时所需要的时间短，同时所占
14、用的存储空间少。五、综合应用题(共 3 小题，每小题 10 分，共 30 分)1证明下述文法 G：SaSbS|aS|d是二义性文法。解：一个文法，如果存在某个句子有不只一棵语法分析树与之对应，那么称这个文法是二义性文法。句子 aadbd 有两棵语法树。如下图：(1) (2)由此可知，SaSbS|aS|d 定义的文法是二义性文法。2对于文法 GS：SAB ， AAa|bB，Ba|Sb 求句型 baSb 的全部短语、直接短语和句柄？句型 baSb 的语法树如图五(2)所示。ASBb B SabdSSa bSSadSa SSa bSdd图五(2) 句型 baSb 的的语法树解：baSb 为句型 baSb 的相对于 S 的短语，ba 为句型 baSb 的相对于 A 的短语，Sb 为句型baSb 的相对于 B 的短语，且为直接短语， a 为句型 baSb 的相对于 B 的短语，且为直接短语和句柄。3设有非确定的有自限动机 NFA M=(A，B ，C，0，1， ，A，C)，其中： (A，0)=C (A，1)=A，B (B，1)=C (C，1)=C。请画出状态转换距阵和状态转换图。解：状态转换距阵为： 0 1A C A，BB CC C状态转换图为：A B 1C11011
