3A.2 文法

3.2.1 定义

自然语言有明确的语法，用来约束如何构建一个合法的句子。程序语言也一样，这个控制程序结构的规则叫着文法。文法是用来定义形式语言结构的规则，其规范的定义如下：

1. 一个终结符号集合, 例如：英文字母

2. 一个非终结符号集合，也被叫着文法变量

3. 产生式，符号的转换规则，通用形式为：α -> β，其中 α 与 β 可以是任意形式的符号串。例如 S ->（），表示任何 S 都可以被一个括号对替换。产生式的右边可以是终结符号与非终结符号的任意组合

4. 开始符号

概括地说，文法就是生成符号串的规则。

3.2.2 上下文无关文法 - Context-Free Grammar(CFG)

程序语言的文法通常使用一种叫着上下文无关文法的形式来表示。其对产生式做了如下限制：α -> β 中，α 只能是一个非终结符号。这也是“上下文无关”的意义：使用产生式将任意非终结符号 A 替换为其他符号串时，跟 A 所在的位置、以及 A 旁边的符号无关。

例如下面文法就是上下文无关文法，用来生成任意的合法括号对：

S -> (S) | SS | ()

其中：

1. 终结符号集合：由 "(" 与 ")" 组成

2. 非中介符号集合：只有 S

3. 产生式有三个

4. 开始符号：S

对编译器而言，任何源程序都是一个字符串，程序语言的文法确定了程序的合法结构。只是程序文法中的终结符号不是单个字母，而是词法分析的输出结果：Token

3.2.3 推导 - Derivation

通过文法生成一个字符串的整个过程被称为一个推导。考虑上面生成括号对的文法：S ->（S）-> （SS）->（（）S）->（（）（））就是一个推导。

• 最左推导 每次都使用最左边的非终结符号进行推倒的过程，例如下面就是一个最左推导：

  S -> SS ->（）S ->（）（S）->（）（（））

• 最右推导 每次都使用最右边的非终结符号进行推倒的过程，例如下面就是一个最右推导：

  S -> SS -> S（S）-> S（（））->（）（（））

3.2.4 解析树 - Parse Tree

解析树是一个推导过程的可视化，其叶子节点都是终结符号，中间节点都是非终结符号，叶子节点从左到右的排列就是被推导的终结符号串。如下例：

推导：S -> SS -> S（S）-> S(())->()(())解析树：

Parse Tree

解析树只反映了整个字符串的推导方式，并没有体现其推导顺序。例如根据上面的解析树无法得知采用的是最左推导还是最右推导。