解析器生成器不需要扫描仪。但是,如果您不使用它,您将非常疯狂。
解析器生成器构建的解析器并不关心你给它们提供什么,只要你称它们为令牌。
要构建不使用扫描仪的解析器生成器,只需将语法定义到字符级别,并将单个字符作为标记提供给解析器。
这很疯狂的原因是解析是比词法分析更复杂的活动。您可以将词法分析器构建为有限状态机,它几乎可以将机器代码转换为“比较并跳转到下一个状态”。对于速度,这真的很难被击败。解析器生成器构建的解析器执行递归下降预测解析(对于大多数 LL 生成器,例如 ANTLR)或通过散列、二进制或线性搜索等进行表查找。因此,解析器在令牌上花费的能量比词法分析器在特点。
如果您将字符作为标记提供给解析器,那么它将在字符上花费比同等词法分析器更多的能量。如果您处理大量输入文本,这最终会很重要,无论您是为数以万计的小输入流还是一些非常大的输入流进行处理。
相对于设计为使用令牌的 GLR 解析器,所谓的无扫描 GLR 解析器存在这个性能问题。
我的公司构建了一个工具, DMS Software Reengineering Toolkit它使用 GLR 解析器(并成功解析了所有你知道的常见语言和许多你不知道的奇怪语言,因为它有一个 GLR 解析器)。我们知道无扫描解析器,但由于速度差异而选择不实现它们;我们有一个经典风格(但非常强大)的类 LEX 子系统,用于定义词法标记。在 DMS 与基于 XT(具有无扫描仪 GLR 解析器的工具)处理相同输入的工具正面交锋的一种情况下,DMS 的速度似乎是 XT 包的 10 倍。公平地说,所做的实验是临时性的,没有重复,但由于它符合我的怀疑,我认为没有理由重复它。YMMV。当然,如果我们想不用扫描仪,那么用字符终端编写语法非常容易,正如我已经指出的那样。
GLR Scannerless 解析器确实有另一个对大多数人来说并不重要的非常好的属性。您可以为无扫描仪解析器采用两个单独的语法,并将它们连接起来,仍然得到一个解析器(通常有很多歧义)。当您将一种语言嵌入到另一种语言中时,这很重要。如果那不是您正在做的事情,那只是学术上的好奇心。
而且,AFAIK,Elkhound 不是没有扫描仪的。(我可能错了)。(编辑:2/10:看起来我错了。不会是我生命中的第一次 :)