愛華網(wǎng)Happy coding
開元編譯器 UCC 研究 － 符號(hào)表 編譯原理知識(shí)加電－[轉(zhuǎn)]BNF 和EBNF的含義與用法(感謝譯者：Sunnybill)
皮貝貝 posted @ 2009年9月16日 10:08 in 編譯器 with tags 編譯原理 BNF EBNP LL LR , 6 閱讀
開源編輯器 UCC研究－語法分析器、詞法分析器
By: Lars Marius Garshol
原文參見：http://www.garshol.priv.no/download/text/bnf.html
（本文是上述作者文章的翻譯，原文版權(quán)歸作者所有）
(譯者：Sunnybill)
BNF 和EBNF的含義與用法 1
簡(jiǎn)介
關(guān)于本文
什么是BNF?
工作原理
基本原理
一個(gè)實(shí)例
EBNF及其用途
一個(gè)EBNF語法實(shí)例
BNF和EBNF的使用
一般用法
如何使用形式語法
解析
最簡(jiǎn)單的方法
自上而下的解析(LL)
一個(gè)LL分析實(shí)例
一個(gè)LL轉(zhuǎn)換實(shí)例
稍難的方法
自底而上的解析(LR)
LL還是LR？
更多信息
附錄
致謝
簡(jiǎn)介
關(guān)于本文
這是一篇針對(duì)<wkwwagbizn.fsf@ifi.uio.no > 16.Jun.98年6月16日發(fā)布在comp.text.sgml 的信息而寫的一篇解釋BNF的短文，有些粗略，不詳之處可與作者聯(lián)系，作者將會(huì)盡量解釋。
現(xiàn)在文章越來越長(zhǎng)，但你不必?fù)?dān)心，文章將會(huì)逐漸深入。如果你不想深入了解，你可以只看感興趣的部分，從中尋找你的問題答案即可。
什么是BNF?
Backus-Naur符號(hào)（就是眾所周知的BNF或Backus-Naur Form）是描述語言的形式化的數(shù)學(xué)方法，由John Backus (也許是Peter Naur)開發(fā)，用于描述Algol 60編程語言的語法。
最初的時(shí)候是許多標(biāo)記（圖例），是John Backus 在數(shù)學(xué)家Emil Post早期工作的基礎(chǔ)上開發(fā)的，Peter Naur 在Algol 60中采用了它，并進(jìn)行了稍許改進(jìn),從而使其出名，因此Naur把BNF叫做Backus Normal Form，而其他人則把它叫成Backus-Naur Form。
BNF被用來形式化定義語言的語法，以使其規(guī)則沒有歧義。事實(shí)上，BNF非常精確，圍繞這些語法有很多數(shù)學(xué)理論，使得人們竟然可以機(jī)械地為基于BNF語法 的語言構(gòu)造解析器。（有些語法不能實(shí)現(xiàn)，但通?？梢允止さ赝ㄟ^轉(zhuǎn)換成其他形式來實(shí)現(xiàn)）。
實(shí)現(xiàn)這個(gè)功能的程序叫做編譯器，最有名的是YACC,當(dāng)然，還有很多很多。
工作原理
基本原理
BNF類似一種數(shù)學(xué)游戲：從一個(gè)符號(hào)開始（叫做起始標(biāo)志，實(shí)例中常用S表示），然后給出替換前面符號(hào)的規(guī)則。BNF語法定義的語言只不過是一個(gè)字符串集 合，你可以按照下述規(guī)則書寫，這些規(guī)則叫做書寫規(guī)范（生產(chǎn)式規(guī)則），形式如下：
symbol := alternative1 | alternative2 ...
每條規(guī)則申明:=左側(cè)的符號(hào)必須被右側(cè)的某一個(gè)可選項(xiàng)代替。替換項(xiàng)用“|”分割（有時(shí)用“::=”替換“:=”，但意思是一樣的）。替換項(xiàng)通常有兩個(gè)符號(hào) 和終結(jié)符構(gòu)成。之所以叫做終結(jié)符是因?yàn)闆]有針對(duì)他們的書寫規(guī)范，他們是書寫過程的終止（符號(hào)通常被叫做非終止符，也有人叫非終端）。
BNF語法的另一個(gè)變化是把終止符（終端）放在引號(hào)中，把他們與符號(hào)區(qū)別開來。有些BNF語法用符號(hào)明確地標(biāo)明允許使用空格的地方，而有的語法則把它留給讀者推測(cè)。
BNF中有一個(gè)特殊符號(hào)“@”，表示符號(hào)可以去掉。如果用@替換符號(hào)，只需要將符號(hào)去掉。這非常有用，因?yàn)槿绻焕眠@個(gè)技巧，有時(shí)很難終止替換過程。
因此，一個(gè)語法描述的語言就是用書寫規(guī)則（生產(chǎn)式規(guī)則）寫的字符串的集合。如果一個(gè)字符串無法用這些規(guī)則寫出，那么，該字符串在這個(gè)語言中就被禁用。
一個(gè)實(shí)例
下面是BNF語法的一個(gè)實(shí)例：
S := '-' FN | FN
FN := DL | DL '.' DL
DL := D | D DL
D := '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
這里的各種符號(hào)都是縮寫的：S是開始符，F(xiàn)N產(chǎn)生一個(gè)分?jǐn)?shù)，DL是一串?dāng)?shù)字列表，D是各個(gè)數(shù)字。
該語法描述的語言的有效句子都是數(shù)字，可能是分?jǐn)?shù)，也可能是負(fù)數(shù)。要寫一個(gè)數(shù)字，首先以S符號(hào)開頭：
S
然后，用S的結(jié)果替換它。上例中，我們可以選擇在數(shù)字前面不加“-”號(hào)而僅僅使用FN，并用FN替換S：
FN
接著用FN的結(jié)果替換FN。我們想寫一個(gè)分?jǐn)?shù)，所以選擇產(chǎn)生兩個(gè)中間帶“.”的十進(jìn)制數(shù)的列表，然后，我們接著在每一行用一個(gè)符號(hào)的結(jié)果替換一個(gè)符號(hào)，像下面的例子：
DL . DL
D . DL
3 . DL
3 . D DL
3 . D D
3 . 1 D
3 . 1 4
這里我們寫了一個(gè)分?jǐn)?shù)3.14。如何寫-5，讀者可自己練習(xí)。要徹底搞明白，還需要研究語法，知道您弄明白為什么按照上述規(guī)則不能寫出3..14。
EBNF及其用途
在DL中，我們已經(jīng)用到了遞歸（如DL能產(chǎn)生新的DL）來表達(dá)許多數(shù)字D的情況。這有點(diǎn)不太靈活，使BNF難以閱讀。擴(kuò)展BNF（EBNF）通過引入下列操作符解決了這個(gè)問題：
l ?：意思是操作符左邊的符號(hào)（或括號(hào)中的一組符號(hào)）是可選項(xiàng)（可以出現(xiàn)0到多次）。
l *：是指可以重復(fù)多次。
l +：是指可以出現(xiàn)多次。
一個(gè)EBNF語法實(shí)例
上面的例子用EBNF可以寫成：
S := '-'? D+ ('.' D+)?
D := '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
提示：EBNF在定義語言方面并不比BNF更強(qiáng)大，只是更方便。凡是用EBNF寫的東西都可以轉(zhuǎn)換成BNF的形式。
BNF和EBNF的使用
一般用法
多數(shù)編程語言標(biāo)準(zhǔn)都使用一些EBNF變量來定義語言的語法。這有兩個(gè)好處：一是在語言的語法上沒有爭(zhēng)議，而是易于編譯器的編寫，因?yàn)榫幾g器的解析器可以用類似YACC這樣的“編譯器編譯器”自動(dòng)產(chǎn)生。
EBNF也用于許多其他標(biāo)準(zhǔn)，如定義協(xié)議格式，數(shù)據(jù)格式和XML,SGML這樣的標(biāo)記語言。（HTML沒有按照語法定義，而是用SGML DTD這樣的高級(jí)語法定義的。）
在BNF web club（http://cuiwww.unige.ch/db-research/Enseignement/analyseinfo/BNFweb.html ）上可以查到BNF的一個(gè)語法集。
如何使用形式語法
現(xiàn)在，我們已經(jīng)了解什么是BNF和EBNF以及它們的用途了，但還不知道為什么它們很有用以及如何利用它們。
形式語法最明顯的用法已經(jīng)提到過了：一旦為語言制定了形式語法，就完全定義了這個(gè)語言。對(duì)于那些東西可以用于語言，那些東西不可以就不會(huì)有歧義了。這非常 有用因?yàn)橛闷胀ㄕZ言描述的語法不僅冗長(zhǎng)，而且會(huì)產(chǎn)生對(duì)不同的解釋。
另一個(gè)好處是：形式語法是數(shù)學(xué)產(chǎn)物，可以被計(jì)算機(jī)理解。實(shí)際上有許多程序可以用(E)BNF語法輸入，并自動(dòng)為給定語法的解析器提供處理代碼。實(shí)際上，這 是設(shè)計(jì)編譯器的常見做法：用帶有語法輸入的所謂“編譯器編譯器”產(chǎn)生編程語言的解析器代碼。
當(dāng)然，編譯器除了做語法檢查之外還做許多其他檢查，他們也產(chǎn)生代碼。這些都沒有在(E)BNF中描述，因此編譯器編譯器通常有針對(duì)一種語法中不同代碼的代碼塊連接（也叫做操作）的特殊語法。
最有名的編譯器編譯器是YACC(Yet Another Complier Complier)，產(chǎn)生C代碼，其他的編譯器還有針對(duì)C++，JAVA，Python等等其他語言的。
解析
最簡(jiǎn)單的方法
自上而下的解析(LL)
按照現(xiàn)有語法解析代碼的最簡(jiǎn)單方法是叫做LL解析（自上而下解析）。它是這樣工作的：對(duì)每一段代碼找出代碼開始的非終端標(biāo)記（叫做初始集）。
然后，在解析時(shí)只需要從起始符開始比較不同代碼段（符號(hào)）初始集和第一個(gè)輸入的符號(hào)，判斷代碼段用的是哪個(gè)起始符作為開始的（用到了那些符號(hào)）。只有不存 在一個(gè)符號(hào)的兩個(gè)初始集含有相同的終止符時(shí)才可以這樣。否則，就不能通過輸入的第一個(gè)終止符選擇哪個(gè)開始符（符號(hào)）了。
LL語法通常按數(shù)字分類，比如LL(1), LL(0)等等。括號(hào)中的數(shù)字是在語法中的任何一點(diǎn)選擇適當(dāng)符號(hào)時(shí)需要同時(shí)考慮的最大終端數(shù)。因此 LL(0)根本不需要檢查終端（終止符），總能夠選擇適當(dāng)?shù)慕K止符。這種情況只發(fā)生在所有符號(hào)只有一個(gè)替換符的情形，而如果只有一個(gè)替換符意味著語言只有 一個(gè)字符串。也就是說LL(0)沒有意義。
最常有也是做有用的LL語法是聯(lián)絡(luò)LL(1)，通過檢查輸入的第一個(gè)終止符總能夠選擇適當(dāng)?shù)奶鎿Q符。而LL(2)需要檢查兩個(gè)符號(hào)，以此類推。
一個(gè)LL分析實(shí)例
為了說明，我們就實(shí)例語法做一個(gè)初始集分析。對(duì)符號(hào)D這非常容易：所有的替換符號(hào)跟它們的初始集（它們產(chǎn)生的）一樣是一個(gè)數(shù)字，D符號(hào)把由10個(gè)數(shù)字組成 的集合作為初始集。這意味著至少有一個(gè)LL(1)語法，因?yàn)檫@時(shí)我們需要一個(gè)終端來選擇適當(dāng)?shù)奶鎿Q符。
對(duì)DL就會(huì)有些麻煩。兩個(gè)替換符都以D開頭，因此都有相同的初始機(jī)。這意味著不能夠通過檢查輸入的第一個(gè)終止符來選擇適當(dāng)?shù)奶鎿Q符。但我們可以通過欺騙輕 松地克服這個(gè)困難：如果輸入的第二個(gè)終止符不是數(shù)字，我們就用第一個(gè)替換符，如果兩個(gè)都是數(shù)字，就用第二個(gè)替換符。也就是說，這至少是LL(2)語法。
這里其實(shí)把事情簡(jiǎn)化了。DL的替換符并沒有告訴我們D @的替換符中的第一個(gè)終止符后哪個(gè)終止符是被允許的，因?yàn)槲覀冃枰涝贒L后面哪個(gè)終止符被允許。這個(gè)終止符集叫做符號(hào)的后續(xù)集（follow set of the symbol），這里是“.”，是輸入的結(jié)尾。
FN符號(hào)更糟糕，因?yàn)閮蓚€(gè)替換符都是以數(shù)字作為其初始集。檢查第二個(gè)也終止符沒有用，因?yàn)樵跀?shù)字列表（DL）中的最后一個(gè)數(shù)字的后面需要查看第一個(gè)終止 符，而我們需要讀取所有的數(shù)字后才能知道有多少數(shù)字。由于有多少數(shù)字并無限制，這就不是一個(gè)對(duì)于任意k的LL(k)語法。
或許有些奇怪，S符號(hào)很簡(jiǎn)單。第一個(gè)替換項(xiàng)“-”是它的初始集，第二個(gè)全部是數(shù)字。也就是說，解析時(shí)從S符號(hào)開始查看輸入項(xiàng)來決定使用哪個(gè)替換項(xiàng)。如果第 一個(gè)終端是“-”，就用第一個(gè)替換項(xiàng)“-”；否則就用第二個(gè)。只有FN和DL替換想會(huì)引起麻煩。
一個(gè)LL轉(zhuǎn)換實(shí)例
其實(shí)也沒有必要失望。多數(shù)非LL(k)語法可以容易地轉(zhuǎn)換成了LL(1)語法。這樣我們需要轉(zhuǎn)換兩個(gè)符號(hào)：FN和DL。
FN的問題是兩個(gè)替換項(xiàng)都以DL開頭，但第二個(gè)后接一個(gè)“.”和另外一個(gè)初始DL后面的DL。這很好解決：我們把FN變成只有以一個(gè)DL開頭的替換項(xiàng)后跟 一個(gè)FP(分?jǐn)?shù)部分)，F(xiàn)P可以是空或是”.”后跟一個(gè)DL。變成下面這樣：
FN := DL FP
FP := @ | '.' DL
現(xiàn)在FN沒有問題了，因?yàn)橹挥幸粋€(gè)替換項(xiàng)，F(xiàn)P也沒有問題，因?yàn)閮蓚€(gè)替換項(xiàng)有不同的初設(shè)集。分別是輸入的結(jié)尾和“.”。
DL是塊硬骨頭，因?yàn)橹饕獑栴}出在遞歸，而且是復(fù)合的，需要從DL中得到一個(gè)D。解決方案是給DL一個(gè)單獨(dú)的替換項(xiàng)，一個(gè)D后接一個(gè)DR（其余的數(shù)字）。 這時(shí)DR就有兩個(gè)替換項(xiàng)：D和DR或@。第一個(gè)替換項(xiàng)以所有的數(shù)字為初始集，第二個(gè)含有“.”和輸入的結(jié)尾作為其初始集，從而解決問題。
這樣就徹底轉(zhuǎn)換成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)
一個(gè)稍難的方法是移動(dòng)替換法或叫自底而上解析。這個(gè)技術(shù)采集所有輸入直道發(fā)現(xiàn)能夠還原成符號(hào)的輸入。這聽起來好像很困難，所以需要給個(gè)例子加以說明。我們 解析“3.14”看看如何從該語法中產(chǎn)生。我們從讀取輸入“3”開始：
3
然后，我們查看能否還原成產(chǎn)生它的符號(hào)。實(shí)際上我們能，它是從符號(hào)D產(chǎn)生的，我們用D替換3。這時(shí)我們注意到D可以從DL產(chǎn)生，所以用DL替換D。（這個(gè) 語法有不確定性，我們可以一直還原到FN，但是是錯(cuò)誤的。簡(jiǎn)單起見我們這里跳過錯(cuò)誤的步驟，但清晰的語法將不會(huì)允許這樣的錯(cuò)誤發(fā)生），之后我們從輸入中讀 取“.”并試圖還原它，但是失敗了。
D
DL
DL .
他不能還原成其它的東西，所以我們繼續(xù)讀取其它輸入“1”，并把它還原成D，在讀取下一個(gè)輸入“4”, “4”也可以還原成D，再還原成DL，然后，“D DL”序列可以進(jìn)一步還原成DL。
DL .
DL . 1
DL . D
DL . D 4
DL . D D
DL . D DL
DL . DL
看一下語法就會(huì)發(fā)現(xiàn)FN恰好能夠還原“DL.DL”序列，于是將其還原。FN是從S產(chǎn)生的，所以FN可以還原成S，到此為止就完成了解析。
DL . DL
FN
S
也許你注意到我們可以先在做還原，也可以等到有多個(gè)符號(hào)在做不同的還原。這種移位還原解析算法有許多復(fù)雜變化，按照復(fù)雜程度和功能分為L(zhǎng)R(0)、 SLR、LALR和LR(1)。LR(1)需要太大的解析表，所以LALR是最常用的算法，而SR(0)和SLR對(duì)多數(shù)編成語言都不夠強(qiáng)大。
LALR 和LR(1)實(shí)在太復(fù)雜了，這里沒法討論，但你已經(jīng)了解了其基本思想。
LL還是LR？
這個(gè)問題已經(jīng)被人回答了，這里引用他的新消息：
希望不要引發(fā)爭(zhēng)議，首先，當(dāng)Frank看到這個(gè)時(shí)不要打我（我老板就是Frank DeRmer，LALR解析的創(chuàng)始人…）。
（借用一下Fischer&LeBlanc's "Crafting a Compiler"的摘要）
簡(jiǎn)單性Simplicity - - LL
通用性Generality - - LALR
操作Actions - - LL
錯(cuò)誤恢復(fù)Error repair - - LL
表大小Table sizes - - LL
解析速度Parsing speed - - comparable (me: and tool-dependent)
簡(jiǎn)單性- - LL 占優(yōu)
==========
LL解析器更簡(jiǎn)單，如果要調(diào)試一個(gè)解析器，考慮遞歸下降解析器（編寫LL解析器的常用方法）要比LALR解析器的表簡(jiǎn)單多了。
通用性 - - LALR 占優(yōu)
==========
在規(guī)范定義的簡(jiǎn)易性，LALR輕松取勝。LL和LALR的最大不同是LL語法必須用左因子法則和消除左遞歸。
提取左因子是必須的，因?yàn)長(zhǎng)L解析器需要基于固定的輸入數(shù)選擇替換。
左回歸是有問題的，因?yàn)橐?guī)則前導(dǎo)標(biāo)記總是統(tǒng)一規(guī)則的前導(dǎo)標(biāo)記。這將導(dǎo)致無窮遞歸。
參考以下連接了解LALR轉(zhuǎn)換成LL語法的方法：
http://www.jguru.com/thetick/articles/lalrtoll.html
許多語言已經(jīng)有了LALR語法，但還需要翻譯。如果語言沒有這樣的語法，寫一個(gè)LL語法也不是什么難事。
操作性 - - LL 占優(yōu)
=======
在LL解析器中可以把操作放在任何地方而不會(huì)引起沖突。
錯(cuò)誤修復(fù) - - LL 占優(yōu)
============
LL解析器具有豐富的環(huán)境信息（上下文信息），對(duì)修復(fù)錯(cuò)誤很有幫助而非報(bào)告所無。
表大小 - - LL
===========
假設(shè)你編寫一個(gè)表驅(qū)動(dòng)LL解析器，它的表只有其他的一半大小。（平心而論，有很多方法優(yōu)化LALR表，使其變?。?br />
解析速度 – 比較(我的觀點(diǎn)：視工具而定)
--Scott Stanchfield in article <33C1BDB9.FC6D86D3@scruz.net > on comp.lang.java.softwaretools Mon, 07 Jul 1997.
更多信息
John Aycock用Python開發(fā)了一個(gè)非常好而且簡(jiǎn)單易用的解析框架叫做SPARK ,用可讀性非常強(qiáng)的論文描述。
編譯器和解析器方面權(quán)威工作是'The Dragon Book'，也叫Compilers : Principles, Techniques, and Tools，作者Aho, Sethi and Ullman。請(qǐng)注意這是一本高級(jí)的數(shù)學(xué)書。
在線的免費(fèi)資料較好的是這本：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 ）呈現(xiàn)的是一個(gè)簡(jiǎn)單、高效而且十分方便的解析框架。方法類似于編譯器編譯器，但它依賴于一個(gè)十分強(qiáng)大的Common Lisp宏系統(tǒng)。
定義BNF語法的句法規(guī)則在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.
