为什么我们不能使用CFG进行扫描/标记化？

Question

我为我的编译器课程进行了练习考试,其中包含以下我无法获得的问题:

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

有没有人有任何想法？

Answer 1

这两个陈述都是不正确的.

您绝对可以使用CFG进行扫描和标记化.实际上,每种常规语言都是无上下文的,因此您可以使用无上下文语法而不是正则表达式重写扫描程序进行扫描.不这样做的主要原因是它通常是矫枉过正; 令牌很少有一个复杂的结构,正则表达通常很好.但是,您可以考虑可能要使用CFG的实例.例如,在C++中,模板中关闭角度括号的处理通常需要编译器进行特殊套管.例如,vector<vector<int>>应该标记为vector < vector < int > >,尽管使用一组标准正则表达式,两个结束括号将被扫描为>>令牌.使用无上下文语法进行扫描可以通过增加上下文来缓解这种情况.

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

     0    1
 q0  q1   q0
 q1  q0   q1

但是,大多数真正的编程语言没有常规结构,因此在实践中使用无上下文语法.

希望这可以帮助!