问题标签 [earley-parser]

我已经用反向指针编写了一个 Earley 解析器，但它不能很好地处理可空语法。我还实现了 Aycock & Horspool 2002 的解决方案，如果它可以为空，则让 PREDICT 跳过非终结标记。不幸的是，这并不能准确地告诉您令牌需要采取哪条特定路径才能到达 epsilon。

我的想法（很愚蠢）是：

对于每个可以为空的非终结符，为该非终结符创建一个路径列表以到达 epsilon。

每次跳过可为空的非终结符时，添加一个称为 NULL 的反向指针。

扩展树时，每次遇到 NULL 时，都会创建一个树列表，列表中的每个路径对应于该可为空的非终结符。

最后，您遍历树列表并删除重复项。

我认为这会显着增加我的算法的时间复杂度，但我想不出一种更有效的方法来生成所有可能的解析树。

谁能建议一种更有效的方法来实现 Aycock & Horspool 2002 来创建解析树？

我偶然发现这篇文章http://compilers.iecc.com/comparch/article/02-04-096 说有两个使用 Earley 解析的 Eiffel 编译器。帖子比较老了。我想知道这里是否有人知道哪些 Eiffel 编译器使用 Earley 解析器以及它们是否仍在使用？链接高度赞赏。

我有一个关于 Earley 解析器的非常基本的问题：如果语法不明确（S -> NP VP(V NP(NP PP)) vs. S -> NP VP(VP((V NP) PP)），两个解析都存储在​​一个图表中还是两个？

我所说的语法如下：

因此，您在解析时可以将 PP 附加到 NP 或 VP。

我的问题是细节是图形图表的样子，这意味着预测、扫描和完成的位置。我假设两个解析都将存储在一个（大）图表中。那么 S' 会在 s[0][8] 和 s[0][16] 中找到吗？那正确吗？通过模棱两可的句子解析带有图形图表的附加图像或链接会有所帮助。

问候

我正在使用PEP java earley 解析器。我现在有一个关于正确站点上的空规则（epsilon（ε））的问题：

我如何在java中定义这样的规则

如果无法应用正确的终端，我如何通过解析查询来使用它。所以例如我有一个词，应该接受什么：

在一个作业中，我被要求为以下功能编写一个 CFG：

def f(x, y): 返回 x + y

def g(x, y): 返回 x – y

def h(x, y, z): 返回 x + y % z

def w(x, y, z): 返回 x * y – z

和

def h1(x, y, z): 返回 (x + y) % z

def h2(x, y, z): 返回 x + y % z

我试图将其作为普通 CFG 进行处理，但是对于函数定义和函数体，我无法做到这一点。我不太确定如何从这种 CFG 开始。

我已经使用队列实现了Earley 解析器来处理状态。队列以顶级规则为种子。对于队列中的每个状态，通过向队列中添加新状态来执行其中一个操作（预测、扫描、完成）。不添加重复状态。

我遇到的问题最好用以下语法描述：

解析A时，会发生以下情况：

如您所知，A不会完全解决。这是因为具有 epsilon 状态的完成只会发生一次，因为它没有添加到队列中。

如何调整我的算法以支持这些 epsilon 状态？

编辑：请注意，使用终端时这不是问题，因为将创建新图表集以插入扫描状态。由于该状态在那里尚不存在，因此将对其进行处理。

我制作了 CFG 语法并使用EarleyParser 算法验证了我的语法。

我想问如何允许规则，即使某些东西超出了生产规则的词汇。让我举一个粗略的例子。

现在我想要的是，如果某个单词不在的词汇表中START，END即使这样，它也应该被检测到。我的问题是不可能在语法中添加所有规则。

如果有人这样输入，中午我吃了一个带有 sprite 的汉堡。现在在中午和与精灵两者都不存在于CFG语法中。对于这个给定的输入，有什么方法我仍然可以从 EarleyParser 获得 S1 模式。

我目前正在努力实现自己的英语语言处理库。真正的挑战是阅读所有丰富的理论材料，并充分了解如何将其全部置于生产轨道上。

到目前为止，我已经取得了一些进展。我实现了句尾检测器和早期解析器。但事实是，除非我在终端词典中包含解析器无法识别的特定单词并构建图表。

为了更明确，请查看我的 CFGrammar 的以下示例：

结果，如果 Earley 解析器遇到，比如说，未知的两个单词 PP，例如“up to”，它将无法识别它并构建图表。

所以我认为在语法解析器之前我需要其他东西来处理我的句子，然后将相关数据转发给解析器。主要思想是在词性标注阶段动态建立字典，然后Earley解析器可以识别一个单词。

我实现了分词器和词法分析器。作为输出，我得到了 S-Expression 树，例如：

但我熟悉隐马尔可夫模型和诸如用于查找最可能状态序列的 Viterbi 算法和用于参数估计的 Baum-Welch 算法之类的算法。

您能否给我一些建议，如何将 Earley 解析器和基于 HMM 的 POS 标记链接在一起。或者，很可能，我走错了方向，所以请指出我错在哪里。现在我有点困惑。谢谢！

我正在研究该OpenSCAD语言的 JavaScript 实现，为此目的，它是一种 C 类型的语言。

我已经能够成功解析各种if和if/else语句：

但是，我遇到了一个特定的组合，它让我留下了“模棱两可的语法”——Nearley.js表示解析可能以多种方式发生：

尝试的解决方案 1：从少数不同的来源制作

尝试的解决方案 #2 选自https://github.com/vsl-lang/VSL/blob/develop/src/vsl/parser/parser.ne

尝试的解决方案3：仍然可以解析两种方式

有没有人成功地用 Earley 语法解析过这种语法？

提示？建议？哎呀，我什至会采取解决方案！

（整个包都可以在 github 上找到，但需要进行一些调整才能在其他机器上运行。） https://github.com/JeremyJStarcher/openscadtojs

我正在创建一个文本区域，它像大多数 IDE 一样具有智能感知。我的方法是使用earley 解析器算法。

我正在使用early-parser-js 库。

下面是语法：

现在，如果我在 textarea 中写“she”，我的代码应该建议下一个可能的节点，如“eats”、“fish”、“fork”等。