バッカス・ナウア記法（BNF）の書き方をわかりやすく学ぶ

CodeMirror6についてさらっと勉強するつもりだったのに、気づけばバッカス・ナウア記法の勉強を強いられていた。「勉強を強いられる」ってすごい虫感のある字列である。虫に見られている感がある。

さておき、バッカス・ナウア記法（Backus–Naur form、略してBNFとも呼ぶ）にはこれまで幾度もお目に掛かってきた。彼らは毎回、初めましての顔をして表れる。記号記号しており、私の脳みそが彼らを理解したがらないからだ。バカの壁ならぬバッカスの壁が働いている。ここで基本的な情報をまとめて、そうした状況にケリをつけたいと思う。

「惣菜パン」でバッカス・ナウア記法の基本を学ぶ

バッカス・ナウア記法とは、なんらかの表現のパターンをわかりやすく書くための記法である。

1950年代後半に、ジョン・バッカス氏がIALという言語（後にAlgolに改名）の構文をシンプルに表現するために発明した。それをピーター・ナウア氏が使いやすく調整したため、バッカス・ナウア記法と呼ばれるようになった。らしい。

この記法では、左辺に表現の名称、右辺にその表現を構成する要素を記述する。

たとえば「惣菜パン」という言葉を例に考える。惣菜パンは、一般に「<具>パン」という名称で呼ばれる。「コロッケパン」「焼きそばパン」「スパゲティパン」「ウィンナーパン」などである。これをバッカス・ナウア記法で書くと以下のようになる。

<総菜パン> ::= <具>パン
<具> ::= コロッケ | 焼きそば | スパゲティ | ウィンナー

<>は分類名を、::=は代入を、|は選択肢をそれぞれ表す。

<>に囲まれた分類名を無印の表現（上記の例ではコロッケ、焼きそばなど）で置き換えると、その規則に基づく表現のパターンを導ける。つまりこの規則では、<惣菜パン>はコロッケパン、焼きそばパン、スパゲティパン、ウィンナーパンの4パターンであることが示されている。

より実践的な例

以下は四則演算の式の例である。記号が多いため複雑に見えるが、基本的な仕組みを理解さえすれば、順を追って置き換えていくだけで読み解けるはずである。

<expression> ::= <term> | <expression> '+' <term> | <expression> '-' <term>
<term> ::= <factor> | <term> '*' <factor> | <term> '/' <factor>
<factor> ::= <number> | '(' <expression> ')'
<number> ::= <digit> | <number> <digit>
<digit> ::= '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

expressionは式、termは項（足し算・引き算に使われる数字）、factorは因子（掛け算・割り算に使われる数字）、digitは桁という意味の英単語である。

最初の行に+と-があるのは、足し算（引き算）より掛け算（割り算）が優先されるためだ。この段階では、掛け算と割り算はtermとしてまとめておく必要がある。このように最初にその分類全体の構造を示し、そこから細部を掘り下げていく形が、バッカス・ナウア記法の基本である。木構造で各要素の親子関係を表現している、とも言える。

実際には、こうした表現の規則を無数に集めて、全体の言語を定義する。

非終端記号と終端記号

バッカス・ナウア記法は、非終端記号と終端記号の組み合わせで構成される。言葉はむずかしいが、実体はやさしいものである。上記に挙げた例で言えば、<>で表現されるのが非終端記号、無印で表現されるのが終端記号に該当する。

なお、ここで使われる終端は、句点のような目で見てわかる終端ではなく、置き換え可能な表現の終端を意味する。

バッカス・ナウア記法で左辺に置かれるのは、必ず非終端記号である。右辺は、非終端記号、あるいは終端記号の組み合わせで表現される。

