2010年2月1日 星期一

(E)BNF表示式

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。

6 則留言:

  1. YES. 接下的計劃是陸續介紹怎麼使用不同方法及工具實作paser,包含純手工打造,lex/yacc(flex/bison),boost.spirit,yard pser等.

    回覆刪除
  2. 關於浮點數部分
    DL := D | DL
    是否應該改成
    DL := D DL | DL
    原本的好像只能寫到小數第一位
    還是有那裡我搞錯了...

    回覆刪除
  3. 不好意思, 這是個筆誤,似乎常犯這種錯..

    應該是DL := D | D DL
    或是DL := D DL | D也可以,但用上面的形式會更好以免stack overflow
    但寫成DL := D DL | DL是不對的

    回覆刪除
  4. 請問
    S := '-' D+ ('.' D+)?
    是否應該改成
    S := ('-')? D+ ('.' D+)?

    回覆刪除
  5. 答對了!
    真是太利害了, 又抓到我的bug!

    回覆刪除

Related Posts Plugin for WordPress, Blogger...