# 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)

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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://gocompiler.shizhz.me/3.b-yu-fa-fen-xi-li-lun-zhi-shi/3.2-wen-fa.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.