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

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

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

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

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

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

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

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

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

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

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

より実践的な例

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

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

なお、*は1回以上の繰り返しを意味する。厳密には、バッカス・ナウア記法に繰り返し表現はない。同記法には、読みやすさを高めるために慣習的な記法がいくつか存在する。*による繰り返し表現は、それらのうちの一つである。

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

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

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

非終端記号と終端記号

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

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

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

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

再帰の考え方

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

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

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

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

<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>)となる。

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

長々とした記事になってしまった。結論として、バッカス・ナウア記法の利点は、簡単な記法を組み合わせて複雑な構文をわかりやすく表現できる点にある。