BNF記法：プログラム言語の設計図

BNF記法：プログラム言語の設計図

記法の由来

「バッカス・ナウア記法」は、略して「ビーエヌエフ記法」と呼ばれ、プログラムを書き表す言葉の文法をきちんと決めるための特別な書き方です。この名前は、この書き方を考えたジョン・バッカスさんとピーター・ナウアさんにちなんで付けられました。バッカスさんは「アルゴル」というプログラムの言葉を作ることに携わっていました。ナウアさんは、バッカスさんの考え方を発展させて、「アルゴル６０」という言葉の文法を書き表すのに使いました。

この書き方を使うと、プログラムの言葉の規則を分かりやすく、簡潔に書き表すことができます。そのため、プログラムを機械の言葉に翻訳する「翻訳機」や、プログラムを直接実行する「実行機」を作るのに欠かせない道具となっています。私たち人間が使う言葉では、あいまいな表現がよくありますが、この書き方を使うことで、機械が理解できるはっきりとした規則を作ることができます。これにより、プログラムの言葉の設計と、実際に使えるようにすることが大きく変わりました。

ビーエヌエフ記法は、ただの書き方ではありません。プログラムの言葉の設計の考え方を具体的にしたものなのです。その影響は、今の計算機科学に深く関わっています。言葉の構造をはっきりさせることで、プログラムを作る人がその言葉を理解しやすくなるだけでなく、翻訳機を作る作業も簡単になりました。ビーエヌエフ記法は、プログラムを作る人にとって分かりやすいだけでなく、機械にとっても分かりやすい言葉を作るための重要な役割を果たしているのです。

記法の構成要素

文法を表現するための方法であるビーエヌエフ記法は、いくつかの基本的な部品を組み合わせて複雑な規則を記述します。大きく分けて、何を定義するかを示す部分、どのように定義するかを示す部分、そしてこれらを結びつける記号の三種類の部品から成り立っています。

まず、何を定義するかを示す部分は、プログラムの部品を表す名前です。例えば、プログラムの中で使われる「変数」や計算を行う「式」など、プログラムを構成する様々な要素がこれにあたります。具体的な例として「変数」という要素を定義したい場合は、「変数」という名前を用います。

次に、どのように定義するかを示す部分は、具体的な定義の内容を表します。例えば、「変数」は「英字」で始まり、その後に「英数字」が続く、といったように定義します。この部分は、定義される要素がどのような規則で構成されるのかを示す役割を果たします。

最後に、これらの部品を結びつける記号として、「＝」や「｜」といった記号が使われます。「＝」という記号は、「左側の要素は右側の内容で定義される」という意味を表します。例えば、「変数 ＝ 英字」と書けば、「変数」は「英字」で定義されるという意味になります。また、「｜」という記号は「または」という意味を表し、複数の選択肢がある場合に使用します。例えば、「変数 ＝ 英字 ｜ 変数 英数字」と書けば、「変数」は「英字」または「変数」の後に「英数字」が続くもので定義される、つまり「英字」で始まり「英数字」が続くものと定義できます。

このように、ビーエヌエフ記法では、限られた種類の記号を用いて複雑な文法規則を表現できます。例えば、整数を「数字」または「整数」の後に「数字」が続くものと定義することで、再帰的な定義も可能です。これは「整数 ＝ 数字 ｜ 整数 数字」と書けます。このような再帰的な定義も、ビーエヌエフ記法の重要な特徴の一つです。

実際の例

たとえば、整数を足し合わせる計算式を規則として書き表してみましょう。この書き表し方の方法を「バッカス・ナウア記法」といいます。この記法では「式 = 整数 ‘+’ 整数」のように表します。これは「式」というものは、「整数」と「+」という記号、そしてもう一つの「整数」を組み合わせたものという意味です。ここで「=」は「～で定義される」という意味で使われます。さらに「整数」自身は数字がいくつか並んだものと考えることができます。そして、「数字」は０から９までのいずれかの文字で表されます。

このように、バッカス・ナウア記法を使うと、複雑な文の組み立て方を段階的に分けて、わかりやすく書き表すことができます。この足し算の例はとても単純ですが、実際のプログラムを動かす言葉では、色々なものが複雑に組み合わさっています。例えば、箱の中に値を入れておく「変数」、計算を行うための「演算子」、計算の順番を操作する「制御構造」などです。

