BNF、EBNF、ABNF、まー正規表現だな

BNFとか正規表現の話を。

ミニマムなBNFと正規表現

BNF（バッカス／ナウア記法）は、プログラミング言語の構文記述によく使われるメタ構文です。もともとは、「?」（省略可能）や「*」（任意回の繰り返し）のような記号は使わなかったようです。現在の正規表現で標準的に使われる「?」「*」「+」は、なくても次のように定義可能なのです。（以下で、EMPTYはそこに何もないことです。ほんとに何も無いと分かりにくいので目印にEMPTYを使います。）

// X は A?
X ::= EMPTY | A

// Y は A*
Y ::= EMPTY | A Y

// Z は A+
Z ::= A | A Z

「|」があれば「?」「*」「+」を定義できますが、その代わりに再帰的な定義になります。

「::=」の左に同じ記号が複数回登場するのを許すと、「|」さえも不要になります。

// X は A?
X ::= EMPTY
X ::= A

// Y は A*
Y ::= EMPTY
Y ::= A Y

// Z は A+
Z ::= A
Z ::= A Z

ミニマムな記法を本家BNFとするときは、「?」「*」「+」などを使う流儀はEBNF(拡張BNF)と呼ぶことがあります。もっとも、現在ではEBNFを使うことが多いでしょうから、いちいち E（Extended）を付ける必要はないと思います。

変態なBNF -- ABNF

A? の代わりに [A]、A+ の代わりに A ... のような代替記法をたまに見かけます。これは分かりやすくていいんじゃないでしょうか。

RFCを読んでみると、なんか変なBNFが使われていることに気がつくでしょう。これは、ABNF（Augmented BNF）です。RFC以外で使われている例を僕は知らないのですが、RFCではこれを使うのが慣例みたいです。

ABNF自体がRFCになっていて http://www.ietf.org/rfc/rfc2234.txt "Augmented BNF for Syntax Specifications: ABNF" で定義されています。普通のBFN、あるいは正規表現と比べてみると、次の表のようにまります。

＼	通常のBNF	ABNF
定義	X ::= ...	X = ...
選択	A | B	A / B
オプション	A?	*1A
繰り返し	A*	*A
1回以上繰り返し	A+	1*A

ABNFでは、繰り返しの星印 * は前に付けます。n*m という形が使えて、「n回以上、m回以下の繰り返し」の意味になります。nのデフォルトが0, mのデフォルトが無限なので、* だけで「任意回の繰り返し」になります。Perlの正規表現と比べてみると：

Perlの正規表現	ABNF
A{2,5}	2*5A
A{2,}	2*A
A{3}	3A

ABNFは、なんでわざわざ普通（多数派）と違う表現を使うんでしょうか？

それと、恐ろしいことには、"ABNF strings are case-insensitive"（ABNFの文字列は、大文字小文字を区別しません）とのこと。

 name = "ab"

この定義は、nameに"ab"ソノモノを割り当てたことにはなりません。普通の書き方で表現するなら：

 name ::= "ab" | "Ab" | "aB" | "AB"

インターネットにおいて使われる文字列定数（例えばトップレベルドメイン名）は大文字小文字を区別しないことが多いので、こういう仕様なんでしょうが、だいぶ違和感ありますね。

"ab"ソノモノを定義したいなら次のように書きます。

 name = %d97 %d98

%d97 %d98 の代わりに、%d97.98 でもOKです。あるいは、%x61 %x62、%x61.62 も使えます。文字番号の先頭には「%」を付けます。範囲を表すには %x30-39 が使えます。XML仕様などを見慣れた僕には、#x61 #x62、[#x61-#x65] のほうがずっとシックリきます。

「シックリ」は個人的な感覚ですが、それにしてもABNFはいいかげん変な構文なので、もう使うのやめればいいのに。