拡張バッカス・ナウア形式

コンピュータサイエンスにおいて、拡張バッカスナウア記法( EBNF ) はメタ構文表記法のファミリーであり、いずれも文脈自由文法の表現に使用できます。EBNF は、コンピュータプログラミング言語などの形式言語の形式的な記述に使用されます。これらは、基本的なバッカスナウア記法(BNF) メタ構文表記法の拡張です。最も初期の EBNF はNiklaus Wirthによって開発され、 Wirth 構文表記法の概念の一部 (異なる構文と表記法を使用) が組み込まれました。今日では、EBNF の多くのバリエーションが使用されています。国際標準化機構は、 1996 年にEBNF標準、ISO/IEC 14977 を採用しました。 ^[1]^[2] Zaytsev によると、しかしながら、この標準は「混乱にさらに 3 つの方言を追加しただけ」であり、成功しなかったことを指摘した後、ISO EBNF がすべての ISO 標準で使用されているわけではないことも指摘しています。 ^[3] Wheelerは、EBNFを使用する際にISO標準を使用することに反対し、W3C拡張マークアップ言語（XML）1.0（第5版）などの代替EBNF表記法を検討することを推奨しています。 ^[4] この記事では、すべてのEBNFに適用される例として、ISOで指定されたEBNFを使用しています。他のEBNFバリアントでは、多少異なる構文規則が使用されています。

基礎

EBNFは形式言語の構文を表現するコードです。 ^[5] EBNFは終端記号と非終端生成規則で構成されており、終端記号をどのように組み合わせて有効なシーケンスを作成するかを規定する制約です。終端記号の例には、英数字、句読点、空白文字などがあります。

EBNF は、記号のシーケンスがそれぞれ非終端記号に割り当てられる生成規則を定義します。

ゼロを除いた数字=  "1"  |  "2"  |  "3"  |  "4"  |  "5"  |  "6"  |  "7"  |  "8"  |  "9"  ;
数字                =  "0"  | ゼロを除いた数字;

この生成規則は、代入の左側にある非終端数字を定義します。縦棒は選択肢を表し、終端記号は引用符で囲まれ、その後に終了文字としてセミコロンが続きます。したがって、数字は0または1または2または3など、9までゼロを除く数字です。

生成規則には、それぞれがコンマで区切られた一連の終端記号または非終端記号を含めることもできます。

12                           =  "1" 、 "2"  ; 
201                  =  "2" 、 "0" 、"  1"  ; 
312             =  "3 " 、 12 ; 
12,201 = 12,201 ;

省略または繰り返し可能な式は、中括弧 { ... } を使用して表すことができます。

正の整数= ゼロを除く数字、 { 数字}  ;

この場合、文字列1、2、...、10、...、10000、... が正しい表現です。これを表現するために、中括弧内に設定されているものはすべて、まったく繰り返さないことも含めて、任意の回数繰り返すことができます。

オプションは角括弧 [ ... ] で表すことができます。つまり、角括弧内に設定されるものはすべて 1 回だけ存在するか、まったく存在しない可能性があります。

整数=  "0"  |  [  "-"  ]、 正の整数;

したがって、整数はゼロ ( 0 ) またはオプションでマイナス記号が前に付く正の整数です。

EBNF は、繰り返し (指定された回数) を記述したり、生成の一部を除外したり、EBNF 文法にコメントを挿入したりするための構文も提供します。

記号表

以下は、RS Scowen による ISO/IEC 14977 規格の提案 (7 ページ、表 1 および 2) を示しています。

例

構文図

EBNF

EBNF も EBNF を使用して記述できます。以下の文法を検討してください (「-」は集合の論理和を示し、「+」は 1 つ以上の一致を示し、「?」はオプション性を示すなどの規則を使用します)。

文字=  "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"  |  "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"  ;

数字=  "0"  |  "1"  |  "2"  |  "3"  |  "4"  |  "5"  |  "6"  |  "7"  |  "8"  |  "9"  ;

シンボル=  "["  |  "]"  |  "{"  |  "}"  |  "("  |  ")"  |  "<"  |  ">" 
       |  "'"  |  '"'  |  "="  |  "|"  |  "."  |  ","  |  ";"  |  "-"  
       |  "+"  |  "*"  |  "?"  |  "\n"  |  "\t"  |  "\r"  |  "\f"  |  "\b"  ;

文字= 文字| 数字| 記号|  "_"  |  " "  ;
識別子= 文字、 { 文字| 数字|  "_"  }  ;

S =  {  " "  |  "\n"  |  "\t "  |  "\r"  |  "\f"  |  "\b"  }  ;

