構文規則を表現するBN記法

構文規則を表現するBN記法

表記法の由来

書き方の決まりを書き表す方法の一つに、ビーエヌ記法というものがあります。これは、バッカス・ナウア記法を短くした呼び名です。一体どのようなものなのでしょうか。

ビーエヌ記法は、プログラムの言葉や、文章の書き方の決まりを書き表すための、特別な書き表し方です。例えるなら、設計図を書くための言葉のようなものです。この書き表し方は、ジョン・バッカスさんとピーター・ナウアさんという二人の研究者によって考え出されました。

二人は、アルゴル６０というプログラムの言葉の書き方の決まりを明らかにするために、このビーエヌ記法を作りました。ビーエヌ記法を使うと、書き方の決まりを、分かりやすく、簡潔に書き表すことができます。ですから、プログラムの言葉を作る時や、その言葉を使ってプログラムを作る道具を作る時に、ビーエヌ記法はとても役に立ちます。

ビーエヌ記法の影響は、その後作られたたくさんのプログラムの言葉や、文章の書き方の決まりにも見られます。ビーエヌ記法のおかげで、言葉を作る人は、より厳密な書き方の決まりを定めることができるようになりました。また、プログラムを書く人は、その言葉の仕組みを正確に理解することができるようになりました。

さらに、プログラムを作る道具を作る人は、ビーエヌ記法に基づいて、プログラムの書き方の決まりをチェックする部分を、より効率的に作ることができるようになりました。このように、ビーエヌ記法は、情報処理の分野で欠かせないものとなっているのです。

基本的な構成要素

ビーエヌ記法は、幾つかの基本的な記号を組み合わせて文の書き方の規則を表現する方法です。この記法は、プログラムの言葉の並び方の規則などを明確に示すために使われます。

まず、「=」という記号は、「～として定義される」という意味です。例えば、「りんご = 赤い丸い果物」と書けば、「りんご」は「赤い丸い果物」として定義されるという意味になります。これは、文の書き方の規則を定義するときに使われます。

次に、「< >」（山括弧）は、まだ細かく分けられる要素を囲む記号です。例えば、「<果物>」と書けば、「果物」という要素は、さらに「りんご」や「みかん」など、具体的なものに分けられることを示します。このような、まだ細かく分けられる要素のことを、非終端要素と言います。

一方で、それ以上細かく分けられない要素もあります。例えば、「赤い」や「丸い」といった言葉は、それ以上分解できません。このような要素は、終端要素と呼ばれ、場合によっては「’赤い’」のように引用符で囲んで表されます。

また、「|」という記号は、「または」という意味です。例えば、「<果物> = りんご | みかん」と書けば、「果物」は「りんご」または「みかん」であることを示します。つまり、複数の選択肢がある場合にこの記号を使います。

これらの記号を組み合わせることで、複雑な文の書き方の規則も表現できます。例えば、「<文> = <主語> <述語>」という規則は、「文」は「主語」と「述語」という二つの要素でできていることを示しています。このように、ビーエヌ記法は、少ない記号で様々な文の書き方の規則を表現できる、便利な方法です。

実際の使用例

ある物事の書き表し方を定めた規則を、実際に使ってみましょう。ここでは、整数を足し算で繋げた式を、例として取り上げます。この式の書き方を、次のように定めます。「式」は「整数」か、「式」に「+」と「整数」を繋げたものになります。「整数」は「数字」か、「整数」に「数字」を繋げたものになります。「数字」は０から９までのどれかになります。

これらの規則に従うと、どのような式が作れるのか見てみましょう。まず、「数字」は０から９までのどれかです。例えば、１や２、３などが「数字」として使えます。次に「整数」は「数字」を繋げたものなので、１や１２、１２３などが「整数」となります。最後に、「式」は「整数」を「＋」で繋げたものです。よって、１＋２＋３や１２３＋４５などが正しい「式」となります。

このように、規則を順々に適用していくことで、正しい式かどうかを判断できます。これらの規則を図で表すと、木の枝のように広がっていくことから、木構造と呼ばれる形になります。この木構造は、式を分解していく過程を表しています。例えば、１＋２＋３という式は、まず１＋２と３に分解できます。さらに１＋２は、１と２に分解できます。このように、式を分解していくことで、最終的に「数字」にたどり着きます。

この書き表し方の規則は、様々な場面で使われています。例えば、日本語の文章も、単語や句、節などを組み合わせて作られています。これらの組み合わせ方は、文法という規則によって定められています。プログラミング言語も同様に、特定の規則に従ってプログラムが書かれています。これらの規則を理解することで、正しく文章を書いたり、プログラムを作成したりすることができます。今回示した例は、一見単純な足し算の式ですが、このような規則を定めることで、複雑な構造を持つ式も表現できるようになります。

拡張BN記法について

拡張バッカス・ナウア記法（拡張BN記法）は、基本的なバッカス・ナウア記法をより使いやすく改良したものです。拡張BN記法は、EBNFとも呼ばれ、もとのBN記法よりも簡潔で、読みやすい構文規則を記述できます。

