BNF

By: Lars Marius Garshol

原文參見：http://www.garshol.priv.no/download/text/bnf.html

（本文是上述作者文章的翻譯，原文版權歸作者所有）

(譯者：Sunnybill)

BNF 和EBNF的含義與用法 1

簡介

關于本文

什麼是BNF?

工作原理

基本原理

一個執行個體

EBNF及其用途

一個EBNF文法執行個體

BNF和EBNF的使用

一般用法

如何使用形式文法

解析

最簡單的方法

自上而下的解析(LL)

一個LL分析執行個體

一個LL轉換執行個體

稍難的方法

自底而上的解析(LR)

LL還是LR？

更多資訊

附錄

緻謝

簡介

關于本文

這是一篇針對<[email protected] > 16.Jun.98年6月16日釋出在comp.text.sgml 的資訊而寫的一篇解釋BNF的短文，有些粗略，不詳之處可與作者聯系，作者将會盡量解釋。

現在文章越來越長，但你不必擔心，文章将會逐漸深入。如果你不想深入了解，你可以隻看感興趣的部分，從中尋找你的問題答案即可。

什麼是BNF?

Backus-Naur符号（就是衆所周知的BNF或Backus-Naur Form）是描述語言的形式化的數學方法，由John Backus (也許是Peter Naur)開發，用于描述Algol 60程式設計語言的文法。

最初的時候是許多标記（圖例），是John Backus 在數學家Emil Post早期工作的基礎上開發的，Peter Naur 在Algol 60中采用了它，并進行了稍許改進,進而使其出名，是以Naur把BNF叫做Backus Normal Form，而其他人則把它叫成Backus-Naur Form。

BNF被用來形式化定義語言的文法，以使其規則沒有歧義。事實上，BNF非常精确，圍繞這些文法有很多數學理論，使得人們竟然可以機械地為基于BNF文法的語言構造解析器。（有些文法不能實作，但通常可以手工地通過轉換成其他形式來實作）。

實作這個功能的程式叫做編譯器，最有名的是YACC,當然，還有很多很多。

工作原理

基本原理

BNF類似一種數學遊戲：從一個符号開始（叫做起始标志，執行個體中常用S表示），然後給出替換前面符号的規則。BNF文法定義的語言隻不過是一個字元串集合，你可以按照下述規則書寫，這些規則叫做書寫規範（生産式規則），形式如下：

symbol := alternative1 | alternative2 ...

每條規則申明:=左側的符号必須被右側的某一個可選項代替。替換項用“|”分割（有時用“::=”替換“:=”，但意思是一樣的）。替換項通常有兩個符号和終結符構成。之是以叫做終結符是因為沒有針對他們的書寫規範，他們是書寫過程的終止（符号通常被叫做非終止符，也有人叫非終端）。

BNF文法的另一個變化是把終止符（終端）放在引号中，把他們與符号差別開來。有些BNF文法用符号明确地标明允許使用空格的地方，而有的文法則把它留給讀者推測。

BNF中有一個特殊符号“@”，表示符号可以去掉。如果用@替換符号，隻需要将符号去掉。這非常有用，因為如果不利用這個技巧，有時很難終止替換過程。

是以，一個文法描述的語言就是用書寫規則（生産式規則）寫的字元串的集合。如果一個字元串無法用這些規則寫出，那麼，該字元串在這個語言中就被禁用。

一個執行個體

下面是BNF文法的一個執行個體：

S := '-' FN | FN

FN := DL | DL '.' DL

DL := D | D DL

D := '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

這裡的各種符号都是縮寫的：S是開始符，FN産生一個分數，DL是一串數字清單，D是各個數字。

該文法描述的語言的有效句子都是數字，可能是分數，也可能是負數。要寫一個數字，首先以S符号開頭：

S

然後，用S的結果替換它。上例中，我們可以選擇在數字前面不加“-”号而僅僅使用FN，并用FN替換S：

FN

接着用FN的結果替換FN。我們想寫一個分數，是以選擇産生兩個中間帶“.”的十進制數的清單，然後，我們接着在每一行用一個符号的結果替換一個符号，像下面的例子：