端末=  "'"  、 文字 - "'"  、 { 文字- " '"  }  、 "'" 
         |  '"'  、 文字 - '"'  、 { 文字 - '"'  }  、 '"'  ;

ターミネータ=  ";"  |  "."  ;

term =  "("  、 S 、 rhs 、 S 、 ")" 
     |  "["  、 S 、 rhs 、 S 、 "]" 
     |  "{"  、 S 、 rhs 、 S 、 "}" 
     | 端末
     | 識別子;

因子= 用語、 S 、 "?" 
       | 用語、 S 、 "*" 
       | 用語、 S 、 "+" 
       | 用語、 S 、 "-"  、 S 、 用語
       | 用語、 S ;

連結=  (  S , 因子,  S ,  ", "  ? ) + ;
交替 = ( S , 連結 , S , "|" ?  )  +  ;

rhs = 交替; 
lhs = 識別子;

ルール=  lhs 、 S 、 "="  、 S 、 rhs 、 S 、 ターミネータ;

文法=  (  S 、 規則、 S )  *  ;

パスカル

代入のみを許可するPascalのようなプログラミング言語は、EBNF で次のように定義できます。

 (* EBNF でのシンプルなプログラム構文 - Wikipedia *)
 プログラム=  'PROGRAM' 、 空白、 識別子、 空白、 
            'BEGIN' 、 空白、 
            { 割り当て、 ";" 、 空白}、
            'END.'  ;
 識別子= アルファベット文字、 { アルファベット文字| 数字}  ;
 数値=  [  "-"  ]、 数字、 { 数字}  ;
 文字列=  '"'  、 { すべての文字 - '"'  }、 '"'  ;
 割り当て= 識別子、 ":="  、 ( 数値| 識別子| 文字列)  ;
 アルファベット文字=  "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"  ;
 数字=  "0"  |  "1"  |  "2"  |  "3"  |  "4"  |  "5"  | " 6" |  "7" | "8" | "9" ;空白= ? 空白文字 ? ;すべての文字= ? すべての表示文字 ? ;

たとえば、構文的に正しいプログラムは次のようになります。

 プログラムDEMO1 BEGIN A := 3 ; B := 45 ; H :=- 100023 ; C := A ; D123 := B34A ; BABOON := GIRAFFE ; TEXT := " Hello world !" ; END .

この言語は、制御フロー、算術式、入出力命令などを簡単に拡張できます。そうすれば、小さくて使いやすいプログラミング言語が開発されます。

BNF に対する利点

EBNF で定義された文法はすべてBNF でも表現できますが、後者での表現は一般的に長くなります。たとえば、オプションと繰り返しは BNF で直接表現できず、何も定義しないか、オプションの場合はオプションの生成規則、繰り返しの場合はそれ自体の再帰的な繰り返しの生成規則のいずれかとして定義された中間規則または代替生成規則を使用する必要があります。EBNF でも同じ構造を使用できます。

BNF では、記号 ( <、>、) がそれ自体に使用されますが、終端文字列を引用符で囲みません。これにより、これらの文字が言語で使用されなくなり、空の文字列には特別な記号が必要になります。EBNF では、|終端は引用符 ( ...または... )で厳密に囲まれます。非終端の山括弧 (" ... ") は省略できます。 ::=""''<>

BNF 構文では 1 行でのみルールを表すことができますが、EBNF では終了文字であるセミコロン文字「;」がルールの終了を示します。

さらに、EBNF には、繰り返し回数の定義、代替の除外、コメントなどの拡張機能のメカニズムが含まれています。

コンベンション

ISO/IEC 14977 規格のセクション 4 によれば、次の規則が使用されます。
- 拡張 BNF の各メタ識別子は、ハイフンで結合された 1 つ以上の単語として記述されます。ただし、標準の例に見られるように、単語の結合は、メタ言語自体の外部にあるメタ識別子を参照する場合にのみ適用されるようです。
- -symbolで終わるメタ識別子は、拡張 BNF の終端記号の名前です。

拡張 BNF の各演算子を表す通常の文字とその暗黙の優先順位は次のとおりです (一番上の優先順位が最も高い)。

 * 繰り返し記号
 - 除外記号
 、 連結記号
 | 定義区切り記号
 = 定義記号
 ; 終了記号
 . 終了記号

