1

ご存知のように、DFA を使用して通常の言語で文字列を検証できます。

例 1. L=ac(b)*bcb|ad(b)*bb. 文字列「acbbbcb」は、DFA によって正しいと検証できます。

また、正規言語をCFGで表現できる場合もあります。

例 2。

  • S -> "a" A "b"
  • A -> "c" B "c" | "d" B
  • B -> "b" B | 「ば」

上記の CFG によって生成される言語は、例 1 の正規表現にすぎません。

つまり、DFA を使用して、この CFG によって生成された (通常の) 文字列を検証できます。しかし、どうすれば対応する構文木を生成できるでしょうか?

4

2 に答える 2

1

すべての正規言語には CFG があります。

DFA は受け入れ/拒否以外の出力を持たないため、厳密に言えば解析ツリーを構築することはできません。ただし、ツリー生成の副作用で拡張できる言語ごとに少なくともいくつかの DFA を持たない理由がわかりません (文法が明確であると仮定して)。これには、DFA が文法の構造を反映するように構築されている必要がある可能性が高いため、必ずしも最小であるとは限りません。

文法があいまいな場合、Gunther が書いているように、DFA はおそらくツリー構築の目的には十分ではありません。

于 2012-05-09T12:26:53.983 に答える
0
  • S -> "a" A "b"
  • A -> "c" B "c" | "d" B
  • B -> "b" B | 「ば」

これは次の方法で達成できると思います。

数ページの紙があると想像してください。紙の各ページには、生産ルールがあります。そして一番上の紙はルール S -> "a" A "b" を持っています。そして、2 つの遷移があります。1 つは「A」から次の紙のページへ、もう 1 つは次の紙のページからこの「A」へです。

このスキームでは、次のページから現在のページへの戻り遷移が発生したときに、次のページのプロダクションが使用されていることがわかります。

このようにして、DFA は解析ツリーを生成できます。ただし、この DFA は「グラフ」ではなく「ツリー」に似ています。

このスキームは完全に正しいとは限りません。何か問題がありましたら、お知らせください。

于 2012-05-24T20:56:29.307 に答える