《编译原理》之常规知识点

1、编译原理之常规知识点编译程序1、编译器 是一种翻译程序， 它用于将 源语言 （即用某种程序设计语言写成的） 程序翻译为 目标语言 （即用二进制数表示的伪机器代码写成的）程序。后者在 windows 操作系统平台 下，其文件的扩展名通常为 .obj。该文件通常还要经过进一步的连接，生成 可执行文件 （机 器代码写成的程序，文件扩展名为 .exe）。通常有两种方式进行这种翻译，一种是编译 ，另一种是 解释 。后者并不生成可执行文件， 只是翻译一条语句、 执行一条语句。这两种方式相 编译比解释运行的速度要快得多。2、编译过程的 5 个阶段 ：词法分析；语法分析；语义分析与中间代码产生；优化；目标代

2、码生成。3、在这五个阶段中， 词法分析 的任务是识别源程序中的单词是否有误，编译程序中实现这 种功能的部分一般称为词法分析器。 在编译器中， 词法分析器通常仅作为 语法分析程序 的一 个子程序以便在它需要单词符号时调用。 在这一编译阶段中发现的源程序错误， 称为 词法错 误。4、语法分析 阶段的目的是识别出源程序的语法结构（即语句或句子）是否错误，所以有时 又常为 句子分析 。编译程序中负责这一功能的程序称为 语法分析器 或 语法分析程序 。在这 一阶段中发现的错误称为 语法错误 。5、C 语言的（源）程序必须经过编译才能生成目标代码，再经过链接才能运行。PASCAL语言、 FORTRAN 语

3、言的源程序也要经过这样的过程。通常将C、 PASCAL 、 FORTRAN 这样的语言统称为 高级语言 。而将最终的可执行程序称为 机器语言程序 。6、在编译 C 语言程序的过程中， 发现源程序中的一个标识符过长， 超过了编译程序允许的 范围，这个错误应在词法分析阶段发现，这种错误通常被称作词法错误。词法分析器的 任务 是以词法规则为依据对输入的源程序进行单词及其属性的识别， 识别 出一个个单词符号。Token（标记或符号），由词法分析器 自动词法分析的 输入 是源程序， 输出 是一个个单词的特殊符号，称为有两种方法可以 实现 词法分析器： 一，手工编写 词法分析程序。 生成 程序生成。语法分

4、析器的 类型 有:自下而上、自上而下。常用的语法分析器有：递归下降分析方法是一种自上而下分析方法 , 算符优先分析法 属于自下而上分析方法， LR 分析法 属于自 下而上分析方法等等。单词符号进行分类为了方便语法分析程序的使用，词法分析过程中通常对所识别出的以 C 语言为例，其中 int、float 等单词通常归入 关键字类 ，而 +、-、*、/等符号归 入 运算符类 等等。词法规则 ，而使用 上下文无关文法 来通常用 正规文法 或 正规式 来描述程序设计语言的 描述程序设计语言的 语法规则 。语法分析阶段中， 处理的输入数据是来自词法分析阶段的单词 符号 。它们是词法分析阶 段的终结符。7、

5、编译程序总框8、在计算机发展的早期阶段，内存较小的不能一次完成程序的编译。这时通常将编译过程 分成若干遍来完成。每一遍完成一部分功能，称为多遍编译。与采用高级程序设计语言写的词法分析器相比， 用汇编语言写的词法分析通常分析速度 要快些。. 词法与语法1、程序语言主要由语法和语义两个方面来定义。2、任何语言的程序都可看成是某字符集上的一个长字符串。3、语言的语法：是指这样的 一组规则 （即产生式） ，用它可以生成和产生一个良定的程序。 这些规则的一部分称为 词法规则 ，另一部分称为 语法规则 。4、词法规则 ：单词符号的形成规则； 语法规则 ：语法单位 （句子）的形成规则。 语义规则 ： 定义程

6、序句子的意义。5、一个 程序语言的基本功能 是描述数据和对数据的运算。6、高级语言的分类：强制式语言；应用式语言；基于规则的语言；面向对象的语言。7、一个语言的字母表为 a,b ，则字符串 ab 的前缀有 a、 ，其中 不是真前缀。8、字符串的连接运算一般不满足交换率。9、文法 G 是一个四元组，或者说由四个元素构成，即非终结符集合VN、非终结符号集合VT 、开始符号 S、产生式集合 P，它可以形式化地表示成 G =(VN，VT，S，P)。按照文法的定义， 这 4个元素中 终结符号集合 是这个文法所规定的语言的 字母表 ，产生式集 合代表文法所规定的语言语法实体的集合。 对 上下文无关文法 ，

