# 第二章：语言及其文法
# 2.1 什么是语言？
语言是信息交流的工具。
简单来说：语言由句子组成，而句子由单词组成。
扩展起来则是：语言是满足一定条件的句子集合，而句子则是满足一定条件的单词序列，单词则是满足一定条件的字符串。
总而言之，语言就是字和组合字的规则。
# 2.2 文法的定义
文法被用于描述语言形式。
语法是语句的组成规则，描述语法方法有 BNF ，语法（描述）图。
词法是单词是组成规则，描述方法有 BNF 范式，正规式，有穷自动机。
文法规则定义存在两种方式，分别是乔姆斯基和克林提出的。前者是形式化的定义，后者是采用自动机理论的定义。这两个东西是编译的根基！除此之外乔姆斯基证明了这两个东西等价！也就是乔姆斯基的研究成果和克林研究的研究成果等价。
下面是乔姆斯基定义的定义，也就是形式化定义。
形式化定义：
通俗的讲，终结符是不可分的元素，非终结符可以继续拆分的元素。
除此之外克林也定义了一套语言规则：
克林从状态转换的角度，也就是自动机理论来研究文法规则。
首先理解闭包，闭包分为正闭包和克林闭包，区别在于克林闭包含有空符号。形式化语言就是克林闭包的子集。
正闭包：
$$ L^+ = L \cup L^1 \cup L^2 \cup L^3 \cup L^4 \cup ...... $$
克林闭包：
$$ L^* = L^0 \cup L \cup L^1 \cup L^2 \cup L^3 \cup L^4 \cup ...... $$
自动机理论推导：
$$ M = (\sum, Q, a, q_0, F) $$
从此以后就采用文法来描述程序设计语言。例如巴科斯范式（BNF），这是一种上下文无关的文法。
# 2.3 语言的定义
如何判断一个句子是否满足文法的定义？
通过推导和规约。
推导和规约是相反的，例如语法分析树自顶向下是推导，自底向上是规约。
# 2.4 文法的分类
如何通过有限的规则来描述无限的语言。
句型和句子的区别。
句型由终结符和非终结符的克林闭包，也就是可以继续向下推导。句子则是终结符的克林闭包，不含非终结符。
区别在于句子中不能含有非终结符，句型中含有非终结符。
乔姆斯基进一步对语言进行了分类。也就是文法分为四种类型，称为乔姆斯基文法分类体系。
- 0 型文法
无限制文法，其中产生式
相当于图灵机。
- 1 型文法 （CSG）
上下文有关文法，一般形式
例如声明变量，在 C 语言中需要先声明变量分配空间，方便后续使用。这就是一个上下文有关文法。
形参和实参个数对应。
相当于线性界限自动机。
- 2 型文法 （CFG）
上下文无关文法，不需要考虑上下文可以直接替换。
不确定的下推自动机。
- 3 型文法
正则文法，分为右线性文法和左线性文法。注意二者不能混淆，要么写成左线型，要么写成右线性。
相当于有穷自动机。
四种文法规则是包含关系，从 0 型开始到 3 型结束约束逐渐递进。
# 2.5 CFG 分析树（上下文无关文法）
分析树的树根表示开始符号，中间结点为非终结符，叶子节点为终结符。
什么是短语？句型中的一个子串，如果这个子串能用一个非终结符推导出来，那么这个子串就是短语。
直接短语是一步推导，间接短语是多步推导。
短语就是语法分析树所有子树的叶子节点。直接短语是仅有父子两代的子树，
句柄是最左直接短语。
二义性文法：分析树存在多个，可以通过引入分析规则来消除二义性。
虽然不存在任何一个算法能够判定一个文法是否具备二义性，但是有一组充分条件，只要满足该组充分条件就必定无二义性。