> For the complete documentation index, see [llms.txt](https://koshizuow.gitbook.io/compilerbook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://koshizuow.gitbook.io/compilerbook/calculator_level_language/recursive_descendent_parsing/bnf.md).

# 以 BNF 描述生成規則

BNF（Backus–Naur form）和其延伸出來的 EBNF（Extended BNF）是用來簡潔清晰描述生成規則的一個方法。本書會使用 EBNF 來說明 C 的文法。本結會先說明 BNF，然後說明 EBNF 所延伸的部份。

BNF 以`A = α₁α₂⋯`的形式來描述生成規則。這代表以把`A`展開成為`α₁α₂⋯`的意思。為0個以上的符號列，可以包含無法再展開的符號、和可以再展開（位於某條生成規則等號左邊）的符號。

無法再展開的符號就稱為「終端符號」（terminal symbol），可以再展開（位於某條生成規則等號左邊）的符號稱為「非終端符號」（nonterminal symbol）。像這樣以生成規則來定義的文法一般稱為「上下文無關文法」（context free grammar）。

非終端符號可以對應到複數條的生成規則。舉例來說有`A = α₁`和`A = α₂`兩條規則時，A可以展開成`α₁`或`α₂`都是正確的。

生成規則的右邊可以為空，這類的規則會把左邊的符號展開成長度為0的符號列。但是，省略右邊的話在字面上會顯的不好讀懂，所以一般 BNF 的規定這類情況會在右邊寫上代表什麼都沒有的符號`ε`（epsilon）。本書也使用這個規定記法。

字串以雙引號寫成像`"foo"`這樣。字串為終端符號。

以上就是基本的 BNF 規則。而 EBNF 則是在 BNF 的規則之上，使用以下符號來更簡潔地描述複雜的規則：

| 寫法        | 意思        |
| --------- | --------- |
| `A*`      | 重複0次以上`A` |
| `A?`      | `A`或`ε`   |
| `A \| B`  | `A`或`B`   |
| `( ... )` | 分組        |

舉例來說，`A = ("fizz" | "buzz")*`中，`A`為`"fizz"`或`"buzz"`重複0次以上的字串。也就是可以展開為：

* `""`
* `"fizz"`
* `"buzz"`
* `"fizzfizz"`
* `"fizzbuzz"`
* `"buzzfizz"`
* `"buzzbuzz"`
* `"fizzfizzfizz"`
* `"fizzfizzbuzz"`
* ⋯⋯

的其中一個。

{% hint style="info" %}

#### 小知識：BNF 和 EBNF

非 Extended 的普通 BNF，並沒有 `*`、`?`、`|`、`( ... )`這些簡潔的寫法，但 BNF 可以生成的句子和 EBNF 是一樣的。原因是如果用下列方法改寫的話，可以把 EBNF 轉換成 BNF。
{% endhint %}

| EBNF              | 對應的BNF                    |
| ----------------- | ------------------------- |
| `A = α*`          | `A = αA` 和 `A = ε`        |
| `A = α?`          | `A = α` 和 `A = ε`         |
| `A = α \| β`      | `A = α` 和 `A = β`         |
| `A = α (β₁β₂⋯) γ` | `A = α B γ` 和 `B = β₁β₂⋯` |

{% hint style="info" %}
舉例來說使用`A = αA`和`A = ε`的生成規則從`A`生成句子`ααα`時，展開的順序為`A → αA → ααA → αααA → ααα`。

像這樣，`*`和`?`這類寫法其實只是捷徑而已，但是越簡潔的寫法越好懂，一般來說，能寫得簡潔就不會用較長的寫法。
{% endhint %}


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## 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://koshizuow.gitbook.io/compilerbook/calculator_level_language/recursive_descendent_parsing/bnf.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.