3

我已经实现了组合 GLR 解析器。其中有：

  • char(·)使用指定字符或字符范围的解析器。
  • many(·)从零到无限次重复指定解析器的组合器。

示例："char('a').many()"将匹配带有任意数量"a"-s 的字符串。

但是many(·)组合器是贪婪的，因此，例如char('{') >> char('{') >> char('a'..'z').many() >> char('}') >> char('}')（">>"解析器的顺序链接在哪里）将成功地消耗整个"{{foo}}some{{bar}}"字符串。

我想实现many(·)在前面的例子中使用的惰性版本，它只会消耗"{{foo}}"。我怎样才能做到这一点？

编辑：

可能是我把你们都弄糊涂了。在我的程序中，解析器是一个函数（或 C++ 中的“函子”），它接受“步骤”并返回“步骤”的森林。“步骤”可能是 OK 类型（表示解析器已成功使用部分输入）和 FAIL 类型（表示解析器遇到错误）。有更多类型的步骤，但它们是辅助的。

Parser = f(Step) -> Collection of TreeNodes of Steps.

所以当我解析输入时，我：

  • 编写简单的预定义 Parser 函数以获得表示所需语法的复杂 Parser 函数。

  • 从输入形成初始步骤。

  • 将初始 Step 赋予复杂的 Parser 函数。

  • 使用 Steps 过滤 TreeNodes，只留下 OK 的（或者如果输入有错误，则使用最少的 FAIL-s）。

  • 从剩下的 Steps 中收集信息。

4

4 回答 4

4

我已经实现并使用 GLR 解析器作为程序转换系统的语言前端已有 15 年了。

我不知道什么是“组合 GLR 解析器”，而且我不熟悉您的表示法，所以我不太确定如何解释它。我认为这是某种咖喱函数符号？我在想象您的组合规则相当于根据终端字符定义语法，其中“char('a').many”对应于语法规则：

 char = "a" ;
 char = char "a" ;

事实上，GLR 解析器会产生所有可能的解析。GLR 解析的关键见解是它对所有可能的解析的伪并行处理。如果您的“组合器”可以提出多个解析（也就是说，它们产生的语法规则与上述规则类似），并且您确实将它们连接到 GLR 解析器，那么它们都会被尝试，并且只有那些平铺的生产序列文本将继续存在（意味着所有有效的解析，例如模棱两可的解析）将继续存在。

如果您确实实现了 GLR 解析器，那么所有可能的解析器的集合对您来说应该非常清楚。它不是暗示您已实现的事实不是 GLR 解析器。

与任何其他解析技术一样，可以使用 GLR 解析器进行错误恢复。我们所做的是在错误点之前保留一组实时解析；当发现错误时，我们尝试（在伪并行中，如果 GLR 解析机制正确弯曲，则可以轻松完成）以下所有操作：a）删除有问题的令牌，b）插入所有本质上是 FOLLOW(x) 的令牌其中 x 是实时解析。本质上，删除令牌，或插入实时解析所需的令牌。然后我们再次松开 GLR 解析器。只有有效的解析（例如，修复）才能存活。如果无法处理当前令牌，则处理带有已删除令牌的流的解析器将继续存在。在最坏的情况下，GLR 解析器错误恢复最终会将所有标记丢弃到 EOF。一个严重的缺点是 GLR 解析器' 在解析错误时，运行时间会急剧增加；如果一个地方有很多，错误恢复时间可能会飞到屋顶。

于 2010-12-08T05:23:53.880 回答
1

GLR 解析器不会产生所有可能的输入解析吗？然后解决歧义是选择您喜欢的解析的问题。为此，我认为解析森林的元素需要根据产生它们的组合器类型进行标记，急切或懒惰。（通常，在看到所有输入之前，您无法逐步解决歧义。）

（这个答案基于我模糊的记忆和对 GLR 解析的模糊可能误解。希望专家能过来。）

于 2010-12-06T11:39:19.947 回答
0

考虑正则表达式<.*?>和输入<a>bc<d>ef。这应该找到<a>，并且没有其他匹配项，对吧？

<.*?>e现在考虑具有相同输入的正则表达式。这个应该找到<a>bc<d>e吧？

这造成了两难境地。为了用户的利益，我们希望>>根据它的两个操作数来理解组合器的行为。然而，没有办法根据第一个解析器的发现来产生第二个解析器的行为。

一个答案是每个解析器生成所有解析的序列，按偏好排序，而不是所有解析器的无序集。贪心匹配将返回从最长到最短排序的匹配；非贪婪，从最短到最长。

于 2010-12-09T15:42:54.797 回答
0

非贪心功能只不过是一种消歧机制。如果你真的有一个通用的解析器（它不需要消除歧义来产生它的结果），那么“非贪婪”是没有意义的；无论运算符是否“非贪婪”，都将返回相同的结果。

非贪婪消歧行为可以应用于广义解析器提供的完整结果集。从左到右工作，过滤与非贪婪运算符相对应的不明确子组，以使用仍能成功解析剩余输入的最短匹配。

于 2014-09-19T15:42:32.430 回答