将词法分析器和语法分析器结合在一起的解析器组合器

Question

将词法分析器和语法分析器结合在一起的解析器组合器

parsinghaskellparser-combinatorsuu-parsinglib

4

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

让我们考虑以下示例：

我有一个带有组合器pLex的词法分析器，它生成MyToken类型的令牌列表。现在我想编写一个解析器，它将消耗这些令牌并构建一个AST。

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

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

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

- Wojciech Danilo

其他解析组合库有时也包含词法分析。有关此内容，请参阅Parsec或parsers中的Token Parsing模块。通常，这是使用解析器组合器的方向。但您始终可以将[MyToken]等级的输出作为输入提供给令牌解析器。 - J. Abrahamson

@J.Abrahamson：我的语法相当复杂，所以我不知道将词法分析器和解析器合并是否是个好主意（但也许使用解析器组合器是正确的方法？）我有一个问题，因为例如我的组合器“pString”返回一个令牌列表（因为在我的语言中字符串可以包含变量，如“test：$name”）。因此，我通常编写一些“end”组合器，它们会返回令牌列表，然后我将它们加在一起。这是一个不好的方法吗？ - Wojciech Danilo

你可以在主解析期间生成的每个tokenstream上触发子解析器。因此，如果 tokenizeSegment :: P String [MyToken] 和 parseSegment :: P [MyToken] SegmentAST，那么可以执行类似于 parse parseSegment <$> tokenizeSegment :: P String (Either ParseError SegmentAST) 的操作。你还可以通过解构 Either 并将 ParseError 传递给主解析器来处理该错误。 - J. Abrahamson

@J.Abrahamson：嗯...但据我所知，无法始终解析tokenizeSegment的结果。例如，结果可能是[Newline, Indentation 2]（Indentation表示缩进级别），除非您知道下一个段落，否则无法将其转换为任何AST结构？ - Wojciech Danilo

要通过解析器组合子制作一个普通的字符串解析器，您需要编写一个字符串解析器，该解析器表示“一个字符串是由引号标记开头，后跟零个或多个非引号字符，并以另一个引号字符结尾”。对于带有拼接的字符串，它将是“零个或多个（非引号字符或拼接）”，然后您需要提供一个单独的函数作为拼接解析器，该函数表示“一个拼接是一个美元符号后跟...”等等。 - Levi Pearson

显示剩余4条评论

2个回答

1

我认为在uu-parsinglib中没有任何东西阻止您使用不同于Text的输入。只是对于Text（和类似的类型），我们提供了一些您可能需要的函数。如果您查看旧版的uulib解析器组合器，您会发现一种基于扫描仪的方法，它可以与较新的uu-parsinglib一样很好地使用。

如果您想处理大量数据，也许最好有一个单独的扫描阶段。错误消息往往更具信息性。在uulib中，您将找到一些支持编写扫描仪的功能（大多数语言都会对词法结构施加某些特殊限制/要求，这些工具往往会失败/需要进行适应（例如，离线规则））。

- Doaitse Swierstra

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

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

- Levi Pearson · Accepted Answer

基于表格的解析器由于其有限的前瞻能力需要分离词法分析和语法分析。如果向前看得足够远以将词法分析合并到解析器中，状态空间会爆炸。

基于组合子的方法通常不会遇到这个问题，因为它们通常进行递归下降解析。除非库的作者另有说明，否则将这些阶段组合在一起没有什么危害，也没有什么好处。

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

至于您关于字符串实现的问题，组合子接受一个类似字符串的输入，其中包含语法结构，并返回相应的语义值，如果它们匹配。在组合子内部，您可以通过直接从输入流中获取信息并通过调用子组合子来组合语义值来构建该语义值。

因此，在您的示例中，“字符串匹配”组合子将在其作用域内具有标记列表，因为它进行了解析。您可以使用 Haskell 的全部功能，以任何对您的语言有意义的方式将这些标记组合成单个 MyString 值：例如一个“SplicedString”类型，表示哪些值要被切片。

字符串组合子可能由“表达式”组合子调用，后者将能够将 MyString 值与其他解析值组合成 MyExpression 值。这是一种从组合子返回语义值的方法！