トップ言語処理入門 > 2.形式言語の構文と意味

2.形式言語の構文と意味

1.形式言語

自然言語: 日本語や英語など、自然に発生したため、厳密な文法に従っていない言語
形式言語: プログラム言語のように、厳格な文法によって生成された言語

チョムスキーの分類

 タイプ  文法     オートマトン       言語例
 0型 句構造文法  チューリングマシン  ―┐
 1型 文脈依存文法 線形有界オートマトン ―┴―自然言語
 2型 文脈自由文法 プッシュダウンオートマトン プログラム言語
 3型 正規文法   有限オートマトン      体系化したコードなど
・オートマトン

オートマトンとは、 形式言語で記述された文を受理するための仮想機械である。 形式言語のタイプ(レベル)により、上のように分類される。 プログラム言語のコンパイラは、理論的にはプッシュダウンオートマトンを基礎にして 設計されている。

有限オートマトン(finite automaton)とは、 有限個の状態と遷移と動作の組み合わせからなる数学的に抽象化された「ふるまいのモデル」である。 通常の有限オートマトンは現在状態と入力信号しかなく、スタックは持たない。 プッシュダウン・オートマトンは有限オートマトンと無限の容量のスタックを組み合せたシステムである。

・句構造文法
単語は書き換え規則にしたがって句(phrase)をつくる。 句は他の単語や句と共にさらに大きな句をつくる。 最終的に文(sentence)と呼ばれる句ができる。この書き換え規則に制限がないのが、0型句構造文法である。
・文脈依存文法
文脈依存文法は、次のような形の生成規則を含む文法である。
xUy → xuy
文脈依存文法では、前後に一定の非終端記号と終端文字から構成される文字列がきたときに、U は u である、 という記述ができる。
・文脈自由文法
全ての生成規則が以下の形式である形式文法のひとつである。
U → u
ここで U は非終端記号であり、u は終端文字と非終端記号から構成される文字列である。
例えば
 「数式とは数字列と演算子からなる」
 「数字列とは、符号、数字の並び、小数点、数字の連続からなる」
 「数字とは、0、1、…、9のいずれかである」
などと定義することにより、 数式の表現方法を厳密に定義できるし、 ある文字列が数式として正しいかどうかを判断できる。
  ここで、定義が必要なもの(数式、演算子、数字など)を非終端記号といい、 0や9など定義を伴わないもの(それ以上分解できないもの)を 終端記号という。 そして、数値を −3.14 とか数式を −2+3.14×5 というように、 非終端記号は最終的には終端記号の並びで表現できる。
 「文脈自由文法」という用語は、前後関係に依存せずに非終端記号を 終端記号に置換できることを意味する。 そして、文脈自由文法によって生成される形式言語を文脈自由言語という。
 ここで、文脈自由文法は構文を定義するだけであり、 演算子や数値がどのような意味を持つのかに関しては、何も示していない。
・文脈自由文法の代表的な記法
プログラミング言語の文法を示す言語として代表的なものにBNFがある。 図法にしたものに構文図がある。
・正規文法

正規文法は全ての正規言語を記述することができ、 そういう意味では有限オートマトンや正規表現 (文字列の集合を一つの文字列で表現する)と等価である。

構文やライブラリに正規表現を備えたプログラミング言語として、 Perl、Java、JavaScript、PHPなどがある。

たとえば、"12:34" のように、二桁の数字二組が ":" で区切られた文字列は JavaScriptの正規表現では /^\d\d:\d\d$/ と表す。 「\d」 は 0〜9の数字を表す。 「^」 は文字列の先頭、「$」は文字列の末尾を表すメタ文字(特別な意味を持たせた文字)である。

2.形式言語の文法

プログラム言語のように、厳格な文法によって生成された言語を形式言語と呼ぶ。 形式言語は、一般に、字句規則・構文規則・意味規則で規定される。
字句規則は、識別子や演算記号、定数といった要素(トークン)の表記法を定め、
構文規則は、文や式の形式を示すものである。
意味規則は、構文の意味を規定するものである。

例えば、算術式に関する文法を定義し、 x = 2 + 10 * 3 から x = 32 を得ることを考えよう。 まず、字句解析によって、プログラムは要素 x, =, 2, +, 10, *, 3 に分解される。

構文解析により、演算子(プログラミング言語では、+, * はもとより、= も演算子と呼ぶ) の優先順位から次のような構文木を得る。

