> For the complete documentation index, see [llms.txt](https://gocompiler.shizhz.me/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://gocompiler.shizhz.me/3.b-yu-fa-fen-xi-li-lun-zhi-shi/3.2-wen-fa.md).

# 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](/files/-Mb0ZsCQY_-Fh4QtW4YM)

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