定冠詞文法

確定節文法（DCG ）は、自然言語または形式言語の文法を、 Prologなどの論理プログラミング言語で表現する方法です。これは、属性文法／接辞文法の概念と密接に関連しています。DCGは通常Prologに関連付けられますが、 Mercuryなどの類似の言語にもDCGが含まれています。DCGは、文法を一階述語論理の確定節の集合として表現するため、確定節文法と呼ばれます。

DCGという用語は、Prologやその他の類似言語における特定の表現形式を指します。定冠詞を用いて文法を表現するすべての方法がDCGとみなされるわけではありません。しかし、Prologとほぼ同じ方法で定冠詞を用いて表現される文法であれば、DCGの機能や特性はすべて同じになります。

DCG の確定節は、文の妥当性や特定の構文木を持つという事実がこれらの公理から導かれる定理とみなせる公理の集合と考えることができます。^{[ 1 ]}これにより、言語における式の認識と構文解析が、論理プログラミング言語の文などの一般的なステートメントの証明の問題になるという利点があります。

DCG の歴史は Prolog の歴史と密接に結びついており、Prolog の歴史はフランスのマルセイユとスコットランドのエディンバラの複数の研究者を中心に展開しています。Prologの初期開発者であるRobert Kowalskiによると、最初の Prolog システムは 1972 年にAlain Colmerauerと Phillipe Roussel によって開発されました。^{[ 2 ]}この言語で書かれた最初のプログラムは、大規模な自然言語処理システムでした。エディンバラ大学の Fernando Pereira とDavid Warrenも Prolog の初期開発に関わっていました。

コルメラウアーは以前、英語とフランス語の翻訳に使用される Q システムと呼ばれる言語処理システムに取り組んでいた。^{[ 3 ]} 1978 年、コルメラウアーは、マルセイユ プロログと呼ばれる初期バージョンの Prolog の一部であったメタモルフォーシス文法と呼ばれる文法表現方法に関する論文を書いた。この論文で、彼はメタモルフォーシス文法の形式的な説明と、それを使用するプログラムの例をいくつか示した。

Prolog の初期の設計者である Fernando Pereira と David Warren は、「確定節文法」という用語を作り出し、今日 Prolog で使用されている DCG の表記法を作成しました。彼らは、このアイデアを Colmerauer と Kowalski に帰し、DCG は Colmerauer のメタモルフォーシス文法の特殊なケースであると指摘しています。彼らは、「言語分析のための確定節文法」という記事でこのアイデアを紹介し、DCG を「文法が一階述語論理の節で表現される形式体系」であり、「プログラミング言語 Prolog の有効なプログラムを構成する」ものだと説明しています。^{[ 4 ]}

ペレイラ、ウォーレン、および他の Prolog の先駆者たちは後に DCG の他のいくつかの側面について執筆しました。ペレイラとウォーレンは「演繹としての構文解析」という記事を執筆し、構文解析にアーリー演繹証明手続きがどのように使用されるかなどを説明しています。^{[ 5 ]}ペレイラはまた、スチュアート M. シーバーと共同で「Prolog と自然言語解析」という本を執筆しました。これは論理プログラミングを使用した計算言語学の一般的な入門書となることを意図したものです。 ^{[ 6 ]}

DCGの基本的な例を挙げると、DCGがどのようなもので、どのような外観をしているかが分かりやすくなります。

文-->名詞フレーズ、動詞フレーズ。noun_phrase --> det 、名詞。動詞フレーズ-->動詞、名詞フレーズ。デット--> [ ] 。det --> [ a ]。名詞--> [猫]。名詞--> [コウモリ]。動詞--> [食べる]。

これにより、「猫がコウモリを食べる」、「コウモリが猫を食べる」などの文が生成されます。この文法によって生成される言語の有効な表現はすべて、Prolog インタプリタで と入力することで生成できますsentence(X,[])。同様に、 のような入力で、文がこの言語で有効かどうかをテストできますsentence([the,bat,eats,the,bat],[])。

DCG表記は、Prologにおける通常の確定節に対する単なる構文糖衣です。例えば、前の例は次のように翻訳できます。

文( A 、Z ) :-名詞句( A 、B ) 、動詞句( B 、Z ) 。名詞句( A 、Z ) :-限定詞( A 、B ) 、名詞( B 、Z ) 。動詞句( A 、Z ) :-動詞( A 、B ) 、名詞句( B 、Z ) 。限定詞([ the | X ]、X ) 。限定詞([ a | X ]、X ) 。名詞([ cat | X ]、X ) 。名詞([ bat | X ]、X ) 。動詞([ eats | X ]、X ) 。

A = P + B = P + (Q + Z) = (P + Q) + Z = S + Z = A

純粋な Prologでは、前の例のようにファンクタに追加の引数がない通常の DCG ルールでは、文脈自由文法しか表現できません。これは、生成規則の左辺に引数が 1 つしかないためです。しかし、次の例のように追加の引数を提供することで、文脈依存文法も DCG で表現できます。

