擴展巴科斯範式
擴展巴科斯-瑙爾範式（EBNF, Extended Backus–Naur Form）是表達作為描述計算機程式語言和形式語言的正規方式的上下文無關文法的元語法(metalanguage)符號表示法。它是基本巴科斯範式(BNF)元語法符號表示法的一種擴展。
它最初由尼克勞斯·維爾特開發，最常用的 EBNF 變體由標準，特別是 ISO-14977 所定義。
基本
[編輯]擴展巴科斯範式是一種表達形式語言文法的代碼，如由終結符即可視字符、數字、標點符號、空白字符等組成的電腦程式的原始碼。
digit excluding zero = "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;
digit = "0" | digit excluding zero ;
這個產生規則定義了在這個指派的左端的非終結符 digit。豎槓表示可供選擇，而終結符被引號包圍，最後跟着分號作為終止字符。所以 digit 是一個 "0" 或可以是 "1 或 2 或 3 直到 9 的一個 digit excluding zero"。
產生規則還可以包括由逗號分隔的一序列終結符或非終結符:
twelve = "1" , "2" ;
two hundred one = "2" , "0" , "1" ;
three hundred twelve = "3" , twelve ;
twelve thousand two hundred one = twelve , two hundred one ;
可以省略或重複的表達式可以通過花括號 { ... } 表示:
natural number = digit excluding zero , { digit } ;
在這種情況下，字符串 1, 2, ...,10,...,12345,... 都是正確的表達式。要表示這種情況，於花括號內設立的所有東西可以重複任何次，包括根本不出現。
可選項可以通過方括號 [ ... ] 表示:
integer = "0" | [ "-" ] , natural number ;
所以 integer 是一個零(0)或可能前導可選的負號的一個自然數。
EBNF 還包括描述指定次數的重複，和排除產生式的某部分或向 EBNF 文法插入註釋的語法。
符號表
[編輯]| 用途 | 符號表示 |
|---|---|
| 定義 | = |
| 串接 | , |
| 終止 | ; |
| 分隔 | | |
| 可選 | [ ... ] |
| 重複 | { ... } |
| 分組 | ( ... ) |
| 雙引號 | " ... " |
| 單引號 | ' ... ' |
| 註釋 | (* ... *) |
| 特殊序列 | ? ... ? |
| 除外 | - |
約定
[編輯]1. 使用了如下約定:
- 擴展 BNF 每個元標識符都被寫為用連字號連接起來的一個或多個字；
- 結束於「-symbol」 的元標識符是擴展 BNF 的終結符的名字。
2. 表示擴展 BNF 的每個操作符的正常字符和它所蘊涵的優先級(頂部為最高優先級)為:
* repetition-symbol - except-symbol , concatenate-symbol | definition-separator-symbol = defining-symbol ; terminator-symbol
3. 下列括號對超越正常優先級:
´ first-quote-symbol first-quote-symbol ´
" second-quote-symbol second-quote-symbol "
(* start-comment-symbol end-comment-symbol *)
( start-group-symbol end-group-symbol )
[ start-option-symbol end-option-symbol ]
{ start-repeat-symbol end-repeat-symbol }
? special-sequence-symbol special-sequence-symbol ?
作為例子，下列語法規則展示了表達重複的設施:
aa = "A";
bb = 3 * aa, "B";
cc = 3 * [aa], "C";
dd = {aa}, "D";
ee = aa, {aa}, "E";
ff = 3 * aa, 3 * [aa], "F";
gg = {3 * aa}, "D";
這些規則定義的終結字符串如下:
aa: A bb: AAAB cc: C AC AAC AAAC dd: D AD AAD AAAD AAAAD etc. ee: AE AAE AAAE AAAAE AAAAAE etc. ff: AAAF AAAAF AAAAAF AAAAAAF gg: D AAAD AAAAAAD etc.
示例
[編輯]只允許賦值的簡單程式語言可以用 EBNF 定義為:
(* a simple program in EBNF − Wikipedia *)
program = 'PROGRAM' , white space , identifier , white space ,
'BEGIN' , white space ,
{ assignment , ";" , white space } ,
'END.' ;
identifier = alphabetic character , [ { alphabetic character | digit } ] ;
number = [ "-" ] , digit , [ { digit } ] ;
string = '"' , { all characters − '"' } , '"' ;
assignment = identifier , ":=" , ( number | identifier | string ) ;
alphabetic character = "A" | "B" | "C" | "D" | "E" | "F" | "G"
| "H" | "I" | "J" | "K" | "L" | "M" | "N"
| "O" | "P" | "Q" | "R" | "S" | "T" | "U"
| "V" | "W" | "X" | "Y" | "Z" ;
digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;
white space = ? white space characters ? ;
all characters = ? all visible characters ? ;
一個語法上正確的程序:
PROGRAM DEMO1
BEGIN
A0:=3;
B:=45;
H:=-100023;
C:=A;
D123:=B34A;
BABOON:=GIRAFFE;
TEXT:="Hello world!";
END.
這個語言可以輕易的擴展上控制流，算術表達式和輸入/輸出指令。就可以開發出一個小的、可用的程式語言了。
比較 EBNF 和 BNF
[編輯]BNF 有着可選項和重複不能直接表達的問題。作為替代，它們需要利用中介規則或兩選一規則，對於可選項，定義要麼是空的要麼是可選的產生式的規則，對於重複，遞歸的定義要麼是被重複的產生式要麼是自身的規則。同樣的構造仍可用在 EBNF 中。
可選項:
signed number = [ sign , ] number ;
可按 BNF-風格定義為:
signed number = sign , number | number ;
或
signed number = optional sign , number ;
optional sign , = ε | sign , ; (* 使用 ε 来更清晰的指示空产生式 *)
重複:
number = { digit } digit ;
可按 BNF-風格定義為:
number = digit | number digit;
EBNF 較 BNF 的優點
[編輯]EBNF 排除了 BNF 的一些缺陷:
- BNF 為自身使用了符號 (<, >, |, ::=)。當它們出現在要定義的語言中的時候，BNF 不得不加以修改或解釋的使用。
- BNF-語法在一行中只表示一個規則。
EBNF 解決了這些問題:
進一步還提供了定義重複次數，排除法選擇(比如除了引號的所有字符)和註釋等的增強機制。
不管所有這些增強，EBNF 在能定義的語言的意義上不比 BNF 更強大。在原理上用 EBNF 定義的任何文法都可以用 BNF 表達。但是經常導致可觀的更多規則的表示。
EBNF 已經被ISO用代碼 ISO/IEC 14977:1996(E) 標準化了。
在某些場合任何擴展的 BNF 都被稱為 EBNF。例如 W3C 使用 one EBNF 來規定 XML。
擴展
[編輯]依據 ISO 14977 標準，提供了兩個設施來擴展 EBNF。其一是在 EBNF 文法部分的特殊序列，它是在問號包圍內的任意文本，其解釋超出了 EBNF 標準的範圍。例如，空格字符可以用如下規則定義:
space = ? US-ASCII character 32 ?;
其二利用圓括號在 EBNF 中不能放置到緊隨標識符之後的事實。下列不是有效的 EBNF:
something = foo ( bar );
所以 EBNF 的擴展可以使用這種表示法。例如，在 Lisp 文法中，函數應用可以用如下規則定義:
function application = list( symbol , [ { expression } ] );
有關工作
[編輯]- W3C 使用一種不同的 EBNF 來指定 XML 語法。
- British Standards Institute 在1981年出版了一個 EBNF 標準: BS 6154。
- IETF 使用在 RFC 4234 中規定的擴充 BNF (ABNF)。
參見
[編輯]引用
[編輯]- Niklaus Wirth: What can we do about the unnecessary diversity of notation for syntactic definitions? （頁面存檔備份，存於互聯網檔案館） CACM, Vol. 20, Issue 11, November 1977, pp. 822-823.
- Roger S. Scowen: Extended BNF — A generic base standard. Software Engineering Standards Symposium 1993.
- The International standard (ISO 14977 （頁面存檔備份，存於互聯網檔案館）) that defines the EBNF is now freely available as zipped pdf file （頁面存檔備份，存於互聯網檔案館）.
外部連結
[編輯]- Article "EBNF: A Notation to Describe Syntax (PDF) （頁面存檔備份，存於互聯網檔案館）" by Richard E. Pattis describing the functions and syntax of EBNF
- Article "BNF and EBNF: What are they and how do they work? （頁面存檔備份，存於互聯網檔案館）" by Lars Marius Garshol
- Article "The Naming of Parts （頁面存檔備份，存於互聯網檔案館）" by John E. Simpson
- ISO/IEC 14977 : 1996(E) （頁面存檔備份，存於互聯網檔案館）
- RFC 4234 - Augmented BNF for Syntax Specifications: ABNF
- BNF/EBNF variants （頁面存檔備份，存於互聯網檔案館） - a table by Pete Jinks comparing several syntaxes.
- Create syntax diagrams from EBNF