在解析器组合器中将词法和解析器结合起来

Question

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

让我们考虑以下示例：

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

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

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

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

Answer 1

基于表的解析器需要将词法分析和解析分离开来，因为它们的前瞻性能力有限。展望未来，将词法分析结合到解析器中，会导致状态空间的爆炸。

基于组合器的方法通常不会遇到这个问题，因为它们通常是在进行递归下降解析.除非图书馆作者另有说明，否则合并这些阶段并没有什么害处，分离它们也不会有什么好处。

尽管uu提供了Str类来抽象不同的类似字符串的输入，但是查看它的定义显示，它仍然假定您最终读取的是Char序列，无论它们来自字符串、ByteString、文本等等。因此，试图让它解析MyToken流似乎很困难。如果你觉得你需要这样做，那么Parsec可能是一个更好的选择。

至于您关于字符串实现的问题，组合器采用包含语法结构的字符串样输入，如果匹配，则返回相应的语义值。在combinator内部，通过直接从输入流中获取语义值并结合您调用的子组合器的语义值，您可以从解析中构建该语义值。

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

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

Answer 2

我认为using中没有什么可以阻止您使用与文本不同的输入。只是，对于文本(和朋友)，我们提供了相当多的功能，您可能需要。如果您查看较早的uulib解析器组合器，就会发现一种基于扫描器的方法，它可以与新的uu-parsinglib一起使用。

如果你想处理大量的数据，也许最好有单独的扫描阶段。错误信息往往更能提供信息。在uulib中，您会发现一些对编写扫描器的支持(大多数语言以某种方式对词法结构设置了一些特殊的限制/要求，其中相当多的工具(失败/需要调整)来创建扫描仪(例如越位规则)。