当使用像Parsec这样的解析器组合库时，我应该使用词法分析器吗？

Question

当使用像Parsec这样的解析器组合库时，我应该使用词法分析器吗？

haskelllexerparsec

48

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

编写词法分析器将 String 输入拆分为标记，然后对 [Token] 执行解析
直接在 String 上编写解析器组合器

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

在其他地方，我看到有人建议不要对标记进行分词（或称为扫描或词法分析），并引用简单性作为主要原因。

在进行或不进行词法分析之间有哪些一般权衡？

- nh2

3

根据我的经验，这取决于你要解析的语言。有些语言如果没有进行词法分析就很难进行解析。请注意，我的翻译不会改变原意，尽量用通俗易懂的语言。 - Pubby

2

@Pubby，不，没有这样的语言。任何语言都可以在没有词法分析器的情况下完美解析。 - SK-logic

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- nh2 · Accepted Answer

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

一个好处是您不再需要考虑空格。在直接（非词法分析）解析器中，您必须在允许空格的所有位置上撒布“space”解析器，这很容易忘记，并且如果空格必须分隔所有标记，则会使代码混乱。

您可以按部就班地思考您的输入，这对人类来说很容易。

然而，如果您执行词法分析，则会遇到问题。

现在你不能再对String使用普通解析器, 例如为了用库函数 parseFloat :: Parsec String s Float (它在输入流上操作于一个String类型的参数) 解析数字, 你必须像这样 takeNextToken :: TokenParser String，然后在其上执行parseFloat解析器，并检查解析结果(通常是Either ErrorMessage a)。这样写起来很混乱且限制了组合性。
你需要调整所有的错误信息。如果你的标记解析器在第20个标记处失败了，在输入字符串中的位置在哪里？你必须手动将错误位置映射回输入字符串，这很繁琐（在Parsec中这意味着需要调整所有的SourcePos值）。
错误报告一般更差。当你在错误的输入上运行string "hello" *> space *> float，比如"hello4"，它会精确告诉你在hello后面缺少空格，而一个词法分析器只会声明发现了一个“无效标记”。
许多人们期望的作为原子单位并由词法分析器分隔的东西实际上对于词法分析器来说太困难了。以字符串字面量为例——突然之间"hello world"不再是两个标记"hello和world"，而是一个标记（当然，如果引号没有被转义，比如\"）——虽然这对于解析器来说很自然，但对于词法分析器来说意味着复杂的规则和特殊情况。
你不能像以前那样方便地在标记上重用解析器。如果你定义了如何从String中解析出双精度，导出它，那么其他人可以使用它；他们不能先运行你的（专门的）标记解析器。
你会被束缚住。当你正在开发要解析的语言时，使用词法分析器可能会让你做出早期决策，修复你后来可能想要更改的东西。例如，想象一下你定义了一个包含一些Float标记的语言。某个时刻，你想引入负数字面量（-3.4和- 3.4）——这可能不可能由于词法分析器将空格解释为标记分隔符。使用仅解析器的方法，你可以保持更灵活，更容易对语言进行更改。这并不奇怪，因为解析器是一个更复杂的工具，本质上编码了规则。

总的来说，我建议大多数情况下都使用无词法分析器的解析器。最终，词法分析器只是一个“简化版”解析器——如果你需要解析器，就将它们合并成一个。

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