以 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"

• ⋯⋯

的其中一個。

小知識：BNF 和 EBNF

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

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

舉例來說使用A = αA和A = ε的生成規則從A生成句子ααα時，展開的順序為A → αA → ααA → αααA → ααα。

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