Bnf

Chomsky 生成語法中的 Context-Free Grammar (CFG) 與Backus 和 Naur 兩人所提出的BNF 語法,可以說是同一件事。然而,BNF 針對程式語言進行精確的描述,在描述語法上更為明確,可以說是 CFG 語法的一個具體描述方式。然而,在許多文章當中,早已將 CFG 與 BNF 兩者的意義視為相同,這是沒有太大影響的。然而,為了明確起見,在本書當中,我們用 BNF 來指稱『以電腦字元集的固定格式,表示 CFG 的一種特別語法』,例如,我們可以將圖 7.6當中的 CFG 寫成如圖 7.8右側的 BNF 語法。這樣的改寫有助於將 BNF 語法以電腦鍵盤打出,而不需要考慮到特殊符號的表達問題。

Context Free Grammar

E => T | E "+" T | E "-" T . 
T => F | T "*" F | T "/" F. 
F => V | "(" E ")". 
V => "1" | "2" | "3" | "4".

BNF 語法

<E> ::= <T> | <E> "+" <T> | <E> "-" <T>
<T>::=<F>|<T> "*" <F> | <T> "/" <F>
<F>::=<V> | "(" <E> ")"
<V>::= "1" | "2" | "3" | "4"

圖 7.8 將<圖 7.6> 的 CFG 改寫為 BNF 語法

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License