ミニマムな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はいいかげん変な構文なので、もう使うのやめればいいのに。