意味解析により、2 + 10 * 3 の演算が行われ、その結果の値(32)が x にセットされる。

3.BNF

字句規則や構文規則は BNF記法で表現されることが多い。

BNF(Backus Naur FormまたはBackus Normal Form)とは、 プログラミング言語の構文を定義するのに用いられるメタ言語(言語を定義するための言語)である。 Backusによって提案され、NaurがALGOL 60 の文法定義に用いた。

現在では、BNFを拡張した様々な拡張BNFが広く用いられ、 プログラミング言語の定義だけでなく、 HTMLやXMLの構文定義、通信プロトコルの定義など幅広い分野で利用されている。

3.1 BNF記法による10進数の定義

次のBNFは、数値(整数)を定義したものである。
   <数値> ::= <数字列>|<符号><数字列>
   <数字列> ::= <数字>|<数字><数字列>
   <数字> ::= 0|1|2|3|4|5|6|7|8|9
   <符号> ::= +|−
 ここで<数値>や<符号>など< >で囲まれたものは非終端記号であり、
 0、1、+ など< >で囲まれていないものは終端記号である。
 そして、3、−314 のように、非終端記号<数値>を終端記号で表すことを 「生成する」という。
 5−3、−2+4 などは生成されないので数値ではない。

3.2 論理式の定義

@ 0と1は論理式である。
A 論理変数 x1,x2,・・・,xn は論理式である。
B もし E が論理式であれば、¬E も論理式である(否定)。
C もし E1 と E2 が論理式であれば、E1 ∨ E2 も論理式である(論理和)。
D もし E1 と E2 が論理式であれば、E1 ∧ E2 も論理式である(論理積)。
E 上の@からDの規則を有限回適用して得られるものだけが論理式である。

上の定義をBNFで記述すると

  <E> ::= 0 | 1 | x1 | x2 | ・・・ | xn | ¬<E> | <E> ∨ <E> | <E> ∧ <E>
となる。ここで、記号 "・・・" はBNFにはないが、数学でよく用いられる記法である。

3.3 四則演算の定義

算術演算の規則はBNFでは次のように表現できる。 ここで、加減乗除演算子は+、−、*、/で表している。 この規則では( )内が先に計算され、*、/が+、−より優先順位が高いことを 正確に反映している。

  <Expr> ::= <Term> | <Expr> + <Term> | <Expr> − <Term> 
  <Term> ::= <Fact> | <Term> * <Fact> | <Term> / <Fact> 
  <Fact> ::= (<Expr>) | 数値 

ここで、::= と | はメタ言語の記号であり、+、−、*、/ は四則演算の演算子である。 このような書き方では、両者の違いが分かりにくいし、 定義する言語にメタ言語の記号 | を演算子として持つ場合、表現できない。 そのため、定義する言語の演算子は例えば '+' のように、引用符で括るなどの記述方法が使われる。 また、定義する言語に現れる予約語(C言語で言えば、int、forなど)も引用符で括る。 そうすれば、メタ変数は < > で括らなくても、予約語と区別できる。 すなわち、この場合、四則演算の構文規則は次のように表される。

  Expr ::= Term | Expr '+' Term | Expr '-' Term 
  Term ::= Fact | Term '*' Fact | Term '/' Fact 
  Fact ::= '(' Expr ')' | 数値 

( )はメタ言語の記号としても使われるが、上の構文規則での ( ) はメタ言語の記号ではなく、 四則演算での記号であることが分かる。 因みに、プログラミング言語の世界では、このような ( ) も演算子と呼ばれる。

4.構文図

構文図(Syntax Chart)とは、BNFと同じような内容を視覚的に表すための図法である。
下図は,数値を定義した構造図である。

Aの部分では,数値とは数字を繰り返したものと定義している。 324のような数字列が数値になる。 Bでは,Aで定義した数値に「+」「−」を付けたものおよび付けないものを 数値として拡大定義している。 全体では,小数点を含むものも数値としている。

練習問題

○問題1 アとイは次の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が同数個」の条件を満足しないので, この生成規則からは生成されない。
○問題2 上の整数規則では 023 とか 00314 も数値となる。 これらを除外するように,規則を改めよ。
○解答
   <数値> ::= <数字列>|<符号><数字列>
   <数字列> ::= 0|<数字>|<数字><数字列>
   <数字> ::= 1|2|3|4|5|6|7|8|9
   <符号> ::= +|−
○問題3 次の文字列のうち,下の構文図で定義されないものはどれか。

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