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