DL . DL

D . DL

3 . DL

3 . D DL

3 . D D

3 . 1 D

3 . 1 4

這裡我們寫了一個分數3.14。如何寫-5，讀者可自己練習。要徹底搞明白，還需要研究文法，知道您弄明白為什麼按照上述規則不能寫出3..14。

EBNF及其用途

在DL中，我們已經用到了遞歸（如DL能産生新的DL）來表達許多數字D的情況。這有點不太靈活，使BNF難以閱讀。擴充BNF（EBNF）通過引入下列操作符解決了這個問題：

l ?：意思是操作符左邊的符号（或括号中的一組符号）是可選項（可以出現0到多次）。

l *：是指可以重複多次。

l +：是指可以出現多次。

一個EBNF文法執行個體

上面的例子用EBNF可以寫成：

S := '-'? D+ ('.' D+)?

D := '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

提示：EBNF在定義語言方面并不比BNF更強大，隻是更友善。凡是用EBNF寫的東西都可以轉換成BNF的形式。

BNF和EBNF的使用

一般用法

多數程式設計語言标準都使用一些EBNF變量來定義語言的文法。這有兩個好處：一是在語言的文法上沒有争議，而是易于編譯器的編寫，因為編譯器的解析器可以用類似YACC這樣的“編譯器編譯器”自動産生。

EBNF也用于許多其他标準，如定義協定格式，資料格式和XML,SGML這樣的标記語言。（HTML沒有按照文法定義，而是用SGML DTD這樣的進階文法定義的。）

在BNF web club（http://cuiwww.unige.ch/db-research/Enseignement/analyseinfo/BNFweb.html ）上可以查到BNF的一個文法集。

如何使用形式文法

現在，我們已經了解什麼是BNF和EBNF以及它們的用途了，但還不知道為什麼它們很有用以及如何利用它們。

形式文法最明顯的用法已經提到過了：一旦為語言制定了形式文法，就完全定義了這個語言。對于那些東西可以用于語言，那些東西不可以就不會有歧義了。這非常有用因為用普通語言描述的文法不僅冗長，而且會産生對不同的解釋。

另一個好處是：形式文法是數學産物，可以被計算機了解。實際上有許多程式可以用(E)BNF文法輸入，并自動為給定文法的解析器提供處理代碼。實際上，這是設計編譯器的常見做法：用帶有文法輸入的所謂“編譯器編譯器”産生程式設計語言的解析器代碼。

當然，編譯器除了做文法檢查之外還做許多其他檢查，他們也産生代碼。這些都沒有在(E)BNF中描述，是以編譯器編譯器通常有針對一種文法中不同代碼的代碼塊連接配接（也叫做操作）的特殊文法。

最有名的編譯器編譯器是YACC(Yet Another Complier Complier)，産生C代碼，其他的編譯器還有針對C++，JAVA，Python等等其他語言的。

解析

最簡單的方法

自上而下的解析(LL)

按照現有文法解析代碼的最簡單方法是叫做LL解析（自上而下解析）。它是這樣工作的：對每一段代碼找出代碼開始的非終端标記（叫做初始集）。

然後，在解析時隻需要從起始符開始比較不同代碼段（符号）初始集和第一個輸入的符号，判斷代碼段用的是哪個起始符作為開始的（用到了那些符号）。隻有不存在一個符号的兩個初始集含有相同的終止符時才可以這樣。否則，就不能通過輸入的第一個終止符選擇哪個開始符（符号）了。

LL文法通常按數字分類，比如LL(1), LL(0)等等。括号中的數字是在文法中的任何一點選擇适當符号時需要同時考慮的最大終端數。是以 LL(0)根本不需要檢查終端（終止符），總能夠選擇适當的終止符。這種情況隻發生在所有符号隻有一個替換符的情形，而如果隻有一個替換符意味着語言隻有一個字元串。也就是說LL(0)沒有意義。

最常有也是做有用的LL文法是聯絡LL(1)，通過檢查輸入的第一個終止符總能夠選擇适當的替換符。而LL(2)需要檢查兩個符号，以此類推。

