1

众所周知，DFA 可用于验证常规语言中的字符串。

示例 1. L=ac(b)*bcb|ad(b)*bb。DFA 可以验证字符串“acbbbcb”是否正确。

此外，有时，常规语言可以用 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 可以通过生成树的副作用来增强（假设语法是明确的）。这可能需要构建 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"。并且有两种过渡：一种是从“A”到下一页纸，另一种是从下一页纸到这个“A”。

在该方案中，当发生从下一页到当前页的返回转换时，我们知道使用了下一页中的产生式。

这样，DFA 就可以生成解析树。但是，这个 DFA 更像是一棵“树”而不是“图”。

这个方案可能并不完全正确。如果您发现任何问题，请告诉我。

于 2012-05-24T20:56:29.307 回答