前言

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

使用巴科斯範式(BNF/EBNF)定義語言

語法定義了一種語言(A grammar defines a language)。

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

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

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

上下文無關語法語法的構成元件

一組規則(rules)是語法的核心組成部分。
規則都有兩個部分：

1. 名稱
2. 名稱的擴充。

定義英文名詞語法的規則：

名詞片語(noun-phrase) 可能擴充為 文章名詞(article noun).

• dog是名詞片語。

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

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

若以數學符號

$\to$來表示「可以擴充為」:

noun-phrase

$\to$ article noun
expression

$\to$ expression + expression

以下是經典的精確表達式語法, 由第2,3,4,6,7規則可以得出

$3\ast 7$是有效的表達式：

• $\mathit{expr}$ : 表達式
• $\mathit{term}$ : 項
• $\mathit{factor}$ : 因子
• $\mathit{const}$ : 常數
• $\mathit{integer}$ : 整數
  
  $$\begin{gathered} \mathit{expr}\to \mathit{term}\mathtt{+}\mathit{expr}(1) \\ \mathit{expr}\to \mathit{term}(2) \\ \mathit{term}\to \mathit{term}\mathtt{\ast }\mathit{factor}(3) \\ \mathit{term}\to \mathit{factor}(4) \\ \mathit{factor}\to \mathtt{(}\mathit{expr}\mathtt{)}(5) \\ \mathit{factor}\to \mathit{const}(6) \\ \mathit{const}\to \mathit{integer}(7) \end{gathered}$$

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中的規則定義語法：

$$\begin{gathered} \mathit{rule}\to \mathit{name}::=\mathit{expansion} \\ \mathit{name}\to \mathit{<}\mathit{identifier}\mathit{>} \\ \mathit{expansion}\to \mathit{expansion}\mathit{expansion} \\ \mathit{expansion}\to \mathit{expansion}|\mathit{expansion} \\ \mathit{expansion}\to \mathit{name} \\ \mathit{expansion}\to \mathit{terminal} \end{gathered}$$

• 我們可能使用正則表達式[-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