BNF範式

BNF範式,是一種用於表示上下文無關文法的語言,上下文無關文法描述了一類形式語言。

BNF範式(BNF: Backus-Naur Form 的縮寫;也稱為巴科斯-瑙爾範式、巴克斯-諾爾範式),是一種用於表示上下文無關文法的語言,上下文無關文法描述了一類形式語言。
是科學哲學家庫恩提出的科學前進的模式,大意是一起工作的科學家們大體有一個共同的守則和目標,比如牛頓的經典力學,為此完成範式內的各項工作,科學的進步也就是一個範式取代另一個範式,比如後來的愛因斯坦的相對論在某種意義上的取代了巨觀上的經典力學,還有量子力學在微觀上完成了這個取代。
BNF範式的內容
在雙引號中的字("word")代表著這些字元本身。而double_quote用來代表雙引號。
在雙引號外的字(有可能有下劃線)代表著語法部分。
< > : 內包含的為必選項。
[ ] : 內包含的為可選項。
{ } : 內包含的為可重複0至無數次的項。
| : 表示在其左右兩邊任選一項,相當於"OR"的意思。
::= : 是“被定義為”的意思
巴科斯範式的內容
在雙引號中的字("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
[ "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 ]
"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 ::= identifier "::=" expression
expression ::= term { "|" term }
term ::= factor
factor ::= identifier |
quoted_symbol |
"(" expression ")" |
"[" expression "]" |
"{" expression "}"
identifier ::= letter { letter | digit }
quoted_symbol ::= """ """
擴展的巴科斯範式 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是這種方法裡定義的一個量詞(常用斜黑體)

相關詞條

相關搜尋

熱門詞條

聯絡我們