编译原理重点 .pdfVIP

编译原理重点

第一章1.编译原理所讨论的问题，就是如何把符合人类思维方式

的、用文字描述的意愿（源程序）翻译成计算机能够理解和执行的形

式（目标程序）。具

体实现从源程序到目标程序转换的程序，被称为编译程序或编译

器。2.用符

号表示的指令被称为汇编指令。3.汇编指令的集合被称为汇编语

言。4.由汇编语言编写的指令序列被称为汇编语言程序。5.通用程序设

计语言是继汇编语言之后发展起来的应用最广的一类语言。6.语言分

为三个层次：高级语言、汇编语言、机器语言。高级语言之间的翻译

被称为转换或者预处理；高级语言可

以直接翻译成机器语言，也可以直接翻译成汇编语言，这两个翻

译过程被称

为编译；从汇编语言到机器语言的翻译称为汇编；把机器语言翻

译成汇编语

言或者把汇编语言翻译成高级语言，分别称它们为反汇编和反编

译。7.公认为最早的编译器是50年代末研制的FORTRAN编译器。8.

解释器与编译器的主要区别：运行目标程序时的控制权在解释器而不

在目标程序。9.通用程序设计语言的典型特征之一是抽象，其抽象程

度是以程序设计语言所支持的基本结

构为特征的，可以大致划分为三种形式：过程、模块（抽象数据

类型、ADT）和类。10.编译器的工作阶段：符号表管理器（词法分析

器、语法分析器、语义分析器、中间代码生成器、代码优化器、目标

代码生成器）出错处理器。

11.编译器从左到右扫描输入该语句，首先进行的是此法分析。词

法分析器的

输入是源程序，输出的是识别出的记号流。12.语法分析器以词法

分析器返回的记号流为输入构造句子的结构，并以树的形式表示出来，

称之为语法树。

13.语义分析器根据语法分析器够早的语法树，进行适当的语义处

理。对于声

明语句，进行符号表的查填。14.编译器生成的目标程序代码的多

种形式：汇编语言形式、可重定位二进制代码形式、内存形式。15.我

们把每个阶段将程序完全扫描一遍的工作模式称为一遍扫描。

第二章1.组成语句的基本单元也可根据其在句子中的作用分类，

最基本的分类有四类：关键字（保留字）、标示符、字面量、特殊符

号。2.产生和识别单词的规则称为模式；按照某个模式（规则）被识

别出的元素称为记号；单词指

被别出的元素自身的值。3.定义2.1语言L是有限字母表∑上有限

长度字符串的集合（字符串是有限的，即字母表中的元素是有限多个；

字符串的长度是

有限的，即字符串中字符的个数是有限多个）4.简答：令∑是一个

有限字母表，则∑上的正规式及其表示的集合递归定义如下：（1）ε

是正规式，它表示集合L（ε）={ε}；（2）若a是∑上的字符，则a是

正规式，它表示集合L（a）

={a}；（3）若正规式r和s分别表示集合L(r)和L(s):①r︱s是正

规式，表

示集合L(r)∪L(s)；②rs是正规式，表示集合L(r)L(s)；③r*表示

正规式，表示集合（L(r)）*；④(r)是正规式，表示的集合仍然是L(r)。

5.可用正规式描

述的语言称为正规语言或正规集。6.简答：NFA是一个五元组

（5-tupie）

M=(S,∑，move,s0,F),其中：（1）S是有限个状态(state)的集合；

（2）∑是有限个输入字符（包括ε）的集合；（3）move是一个状态

转移函数，

move(si,ch)=sj表示当前状态si遇到输入字符ch，则转移到状态

sj；（4）s0是唯一的初态（也称开始状态）；（5）F是终态集（也

称接受状态集），它是S的子集，包含了所有的终态。7.有限自动机可

以用两种直观的方式来表示——状态转换图和状态转换矩阵，简称转

换图和转换矩阵。8.定义2.5DFA

是NFA的一个特例，其中：（1）没有状态具有ε状态转移（ε—

trasition），即状态转换图中没有标记ε的边；（2）对每一个状态s

和每一个字符a，最多有一个下一状态。9.定义2.6若有限自动机M和

M’识别同一个正规集，则称M和M’是等价的，记为M=M’。

第三章1.语法分析的双重含义：（1）规定句子形成的规