---
title: "使用巴科斯範式(BNF/EBNF/ABNF)定義語言"
description: "瞭解如何使用巴科斯範式及其擴展來定義語言"
# image: https://hackmd.io/screenshot.png
tags: BNF,EBNF,ABNF
# robots: noindex, nofollow
langs: zh-Hant
---

# 前言
本筆記參考[The language of languages]的文章，來瞭解如何使用巴科斯範式及其擴展來定義語言。

# 使用巴科斯範式(BNF/EBNF)定義語言
語法定義了一種語言(A grammar defines a language)。

每種語言的背後都有一種語法，它決定了語言的結構。

上下文無關語法(context-free grammar)是在計算機科學中最常見的語法類型。

上下文無關語法能描述語言的遞歸語法結構。

## 上下文無關語法語法的構成元件
一組規則(rules)是語法的核心組成部分。
規則都有兩個部分：
1. 名稱
2. 名稱的擴充。

定義英文名詞語法的規則：
> **名詞片語(noun-phrase)** 可能擴充為 **文章名詞(article noun)**.
- *dog*是名詞片語。

描述一種編程語言的規則：

> **表達式(expression)** 可能擴充為 **表達式** + **表達式**

若以數學符號$\rightarrow$來表示「可以擴充為」:

> noun-phrase $\rightarrow$ article noun
expression $\rightarrow$ expression + expression

以下是經典的精確表達式語法, 由第2,3,4,6,7規則可以得出$3*7$是有效的表達式：
- $\mathit{expr}$ : 表達式
- $\mathit{term}$ : 項
- $\mathit{factor}$ : 因子
- $\mathit{const}$ : 常數
- $\mathit{integer}$ : 整數
$$
\mathit{expr} \rightarrow \mathit{term}\; \mathtt{+}\; \mathit{expr} ~~ (1)
\\
\mathit{expr} \rightarrow \mathit{term} ~~ (2)
\\
\mathit{term} \rightarrow \mathit{term}\; \mathtt{*}\; \mathit{factor} ~~ (3)
\\
\mathit{term} \rightarrow \mathit{factor} ~~ (4)
\\
\mathit{factor} \rightarrow \mathtt{(}\;\mathit{expr}\;\mathtt{)} ~~ (5)
\\
\mathit{factor} \rightarrow \mathit{const} ~~ (6)
\\
\mathit{const} \rightarrow \mathit{integer} ~~ (7)
$$

## Backus-Naur Form (BNF) notation
在描述語言時，巴科斯範式(Backus-Naur Form)是正式表示法，應用於供人類消耗的編碼語法。

每個規則都具有以下結構：
$$
\mathit{name} ::= \mathit{expansion}
$$
- 符號 $::=$ 表示「可以擴充為」或「可以替換為」
- $\mathit{name}$ 也稱為**非終端符(non-terminal symbol)**。
- BNF的每個 $\mathit{name}$ 都用**尖括號**`<>`包圍，無論它出現在規則的左側還是右側。
- $\mathit{expansion}$ 是一個包含**終端符**和**非終端符**的表達式，通過排序和選擇將它們連接在一起。
- **終端符(terminal symbol)** 是像`"+"`或`"function"`或`integer`的文字
- 並置(juxtaposition)的表達式代表**檢測順序**
- $\mathit{expansion} ::= \mathit{expansion}~ \mathit{expansion}$
- 豎條`|`代表**選擇(choice)**:
- ` <expr> ::= <term> "+" <expr> | <term>`

將經典的精確表達式語法以BNF表示：

 <expr> ::= <term> "+" <expr>
         |  <term>

 <term> ::= <factor> "*" <term>
         |  <factor>

 <factor> ::= "(" <expr> ")"
           |  <const>

 <const> ::= integer

自然地，我們可以為BNF中的規則定義語法：
$$
\mathit{rule} \rightarrow \mathit{name} ::= \mathit{expansion}
\\
\mathit{name} \rightarrow \mathit{<identifier>}
\\
\mathit{expansion} \rightarrow \mathit{expansion} ~ \mathit{expansion}
\\
\mathit{expansion} \rightarrow \mathit{expansion} ~|~\mathit{expansion}
\\
\mathit{expansion} \rightarrow \mathit{name}
\\
\mathit{expansion} \rightarrow \mathit{terminal}
$$

- 我們可能使用正則表達式`[-A-Za-z_0-9] +`來定義標識符(identifier)。
- 終端可以是帶引號的文字(例如`"+"`，`"switch"`或`"<<="`)，也可以是類別名稱的文字(例如`integer`)。

