问题标签 [parse-forest]

我试图让解析器从不明确的语法中返回所有可能的解析结果（解析森林），并通过根据用户上下文/历史和知识库评估它们来从解析森林中进行选择。出于性能原因，这可能应该使用 packrat 解析器和搜索限制/上限参数来限制在应用生产规则时递归调用的数量以避免无限循环。

作为 Scala 及其 Parser Combinators 的新手，我不知道如何做到这一点，或者根本不知道它是否可以做到。有人可以帮忙吗？非常感激。

最好的问候，托马斯·胡安

我正在尝试使用Rascal MPL设计一个岛语法，但遇到了一个问题：

在 SDF 中实现 Island Grammar 时，一种非常常见的方法是使用 {avoid} 属性定义“包罗万象”的水生产。如果其他产品适用，这会阻止解析器使用此产品。这允许指定一个默认行为，该行为可以被其他产品覆盖而不会产生歧义。一个非常简单的例子是：

我尝试用 Rascal MPL 重现这种行为。我的目标是创建一个岛语法，将所有条件预处理器指令收集到一段 C/C++ 代码中，并使用 Water 生成跳过其余输入。

我试图通过使用 ">" 运算符为ConditionalDirective产生更高的优先级来创建 {avoid} 效果，但这显然不起作用。解析树仍然包含歧义。

例如，如果我解析上面的代码，我会得到一个如下所示的解析树：

据我从Rascal Documentation可以看出，在我的情况下，使用“优先级”运算符可能不是要走的路，但我看不到任何其他可能性。不过我认为有一种方法，因为 rascal 的作者明确指出，每个 SDF 语法都可以转换为 rascal 语法。

有没有办法用流氓 MPL 重现 SDF {avoid} 功能？或者是否有可能以某种方式过滤解析森林，重新应用优先级？

Is there any existing implementation of the GLL algorithm, either in the form of parser combinators (preferred) or as a parser generator for C or C++?

My requirements are that the output is a shared packed parse forest (SPPF) which I can later disambiguate using semantic and/or contextual rules. There are other parsing algorithms such as GLR which are able to cope with general context-free grammars, however, all GLR parser generators I could find either return the first successful parse tree or fail if any ambiguity remains at the end.

假设我有一个很好的模棱两可的 Marpa 语法和一个很好的模棱两可的输入字符串。

我可以用 Marpa 解析字符串并最终得到一个解析森林。我什至可以遍历森林中的每个解析树。

但是我怎样才能“沿着”解析森林进行迭代呢？

描述我的意思：

解析森林是一种图，它可以具有备选方案分离的节点，以及备选方案重新组合成“主流”的节点。

假设这些是一个解析森林的替代解析树：

• A B1 C
• A B2 C
• A B3 B4 C

有一个主流A......C但是一个模棱两可的B部分。

当然，在现实世界的解析中，分支可能有许多级别的分支，并且可能存在不重新加入单个主流的流。但总的来说，两种或多种解释会有很多共同的部分。

可以使用哪些方法沿着明确和不明确的节点链进行迭代？

事实上我可以输出整个图表吗？

我想探索在自然语言的上下文中使用形式语言处理。为此，我正在寻找一种对歧义具有鲁棒性的解析器生成器，因为当它可以使用多个产生式来生成相同的字符串时，它不会将 EBNF 表示为无效。此外，处理冗余的标准方法是返回解析森林而不是解析树。

我不是在问最好的工具是什么，但前提是有可以为 C# 获得的工具。如果有，我在哪里可以找到它们。

该工具是开源的还是专有的并不重要。

答案将授予满足解析器生成器返回的解析器所需约束的唯一（前面未提及）工具的最长列表。

请帮我探索解析森林。

我尝试为森林的每个节点分配一个数字，这样就不会有 2 个节点具有相同的数字。我尝试使用 2 个相互调用递归的函数，但我得到了一些编译错误。这是代码：

我得到的错误是：

.hs:27:34: 无法匹配预期类型b0 -> c0' with actual typeTree Int 可能原因：( Node' is applied to too many arguments In the first argument of.)'，即 `Node n fst' 在表达式中：Node n fst 。numberForest (n + 1) xs

出了什么问题，我应该如何解决这个问题？