ＢＮＦ（形式言語）

学習のポイント

プログラミング言語の設計をするには文法を明確にするには、それを定義する形式言語が必要になります。ここでは、形式言語の代表例であるＢＮＦとその周辺について学習します。

キーワード

形式言語、文脈自由文法、ＢＮＦ、生成規則、構文図

形式言語

自然言語と形式言語: 日本語や英語など、自然に発生したため、必ずしも文法に従っていない言語を自然言語といいます。それに対して、プログラム言語のように、厳格な文法によって生成された言語を形式言語といいます。
　チョムスキーは，言語を文法に従うレベルにより、次の４つに区分しました。
　　タイプ　文法　　　　　オートマトン　　　　　　　　言語例
　　　０型　　句構造文法　　チューリングマシン　　　　┐
　　　１型　　文脈依存文法　線形有界オートマトン　　　┴自然言語
　　　２型　　文脈自由文法　プッシュダウンオートマトン　プログラム言語
　　　３型　　正規文法　　　有限オートマトン　　　　　　体系化したコードなど
オートマトン: オートマトンとは、形式言語で記述された文を受理するための仮想機械です。形式言語のタイプにより、上のように分類されます。プログラム言語のコンパイラは、理論的にはプッシュダウンオートマトンを基礎にして設計されています。
文脈自由文法: 例えば「数式とは数字列と演算子からなる」「数字列とは、符号、数字の並び、小数点、数字の連続からなる」「数字とは、０、１、…、９のいずれかである」などと定義することにより、数式の表現方法を厳密に定義できますし（この例示は厳密ではない）、ある文字列が数式として正しいかどうかを判断することができます。
　ここで、定義が必要なもの（数式、演算子、数字など）を非終端記号といい、０や９など定義を伴わないもの（それ以上分解できないもの）を終端記号といいます。そして、数値を「－３．１４」とか数式を「－２＋３．１４×５」というように、非終端記号は最終的には終端記号の並びで表現できます。
　「文脈自由」という用語は、前後関係に依存せずに非終端記号を終端記号に置換できることを意味しています。そして、文脈自由文法によって生成される形式言語を文脈自由言語といいます。
　ここで、文脈自由文法は構文を定義するだけであり、演算子や数値がどのような意味を持つのかに関しては、何も示していないことに留意してください。
文脈自由文法の代表的な記法: プログラミング言語の文法を示す言語として代表的なものにＢＮＦがあります。図法にしたものに構文図があります。

ＢＮＦ

ＢＮＦとは

ＢＮＦ（Backus-Naur Form）とは、プログラミング言語の構文を定義するのに用いられるメタ言語です。ALGOL 60 の文法定義のために考案されました。現在では、ＢＮＦを拡張したＥＢＮＦが広く用いられ、ＨＴＭＬやＸＭＬの構文定義、通信プロトコルの定義にも利用されています。

ＢＮＦの文法

次のＢＮＦは、数値を定義したものです。
　　　＜数値＞ ::＝＜数字列＞｜＜符号＞＜数字列＞｜＜数字列＞．＜数字列＞
　　　＜数字列＞ ::＝＜数字＞｜＜数字列＞＜数字＞
　　　＜数字＞ ::＝０｜１｜２｜３｜４｜５｜６｜７｜８｜９
　　　＜符号＞ ::＝＋｜－
　ここで＜数値＞や＜符号＞など＜　＞で囲まれたものは非終端記号であり、０、１、＋、．など＜　＞で囲まれていないものは終端記号です。
　そして、「３」「３．１４」「－３.１４」のように、非終端記号＜数値＞を終端記号で表すことを「生成する」といいます。また、「．１４」「３.１４．１６」「－２＋４」などは生成されないので数値ではありません。

「＜○○＞ ::＝ △△」は、「○○とは△△の構成になる」という意味です。
「○○｜△△」は、「○○または△△のどちらかを選択せよ」の意味です。
「＜数字列＞ ::＝＜数字＞｜＜数字列＞＜数字＞」の＜数字列＞のように、左辺の記号を右辺に記述することができます。
「＜数字列＞ ::＝＜数字＞」から、３は数字列です。
数字列を３、数字を１とすれば、「＜数字列＞ ::＝＜数字列＞＜数字＞」ですから、３１は数字列です。

練習問題

○問題
　アとイは次のＢＮＦによる生成規則から生成されるか。
　　　　生成規則　　<式>::＝Ｃ｜Ａ<式>Ｂ｜<式><式>
　ア．ＡＣＢＡＡＣＣＢＢ　　イ．ＣＣＡＣＡＡＣＢＢ
○解答
「<式>::＝Ｃ」で生成できる式は，Ｃだけである。「<式>::＝Ａ<式>Ｂ」で生成できる式は，Ａ<Ｃ>Ｂ，Ａ<ＡＣＢ>Ｂ，Ａ<ＡＡＣＢＢ>Ｂのように，Ｃを中央にして前後にＡとＢが同数個並んだものになる。「<式>::＝<式><式>」で生成できる式は，<Ｃ><Ｃ>，<Ｃ><ＡＡＣＢＢ>，<ＡＡＣＣＢＢ><ＡＣＢ>のように，式が複数個並んだものになる。
すなわち，１個以上連続したＣを中央にして前にＡと後にＢが同数個並んだ式に分解できれば，この式は生成規則から生成されることになる。
アは，<ＡＣＢ><ＡＡＣＣＢＢ>と分解されるので，生成された式である。
イは，<ＣＣ><ＡＣ><ＡＡＣＢＢ>となるが，<ＡＣ>は，「中央にＣが１個以上」と「前にＡと後にＢが同数個」の条件を満足しないので，この生成規則からは生成されない。

構文図

構文図の例: 構文図（Syntax Chart）とは、ＢＮＦと同じような内容を視覚的に図化するための図法です。
下図は，数値を定義した構造図です。Ａの部分では，数値とは数字を繰り返したものと定義しています。３２４のような数字列が数値になります。Ｂでは，Ａで定義した数値に「＋」「－」を付けたものおよび付けないものを数値として拡大定義しています。全体では，小数点を含むものも数値としています。
練習問題: ○問題
次の文字列のうち，下の構文図で定義されないものはどれか。

　ア　ａ　　　イ　ａｂ　　　ウ　ｂａ　　　エ　ａａａ
○解答
　構文図の左の部分は，文字列の先頭がａが０個以上並ぶことを示しており，右の部分は，その後にａかｂが１つあることを示している。従ってウがこの定義に合致しません。