拡張BN記法には、繰り返しや選択といった表現方法が追加されています。例えば、角括弧「[ ]」を使うと、その中身が省略可能であることを示せます。「名前 [敬称]」のように書けば、「名前」の後に「敬称」を付けても付けなくてもよい、という意味になります。

また、波括弧「{ }」を使うと、その中身の繰り返しを表現できます。「{数字}」と書けば、「数字」が一つ以上連続していることを意味します。例えば、「数列 { , 数列 }」と書けば、「数列」の後に「,（読点）」と別の「数列」を続けていくことができ、全体として複数の数列が読点で区切られて並んでいることを示せます。

丸括弧「( )」は、複数の要素をまとめて一つのグループとして扱うために使います。例えば、「(氏名 | 住所)」と書けば、「氏名」か「住所」のどちらか一方を選ぶことを意味します。

これらの記号を使うことで、複雑な構文規則も簡潔に表現できます。例えば、「整数 = {数字}」は、「整数」は「数字」の繰り返しで構成されることを示しています。これは、もとのBN記法で「整数 = 数字 | 整数 数字」と書いていたものと同じ意味です。つまり、数字が一つだけでも整数ですし、複数の数字が続いていても整数である、ということを簡潔に表現できます。

このように拡張BN記法は、簡潔で表現力が高いことから、様々な場面で活用されています。

他の記法との関連性

ベーカス・ナウア記法（BN記法）は、他の形式言語の記述方法と密接な関係があります。この記法を学ぶことで、他の記法の理解も深まります。

まず、構文図との関連性をみていきましょう。構文図は、プログラミング言語などの文法規則を図を使って視覚的に表現する方法です。BN記法のように記号を用いる代わりに、図形と矢印を用いて規則を表します。例えば、四角は要素を表し、丸は選択肢を表し、矢印は流れを表します。このように視覚的に表現することで、複雑な文法規則も直感的に把握しやすくなります。BN記法と構文図は、どちらも形式言語を明確に記述することを目的としており、表現方法は違えど、互いに補完し合う関係にあると言えるでしょう。

次に、正規表現との関連性について説明します。正規表現は、文字列のパターンを表現するための簡潔な記法です。特定の文字列の検索や置換など、文字列処理に広く活用されています。例えば、「*」は直前の文字の０回以上の繰り返しを、「+」は１回以上の繰り返しを表します。「｜」は「または」を表します。これらの記号を組み合わせることで、複雑な文字列パターンを簡潔に表現できます。正規表現は、BN記法のように明確な規則に基づいて定義されており、文字列の集合を表現するという点で共通しています。BN記法で表現される構文規則の一部は、正規表現を用いて記述することも可能です。

このように、BN記法は、構文図や正規表現といった他の形式言語の記述方法と関連しています。これらの記法を学ぶことで、形式言語への理解がより深まり、プログラムの設計や開発に役立てることができるでしょう。

まとめ

形式言語の文法を定義するための簡潔な手段として、バッカス・ナウア記法、略してBN記法があります。これは、プログラミング言語をはじめ、様々な形式言語の構造を記述する際に広く使われています。BN記法を用いることで、言語の設計者は構文規則を明確かつ簡潔に表現でき、プログラマーは言語の構造を正確に理解することができます。また、コンパイラやインタプリタといった処理系の実装者にとっても、BN記法は仕様を理解し実装する上で欠かせないツールとなっています。

BN記法の基本的な要素は、定義したい要素を表す名前と、その要素を構成する記号列からなります。例えば、整数を表す要素を定義する場合、「整数 = 数字の並び」のように記述します。ここで、「=」は「～で定義される」という意味で、右辺の「数字の並び」は具体的な記号列を表します。

BN記法には、選択や繰り返しといった表現のための拡張記法も用意されています。例えば、「｜」記号を使うことで、複数の選択肢を表現できます。例えば、「式 = 整数 ｜ 実数」のように記述することで、「式」は「整数」または「実数」のいずれかであることを示せます。また、「｛｝」記号を使うことで、要素の繰り返しを表現できます。例えば、「数字の並び = 数字 ｛ 数字 ｝」のように記述することで、「数字の並び」は1つ以上の数字からなることを示せます。

BN記法を理解することは、構文図や正規表現といった関連する記法を理解する上でも役立ちます。構文図は、図形を使って構文規則を視覚的に表現したものであり、正規表現は文字列のパターンを表現するための記法です。これらの記法は、BN記法と密接に関連しており、互いに補完し合う関係にあります。

情報処理の分野において、BN記法は重要な役割を担っています。プログラミング言語やマークアップ言語など、様々な形式言語の構文規則を記述するために、BN記法は欠かせないツールです。新しい言語が登場するたびに、BN記法はその構文規則を明確に表現するために活用され続けるでしょう。プログラミングや情報科学を学ぶ上で、BN記法の理解は不可欠と言えるでしょう。