句構造文法

　いわゆる文法、というか生成文法とかに入る前に、形式的な文法にちょっと慣れてもらおうかと思います。

　形式的な文法は4つのクラスがあります。えーとどっちから書くのがいいのかな。まぁ順番に。

　まず「0型文法」と呼ばれるものがあります。

　ここで終端記号と非終端記号という言葉を導入します。終端記号というは、たとえば、具体的な単語と思ってください。もちろん、実際には具体的な単語ではなく、微妙に抽象化したものを使う場合もあります。ですが、イメージとしては具体的な単語と思ってもらって構いません。

　さて0型文法というのは、こういう規則を認める文法です。

　　α→β (α、βともに終端記号でも非終端記号でもかまわない)

　これは、αとβという一文字で書いていますが、実際にはαγδ→βηζωとかでもかまいません。ただαからβに書き換えるというだけで、αにもβにも何の制限もない文法です。

　これは強力ですが、あまり役に立ちません。どんな書き換えも認めてしまっているので。

　次に「1型文法」、あるいは「文脈依存文法」と呼ばれるものがあります。これで認める規則は0型文法と同じです。ただし、αの長さよりβの方が長いという条件がつくだけです。

　3つめに「2型文法」、あるいは「文脈自由文法」と呼ばれるものがあります。これで認められる書き換え規則は次のようなものです。

　　A→β

　　　ここでAは非終端記号で、βは一個以上の非終端記号あるいは終端記号です

　A→βという書きかた以外にも、もちっと制限がついた書きかたがあったりもします。

　これは使い勝手がいい文法で、プログラミング言語の文法の記述や、コンピュータに自然言語を処理させるさいにもよく使われます。

　ここで、文脈依存文法と文脈自由文法の違いを見てみましょう。というか、なぜ「依存」であり、なぜ「自由」なのかということです。

　簡単に言えば、文脈依存文法では左辺がαであったのに対して文脈自由文法では左辺Aという違いです。

　文脈自由文法では左辺は非終端記号が一つ「A」でした。対して文脈依存文法ではそういう制限はありません。「制限がない」から「自由」と連想されるとちょっと違います。

　例えば文脈依存文法では、AαB→AβBという規則も書けます。この場合、AとBにはさまれているαをβに書き換えるという規則です。αの書き換えが、その前後のAとBに制限を受けています。このAとBに制限を受けるというところが「文脈に依存している」ということになるわけです。

　文脈自由文法では左辺はAなど一文字しか書けません。どういう文字列、あるいは文脈でAが現われようとも、そのAを書き換えることを認めています。文脈に頓着しないという意味で文脈から自由です。

　4つめが「3型文法」とか、「正規文法」と呼ばれるものです。

　　A→αB

　　あるいは

　　A→α

　　　ここでAとBは一つの非終端記号で、αは一つの終端記号です。

　　　A→αは、Bとしてφ(空)を認めればなくても構わないのですが。

　文脈自由文法だと、書き換えで終端記号が出てこなくてもかまわないのですが、正規文法だと書き換えで終端記号が出てこないといけません。(文脈自由文法の書き方にもよりますが。)

　だからなんだという声も聞こえますが。

　「正規表現」という言葉を聞いたことはないでしょうか。ファイルの中の文字列の検索や置換に便利ですよね。プログラミング言語によっては、ここで紹介した正規文法を拡張しているものもありますが、正規表現をどうこうするのに正規文法が使われます。とっても便利です。おそらく意識的に使う文法のクラスとしては正規文法が一番身近なものだと思います。

　ただ、まぁ、使い易いというのは制限の強さという面もあり、正規文法でなんでも片付けるのはちょっと無理があります。

　なお、正規文法だけでというわけではないのですが、sed (stream editor)というツールがあります。sedの文法は面倒っちゃ面倒ですが、単純に書けるようになっている分、わかりにくくなっているだけです。で、sedのスクリプトですが、チューリング完全になっています。つまり、sedでスクリプトで書けるものはなんでも計算できるわけです。単純なものでよければ、機械翻訳のスクリプトもすぐに書けます。このあたりは「項書き換え」みたいな考えを理解していると、そういうスクリプトも書きやすくなります。まぁそれはまたいずれ。

　でもsedで何でも計算できると言っても、それはsedの正規表現以外の部分も寄与しての話です。実際にプログラミング言語や自然言語を扱おうとすると、文脈自由文法が必要になります。

　それと日本語の場合だと、こういう例もあります。

　　「私は本を買った」

　　「本を私は買った」

　文脈自由文法の書きかたにもよるのですが「は」とか「を」とかを反映させようとすると、構成要素は同じこの二つの文について、対応する二つの書き換え規則が必要になります。だいたいの文はもっと長いので、もっと面倒になります。まぁ文法の書きかたの問題でもあるのですが。

　それはそれとして、プログラミング言語の文法はだいたい文脈自由文法で書かれます。なので正規文法と同じくらい、あるいはもっと実はお世話になっているのが文脈自由文法です。

　文脈依存文法以上の方が文脈自由文法よりも強力なのですが、たぶんそんなに使われていないと思います。というのも処理が面倒になるから。

　とは言っても、自然言語を文脈自由文法のクラスだけで書けるのかどうかはまだ不明です。

　そんなこんなでちょっと形式的な文法の話でした。興味をもたれましたら、正規表現とかプログラミング言語の文法の定義とかをそこらへんで検索して眺めてもらうといいかもしれません。