《编译原理》之常规知识点
一、 编译程序
1、 编译器是一种翻译程序，它用于将源语言（即用某种程序设计语言写成的）程序翻译为目标语言（即用二进制数表示的伪机器代码写成的）程序。后者在windows操作系统平台下，其文件的扩展名通常为.obj。该文件通常还要经过进一步的连接，生成可执行文件（机器代码写成的程序，文件扩展名为.exe）。通常有两种方式进行这种翻译，一种是编译，另一种是解释。后者并不生成可执行文件，只是翻译一条语句、执行一条语句。这两种方式相编译比解释运行的速度要快得多。
2、 编译过程的5个阶段：词法分析；语法分析；语义分析与中间代码产生；优化；目标代码生成。
3、 在这五个阶段中，词法分析的任务是识别源程序中的单词是否有误，编译程序中实现这种功能的部分一般称为词法分析器。在编译器中，词法分析器通常仅作为语法分析程序的一个子程序以便在它需要单词符号时调用。在这一编译阶段中发现的源程序错误，称为词法错误。
4、 语法分析阶段的目的是识别出源程序的语法结构（即语句或句子）是否错误，所以有时又常为句子分析。编译程序中负责这一功能的程序称为语法分析器或语法分析程序。在这一阶段中发现的错误称为语法错误。
5、 C语言的（源）程序必须经过编译才能生成目标代码，再经过链接才能运行。PASCAL语言、FORTRAN语言的源程序也要经过这样的过程。通常将C、PASCAL、FORTRAN这样的语言统称为高级语言。而将最终的可执行程序称为机器语言程序。
6、 在编译C语言程序的过程中，发现源程序中的一个标识符过长，超过了编译程序允许的范围，这个错误应在词法分析阶段发现，这种错误通常被称作词法错误。
? 词法分析器的任务是以词法规则为依据对输入的源程序进行单词及其属性的识别，识别
出一个个单词符号。 ? 词法分析的输入是源程序，输出是一个个单词的特殊符号，称为Token（标记或符号）。 ? 有两种方法可以实现词法分析器：一，手工编写词法分析程序。二，由词法分析器自动
生成程序生成。 ? 语法分析器的类型有:自下而上、自上而下。常用的语法分析器有：递归下降分析方法
是一种自上而下分析方法, 算符优先分析法属于自下而上分析方法，LR分析法属于自下而上分析方法等等。 ? 为了方便语法分析程序的使用，词法分析过程中通常对所识别出的单词符号进行分类。
以C语言为例，其中int、float等单词通常归入关键字类，而‘+’、‘-’、‘*’、‘/’等符号归入运算符类等等。
? 通常用正规文法或正规式来描述程序设计语言的词法规则，而使用上下文无关文法来
描述程序设计语言的语法规则。 ? 语法分析阶段中，处理的输入数据是来自词法分析阶段的单词符号。它们是词法分析阶
段的终结符。 7、 编译程序总框
源程序 词法分析器 单词符号 语法分析器 表
语法单位 语义分析与中间代码产生中间代码 优化器 中间代码 目标代码生成器 目标代码 出 格管理错处理8、 在计算机发展的早期阶段，内存较小的不能一次完成程序的编译。这时通常将编译过程分成若干遍来完成。每一遍完成一部分功能，称为多遍编译。
与采用高级程序设计语言写的词法分析器相比，用汇编语言写的词法分析通常分析速度要快些。 二. 词法与语法
1、 程序语言主要由语法和语义两个方面来定义。
2、 任何语言的程序都可看成是某字符集上的一个长字符串。
3、 语言的语法：是指这样的一组规则（即产生式），用它可以生成和产生一个良定的程序。这些规则的一部分称为词法规则，另一部分称为语法规则。
4、 词法规则：单词符号的形成规则；语法规则：语法单位（句子）的形成规则。语义规则：定义程序句子的意义。
5、 一个程序语言的基本功能是描述数据和对数据的运算。
6、 高级语言的分类：强制式语言；应用式语言；基于规则的语言；面向对象的语言。 7、 一个语言的字母表为{a,b}，则字符串ab的前缀有a、ε，其中ε不是真前缀。 8、 字符串的连接运算一般不满足交换率。
9、 文法G是一个四元组，或者说由四个元素构成，即非终结符集合VN、非终结符号集合VT 、开始符号S、产生式集合P，它可以形式化地表示成G =（VN，VT，S，P）。 按照文法的定义，这4个元素中终结符号集合是这个文法所规定的语言的字母表，产生式集合代表文法所规定的语言语法实体的集合。对上下文无关文法，通常我们只需要写出这个文法的产生式集合就可以确定这个文法的其他所有元素。其中，第一条产生式的左部符号为开始符号，而所有产生式的左部符号构成的集合就是该文法的非终结符集合。 ? 文法的例子：
设文法G=（VN，VT， S，P），其中P为产生式集合，它的每个元素的形式为产生式。 10、如果文法G的一个句子存在两棵不同的最左语法分析树，则这个文法是无二义的。 11、如果文法G的一个句子存在两棵不同的最右语法分析树，则这个文法是无二义的。 12、如果文法G的一个句子存在两棵不同的语法分析树，则这个文法是无法判断是否是二义的。
13、A为非终结符，如果文法存在产生式A??，则称?A?可以推导出a??；反之，称a??可归约为?A?。
14、乔姆斯基（Chomsky）将文法分为四类，即0型文法、1文法、2文法、3文法。 按照乔姆斯基对方法的分类，上下文无关文法是2型文法，2型文法的描述能力最强，3型文法又称为正规文法。
15、产生式S→Sa | a产生的语言为L(G) = {an | n ≥ 1}。
16、确定有限自动机DFA是非确定有限自动机NFA的特例；对任一非确定有限自动机能找到一个与之等价的确定有限自动机。
17、DFA和NFA的主要区别有三点：一、DFA初态唯一，NFA初态不唯一；二、DFA弧标记为Σ上的元素，NFA弧标记为Σ*上的元素；三、DFA的函数为单射，NFA函数不是单射。
18、有限自动机中两个状态S1和S2是等价的是指，无论是从S1还是S2出发，停于终态