## Extended BNF (EBNF) notation
擴展巴科斯範式（Extended BNF）是巴科斯範式的擴展集合。它允許在擴充中的附加操作。

### 可選擇性的項目
在EBNF中，若方括號包圍著擴充`[expansion]`，表示此擴充是可選擇性的項目。

例如負數的規則如下：

<term> ::= [ "-" ] <factor>

### 重複
在EBNF中，花括號`{}`表示該表達式可以重複零次或更多次。

例如常規逗號分隔參數列表的規則：

<args> ::= <arg> { "," <arg> }

### 分組
為了表示優先順序，EBNF語法可以使用括號`()`明確定義擴充順序。

例如定義允許加法和減法的表達式規則：

<expr> ::= <term> ("+" | "-") <expr>

### 串聯
在某些形式的EBNF中，運算符明確表示串聯(concatenation)，而不是依靠並置(juxtaposition)。

## Augmented BNF (ABNF) notation
協議規範通常使用增強巴科斯範式(Augmented BNF)。[RFC 5234]定義了ABNF。

從原則上講，ABNF與EBNF相似，不同之處在於ABNF的選擇(choice)，可選擇項(option)和重複(repetition)表示法不同。

ABNF還提供了精確指定特定byte值的能力；詳細訊息在協議中至關重要。

在ABNF中：
- 選擇的符號為`/`
- 可選擇項為`[]`
- 重複為前綴`*`
- 重複n次或多次是前綴`n*`
- 重複n到m次是前綴`n*m`
- EBNF的`{expansion}`在ABNF中變為`*(expansion)`

範例可參考取自[RFC 5322 section-1.2]的日期和時間格式的定義。

# BNF的正則擴展
在語法中通常會找到[類似正則表達式]的操作。

在這些語法中：
- 後綴`*`表示"重複0次或多次"
- 後綴`+`表示"已重複1次或多次”
- 後綴`？`表示"0或1次"

Python中浮點文字的定義是一個很好的例子：

floatnumber   ::=  pointfloat | exponentfloat
pointfloat    ::=  [intpart] fraction | intpart "."
exponentfloat ::=  (intpart | pointfloat) exponent
intpart       ::=  digit+
fraction      ::=  "." digit+
exponent      ::=  ("e" | "E") ["+" | "-"] digit+

## 數學文法
參閱[translating math into code]

## 在上下文無關語法以外
正則表達式(Regular expression)在描述能力上位於上下文無關語法的下方：您可以將任何正則表達式重寫為表示該表達式匹配的形式的語法。但是，事實並非如此：並非所有語法都可以轉換為等效的正則表達式。

為了超越上下文無關文法的表達能力，需要在語法中允許一定程度的上下文敏感性。

上下文敏感性(context-sensitivity)意味著終端符也可能出現在規則的左側。

範例:

 <top> ::= <a> ")"
 <a>   ::= "(" <exp>

 "(" <exp> ")" ::= 7

- `<top>`可以擴展為`<a> ")"`
- 其可以擴展為`"(" <exp> ")"`
- 其可以擴展為`7`

就其可描述的語言而言，它使語法等效於圖靈機。

通過限制規則，使左側的符號嚴格少於右側的所有擴展，上下文相關語法等同於(可確定的)[線性有界自動機(Linear bounded automaton)]。

即使某些語言是上下文相關的，上下文相關的語法也很少用於描述計算機語言。

例如，由於C處理標識符和類型的方式，C有點上下文敏感性，但是這種上下文敏感性是通過特殊約定解決的，而不是通過在語法中引入上下文敏感性來解決的。

# 解析
本文介紹了解釋語法和常用符號的過程。一個密切相關的主題是解析(Parsing)。

解析採用語法和字符串，並回答兩個問題：
1. 該字符串是語法語言嗎？
2. 該字符串相對於語法的結構是什麼？

參閱[Parsing Techniques: A Practical Guide]

[The language of languages]: http://matt.might.net/articles/grammars-bnf-ebnf/
[RFC 5234]: http://tools.ietf.org/html/rfc5234
[RFC 5322 section-1.2]: http://tools.ietf.org/html/rfc5322#section-1.
[類似正則表達式]: http://matt.might.net/articles/sculpting-text/
[translating math into code]: http://matt.might.net/articles/discrete-math-and-code/
[線性有界自動機(Linear bounded automaton)]: https://zh.wikipedia.org/zh-tw/%E7%BA%BF%E6%80%A7%E6%9C%89%E7%95%8C%E8%87%AA%E5%8A%A8%E6%9C%BA
[Parsing Techniques: A Practical Guide]: https://www.tenlong.com.tw/products/9781441919014