7、通常我们只需要写出这个文 法的产生式集合就可以确定这个文法的其他所有元素。其中， 第一条产生式的左部符号为 开始符号 ，而 所有产生式的左部符号构成的集合就是该文法的 非终结符集合 。文法的 例子 ：设文法 G=(VN，VT， S，P)，其中 P为产生式集合 ，它的每个元素的形式为 产生式 。10、如果文法 G 的一个句子存在两棵不同的最左语法分析树，则这个文法是无二义的。11、如果文法 G 的一个句子存在两棵不同的最右语法分析树，则这个文法是无二义的。12、如果文法 G 的一个句子存在两棵不同的语法分析树，则这个文法是无法判断是否是二 义的。13、A 为非终结符， 如果文法存在产生式 A ，

8、则称 A 可以推导出 a ；反之，称 a 可归约为 A 。14、乔姆斯基( Chomsky )将文法分为四类，即 0型文法、 1文法、 2文法、 3文法。按照乔姆斯基对方法的分类， 上下文无关文法 是2型文法， 2型文法的描述能力最强， 3 型文法又称为 正规文法 。15、产生式 SSa | a产生的语言为 L(G) = a n | n 1。16、确定有限自动机 DFA 是非确定有限自动机 NFA 的特例； 对任一非确定有限自动机能找 到一个与之等价的确定有限自动机。17、DFA 和 NFA 的主要区别有三点：一、 DFA 初态唯一， NFA 初态不唯一；二、 DFA 弧 标记为 上的元素，

9、NFA 弧标记为 *上的元素；三、 DFA 的函数为单射， NFA 函数不是单 射。18、有限自动机中两个状态 S1和 S2是等价的是指，无论是从 S1还是 S2 出发，停于终态 时，所识别的输入字的集合相同。19、自 下而上的分析方法 ，是一个不断归约的过程。20、递归下降分析器 ：当一个文法满足 LL(1) 条件时，我们就可以为它构造一个不带 回溯 的 自上而下分析程序。 这个分析程序是由一组 递归过程 组成的， 每个过程对应文法的一个非终 结符。A Aa 这个产生式中含有的左递归是 直接左递归 。 递归下降分析法 中，必须要消除 所有的左递归。 递归下降分析法 中的 试探分析法 之所以要

10、不断用一个产生式的多个 候选式 进行逐个试探，最根本的原因是这些候选式有 公共左因子 。21、算符优先分析 法是一种自下而上的分析方法，它适合分析各种程序设计语中的表达式 ，并宜于 手工实现 。目前最广泛的 无回溯 的“移进 - 归约”方法是 自下而上 分析方法。22、在 表驱动预测分析器 中， 1)读入一个终结符 a，若该终结符与栈项的终结符相同，并 且不是结束标志 $，则此时栈顶符号出栈； 2)若此时栈项符号是终结符并且是 $，并且读入 的终结符不是 $，说明源程序有语法错误； 3)若此时栈顶符号为 $，并且读入的终结符也是 $， 则分析成功。23、算符优先分析方法 不存在使用形如 T F

11、 这样的产生式进行的归约，即只要求终结符 的位置与产生式结构一致，从而使得分析速度比 LR 分析法更快。24、LR(0) 的例子：产生式 E E+T 对应的 LR( 0)项目中，待归约的项目是 E E+?T，移进项目是 E E?+T， 还有两个项目为 E ?E+T 和 E E+T?。当一个 LR(0) 项目集中含有两个 归约项目 时，称这个项目集中含有 归约 -归约冲突 。25、LL(1)文法的产生式中一定没有 公共左因子 ，即 LL(1)文法中一定没有 左递归 。为了避 免回溯，在 LL(1) 文法的预测分析表中，一个表项中至多只有一个产生式。预测分析方法 (即 LL(1)方法)，由一个 栈，一个 总控程序 和一个 预测分析表 组成。其 中构造 出预测分析表是该分析方法的关键。26、LR(0)与 SLR(1)两种分析方法相比， SLR(1)的能力更强。27、静态语义检查 一般包括以下四个部分，即 类型检查 、控制流检查 、名字匹配检查 、 一 致性检查 。C 语言编译过程中下述常见的错误都属于检查的范围：a) 将字符型指针 的值赋给 结构体类型的指针 变量：类型检查。b) switch语句 中，有两个 case语句 中出现了相同的常量：一致性检查。c）break 语句 在既不是循环体内、又不