一個LL分析執行個體

為了說明，我們就執行個體文法做一個初始集分析。對符号D這非常容易：所有的替換符号跟它們的初始集（它們産生的）一樣是一個數字，D符号把由10個數字組成的集合作為初始集。這意味着至少有一個LL(1)文法，因為這時我們需要一個終端來選擇适當的替換符。

對DL就會有些麻煩。兩個替換符都以D開頭，是以都有相同的初始機。這意味着不能夠通過檢查輸入的第一個終止符來選擇适當的替換符。但我們可以通過欺騙輕松地克服這個困難：如果輸入的第二個終止符不是數字，我們就用第一個替換符，如果兩個都是數字，就用第二個替換符。也就是說，這至少是LL(2)文法。

這裡其實把事情簡化了。DL的替換符并沒有告訴我們D @的替換符中的第一個終止符後哪個終止符是被允許的，因為我們需要知道在DL後面哪個終止符被允許。這個終止符集叫做符号的後續集（follow set of the symbol），這裡是“.”，是輸入的結尾。

FN符号更糟糕，因為兩個替換符都是以數字作為其初始集。檢查第二個也終止符沒有用，因為在數字清單（DL）中的最後一個數字的後面需要檢視第一個終止符，而我們需要讀取所有的數字後才能知道有多少數字。由于有多少數字并無限制，這就不是一個對于任意k的LL(k)文法。

或許有些奇怪，S符号很簡單。第一個替換項“-”是它的初始集，第二個全部是數字。也就是說，解析時從S符号開始檢視輸入項來決定使用哪個替換項。如果第一個終端是“-”，就用第一個替換項“-”；否則就用第二個。隻有FN和DL替換想會引起麻煩。

一個LL轉換執行個體

其實也沒有必要失望。多數非LL(k)文法可以容易地轉換成了LL(1)文法。這樣我們需要轉換兩個符号：FN和DL。

FN的問題是兩個替換項都以DL開頭，但第二個後接一個“.”和另外一個初始DL後面的DL。這很好解決：我們把FN變成隻有以一個DL開頭的替換項後跟一個FP(分數部分)，FP可以是空或是”.”後跟一個DL。變成下面這樣：

FN := DL FP

FP := @ | '.' DL

現在FN沒有問題了，因為隻有一個替換項，FP也沒有問題，因為兩個替換項有不同的初設集。分别是輸入的結尾和“.”。

DL是塊硬骨頭，因為主要問題出在遞歸，而且是複合的，需要從DL中得到一個D。解決方案是給DL一個單獨的替換項，一個D後接一個DR（其餘的數字）。這時DR就有兩個替換項：D和DR或@。第一個替換項以所有的數字為初始集，第二個含有“.”和輸入的結尾作為其初始集，進而解決問題。

這樣就徹底轉換成LL(1)文法了：

S := '-' FN | FN

FN := DL FP

FP := @ | '.' DL

DL := D DR

DR := D DR | @

D := '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

稍難的方法

自底而上的解析(LR)

一個稍難的方法是移動替換法或叫自底而上解析。這個技術采集所有輸入直道發現能夠還原成符号的輸入。這聽起來好像很困難，是以需要給個例子加以說明。我們解析“3.14”看看如何從該文法中産生。我們從讀取輸入“3”開始：

3

然後，我們檢視能否還原成産生它的符号。實際上我們能，它是從符号D産生的，我們用D替換3。這時我們注意到D可以從DL産生，是以用DL替換D。（這個文法有不确定性，我們可以一直還原到FN，但是是錯誤的。簡單起見我們這裡跳過錯誤的步驟，但清晰的文法将不會允許這樣的錯誤發生），之後我們從輸入中讀取“.”并試圖還原它，但是失敗了。

D

DL

DL .

他不能還原成其它的東西，是以我們繼續讀取其它輸入“1”，并把它還原成D，在讀取下一個輸入“4”, “4”也可以還原成D，再還原成DL，然後，“D DL”序列可以進一步還原成DL。

DL .

DL . 1

DL . D

DL . D 4

DL . D D

DL . D DL

DL . DL

