DFAを使用して、Context-Free Grammarで指定された通常の言語を解析し、解析木を生成できますか？

Question

DFAを使用すると、通常の言語で文字列を検証できます。

例1：L = ac（b）* bcb | ad（b）* bb。文字列 "acbbbcb"は、DFAによって正しいものとして検証できます。

また、時々、標準的な言語をCFGで表現することができます。

例2

• S - > "" "B"
• A - > "C" B "C" | "d" B
• B→ "b" B | 「B」

上記のCFGによって生成された言語は、我々はこのCFGによって生成された（通常の）文字列を検証するためにDFAを使用することができることを意味し、例1

でちょうど正規表現です。しかし、どのようにして対応する解析木を生成できますか？

Answer 1

すべての標準言語にはCFGがあります。

DFAには受け入れ/拒否以外の出力がないため、厳密には構文解析ツリーを構築することはできません。しかし、私は木の生成の副作用（文法が明白であると仮定して）を増強することができる、各言語の少なくともいくつかのDFAをなぜ持つことができないのか分かりません。これは、DFAが文法の構造を反映するように構築されているため、必ずしも最小限であるとは限りません。

文法があいまいである場合、Guntherが書いているように、DFAはツリー構築の目的では不十分です。

Answer 2

• S - > "" "B"
• A - > "C" B "C" | "d" B
• B→ "b" B |

  あなたは、紙のいくつかのページを持っている想像して：「B」

私がこの方法で達成することができると思います。紙の各ページには、制作ルールがあります。そして、一番上の紙には規則S→ "a" A "b"があります。そして、2つのトランジションがあります：1つは「A」から次のページまで、もう1つは次のページからこの「A」までです。

このスキームでは、次のページから現在のページへのリターン遷移が発生すると、次のページの生産が使用されていることがわかります。

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

このスキームが完全ではない可能性があります。問題が見つかった場合は、私に知らせてください。