このブログの更新は Twitterアカウント @m_hiyama で通知されます。
Follow @m_hiyama

メールでのご連絡は hiyama{at}chimaira{dot}org まで。

はじめてのメールはスパムと判定されることがあります。最初は、信頼されているドメインから差し障りのない文面を送っていただけると、スパムと判定されにくいと思います。

参照用 記事

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