我们可以使用DFA来解析由上下文无关语法指定的常规语言并生成解析树吗？
正如我们所知，DFA可以用来验证常规语言中的字符串。我们可以使用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 | “B”
由上述CFG产生的语言仅仅是实施例1
也就是说，我们可以使用DFA，以验证由该CFG产生的（正常）的字符串在正则表达式。但是，我们如何才能生成相应的分析树？
所有正规语言都有CFG。
由于DFA没有超出接受/拒绝的任何输出，因此严格来说不能构建解析树。然而，我不明白为什么每个语言都不能有至少一些DFA，这些DFA可能会因产生树的副作用而增加（假设语法是明确的）。这可能要求DFA的构建是为了反映语法的结构，因此不一定是最小的。
如果语法不明确，那么就像Gunther写道的那样，DFA可能不足以用于构建树的目的。
嗨，同上，我认为你的观点，这需要DFA是建立在语法生产规则的镜像之上，是真实而必要的。 – JackWM
- 的S - >的 “a” A “B”
- A - >的 “c” B “C” | “d”B
- B - >“b”B | “B”
我认为这可以通过这种方式来实现：
想象一下，你有纸几页。在每一页纸中，都有一个生产规则。最顶级的论文有规则S - >“a”A“b”。有两个过渡：一个是从“A”到下一页纸，另一个是从下一页纸到这个“A”。
在此方案中，当从下一页返回到当前页面发生时，我们知道使用下一页中的生产。
通过这种方式，DFA可以生成分析树。但是，此DFA更像是“树”而不是“图”。
该方案可能不完全正确。如果您发现任何问题，请告诉我。
这不是你的问题的答案，但一段时间以前，我发现了一个“在线正则表达式可视化器”：http://regexvisualizer.apphb.com/ –