SOGO論壇

標題: Bnf [列印本頁]

作者: mm117777 時間: 2012-7-12 09:13:40 標題: 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 語法

作者: alphi 時間: 2012-7-15 15:15:03

本帖最後由 alphi 於 2012-7-15 21:42 編輯

Context-Free Grammar(CFG)是一種語言理論,其中在語言層級
Type 3: Regulator Language (正規語言)
Type 2: Context-Free Language (上下文無關語言)
Type 1: Context-Sensitive Language(上下文無關語言)
Type 0: 可列舉語言
......

其中CFG其解析就需要O(n^3),使用CYK演算法,到了CSG使用PDA(PushDown Automation)下推自動機已經到NP-Complete.

其中BNF會出現是因為Buck 與當時的發明Pascal語言的大師在討論如何更可以描述編譯器的設計語言.當然現在也有許多形式語言可以使用.例如EBNF,A+,Yacc,....

就已CFG 與BNF的關係就像是MP3演算法與WinAmp的關係是差不多.而非等價^^

作者: mm117777 時間: 2012-7-15 16:14:15

本帖最後由 mm117777 於 2012-7-15 16:16 編輯

alphi 發表於 2012-7-15 15:15
Context-Free Grammar(CFG)是一種語言理論,其中在語言層級
Type 0: Regulator Language (正規語言)
Type 1: ...

我的來源是從陳鐘誠來的http://sp1.wikidot.com/bnf我是從這學的如有錯請指導一下
我會告訴陳鐘誠說您錯了請改正不要教錯下代學子

作者: mm117777 時間: 2012-7-15 21:22:41

alphi 發表於 2012-7-15 15:15
Context-Free Grammar(CFG)是一種語言理論,其中在語言層級
Type 0: Regulator Language (正規語言)
Type 1: ...

1. 89、90、91、92、94、95、97年度優良教學教師.教育部及國立交通大學也有問題!!!

作者: alphi 時間: 2012-7-15 21:41:14

mm117777 發表於 2012-7-15 21:22
1. 89、90、91、92、94、95、97年度優良教學教師.教育部及國立交通大學也有問題!!! ...

http://zh.wikipedia.org/wiki/%E5 ... F%E8%8C%83%E5%BC%8F 這個出處會比較準確,在Content-Free Grammar 具有正規表示只有CNF,GNF這兩種,BNF主要用來描述
編譯語言本身
http://zh.wikipedia.org/wiki/巴科斯范式
這邊文章也描述BNF並非是Content-Free Grammar 中標準的實現之一,所以我才說CFG&BNF就像是MP3演算法跟Winamp的關係

作者: mm117777 時間: 2012-7-15 22:20:21

alphi 發表於 2012-7-15 21:41
http://zh.wikipedia.org/wiki/%E5%B7%B4%E7%A7%91%E6%96%AF%E8%8C%83%E5%BC%8F 這個出處會比較準確,在Co ...

可不可以也請您一起向教育部及金門大學說陳鐘誠教授教錯了以免教錯下代學子!
感恩合十

歡迎光臨 SOGO論壇 (https://oursogo.com/)