编译原理复习点.docVIP

编译原理复习 1.简答题 /**********往年问答题**********/ 1)按照次序写出一个完整的编译器的各个阶段以及各个阶段的输入输出(The phases of a complier)。 扫描程序：执行词法分析将字符序列收集到称作记号的有意义单元中。输入：源程序，输出：记号； 语法分析程序：从扫描程序中获得记号形式的源代码，并完成定义程序结构的语法分析。输入：记号，输出：语法树； 语义分析程序：分析程序中在执行之前被确定但是不易由语法表示和分析程序分析的特征，即分析程序中的静态语言。输入：语法树，输出：注释树； 源代码优化程序：对代码进行改进产生中间代码。输入：注释树，输出：中间代码； 代码生成器：得到中间代码，并生成目标机器的代码。输入：中间代码，输出：目标代码； 目标代码优化程序：改进由代码生成器生成的目标代码，包括：选择编址模式以提高性能、将速度慢的指令更换成速度快的，以及删除多余的操作。输入：目标代码，输出：优化后目标代码。 2)词法分析和语法分析的功能分别是什么(The task of a scanner,parser) 词法分析：将源程序读作字符文件并将其分为若干记号。 语法分析：从扫描程序中获得记号形式的源代码，并确定程序的语法结构，以及构造出表达该结构的语法树或分析树。 3)编译器的前端(front end)和后端(back end)分别包括哪几个阶段？前后端分开有什么好处？ 前端：只依赖于源语言的操作，包括：扫描程序、语法分析程序、语义分析程序和中间代码的综合。 后端：只依赖于目标语言的操作，包括：代码生成器和一些优化分析。 好处：该结构对编译器的可移植性十分重要。 4)给出上下文无关文法(context-free grammar)的定义 若一个形式文法 G = (N, Σ, P, S) 的产生式规则都取如下的形式：V - w，则称之为上下文无关的，其中 V∈N ，w∈(N∪Σ)* 5)解释器(interpreter)和编译器(compiler)有什么本质区别？ 解释器立即执行源程序而不是生成在翻译完成后才执行的目标代码。 6)分析树(parse tree)和抽象语法树(syntax tree)有什么不同？ 分析树是一个作了标记的树，其内部的节点由其表示的结构名标出，树叶节点则表示输入中的记号序列。抽象语法树是源代码记号序列的抽象表示。分析树不利于表示程序结构，包括了比生成可执行代码所需要的更多信息。抽象语法树不能重新得到记号序列，但是包含了转换所需的所有信息，而且比分析树效率更高。分析程序可通过一个分析树表示所有步骤，但是通常只能构造出一个抽象语法树。 7)在建立LL(1)语法分析器的时候，提取左因子和消除左递归的目的分别是什么？ 提左因子 只是推后产生式的选择决定，等到获取足够多的输入再作选择。 消除左递归 是因为LL文法不能处理含有左递归的文法。 /*******以下根据老师复习课补充**********/ 8)什么是分析部分（analysis）和综合部分(synthesis)？分开两者有什么好处？ 将分析源程序以计算其特性的编译器操作归为编译器的分析部分；将生成翻译代码时所涉及到的操作称作编译器的综合部分。词法分析、语法分析和语义分析属于分析部分。代码生成是综合部分。优化步骤中，分析和综合都有。 好处：分析正趋向于易懂和更具有数学性，而综合要求更深的专业技术。因此将分析步骤和综合步骤分开以便发生变化时互不影响是很有用的。 9)什么是遍(pass)？ 编译器发现，在生成代码之前多次处理整个源程序很方便，这些重复就是遍。首遍是从源中构造一个语法树和中间代码，在它之后的遍是由处理中间表示、向它增加信息、更换结构或生成不同的表示组成。 10)给出最左推导和最右推导的定义 最左推导：是指每一步中最左的非终结符都要被替换的推导。 最右推导：是指每一步中最右的分终结符都要被替换的推导。 11)什么是自顶向下分析？什么是自底向上分析？二者有什么不同？ 自顶向下分析算法：自顶向下的分析算法通过在最左推导中描述出各个步骤来分析记号串输入，之所以称这样的算法为自顶向下是由于分析树隐含的编号是一个前序编号，而且其顺序是由根到叶。 自底向上分析算法：最普通的自底向上算法称作LR（1）分析（L表示由左向右处理输入，R表示生成了最右推导，而数字1则表示使用了先行的1个符号）。 12)什么是NFA？什么是DFA？ DFA下一个状态由当前状态和输入字符唯一给出的自动机。 形式定义：DFA（确定性有穷自动机）M由字母表?、状态集合S、转换函数T: S′?-S、S的初始状态s0?S以及接受状态的集合AìS组成。由M接受的且写作L(M)被定义为字符c1c2c3……cn串的集合，其中每个ci??，存在