巴科斯範式

巴科斯範式（英語：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