Web教材一覧アルゴリズム

BNF(形式言語)

学習のポイント

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

キーワード

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


形式言語

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

文脈自由文法の代表的な記法
プログラミング言語の文法を示す言語として代表的なものにBNFがあります。図法にしたものに構文図があります。

BNF

BNFとは
BNF(Backus-Naur Form)とは、プログラミング言語の構文を定義するのに用いられるメタ言語です。ALGOL 60 の文法定義のために考案されました。現在では、BNFを拡張したEBNFが広く用いられ、HTMLやXMLの構文定義、通信プロトコルの定義にも利用されています。
BNFの文法
次のBNFは、数値を定義したものです。
   <数値> ::= <数字列>|<符号><数字列>|<数字列> .<数字列>
   <数字列> ::= <数字>|<数字列><数字>
   <数字> ::= 0|1|2|3|4|5|6|7|8|9
   <符号> ::= +|-
 ここで<数値>や<符号>など< >で囲まれたものは非終端記号であり、0、1、+、.など< >で囲まれていないものは終端記号です。
 そして、「3」「3.14」「-3.14」のように、非終端記号<数値>を終端記号で表すことを「生成する」といいます。また、「.14」「3.14.16」「-2+4」などは生成されないので数値ではありません。
  • 「<○○> ::= △△」は、「○○とは△△の構成になる」という意味です。
  • 「○○|△△」は、「○○または△△のどちらかを選択せよ」の意味です。
  • 「<数字列> ::= <数字>|<数字列><数字>」の<数字列>のように、左辺の記号を右辺に記述することができます。
    「<数字列> ::= <数字>」から、3は数字列です。
    数字列を3、数字を1とすれば、「<数字列> ::= <数字列><数字>」ですから、31は数字列です。
練習問題
○問題
 アとイは次のBNFによる生成規則から生成されるか。
    生成規則  <式>::=C|A<式>B|<式><式>
 ア.ACBAACCBB  イ.CCACAACBB
○解答
「<式>::=C」で生成できる式は,Cだけである。「<式>::=A<式>B」で生成できる式は,A<C>B,A<ACB>B,A<AACBB>Bのように,Cを中央にして前後にAとBが同数個並んだものになる。「<式>::=<式><式>」で生成できる式は,<C><C>,<C><AACBB>,<AACCBB><ACB>のように,式が複数個並んだものになる。
すなわち,1個以上連続したCを中央にして前にAと後にBが同数個並んだ式に分解できれば,この式は生成規則から生成されることになる。
アは,<ACB><AACCBB>と分解されるので,生成された式である。
イは,<CC><AC><AACBB>となるが,<AC>は,「中央にCが1個以上」と「前にAと後にBが同数個」の条件を満足しないので,この生成規則からは生成されない。

構文図

構文図の例
構文図(Syntax Chart)とは、BNFと同じような内容を視覚的に図化するための図法です。
下図は,数値を定義した構造図です。Aの部分では,数値とは数字を繰り返したものと定義しています。324のような数字列が数値になります。Bでは,Aで定義した数値に「+」「-」を付けたものおよび付けないものを数値として拡大定義しています。全体では,小数点を含むものも数値としています。

練習問題
○問題
次の文字列のうち,下の構文図で定義されないものはどれか。

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