バッカス・ナウア記法を使うことで、これらの要素を整理して、厳密な定義を与えることができます。これはプログラムを動かす言葉の設計や、実際にコンピュータで動くようにする作業の支えとなっています。たとえば、皆さんが普段使っているアプリや、見ているウェブサイトの裏側では、このバッカス・ナウア記法を元にして作られたプログラムが動いているのです。一見単純な計算式でさえ、バッカス・ナウア記法で厳密に定義することで、コンピュータが正しく理解し、実行できるようになります。このようにバッカス・ナウア記法は、私たちがコンピュータとやりとりする上で、なくてはならない重要な役割を担っているのです。

拡張BNF記法

拡張バッカス・ナウア記法（ＥＢＮＦ）は、バッカス・ナウア記法（ＢＮＦ）を土台として、より多くの表現ができるようにした記法です。ＢＮＦで文法を記述する際には、繰り返しや任意の要素の記述が複雑になりがちでしたが、ＥＢＮＦでは、これらの表現を簡潔に記述するための工夫が凝らされています。

例えば、ある要素が何回も繰り返されることを表す場合、ＢＮＦでは同じ記述を何度も繰り返す必要がありました。しかし、ＥＢＮＦでは「＊」という記号を使うことで、「０回以上の繰り返し」を簡単に表現できます。同様に、「＋」という記号は「１回以上の繰り返し」を、「［］」という記号は「あってもなくてもよい要素」を表します。これらの記号のおかげで、複雑な文法規則をコンパクトに記述できるようになりました。

具体例として、プログラムの中で名前として使われる「識別子」を考えてみましょう。識別子は、一般的に、先頭は英字で始まり、その後ろには英字、数字、または記号「＿」が続きます。これをＢＮＦで記述しようとすると、非常に複雑な表現になってしまいます。しかし、ＥＢＮＦを使えば、「識別子 = 英字 ｛ 英数字 | ‘＿’ ｝」のように簡潔に記述できます。これは、「識別子は英字で始まり、その後に英数字または「＿」が０回以上続く」という意味です。

このように、ＥＢＮＦはＢＮＦの表現力を高め、より実用的な文法記述を可能にしています。ＥＢＮＦは、様々なプログラム言語の文法を記述する際に広く使われており、現代のプログラム言語開発においてなくてはならないものとなっています。

記法の意義と影響

計算機に指示を出すための言葉、つまりプログラムを書き記すための規則を定めたものを、プログラム言語と言います。そのプログラム言語を作る際に、どのような単語や文の並び方が正しいのかを、厳密に書き表す方法が必要です。そこで登場したのが、「バッカス・ナウア記法」と呼ばれる、プログラム言語を記述するための方法です。

この記法が登場する以前は、プログラム言語の書き方は、普段私たちが使っている言葉で説明されていました。しかし、普段使っている言葉では、どうしても意味があいまいになってしまうことがあります。そこで、数学のように厳密な記号を用いることで、プログラム言語の構造を明確に表現できるようになりました。

この厳密な表現のおかげで、プログラム言語を理解し、実行するプログラムを作るのが、以前よりもずっと簡単になりました。プログラムを作る道具を「翻訳機」や「実行機」と呼ぶならば、バッカス・ナウア記法は、高性能な翻訳機や実行機を作るための設計図のようなものです。設計図が正確であれば、翻訳機や実行機も正確に動作し、プログラムの間違いを減らし、異なる種類の計算機でも同じように動くプログラムを作ることが容易になります。

バッカス・ナウア記法は、プログラム言語の研究にも大きく役立ちました。プログラム言語が持つ、文章としての構造や意味を研究する分野に、大きな進歩をもたらしました。プログラムの文法を分析したり、意味を理解したりする研究に、なくてはならない道具となったのです。

バッカス・ナウア記法は、単なる書き方の提案ではなく、プログラム言語の設計そのものを大きく変えました。そして、現代の計算機科学において、バッカス・ナウア記法とその仲間たちは、プログラム言語を作る上で欠かせない道具として広く使われています。この記法の影響は、これからのプログラム言語の発展にも、間違いなく続いていくでしょう。