ちなみに使われる記号については、ケースバイケースで揺れがある。一般に非終端記号は角カッコ（<>）で囲われるか、あるいは特に記号は使わずに表現される。非終端記号に角カッコが使われない場合、終端記号はシングルクォーテーション(')、あるいはダブルクォーテーション(")で囲って表現される。また、|がorと表現されることもある。

後述の拡張バッカス・ナウア記法含め、実用のシーンでは地味に使われる記号に揺れがある。ただ、オリジナルのシンプルなBNFをきちんと押さえておけば、類推でがんばれるかと思う。もとい、がんばりたい。

再帰の考え方

ある処理を実行し、なんらかの条件を判断して、それに合致しなければ再び同じ処理を実行する。これが再帰のおおまかな概要である。たとえば文章を一行読むという動作は、「文字を読む」という動作を、「句点に辿り着くまで」再帰的に繰り返すことで実現される。

ポイントは、再帰には必ず終了の条件がついて回る点である。この終了条件をベースケース（基底条件）という。

バッカス・ナウア記法では、再帰の表現がよく使われる。同記法が最初に使われたと思しきバッカス氏の論文でも、例示に再帰が含まれていた。この事実だけでも、重要な概念であることが窺い知れる。

ちなみに以下のようなものである。

<ab> ::= (or[or<ab>(or<ab><d>

この例では、[、(、<d>がベースケース、2つの<ab>が再帰ケースである。<d>は10進数を表す。バッカス氏は、<ab>が取り得る値の一部として、以下の4つを挙げている。

[((1(37(
(12345(
(((
[86

むずい。

頭にやさしい再帰の例

たとえば「アタァ」とか「ホアタァ」とか叫んでなにかを殴る人がいたとする。この人物の発声をXと名付け、バッカス・ナウア記法で表すと以下のようになる。

<X> ::= ア | ァ | タ| ホ | <X><X>

Xは、ア、ァ、タ、ホのいずれかの1文字、あるいは <X><X>で作られる。この場合、ア、ァ、タ、ホがベースケースとなる。<X><X>の部分が再帰ケースであり、初見殺しのややこしいポイントである。

簡便のために、以降はア | ァ | タ| ホをYとする。2つの<X>は、どちらもYの中のいずれかの1文字、あるいは<X><X>に置き換えられる。そのため、組み合わせは以下のようになる。

<X><X> ::= Y<X> | <X>Y | YY | <X><X><X>

Yはア、ァ、タ、ホのいずれか1文字であるから、YYは「アア」や「アァ」、「タタ」、「ァホ」、など2文字の組み合わせとなる。

一方、Y<X>、<X>Y、<X><X><X>は再帰ケースである。再び置き換えを行い、ベースケースと再帰ケースを掘り下げていく。

つまり発声Xは、ア、ァ、タ、ホの無限の組み合わせを作る。発声Xというより、発生Xである。

ア
アァタタタタタァホァタァ
ホァタタァタタァタ
ァアホアホアホアホ
...etc

わかりやすい説明を試みたつもりが、余計わかりにくくしてしまった気がする。

もう少し実際的な例

応用情報技術者試験の過去問に、バッカス・ナウア記法の再帰に関するちょうどよい問題があった。

問4 次に示す記述は、BNFで表現されたあるプログラム言語の構文の一部である。
<パラメタ指定>として、適切なものはどれか。

<パラメタ指定> ::= <パラメタ> | (<パラメタ指定>, <パラメタ>)
<パラメタ> ::= <英字> | <パラメタ><英字>
<英字> ::= a | b | c | d | e | f | g | h | i

ア ((abc, def), ghi)
イ ((abc, def))
ウ (abc, (def))
エ (abc)

出典: 平成30年度秋季応用情報技術者試験午前問4

バッカス・ナウア記法は、非終端記号と終端記号を地道に置き換えていけば（あるいはその逆をしていけば）必ず読み解ける。

ただ、このままだと記号記号していて、私の頭がパンクする。やはりX、Yに置き換えて考えてみたい。 <パラメタ指定>は、以下のように置き換えられる。

<X> ::= <Y> | (<X>,<Y>)

<X>は、<Y>か、(<X>,<Y>)のパターンをとる。一見すると非終端記号しかないため、解くのが大変そうである。しかしよくよく見れば、<Y>、つまり<パラメタ>は、英字の繰り返しであることがわかる。これは解答の選択肢からも一目瞭然である。

<Y>は連続する英字であり、それ以上掘り下げる必要はない。

続いて (<X>,<Y>)の再帰パターンを考える。この<X>も、(<X>,<Y>)のパターンをとる。つまり(<Y>,<Y>)か、((<X>,<Y>),<Y>)となる。以降も同様で、次は((<Y>,<Y>),<Y>)あるいは(((<X>,<Y>),<Y>),Y>)となる。

この時点で、<パラメタ指定>に合致するのはアに絞られる。

拡張BNF記法（Extended Backus–Naur form）

オリジナルはシンプルだが、BNFが普及するにつれて悩ましい点が出てきた。繰り返しの表現を書くのが面倒くさい。同じグループの語をわかりやすく示したい、コメントとかも入れたい、などなどである。そのため、より使いやすく改良がなされた。言語っておもしろい、人間ってさいこう。

で、この拡張されたBNF記法は、そのまま拡張BNF記法（Extended Backus–Naur form、略してEBNF）と呼ばれる（なお、正式な定義はISO/IEC 14977:1996でなされている）。

拡張された記法は以下の通りである。

=       ::= の代わり
,       要素を順番に並べるときの区切り
;       1つの定義の終わり
|       選択の区切り
(...)   グループ化
[...]   オプション（0または1回）
{...}   繰り返し（0回以上）
...     文字範囲の指定 (例: 'a'..'z')
""			終端記号1
''			終端記号2
?...?   特殊シーケンス
(*...*) コメント
-       除外記号で

カンマの、要素を順番通りに並べるというのは、"int", space, identifier;のように表現の塊の順序を定義したい時に使う、という意味である。

パイプは選択で、"int" | "float" | "double"のように、いずれかをマッチさせたい時に使う。

また、オプションの[...]は、あってもなくてもよい、という意味である。例えば[ "the" | 'a' ]のようにすると、theとaのいずれかがあってもよいし、別になくてもよい、ということになる。

特殊シーケンス（Special Sequence）は、定義段階では具体的に定められないが、必要なことは確定している表現を定義するために使う。これは、正直よくわからないので推測である。例えばprimitive_value = number | string | ?将来必要になるプリミティブ値?;みたいなこと。だろう。

除外記号の-は、そのまま表現の引き算のように使う。alphabet - "a"とすると、"a"を除外した26文字にマッチする。嘘。もともと26文字だった。25文字にマッチする。

また、BNF/EBNFは、こっちのがよくなくな〜い？的に方言が追加され、市民権を得ているケースが少なくない。代表的な表記としては以下のようなものが挙げられる。

+       1回以上の繰り返し
*       0回以上の繰り返し（{...}の代替表記）
?       オプション（[...]の代替表記）
/       選択（|の代替表記）
->      定義（=の代替表記）
=>      定義（=の代替表記）
<>      非終端記号の囲み。オリジナルと同じ

これらの表現を採用すると、例えば先に示した加減乗除の例は、以下のようにさらに端的に表現できる。

<expression> ::= <term> ( ('+' | '-') <term> )*
<term>    ::= <factor> ( ('*' | '/') <factor> )*
<factor>  ::= <number> | '(' <expression> ')'
<number>  ::= <digit>+
<digit>   ::= '0'..'9'

人間って勝手。