SOGO論壇
  登入   註冊   找回密碼
SOGO論壇 › 論壇 › ≡ 電腦數位 ≡ › 電子電機暨資訊工程館 › Bnf
返回列表
查看: 1190|回覆: 5
列印 上一主題 下一主題

[技術文章] Bnf [複製連結]

mm117777

Rank: 11Rank: 11Rank: 11Rank: 11

熱心參予論壇活動及用心回覆主題勳章 數位硬體勳章

狀態︰ 離線
跳轉到指定樓層
1樓
發表於 2012-7-12 09:13:40 |只看該作者 |倒序瀏覽


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

Rank: 5Rank: 5

數位軟體勳章

狀態︰ 離線
2樓
發表於 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 21:27:42
mm117777  我的來源http://ccckmit.wikidot.com/ve:icarus我是從這學的如有錯請指導一下  發表於 2012-7-15 15:29:48

檢舉

mm117777

Rank: 11Rank: 11Rank: 11Rank: 11

熱心參予論壇活動及用心回覆主題勳章 數位硬體勳章

狀態︰ 離線
3樓
發表於 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我是從這學的如有錯請指導一下
我會告訴陳鐘誠說您錯了請改正不要教錯下代學子

點評

alphi  哈哈,人家是教授呢.不過因為我在研究所是研究自然語言處理.所以對這個比較了解  發表於 2012-7-15 21:17:11
alphi  哈哈,人家是教授呢.不過因為我在研究所是研究自然語言處理.所以對這個比較了解  發表於 2012-7-15 21:17:11

檢舉

mm117777

Rank: 11Rank: 11Rank: 11Rank: 11

熱心參予論壇活動及用心回覆主題勳章 數位硬體勳章

狀態︰ 離線
4樓
發表於 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:46:52

檢舉

alphi

Rank: 5Rank: 5

數位軟體勳章

狀態︰ 離線
5樓
發表於 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的關係
已有 1 人評分SOGO幣 收起 理由
mm117777 + 2 您的真誠回覆內容精闢，堪為表率，值得鼓勵.

總評分: SOGO幣 + 2   查看全部評分

檢舉

mm117777

Rank: 11Rank: 11Rank: 11Rank: 11

熱心參予論壇活動及用心回覆主題勳章 數位硬體勳章

狀態︰ 離線
6樓
發表於 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 ...

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

檢舉

返回列表
請注意︰利用多帳號發表自問自答的業配文或置入性行銷廣告者，將直接禁訪或刪除帳號及全部文章！
高級模式
B Color Image Link Quote Code Smilies
您需要登錄後才可以回覆 登入 | 註冊


本論壇為非營利自由討論平台，所有個人言論不代表本站立場。文章內容如有涉及侵權，請通知管理人員，將立即刪除相關文章資料。侵權申訴或移除要求：abuse@oursogo.com

GMT+8, 2025-2-6 14:41

品味生活|休閒天地|興趣嗜好|學術藝文|女性頻道|電腦數位|遊戲天堂|影視音樂|宗教綜合|綜合圖片|綜合影片|成人園地
© 2004-2025 SOGO論壇 OURSOGO.COM
回頂部