通常の優先順位は、次の括弧のペアによって上書きされます。
```
 (* コメント開始記号、コメント終了記号 *) 
 '  最初の引用符記号、最初の引用符記号  ' 
 (  グループ開始記号、グループ終了記号  ) 
 [  オプション開始記号、オプション終了記号  ] 
 {  リピート開始記号、リピート終了記号  } 
 ?  特殊シーケンス記号、特殊シーケンス記号  ? 
 "   2 番目の引用符記号、2 番目の引用符記号  "
```
最初の引用符はISO/IEC 646:1991 で定義されているアポストロフィ、つまり Unicode U+0027 ( ') です。ISO/IEC 14977:1996(E) で使用されているフォントでは、このアポストロフィは Unicode U+00B4 ( ) の鋭角文字に非常によく似ているため´、混乱が生じることがあります。ただし、ISO 拡張 BNF 標準では、規範的な参照として ISO/IEC 646:1991「情報交換のための ISO 7 ビット符号化文字セット」を参照しており、他の文字セットについては言及していないため、正式には 7 ビット ASCII 範囲外の Unicode 文字との混乱はありません。

例として、次の構文規則は繰り返しを表現する機能を示しています。

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 },  "G" ; 
hh =  ( aa |  bb |  cc ),  "H" ;

これらのルールによって定義される終端文字列は次のとおりです。

ああ:
bb: AAAB
cc: C AC AAC AAAC
dd: D AD AAD AAAD AAAAD など
ee：AAE AAAE AAAAE AAAAE など
ff: AAAF AAAAF AAAAAF AAAAAAF
gg: G AAAG AAAAAAG など。
hh: ああああああああああああああ

拡張性

ISO 14977 標準によると、EBNF は拡張可能であることになっており、2 つの機能が説明されています。1 つ目は、EBNF 文法の一部である特殊シーケンスです。特殊シーケンスは、疑問符で囲まれた任意のテキストです。特殊シーケンス内のテキストの解釈は、EBNF 標準の範囲外です。たとえば、スペース文字は次のルールで定義できます。

 スペース=  ? ASCII 文字 32 ? ;

2 番目の拡張機能は、EBNF の括弧は識別子の横に置けない (括弧は識別子と連結する必要がある) という事実を利用することです。以下は有効な EBNF です。

 何か=  foo 、 (  bar );

以下は有効な EBNF ではありません:

 何か=  foo (  bar );

したがって、EBNF の拡張ではその表記法を使用できます。たとえば、Lisp文法では、関数の適用は次の規則によって定義できます。

 関数アプリケーション= リスト( シンボル,  { 式}  );

参照

Meta-II – 初期のコンパイラ記述ツールと表記法
フレーズ構造ルール– 自然言語におけるEBNFに直接相当する
正規表現
スピリットパーサーフレームワーク

参考文献

^ Roger S. Scowen: 拡張 BNF — 汎用基本標準。ソフトウェアエンジニアリング標準シンポジウム 1993。
^ EBNF の多くの形式の 1 つである 国際標準 (ISO 14977) が、Zip 圧縮された PDF ファイルとして無料で利用できるようになりました。
^ Zaytsev, Vadim (2012 年 3 月 26 ～ 30 日)。「BNF の登場: 構文定義の表記法の不必要な多様性について、私たちは何をしてきたのか?」(PDF)。第 27 回 ACM 応用コンピューティングシンポジウム (SAC '12) の議事録。イタリア、リーヴァ・デル・ガルダ。p. 1。
^ Wheeler, David A. (2019). 「ISO/IEC 14977 拡張バッカスナウア記法 (EBNF) を使用しないでください」。2021 年 2 月 26 日閲覧。
^ Pattis, Richard E.「EBNF: 構文を記述するための表記法」(PDF) . ICS.UCI.edu .カリフォルニア大学アーバイン校. p. 1 . 2021-02-26閲覧。

外部リンク

ISO/IEC 14977:1996(E) 規格
BNF/EBNF のバリエーション – Pete Jinks によるいくつかの構文を比較した表

[1] Roger S. Scowen: 拡張 BNF — 汎用基本標準。ソフトウェアエンジニアリング標準シンポジウム 1993。

[2] ^ EBNF の多くの形式の 1 つである 国際標準 (ISO 14977) が、Zip 圧縮された PDF ファイルとして無料で利用できるようになりました。

[3] Zaytsev, Vadim (2012 年 3 月 26 ～ 30 日)。「BNF の登場: 構文定義の表記法の不必要な多様性について、私たちは何をしてきたのか?」(PDF)。第 27 回 ACM 応用コンピューティングシンポジウム (SAC '12) の議事録。イタリア、リーヴァ・デル・ガルダ。p. 1。

[4] Wheeler, David A. (2019). 「ISO/IEC 14977 拡張バッカスナウア記法 (EBNF) を使用しないでください」。2021 年 2 月 26 日閲覧。

[5] Pattis, Richard E.「EBNF: 構文を記述するための表記法」(PDF) . ICS.UCI.edu .カリフォルニア大学アーバイン校. p. 1 . 2021-02-26閲覧。

基礎

記号表

例

構文図