s --> a ( N ), b ( N ), c ( N ). a ( 0 ) --> []. a ( M ) --> [ a ], a ( N ), { MはN + 1 }. b ( 0 ) --> []. b ( M ) --> [ b ], b ( N ), { MはN + 1 }. c ( 0 ) --> []. c ( M ) --> [ c ], c ( N ), { MはN + 1 }.

この一連の DCG ルールは、次の形式の文字列で構成される言語を生成する文法を記述します。${\displaystyle a^{n}b^{n}c^{n}}$[ ^{8 ]​}

s -->シンボル( Sem , a )、シンボル( Sem , b )、シンボル( Sem , c )。記号( end 、_ ) --> []。シンボル( s ( Sem ), S ) --> [ S ]、シンボル( Sem , S )。

この一連の DCG ルールは、次の形式の文字列で構成される言語を生成する文法を記述します。${\displaystyle a^{n}b^{n}c^{n}}$nを構造的に表現することによって

さまざまな言語的特徴も、ファンクターに追加の引数を与えることで、DCG でかなり簡潔に表現できます。^{[ 9 ]}例えば、次の DCG ルールセットを考えてみましょう。

文-->代名詞(主語)、動詞句。動詞句-->動詞、代名詞(目的語)。代名詞(主語) --> [彼]。代名詞(主語) --> [彼女]。代名詞(目的語) --> [彼]。代名詞(目的語) --> [彼女]。動詞--> [好き]。

この文法では、「彼は彼女が好きだ」や「彼は彼が好きだ」のような文は許容されるが、 「彼女は彼が好きだ」や「彼は彼が好きだ」のような文は許容されない。

DCGの主な実用的な用途は、与えられた文法の文を解析すること、つまり構文木を構築することです。これは、次の規則のように、DCGのファンクタに「追加の引数」を与えることで実現できます。

文( s ( NP , VP )) -->名詞フレーズ( NP )、動詞フレーズ( VP )。名詞フレーズ( np ( D , N )) --> det ( D )、名詞( N )。動詞フレーズ( vp ( V , NP )) -->動詞( V )、名詞フレーズ( NP )。det ( d (ザ)) --> [ザ]。det ( d ( a )) --> [ a ]。名詞( n (バット)) --> [バット]。名詞( n (猫)) --> [猫]。動詞( v (食べる)) --> [食べる]。

これで、任意の文の構文解析ツリーを取得するために、インタプリタに問い合わせることができるようになった。

| ?- sentence ( Parse_tree , [ the , bat , eats , a , cat ], []). Parse_tree = s ( np ( d ( the ), n ( bat )), vp ( v ( eats ), np ( d ( a ), n ( cat )))) ? ;

DCG は、構文解析アプリケーション以外の場所でコード内の特定のパラメータを隠すための便利な構文糖衣として機能します。宣言的に純粋なプログラミング言語であるMercuryでは、I/O は引数のペアで表現する必要がありますio.state。DCG 表記法を使用すると、I/O の使用がより便利になります^{[ 10 ]}。ただし、通常は状態変数表記法が好まれます^{[ 11 ]} 。DCG 表記法は、Prolog と同様に、Mercury の構文解析や同様のことにも使用されます。

DCG は Pereira と Warren によって導入されて以来、いくつかの拡張が提案されてきました。Pereira 自身は外置文法 (XG) と呼ばれる拡張を提案しました。^{[ 12 ]}この形式は、左外置などの特定の文法現象をより簡単に表現できるようにすることを目的としていました。Pereira は、「XG ルールと DCG ルールの違いは、XG ルールの左辺に複数の記号が含まれる可能性がある点です」と述べています。これにより、文脈依存文法のルールをより簡単に表現できるようになります。

ピーター・ヴァン・ロイは、複数のアキュムレータを可能にするためにDCGを拡張した。^{[ 13 ] [ 14 ]}

もう一つ、より最近の拡張は、NEC株式会社の研究者によって1995年にマルチモーダル確定節文法（MM-DCG）と呼ばれるものが作成されました。彼らの拡張は、画像などの非テキスト部分を含む表現の認識と解析を可能にすることを目的としていました。^{[ 15 ]}

1984 年に Harvey Abramson によって、確定節翻訳文法 (DCTG) と呼ばれる別の拡張が記述されました。^{[ 16 ]} DCTG 表記は DCG 表記と非常によく似ています。主な違いは、ルールで::=の代わりにを使用することです。これは、文法属性を便利に処理するために考案されました。 ^{[ 17 ]} DCTG を通常の Prolog 節に変換する方法は DCG と同様ですが、引数が 2 個ではなく 3 個追加されます。-->

• チョムスキー階層
• 文脈自由文法
• 自然言語処理
• 句構造文法

• 「Prologによる自然言語処理」。 2009年5月26日にオリジナルからアーカイブされました。
• 文脈自由文法とDCG
• 定冠詞文法：もはや構文解析のためだけのものではない
• 言語分析のための定冠詞文法