看一下文法就會發現FN恰好能夠還原“DL.DL”序列，于是将其還原。FN是從S産生的，是以FN可以還原成S，到此為止就完成了解析。

DL . DL

FN

S

也許你注意到我們可以先在做還原，也可以等到有多個符号在做不同的還原。這種移位還原解析算法有許多複雜變化，按照複雜程度和功能分為LR(0)、 SLR、LALR和LR(1)。LR(1)需要太大的解析表，是以LALR是最常用的算法，而SR(0)和SLR對多數編成語言都不夠強大。

LALR 和LR(1)實在太複雜了，這裡沒法讨論，但你已經了解了其基本思想。

LL還是LR？

這個問題已經被人回答了，這裡引用他的新消息：

希望不要引發争議，首先，當Frank看到這個時不要打我（我老闆就是Frank DeRmer，LALR解析的創始人…）。

（借用一下Fischer&LeBlanc's "Crafting a Compiler"的摘要）

簡單性Simplicity - - LL

通用性Generality - - LALR

操作Actions - - LL

錯誤恢複Error repair - - LL

表大小Table sizes - - LL

解析速度Parsing speed - - comparable (me: and tool-dependent)

簡單性- - LL 占優

==========

LL解析器更簡單，如果要調試一個解析器，考慮遞歸下降解析器（編寫LL解析器的常用方法）要比LALR解析器的表簡單多了。

通用性 - - LALR 占優

==========

在規範定義的簡易性，LALR輕松取勝。LL和LALR的最大不同是LL文法必須用左因子法則和消除左遞歸。

提取左因子是必須的，因為LL解析器需要基于固定的輸入數選擇替換。

左回歸是有問題的，因為規則前導标記總是統一規則的前導标記。這将導緻無窮遞歸。

參考以下連接配接了解LALR轉換成LL文法的方法：

http://www.jguru.com/thetick/articles/lalrtoll.html

許多語言已經有了LALR文法，但還需要翻譯。如果語言沒有這樣的文法，寫一個LL文法也不是什麼難事。

操作性 - - LL 占優

=======

在LL解析器中可以把操作放在任何地方而不會引起沖突。

錯誤修複 - - LL 占優

============

LL解析器具有豐富的環境資訊（上下文資訊），對修複錯誤很有幫助而非報告所無。

表大小 - - LL

===========

假設你編寫一個表驅動LL解析器，它的表隻有其他的一半大小。（平心而論，有很多方法優化LALR表，使其變小）

解析速度 – 比較(我的觀點：視工具而定)

--Scott Stanchfield in article <[email protected] > on comp.lang.java.softwaretools Mon, 07 Jul 1997.

更多資訊

John Aycock用Python開發了一個非常好而且簡單易用的解析架構叫做SPARK ,用可讀性非常強的論文描述。

編譯器和解析器方面權威工作是'The Dragon Book'，也叫Compilers : Principles, Techniques, and Tools，作者Aho, Sethi and Ullman。請注意這是一本進階的數學書。

線上的免費資料較好的是這本：http://www.cs.vu.nl/~dick/PTAPG.html 。

Frank Boumphrey的another EBNF tutorial，（http://www.hypermedic.com/style/xml/ebnf.htm ）

Henry Baker的an article about parsing in Common Lisp（http://home.pipeline.com/~hbaker1/Prag-Parse.html ）呈現的是一個簡單、高效而且十分友善的解析架構。方法類似于編譯器編譯器，但它依賴于一個十分強大的Common Lisp宏系統。

定義BNF文法的句法規則在RFC 2234（http://www.ietf.org/rfc/rfc2234.txt ）中可以找到，the ISO 14977 standard中也有。

附錄

緻謝

Thanks to:

• Jelks Cabaniss, for encouraging me to turn the news article into a web article, and for providing very useful criticism of the article once it appeared in web form.

• C. M. Sperberg-McQueen for extra historical information about the name of BNF.

• Scott Stanchfield for writing the great comparison of LALR and LL. I have asked for permission to quote this, but have received no reply, unfortunately.

• James Huddleston for correcting me on John Backus' name.