parsing - 在解析器组合器中组合词法分析器和解析器

Question

我正在使用uu-parsinglib，但我认为以下问题是解析器组合器通用的。

让我们考虑以下示例:

我有一个带有组合器pLex的词法分析器，它生成一个标记列表(类型为MyToken)。我现在想编写一个解析器，它将使用 token 并构建 AST。

连接词法分析器和解析器的最佳方式是什么？现在我有一个 lex 函数:

lex s = parse ( (,) <$> pLex <*> pEnd) (createStr (LineColPos 0 0 0) s)

我应该创建一个函数parse p = ...吗？如果是，我如何构建它来跟踪词法分析器的列和行？或者我应该创建一个 parserCombinator，它将以某种方式使用 pLex 组合器？

Answer 1

基于表的解析器需要将词法分析和解析分开，因为它们的前瞻能力有限。向前看足够远，将词法分析结合到解析器中将会爆炸状态空间。

基于组合器的方法通常不会遇到这个问题，因为它们通常进行递归下降解析。除非库作者另有说明，否则组合这些阶段并没有什么坏处，而且将它们分开也没有多大好处。

尽管 uu-parsinglib 提供了 Str 类来抽象不同的类似字符串的输入，但查看其定义表明它仍然假设您最终读取的是 Char 序列，无论它们来自String、ByteString、Text 等。因此尝试让它解析 MyToken 流似乎很困难。如果您觉得需要这样做，秒差距可能是更好的选择。

关于您关于字符串实现的问题，组合器采用包含语法结构的类似字符串的输入，并返回相应的语义值(如果它们匹配)。在组合器内部，您可以通过从输入流和中获取直接解析的内容来构建语义值，并通过组合来自您调用的子组合器的语义值。

因此，由于它所做的解析，示例中的“字符串匹配”组合器将在其范围内包含一个标记列表。您可以使用 Haskell 的全部功能，以对您的语言有意义的任何方式将这些标记组合成单个 MyString 值:也许是一个 'SplicedString' 类型，代表要切入其中的值。

字符串组合器可能由“表达式”组合器调用，该组合器能够将 MyString 值与其他解析值组合成 MyExpression 值。它是组合器一路返回语义值!