4

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

让我们考虑以下示例:

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

连接词法分析器和解析器的最佳方法是什么?现在我有一个lex功能:

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

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

4

2 回答 2

3

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

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

尽管 uu-parsinglib 提供了Str对不同的类似字符串的输入进行抽象的类,但查看它的定义表明它仍然假设您最终正在读取一个字符序列,无论它们来自字符串、字节字符串、文本等。所以尝试让它解析 MyToken 流似乎很困难。如果您觉得需要这样做,Parsec 可能是一个更好的选择。

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

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

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

于 2013-08-13T20:46:59.710 回答
1

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

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

于 2013-08-15T08:23:45.663 回答