什麼是BNF範式

from:http://archer49.spaces.live.com/blog/cns!838BE88BC5E4CDA3!778.entry

什麼是BNF範式,什麼又是EBNF範式?

巴科斯範式及其擴充

BNF & Augmented BNF   

     什麼是巴科斯範式？

　　巴科斯範式(BNF: Backus-Naur Form 的縮寫)是由 John Backus 和 Peter Naur 首先引入的用來描述計算機語言文法的符号集。

　　現在，幾乎每一位新程式設計語言書籍的作者都使用巴科斯範式來定義程式設計語言的文法規則。   

     巴科斯範式的内容  

在雙引号中的字("word")代表着這些字元本身。而double_quote用來代表雙引号。

在雙引号外的字（有可能有下劃線）代表着文法部分。

尖括号( < > )内包含的為必選項。

方括号( [ ] )内包含的為可選項。

大括号( { } )内包含的為可重複0至無數次的項。

豎線( | )表示在其左右兩邊任選一項，相當于"OR"的意思。

::= 是“被定義為”的意思。 

     巴科斯範式示例  

         這是用BNF來定義的Java語言中的For語句的執行個體：

FOR_STATEMENT ::=       "for" "(" ( variable_declaration |   ( expression ";" ) | ";" )       [ expression ] ";"       [ expression ] ";"       ")" statement

         這是Oracle packages的BNF定義：

package_body ::= "package" package_name "is" package_obj_body { package_obj_body } [ "begin" seq_of_statements ] "end" [ package_name ] ";" package_obj_body ::= variable_declaration | subtype_declaration | cursor_declaration | cursor_body | exception_declaration | record_declaration | plsql_table_declaration | procedure_body | function_body procedure_body ::= "procedure" procedure_name [ "(" argument { "," argument } ")" ] "return" return_type "is" [ "declare" declare_spec ";" { declare_spec ";" } ] "begin" seq_of_statements [ "exception" exception_handler { exception_handler } ] "end" [ procedure_name ] ";" statement ::= comment | assignment_statement | exit_statement | goto_statement | if_statement | loop_statement | null_statement | raise_statement | return_statement | sql_statement | plsql_block

    這是用BNF來定義的BNF本身的例子：

syntax     ::=  { rule } rule       ::=  identifier  "::="  expression expression ::=  term { "|" term } term       ::=  factor { factor } factor     ::=  identifier |                 quoted_symbol |                 "("  expression  ")" |                 "["  expression  "]" |                 "{"  expression  "}" identifier ::=  letter { letter | digit } quoted_symbol ::= """ { any_character } """

     擴充的巴科斯範式 Augmented BNF 

　　RFC2234 定義了擴充的巴科斯範式(ABNF)。近年來在Internet的定義中ABNF被廣泛使用。ABNF做了更多的改進，比如說，在ABNF中，尖括号不再需要。 

    什麼是EBNF? 基本 (EBNF) 定義 有關 EBNF 協定的詳細情況，可以參看 Computing Dictionary.

這裡是要點一覽:

"..." : 術語符号 [...] : 選項: 最多出現一次 {...} : 重複項: 任意次數，包括 0 次 (...) : 分組 | : 并列選項，隻能選一個 斜體字: 參數，在其它地方有解釋

  http://estone.nease.net/sgf/sgf4.html#2 裡會給出一個EBNF在棋牌類的應用.   --------------------------------------------------------------------------------------------   <BNF>::=     <非終結符>::=<或項清單>  

  <或項清單>::=     <項>     |     <或項清單>|<項>  

  <項>::=     <非終結符>     |     <終結符>   |   <項><非終結符>   |   <項><終結符>  

  <非終結符>::=       <非終結符名>  

  （   但願能有人看得懂:-)   )  

  BNF就是巴科特·瑙爾式的縮寫，  

  在計算機的史前時代（1950s)，曾有一位大師，他奠定了現代計算機的基礎  

  在他老人家的諸多成就之中，包括了對形式語言的研究，和發明了進階語言：  

  FORTRAN。  

  為了紀念他老人家，我們把他提出的一套描述語言的方法叫做BNF  

  其實BNF很簡單::=表示定義   |表示或   尖括号(<>)括起來的是非終結符  

  所謂非終結符就是語言中某些抽象的概念，終結符就是可以直接出現在  

  語言中的符号  

  比如：C語言的聲明語句可以用BNF這樣描述：  

  <聲明語句>   ::=   <類型><辨別符>;   |   <類型><辨別符>[<數字>];  

  這一句中<聲明語句>這個非終結符被定義成了兩種形式（上面用|隔開的兩部分）  

  在這裡引入了三個終結符:   分号;     左右方括号[   ]  

  <類型>   ::=   <簡單類型>   |   <指針類型>   |   <自定義類型>  

  <指針類型>   ::=   <簡單類型>   *   |   <自定義類型>   *  

  <簡單類型>   ::=   int|char|double|float|long|short|void  

  <自定義類型>   ::=   enum<辨別符>|struct<辨別符>|union<辨別符>|<辨別符>  

  到這裡就基本上把<類型>定義清楚了  

  <數字>   ::=   0X<十六進制數字串>   |   0<八進制數字串>   |   <十進制數字串>  

  <十六進制數字串>   ::=   <十六進制數字>   |   <十六進制數字串><十六進制數字>    

  <八進制數字串>   ::=   <八進制數字>   |   <八進制數字串><八進制數字>    

  <十進制數字串>   ::=   <十進制數字>   |   <十進制數字串><十進制數字>    

  <十六進制數字>   ::=   <十進制數字>   |   A   |   B   |   C   |   D   |   E   |   F  

  <十進制數字>     ::=   <八進制數字>   |   8   |   9    

  <八進制數字>   ::=   0   |   1   |   2   |   3   |   4   |   5   |   6   |   7  

  到這裡就把<數字>定義清楚了  

  <辨別符>   ::=   <字母>   |   <辨別符>   <字母數字串>  

  <字母數字串>   ::=   <字母>|<十進制數字>|<字母數字串><字母>|<字母數字串><十進制數字>    

  <字母>   ::=   _   |   <大寫字母>   |   <小寫字母>  

  <小寫字母>   ::=   a|b|c|d|e|f|g|h|i|j   ……   （偷個懶）  

  <大寫字母>   ::=   A|B|C|D|E|F|G|H|I|J   ……  

  到此為止整個聲明語句就定義完了（就是說已經沒有非終結符了），雖然看起來很  

  繁，但前面定義的各種非終結符都可以很容易的在别的地方重用比如，函數聲明  

  可以定義成下面的樣子：  

  <函數聲明語句>   ::=   <類型><辨別符>(<形參表>);  

  <形參表>   ::=   <類型><辨別符>   |   <形參表>,<形參表>  

  隻用兩句就描述完了，是以BNF實際上比用自然語言要簡練得多  

  （整個C語言隻用一二百句就可以描述清楚）  

  而且相當的精确，不會有自然語言中那種模棱兩可的表達  

  如果你對BNF比較敏感的話，會發現C裡面的辨別符不能由數字開頭  

  而且在C裡面下劃線是被當做字母看待的（也就是說能用字母的地方  

  都可以用下劃線）比如：（最好用老一點的編譯器比如PDP11上的cc）  

  #define   ____   main  

  #define   ___   for  

  typedef   char*   _____;  

  int   (*______)(char   *,   ...)   =   printf;   //如果這一句不靈，就用下面這句  

  //#define   ______   printf                         //如果你用的是C++可以試一下下面這個  

  //int   (*______)(const   char   *,   ...)   =   printf;    

  ____(_,char*   __[])   //要是你編譯器不吃，可以改成int   ____(int   _,char*__[])  

  {  

      ___(   ;   _   ;   _   --)  

      {  

            ______("%s/n",   __[_]);  

      }  

  }  

  另外，還有一種EBNF就沒有正宗的BNF這麼爽了，也有很多人在用，前面的  

  那些遞歸的定義被寫成了{}  

  有一段時間PASCAL愛好者們喜歡用一個叫文法圖的東西，畫出來很難看，但  

  功能和BNF差不多，現在好象已經沒多少人用了  

  近幾年流行另一種東西：  

  digit   =   one   of  

                  0   1   2   3   4   5   6   7   8   9  

  這裡非終結符digit用斜體表示，one   of是這種方法裡定義的一個量詞（常用斜黑體）  

  我不喜歡這個，因為我眼神不好，常常分不清那個是斜體，那個是正體