EBNF

EBNF（拡張バッカス・ナウア記法）とは

EBNF（Extended Backus-Naur Form）は、文脈自由文法を表現するためのメタ文法記法であり、プログラミング言語や形式言語の構文を形式的に記述する際に用いられます。これは、バッカス・ナウア記法（BNF）を拡張したものであり、より簡潔かつ直感的に文法を表現できるようになっています。EBNFは、ISO 14977として国際標準化もされています。

EBNFの基本

EBNFは、終端記号と非終端記号、そして生成規則によって構成されます。

終端記号：具体的な文字、数字、記号など、それ以上分解できない要素です。プログラムのソースコードを構成する最小単位です。
非終端記号：文法的な構成要素を表す記号で、他の記号の組み合わせで定義されます。
生成規則：非終端記号がどのような記号列で構成されるかを定義する規則です。

例えば、以下のような生成規則があるとします。

ebnf
digit = "0" | digit-excluding-zero ;
digit-excluding-zero = "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9";


この例では、`digit`が非終端記号であり、`0`から`9`までの数字のいずれかを表します。`|`は選択を表し、`"`で囲まれた部分は終端記号を表します。

EBNFの構文要素

EBNFには、BNFにはない便利な構文要素が導入されています。

繰り返し：中括弧`{ ... }`で囲まれた部分は、0回以上の繰り返しを意味します。

ebnf
natural-number = digit , { digit } ;


この例では、`natural-number`は1つ以上の数字の並びを表します。
省略可能：大括弧`[ ... ]`で囲まれた部分は、省略可能であることを意味します。

ebnf
integer = [ "-" ] , natural-number;


この例では、`integer`はオプションでマイナス符号が付いた`natural-number`を表します。

グループ化：括弧 `( ... )` で囲むことで、複数の要素を一つのグループとして扱うことができます。

BNFとの違い

BNFでは、オプションや繰り返しを直接的に表現できませんでした。そのため、中間的な規則を定義したり、再帰的な規則を使用したりする必要がありました。EBNFでは、これらの問題を中括弧`{ }`や大括弧`[ ]`といった記号でより簡潔に表現できるようになりました。

例えば、BNFでオプションを表現するには、以下のようになります。

bnf
::= |
::= "-"


EBNFでは、以下のようによりシンプルに表現できます。

ebnf
integer = [ "-" ] , natural-number;

ISOによる拡張

ISO 14977では、EBNFをさらに拡張するための仕組みが導入されました。その一つとして、疑問符`?`で囲まれたテキストは、EBNFの解釈範囲外として扱うことができます。これにより、コメントや注釈を文法定義に含めることが可能になります。

また、括弧を識別子に続けて配置できないというEBNFの制約を利用して、独自の拡張記法を導入することができます。例えば、LISPの関数呼び出しは以下のように定義できます。

ebnf
function-application = list( symbol , { expression } );

EBNFの応用例

EBNFは、プログラミング言語の構文定義、データ形式の定義、プロトコルの仕様記述など、様々な分野で活用されています。

例えば、単純な代入文しかないプログラミング言語をEBNFで定義すると、以下のようになります。

ebnf
program = { statement } ;
statement = variable , "=" , expression , ";" ;
variable = letter , { letter | digit } ;
expression = variable | number ;
number = digit , { digit } ;
letter = "a" | "b" | ... | "z" ;
digit = "0" | "1" | ... | "9" ;


この文法で定義されたプログラムの例としては、以下のようなものがあります。


x = 123;
y = x;

EBNFの記号と優先順位

EBNFで用いられる記号には、以下のような優先順位があります。

1. `*` (繰り返し)
2. `-` (除外)
3. `,` (連結)
4. `|` (選択)
5. `=` (定義)
6. `;` (終端)

また、括弧によって優先順位を変更できます。

その他の拡張と関連仕様

EBNFには、ISO標準以外にも様々な拡張が存在します。W3Cは、XMLの文法記述に独自のEBNFを使用しています。また、IETFは、ABNF（Augmented BNF）をプロトコル記述に採用しています。

まとめ

EBNFは、BNFを拡張したメタ文法記法であり、プログラミング言語や形式言語の文法をより簡潔かつ直感的に記述することができます。繰り返しや省略可能な要素を直接的に表現できるため、複雑な文法も明確に定義することが可能です。ISO 14977として標準化もされており、様々な分野で広く利用されています。

もう一度検索