49

在像 Haskell's Parsec 这样的解析器组合库中编写解析器时，您通常有两种选择：

  • 编写一个词法分析器将您的String输入拆分为标记，然后执行解析[Token]
  • 直接写解析器组合器String

第一种方法似乎很有意义，因为许多解析输入可以理解为由空格分隔的标记。

在其他地方，我看到人们建议不要标记化（或扫描或词法分析，有些人如何称呼它），引用简单是主要原因。

词法分析和不做词法之间的一般权衡是什么？

4

1 回答 1

62

最重要的区别是词法分析将翻译您的输入域。

一个很好的结果是

  • 您不必再考虑空格了。在直接（非词法分析）解析器中，您必须space在所有允许使用空格的地方添加解析器，这很容易忘记，并且如果空格必须分隔所有标记，它会使您的代码混乱。

  • 您可以逐个考虑您的输入，这对人类来说很容易。

但是，如果您确实执行词法分析，则会遇到以下问题

  • 您不能再使用通用解析器String了 - 例如，使用库函数解析数字parseFloat :: Parsec String s Float（对字符串输入流进行操作），您必须执行类似的操作takeNextToken :: TokenParser String，并execute在parseFloat其上使用解析器，检查解析结果（通常Either ErrorMessage a）。这写起来很乱，并且限制了可组合性。

  • 您已调整所有错误消息。如果您的标记解析器在第 20 个标记处失败，那么输入字符串在哪里？您必须手动将错误位置映射回输入字符串，这很乏味（在 Parsec 中，这意味着调整所有SourcePos值）。

  • 错误报告通常更糟糕。string "hello" *> space *> float在错误的输入上运行like"hello4"会准确地告诉您在 之后缺少预期的空格hello，而词法分析器只会声称找到了"invalid token".

  • 许多人们认为是原子单元并被词法分析器分开的东西实际上对于词法分析器来说“太难”了。以字符串文字为例——突然不再"hello world"是两个标记"hello了world"（当然，如果引号没有被转义，比如）\" ——虽然这对于解析器来说是很自然的，但对于词法分析器来说，这意味着复杂的规则和特殊情况。

  • 您也不能在令牌上重复使用解析器。如果您定义如何解析 a 中的双精度String，则将其导出，世界其他地方都可以使用它；他们不能先运行您的（专业）标记器。

  • 你被它困住了。当您开发要解析的语言时，使用词法分析器可能会导致您做出早期决策，修复您以后可能想要更改的内容。例如，假设您定义了一种包含某些Float标记的语言。在某些时候，您想要引入否定文字 ( -3.4and - 3.4) - 由于词法分析器将空格解释为标记分隔符，这可能是不可能的。使用仅解析器的方法，您可以保持更灵活，更轻松地更改您的语言。这并不奇怪，因为解析器是一种更复杂的工具，它天生就对规则进行编码。

总而言之，我建议在大多数情况下编写无词法分析器的解析器。

最后，词法分析器只是一个“简化”* 解析器 - 如果您仍然需要一个解析器，请将它们组合成一个。

* 从计算理论我们知道，所有正则语言也是上下文无关语言；词法分析器通常是常规的、上下文无关的解析器，甚至是上下文敏感的（像 Parsec 这样的单子解析器可以表达上下文敏感）。

于 2013-03-05T05:02:52.860 回答