我已经用后向指针编写了一个 Earley 解析器，但它不能很好地处理可空语法。我还实现了 Aycock & Horspool 2002 的解决方案，如果它可为空，则使 PREDICT 跳过非终结符标记。不幸的是，这并不能准确地告诉您 token 需要采用哪条特定路径才能到达 epsilon。
我的想法(相当愚蠢)是:
For each nullable nonterminal, create a list of paths for that nonterminal to get to epsilon.
Every time you skip over a nullable nonterminal, add a back pointer called NULL.
When you're expanding the tree, every time you encounter NULL, you create a list of trees, one for each path in the list for that nullable nonterminal.
Finally, you go through the list of trees and get rid of duplicates.
我认为这会显着增加我的算法的时间复杂度，但我想不出更有效的方法来生成所有可能的解析树。
谁能建议一种更有效的方法来实现 Aycock & Horspool 2002 来创建解析树？
最佳答案
你听说过Marpa吗？ ？
基本上是 Earley + Aycock&Horspool + Leo + 作者(Jeffrey Kegler)的改进。
您可能对 Theory 感兴趣作者博客部分和the author's paper about Marpa .
希望这对您有所帮助。
关于algorithm - 实用 Earley 解析 (Aycock & Horspool 2002) : How to add back pointers?，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/25893690/