巴科斯範式

巴科斯範式(英語: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 規定是推導規則(產生式)的集合,寫為:

<符號> ::= <使用符號的表達式>

這裏的 <符號> 是非終結符,而表達式由一個符號序列,或用指示選擇豎槓 '|' 分隔的多個符號序列構成,每個符號序列整體都是左端的符號的一種可能的替代。從未在左端出現的符號叫做終結符

參見

引用

本條目部分或全部內容出自以GFDL授權發佈的《自由線上電腦詞典》(FOLDOC)。

外部連結