巴科斯範式
外觀
![本頁使用了標題或全文手工轉換](http://upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
![]() | 此條目可參照德語維基百科相應條目來擴充。 (2023年7月13日) |
巴科斯範式(英語:Backus Normal Form,縮寫為 BNF),又稱為巴科斯-諾爾範式(英語:Backus-Naur Form,縮寫同樣為 BNF,也譯為巴科斯-瑙爾範式、巴克斯-諾爾範式),是一種用於表示上下文無關文法的語言,上下文無關文法描述了一類形式語言。它是由約翰·巴科斯(John Backus)和彼得·諾爾(Peter Naur)首先引入的用來描述計算機語言語法的符號集。
儘管巴科斯範式也能表示一部分自然語言的語法,它還是更廣泛地使用於程式語言、指令集、通信協議的語法表示中。大多數程式語言或者形式語義方面的教科書都採用巴科斯範式。在各種文獻中還存在巴科斯範式的一些變體,如擴展巴科斯範式 EBNF 或擴充巴科斯範式 ABNF。
發展歷史
[編輯]約翰·巴科斯首次在ALGOL 58中實作出巴科斯範式。彼得·諾爾在ALGOL 60之中,進一步發展它的概念並將它的符號加以簡化,稱其為巴科斯範式(Backus Normal Form)。但高德納主張應稱為巴科斯-諾爾範式(Backus–Naur Form),因為它不算是一種正規形式(Normal form)。
介紹
[編輯]BNF 規定是推導規則(產生式)的集合,寫為:
<符號> ::= <使用符號的表達式>
這裏的 <符號> 是非終結符,而表達式由一個符號序列,或用指示選擇的豎槓 '|' 分隔的多個符號序列構成,每個符號序列整體都是左端的符號的一種可能的替代。從未在左端出現的符號叫做終結符。
參見
[編輯]- 八篇書(使用數學結構的梵語文法)
- 擴充巴科斯範式(ABNF)
- 擴展巴科斯範式(EBNF)
- GOLD BNF分析器
- GNU bison GNU版本的Yacc
- 正則表達式
- Wirth語法表示法1977提出的對BNF的一個替代者
- Yacc分析器生成器(與Lex預處理器一起使用)
- ANTLR用Java寫的另一個分析器生成器
- 上下文有關文法
- 形式文法
- 分析表達式文法
- 隨機上下文無關文法
引用
[編輯]本條目部分或全部內容出自以GFDL授權發佈的《自由線上電腦詞典》(FOLDOC)。
外部連結
[編輯]- Algol-60 BNF, the original BNF.
- Sample grammars at the BNF Web club.
- [1] (頁面存檔備份,存於互聯網檔案館) contains a posting on news:comp.compilers that explains some of the history of the two names (Backus-Naur form vs. Backus normal form).
- Article BNF and EBNF: What are they and how do they work? (頁面存檔備份,存於互聯網檔案館) by Lars Marius Garshol.
- RFC 4234[失效連結] Augmented BNF for Syntax Specifications: ABNF
- Comparision of different variants of BNF
- Syntax diagram of EBNF
- Generation of syntax diagrams from EBNF