BNF只是CFG的一個特殊寫法

BNF的歷史如下：
1950年左右，第一種高階語言 Fortran 被開發出來。大約在同一時期，語言學家喬姆斯基﹝Noam Chomsky﹞發明了 context-free grammar (CFG)，用來描述其自然語言理論中的深層結構。1960年，Fortran 的開發者 John Backus 被邀請參加 ALGOL 程式語言的開發，Backus 發現 CFG 的衍生語法很適合用來描述高階程式語言的 statements，在那篇著名的 ALGOL60 Report 中，他稍微修改了了 CFG 的衍生語法，用來描述 ALGOL60 的語言結構以及 statement 的衍生方式。該篇報告的負責編輯是 Peter Naur，所以 ALGOL60 的 CFG 衍生語法就被稱為 Backus-Naur Form﹝BNF﹞。CFG 所描述的是英文的階層結構與衍生方式，BNF 則是 CFG 的程式語言版本。CFG 的例子如下：
sentence -> NP VP (NP = noun phrase, VP = verb phrase)
NP -> article adjective noun | article noun
VP -> verb NP
noun -> house | boy | gurl
verb -> likes | hits

" | "這個符號的意義,
這個符號是"或者"的意思,
比如說:
noun -> house | boy | gurl
這句的意思就是noun這東西可以是house 或者 boy 或者 gurl

BNF(Backus-Naur Form)是由John Backus所開發，可用來表示與上下文無關文法的語言，也就是一種用來描述語言的中繼語言(meta-language)。一個BNF表示式是由一個非終端符號(non-terminal)和它的產生式所組成，產生式可以是一個終端符號(terminal)和非終端符號組成的序列。(終端符號中的標點符號一般使用單引號括起來，而字串則使用雙引號)

底下為一個簡單的範例：

sent := subj verb '.'
subj := “Birds”
verb := “sing”

在上面的例子裡面，如Birds、sing及句點('.')表示終端符號。而sent及verb表示為非終端符號。這條BNF句子定義了一條文法，表示的意思為，一個sent是由subj及verb再以一個句點為結尾所構成。

BNF表示式有以下幾種主要表示形式：

(1) S := A B C
(2) S := A | B | C
(3) S := {A}

第一條表示說，S是由ABC三個符號所定義， 而ABC是以序列的形式依序出現，也就是說A之後一定跟著一個B，而B之後一定跟著一個C。第二條表示說，由S可推導出A或B或C其中之一。第三條表示說，由S可以推導出一個或多個A。

範例：

S := x A
A := y | z

(1) xy (O)
(2) xz (O)
(3) xx (X)
(4) yz (X)

以上4個範例中，只有(1)(2)是符合上面BNF文法定義的句子，因為x之後只能接y或z所以(3)不符合文法，因為S只能以x開頭為句子所以(4)也文法錯誤。

範例：

id := alpha {alpha}
alpha := a | b | c | d

(1) aabbbcdd (O)
(2) cabbbda (O)
(3) baccab (O)
(4) bdax (X)
(5) 5acd (X)

在上面的5個範例裡面，其中(1)(2)(3)項是正確符合上面BNF的文法定義。而(4)因為alpha裡不包含x符號所以語法不正確。而(5)因為alpha裡面不包含5所以也不正確。

範例：

S := '-' FN | FN
FN := DL | DL '.' DL
DL := D | D DL
D := '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

這幾條規則可以用來描述如3.14這樣的浮點數或如-3.14具有負號的浮點數。在DL這條規則裡面我們看到了它的定義中還出現了自己，用自己來定義自己的情況，也就是說這是一種遞迴的定義形式。雖然還是勉強能夠看的懂這些定義，不過還是有點不是那麼直覺易用，所以後來又出現了BNF的擴展形式EBNF(Extended Backus Naur Form)，EBNF引進了底下幾個新的符號改進了這些問題。

(1)?：表示符號左方的符號(或左方的括號中的一組符號)是可有可無 (optional)。
(2)*：表示符號左方的符號的數量可以出現0次以上。
(3)+：表示符號左方的符號的數量可以出現1次以上。

所以上面的浮點數範例使用EBNF可以重新改寫成如下的形式。

S := '-' D+ ('.' D+)?
D := '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

這樣是不是變的簡單明瞭多了？當然EBNF並沒有比BFN強大到那裡，只不過和BFN比較起來在使用上更加方便而已，而所有的EBNF表示式都是可以轉換為BNF表示式的。

;

有了EBNF表示式的基本認識之後對實作parser會有幫助，之後再介紹如何使用不同工具實作parser。

http://www.scribd.com/doc/20355940/Chapter-7

http://www.cs.olemiss.edu/~cbzickos/download_files/450/ch3.ppt

http://hpds.ee.ncku.edu.tw/~hjsin/courses/SP/Chap03.pdf

也就是說，你要先根據某種語法規則(rules of grammar)定義一個Language，對於某個符合這個語法規則的statement，可畫出一棵樹，這棵樹就稱為「Parse Tree」。

相關資料，可在「系統程式」得到一些，在「編譯程式」會提到很多，並且還有實作的方法。而在「計算理論」裡面，會有一些理論方面的討論