6

文脈依存の文法を理解しようとしていて、言語が

  1. {ww | w は文字列です}
  2. {a n b n c n | a、b、cは記号です}

文脈自由ではありませんが、型指定されていないラムダ計算に似た言語が文脈依存であるかどうかを知りたいです。単純だがおもちゃではない例 (上記のおもちゃの例を考えます) の例を見てみたいと思います。たとえば、記号の文字列がは現在スコープ内にあります (たとえば、関数の本体を生成する場合)。文脈依存文法は、未定義/未宣言/未結合の変数を (セマンティックではなく) 構文エラーにするのに十分強力ですか?

4

1 に答える 1

10

はい、状況依存文法（CSG）は、未定義/未宣言/非バインド変数をチェックするのに十分強力ですが、残念ながら、CSGの文字列を解析するための効率的なアルゴリズムはわかりません。

状況依存言語の実際の例は、Cプログラミング言語です。最初に変数を宣言し、後でそれらを使用するような機能により、C言語は状況依存言語（CSL）になります。（型なしラムダ計算についてはわかりません）。

また、CSL（またはCSG）の線形解析アルゴリズムがわからないためです。これがコンパイラ設計の理由です。CFGを解析するための効率的なアルゴリズムがわかっているため（制限された形式の場合）、構文チェックにCFG（およびその解析アルゴリズムのみ）を使用します。コンパイラは、最初に文脈自由機能を解析し、その後、問題のある方法で状況依存機能を処理します（たとえば、シンボルテーブルで使用されている変数が定義されているかどうかを確認します。定義されていない場合は、エラーが発生します）。

また、状況依存文法は自然言語処理（NLP）で使用されます。そして、ほとんどの自然言語は文脈依存言語の例です。（サンスクリット語についてはよくわかりません）。

私はそれをばかげているが単純な例で説明しようとします（それは単なるアイデアです、あなたはそれを洗練することができます）：

NOUN     -->  { BlueBomber, Grijesh, I, We}
TENSE    -->  { am, was, is, were}
VERB     -->  { going, eating, working}

SENTENCE --> <NOUN> <TENSE> <VERB>

さて、この文法を使用して、いくつかの正しいステートメントを生成できますが、いくつかは間違っています。例えば、

SENTENCE --> <NOUN>   <TENSE>   <VERB>
             Grijesh    is       working       [Correct statement]

だが

             Grijesh    am       working       [wrong statement]

理由：<TENSE>の値は値<NOUN>（たとえばI <TENSE> --> I am）に依存するため、文法は英語で正しいステートメントを生成しません。

実際、完全な英語の文脈自由文法を書くことはできません！

お気づきかもしれませんが、自然言語の翻訳者や文法チェッカーは正しく機能しません（長いステートメントで試してください）。この問題は、状況依存の解析アルゴリズムの下にあるためです。

参考：アルン・クマール博士の講演をご覧いただけます。 いくつかの講義で、彼はあなたが何に興味を持っているかを正確に説明しています。

于 2012-12-31T08:39:44.517 に答える