17

チョムスキー タイプ 2 (文脈自由言語) とチョムスキー タイプ 3 (正規言語) の違いをうまく説明できません。

誰かが平易な英語で答えてくれませんか? 階層全体を理解するのに苦労しています。

4

3 に答える 3

25

タイプ II 文法は、スタックを持つタイプ III 文法です。

タイプ II 文法は、基本的に入れ子を持つタイプ III 文法です。

タイプ III 文法 (通常):

ユースケース - CSV (カンマ区切り値)

特徴:

  • FSM (Finite State Machine) を使用して読み取ることができます
  • 中間ストレージを必要としない
  • 正規表現で読める
  • 通常、1D または 2D データ構造を使用して表現される
  • フラットであり、入れ子や再帰的なプロパティがないことを意味します

元：

this,is,,"an "" example",\r\n
"of, a",type,"III\n",grammar\r\n

上記のテキストのすべてのルールとエッジ ケースを理解できる限り、CSV を解析できます。

タイプ II 文法 (文脈自由):

ユース ケース - HTML (ハイパー テキスト マークアップ言語) または SGML 全般

特徴:

  • DPDA (Deterministic Pushdown Automata) を使用して読み取ることができます
  • 中間ストレージ用のスタックが必要になります
  • AST (Abstract Syntax Tree) として表現できます。
  • ネストおよび/または再帰プロパティを含む場合があります

HTML は通常の文法として表現できます。

<h1>Useless Example</h1>
<p>Some stuff written here</p>
<p>Isn't this fun</p>

しかし、FSM を使用してこれを解析してみます。

<body>
  <div id=titlebar>
    <h1>XHTML 1.0</h1>
    <h2>W3C's failed attempt to enforce HTML as a context-free language</h2>
  </div>
  <p>Back when the web was still pretty boring, the W3C attempted to standardize away the quirkiness of HTML by introducing a strict specification</p
  <p>Unfortunately, everybody ignored it.</p>
</body>

違いを見ます？パーサーを作成していると想像してください。開始タグで開始し、終了タグで終了できますが、終了タグに到達する前に 2 番目の開始タグに遭遇するとどうなりますか?

簡単です。最初の開始タグをスタックにプッシュし、2 番目のタグの解析を開始します。存在するネスティングのレベルの数だけこのプロセスを繰り返します。構文が適切に構造化されている場合、スタックは、構築された反対のレベルで一度に 1 レイヤーずつ展開できます。

「純粋な」文脈自由言語の厳密な性質により、プログラムによって生成されない限り、それらは比較的まれです。JSON がその代表的な例です。

文脈自由言語の利点は、非常に表現力が豊かでありながら、解析が比較的簡単なことです。

しかし、ちょっと待ってください。HTML はコンテキストフリーであると言っただけではありませんか。はい、整形式 (つまり、XHTML) であれば問題ありません。

XHTML はコンテキストフリーと見なされる場合がありますが、より緩やかに定義された HTML は、実際にはタイプ I (つまり、コンテキスト依存) と見なされます。その理由は、パーサーが構造化されていないコードに到達すると、周囲のコンテキストに基づいてコードを解釈する方法を実際に決定するためです。たとえば、要素に終了タグがない場合、終了タグを配置する場所を決定する前に、その要素が階層内のどこに存在するかを決定する必要があります。

コンテキストフリー言語をコンテキスト依存にするその他の機能には、テンプレート、インポート、プリプロセッサ、マクロなどがあります。

要するに、文脈依存言語は文脈自由言語によく似ていますが、文脈依存言語の要素はプログラムの状態に応じて異なる方法で解釈される場合があります。

免責事項: 私は CompSci の正式な訓練を受けていないため、この回答には誤りや仮定が含まれている可能性があります。ターミナルと非ターミナルの違いを私に尋ねたら、あなたは自分自身をぼんやりと見つめるでしょう。Type III (レギュラー) パーサーを実際に構築し、残りの部分について詳しく読むことで、これについて多くのことを学びました。

于 2013-01-08T03:18:56.423 に答える
6

ウィキペディアのページには、良い写真と箇条書きがあります。

大まかに言えば、通常の言語を記述できる基盤となるマシンはメモリを必要としません。入力でステートマシン (DFA/NFA) として実行されます。正規言語は正規表現でも表現できます。

「次の」レベルの複雑さが追加された言語は、文脈自由言語です。この種の言語を記述する基盤となるマシンは、文脈に依存せず規則的ではない言語を表現できるように、ある程度のメモリを必要とします。マシンにメモリを追加すると、マシンがもう少し強力になることに注意してください。そのため、最初はメモリを必要としなかった言語 (通常の言語など) を引き続き表現できます。基礎となるマシンは通常、プッシュダウン オートマトンです。

于 2012-07-18T20:15:49.430 に答える
5

タイプ 3 文法は、一連の状態で構成されます。埋め込みを表現できません。たとえば、タイプ 3 の文法では、かっこで内容を「囲む」必要があることを示す方法がないため、一致するかっこを必要とすることはできません。これは、Derek が指摘しているように、タイプ 3 文法は、現在の状態に到達するために通過した以前の状態について何も「記憶」していないためです。

タイプ 2 文法は、他のプロダクションを組み込むことができる一連の「プロダクション」 (パターンと考えることができます) で構成されます。したがって、それらは再帰的に定義されます。プロダクションは、含まれているものに関してのみ定義でき、それ自体の外側を「見る」ことはできません。これが文法を文脈自由にするものです。

于 2012-07-18T20:27:11.843 に答える