怖くないバッカスナウア記法(BNF)入門 #言語作成

バッカスナウア記法の説明はたくさん存在しています。しかし、プログラミング言語を作ろうとしている人にとっても、なんだかめんどくさいなぁと思う人は多いように感じます。正規表現はそんなに嫌いじゃないけどBNFは嫌だ。言語を作るのは楽しいけど、仕様書くのはめんどくさい。そんな人も多いと思います。正規表現は歴史を知らずにつくり方を知らずに使っている人も多いでしょう。歴史的経緯は置いておいて、正規表現の拡張としてBNFを捉えればそんなに難しくないと思えるようになるのではないかと思い、この文章を書きました。

正規表現

プログラミング言語を作るのであれば、正規表現は知っていたほうが良いでしょう。
正規表現は、文字列操作をする上で便利な記法です。
Webブラウザ上でもJavaScriptを使って簡単に試すことができます。

たとえば、整数は以下のように表すことができます。

[0-9]+

?は0回か1回
*は0回以上の繰り返し
+は1回以上の繰り返し

を表し、

|で選択を表します。

1+2*3のような式であれば、正規表現でも表すことは可能です。

[0-9]+((\+\*)[0-9]+)*

と書くことが可能です。以下に示すJavaScriptで試してみることができます:

if("1+2*3*4".match(/[0-9]+((\+\*)[0-9]+)*/))
console.log("ok");

簡単だと思う人は多いのではないでしょうか？

オレオレ拡張バッカスナウア記法(EBNF)

正規表現は便利ですが、((1+2)*3)のような括弧を含む数式は残念ながら表すことができません。
実は括弧を含む数式は関数のように名前を使えば表すことができます。
そこで正規表現に名前をつけて参照できるようにすることを考えてみましょう。
イメージ的には以下のようになります：

digits ::= [0-9]+
exp    ::= digits((\+\*)digits)*

うーむ。これじゃダメです。digitという名前と、文字列のdigitのどちらかを区別することができません。そこで文字列はダブルクォート""で括ることにします:

digits ::= ("0"|...|"9")+
exp    ::= digits (("+" | "*") digits)*

ここで、[0-9]は、("0"|...|"9")と書くことにしました。
こういう書き方であれば、括弧を追加することができます。

digits ::= ("0"|...|"9")+
exp    ::= digits (("+" | "*") digits)*
        |  "(" exp ")"

こういう書き方が、オレオレEBNF(オレオレ拡張BNF)と呼ばれます。
本当に表せてるのかーっということで、頭の中でぐるぐると考えてみてください。expは"("があったら、expがさいきてきによびだされて、終わったら")"があればいいのだから、、、括弧がある文法が表せているよねっと。
短く書いてあるのに最初は、わからん！むかつく、バーン！！！ってなるかもしれませんけど、わかってしまいましょうｗ

バッカスナウア記法(BNF)

拡張BNFはわかったとして、元々のBNFはどういう記法なのでしょう？
元々のBNFには+や*はありません。繰り返し命令がないのにどうやって繰り返しを表現するのかというと、再帰で書けばいいのです。

<digit>  ::= ("0"|"1"|"2"|"3"|"4"|"5"|"6"|"7"|"8"|"9")
<digits> ::= <digit> | <digit> <digits>
<exp>    ::= <digits> | <digits> ("+" | "*") <exp> | "(" <exp> ")"

名前は、<>でくくって書きます。
以上のように書けば、繰り返し命令なんてなくたって書けるのです。
関数型言語ではループ文は必要ない。再帰で書けばいいんだという話に似ています。

よくある拡張BNF

[]をオプション、0回か1回の出現を表し、{}を0回以上の繰り返し、+は1回以上の繰り返しで書きます。正規表現の[0-9]は('0'|...|'9')のように、...で省略して書きます。

digits = ("0"|...|"9")+
exp    = digits { ("+" | "*") digits }
       |  "(" exp ")"

掛け算と足し算の優先順位を考えると

digits = ("0"|...|"9")+
exp    = exp2 { "+" exp2 }
exp2   = exp3 { "*" exp3 }
exp3   = digits | "(" exp ")"

と書けます。

BNFのここが嫌だ！

BNFの嫌なところをあげてストレスを解消しましょうｗ

BNFにはあいまいさがあって嫌だ。

BNFは仕様を理解するのに人が読むためのものでもあります。
自然言語の文法にはあいまいさがあります。しかし我々は読むことができますよね。人が読む場合に読みやすい書き方がBNFです。プログラミング言語はあいまいさがないのになんであいまいさのあるBNFを使うんだ！！イライラっていうことはあると思います。それは理解のしやすさを優先しているからなのです。BNFはいわば妄想の道具ですｗ言語をああだこうだ考えるのは楽しいですよね。しかし、パーサを作るのはめんどくさい作業です。でも、BNF使って妄想すればパーサ作るよりずっと楽に作業できるんです。便利だよ。

Yaccが嫌だ

BNFを書いて便利に使ってみたいけど、わけわからないツールでよくわからん書き方をしないといけなくて嫌だと思うかもしれません。ぐっと我慢して慣れましょう。慣れると楽しいですよ。字句解析器作って、パーサ作って、メイン関数から読んで構文木作ってがごちゃごちゃして嫌だーっていうのはわかりますけど慣れちゃえば勝ちです。

コンフリクトが嫌だ

Yaccを使っているとコンフリクトが出て嫌だったりします。これは最初は気にしなくて良いです。コンフリクトはワーニングであって、動かないわけではありません。人が理解できて、動けばとりあえずいいんです。最初は気にするな。無理してなくそうとしなくても十分大丈夫です。
コンフリクトの解消をするのはYaccに十分なれてからでも遅くはありません。

左再帰が嫌だ

下降型のパーサを書くのには左再帰があると無限ループに陥ります。なので左再帰が書けないようにしてくれと思うかもしれません。
でも、人が読むのには別に実装上の問題は関係ないのです。
左再帰を消すのも楽しい作業です。楽しみましょう。
オレオレ拡張BNFを使えば楽チンです。

BNFは踏み絵じゃねぇんだよ

エリートはBNFがわかって、愚民はわからんのだ。ゆえに、BNFがわからんお前はバカであり、バカなやつの作った言語なぞ使えるか。馬鹿者。ひょひょっひょひょっひょ！みたいな感じを受けると嫌になります。BNFは踏み絵じゃないです。BNFわからなくても言語作れるならすごいっす。

まとめ

BNFは怖くありません。
BNFは正規表現に名前をつけて再帰呼び出しできるように拡張したものです。
オリジナルのBNFはループがないけど、再帰があればループは書けます。
BNFにはあいまいさがありますが、人間には読みやすいものです。
BNFは妄想の道具であるので処理系は必要なく楽しいものです。
コンフリクトは最初は気にしない。
BNFは慣れたもん勝ち
BNF書くのは楽しいのでみんな書きましょう！