2

我的编译器课程有一个练习考试，其中有以下我无法回答的问题：

  1. 为什么我们不能使用上下文无关语法（CFG）来扫描/标记？
  2. 为什么我们不使用确定性有限自动机 (DFA) 进行解析？

有没有人有任何想法？

4

1 回答 1

9

这两种说法都不正确。

您绝对可以使用 CFG 进行扫描和标记化。事实上，每种正则语言也是上下文无关的，因此您可以重写扫描仪以使用上下文无关语法而不是正则表达式进行扫描。不这样做的主要原因是它通常是矫枉过正的。标记很少有复杂的结构，而正则表达式通常工作得很好。但是，您可以考虑可能要使用 CFG 的实例。例如，在 C++ 中，处理模板中的右尖括号通常需要编译器进行特殊大小写。例如，vector<vector<int>>应该标记为vector < vector < int > >，尽管使用一组标准的正则表达式，两个右大括号将被扫描为>>标记。使用上下文无关语法进行扫描可以通过拥有更多上下文来缓解这种情况。

此外，只要您的语言足够简单，您绝对可以使用正则表达式进行解析。大多数语言都过于复杂，无法使用正则表达式进行编码（例如，任何涉及嵌套括号的内容都无法使用正则表达式进行解析），因此我们倾向于使用 CFG 代替，但有些语言可以使用正则表达式进行解析。例如，将 DFA 描述为这样的表肯定可以通过正则表达式进行解析：

     0    1
 q0  q1   q0
 q1  q0   q1

然而，大多数真正的编程语言没有规则结构，因此在实践中使用上下文无关语法。

希望这可以帮助！

于 2012-04-08T19:15:33.703 回答