编译原理基础知识
哥德尔不完备定理
对于一个形式系统，它能从基本的公理推导出其他结论。
- 如果它能推出所有的结论，那么它就是完全性的。
- 如果它推出的所有结论都是对的，那么它就是可靠的。 可靠性的证明容易保证，只要保证公理是对的，推导过程是对的，那么就是可靠的。 但是问题就在于完全性的证明。哥德尔证明出，如果一个系统能表达初等数学，那么存在一个公式，形式系统既不能推出它，也不能推出它的否定，即形式系统无法判定它. 也就是再强的形式系统也具有其无法证明的陈述。
文法
乔姆斯基把文法分成 4 种类型，即 0 型，1 型，2 型，和 3 型。
0 型文法
0 型文法也称短语文法，0 型文法的能力相当于图灵机 (Turing), 或者说任何 0 型语言都是递归可枚举的。 产生式没有任何限制。 图灵机对于任意输入，只有三种状态：
接受: 正确运行到结束并且停机。拒绝: 状态转移函数无定义，落空停机。不停机（无法判定）: 一直有定义，但永不停机。 如果对于 L 语言，它的任何串的结果都是 1 或 2, 那么它任何一个串都能被判定，这样就称之为递归语言。 如果对于 L 语言，它的任何串的结果都是 1 或 2 或 3, 即如果一个串在接受集合内，就一定会接受，如果不再，就无法验证，这样就称之为递归可枚举语言。递归语言是递归可枚举语言的子集。
1 型文法
形如 αAβ -> αγβ , α, β 可以是空串，但 γ 必须不能是空串。1 型文法也称上下文有关法，其能力相当于线性界限自动机.
2 型文法
2 型文法也称上下文无关法，其能力相当于非确定的下推自动机.
形如 A -> γ . 这里的 A 是非终结符号， γ 是包含非终结符号与终结符号的字串。这种文法规定的语言可以被非确定下推自动机接受。上下文无关语言为大多数程序设计语言的语法提供了理论基础。
3 型文法
3 型文法也称右线性文法，由于这种文法等价于正规式，所以也称正规文法，相当于有限状态自动机.
- 左边必须只有一个字符，且必须是非终结符；
- 其右边最多只能有两个字符，且当有两个字符时第一个为非终结符而另一个为终结符。当右边只有一个字符时，此字符必须为终结符。或者右侧是空。 从文法描述语言的能力来说，0 型文法最强，3 型文法最弱.
自动机
图灵机
图灵机是个抽象的计算模型。它拥有一个读写头，一个无限长的纸带，一个寄存器（用以存储当前的状态，其中有个特殊的状态叫停机状态）, 一套通用的计算规则。 我们可以构造出一个特殊的图灵机，它接受任意一个图灵机 M 的编码，然后模拟 M 的运作，这样的图灵机称为通用图灵机 (Universal Turing Machine). 现代电子计算机其实就是这样一种通用图灵机的模拟，它能接受一段描述其他图灵机的程序，并运行程序实现该程序所描述的算法。但是也只是模拟，因为计算机的存储能力是有限的。 计算机的极限计算能力就是通用图灵机的计算能力。
线性界限自动机
线性界限自动机就是把计算固定在输入带范围上的图灵机。也就是不是无限长的纸带。
下推自动机
下推自动机 (PDA) 可以看成是一个带有附加下推存储器的有限自动机，下推存储器是一个堆栈。 如果把下推自动机扩展，允许一个有限状态自动机存取两个栈，将会得到一个能力更强的自动机，与图灵机等价。
有限状态自动机
自动机从初始状态 q0 起，逐一读入输入串（由输入字母表 Σ 的字母构成）的每一个字母，根据当前状态、输入字母和转移函数 δ 决定自动机的下一步状态；如果输入串结束时，自动机处于终结状态集合 F 的某一个状态，这表示自动机接受该字串；否则自动机不接受该字串。
