如何构建LL(k>1)的解析表？

Question

在网络上，有很多例子展示如何从LL(1)分析器的first/follow集构造上下文无关文法的解析表。

但是我没有找到与k>1情况有关的有用信息。即使维基百科也没有相关信息。

我预计它在某种程度上类似，但指向这个领域现有研究的提示将非常有帮助。

- Petr Kozelka

---

我有一本关于解析的好书的副本，但不幸的是，它跳过了这个主题。我和你一样好奇。据我所知，k > 1的算法涉及的内容更加复杂，而且在实践中完全不可行。我想我们只能等着看了！ - templatetypedef

我认为这并不是不可行的。至少ANTLR声称可以解析LL(K)（任意K）语法。 - Odobenus Rosmarus

使用递归下降解析器很容易，只需维护一个向前查看列表即可。然后有许多优化可以改进这一点，例如记忆化和回溯。不确定如何在基于表的解析器中运作！你已经想出来了吗？ - Austin Henley

并不是真的 - 但使用一个不太正规的解决方法：词法分析器部分将一些多个符号“包装”成一个，然后我使用LL(1)。然而，这种解决方案有局限性。我正在使用表驱动解析器，因为它似乎具有最佳性能。 - Petr Kozelka

从数学角度来看，第一集和后续集中的字符串长度为k个字符，而不仅仅是单个字符。从实现的角度来看，你如何匹配这些取决于你表示令牌的方式，我想。 - Will

这里有关于LL(k)解析的所有信息，包括几种基于表格的算法的描述和比较。我还建议查看Terence Parr的LL(*)。这是ANTLR中使用的算法。关于LL(k)解析的另一个有价值的信息来源是Terence Parr的博士论文。 - Max Mouratov

Answer 1

我遇到了相同的问题，正在构建LR解析器，不过不是LL。我找到了一个比@cakeplus提到的LL（k）更好的页面--http://www.seanerikoconnor.freeservers.com/ComputerScience/Compiler/ParserGeneratorAndParser/QuickReviewOfLRandLALRParsingTheory.html，还有相关的免费论文--http://ci.nii.ac.jp/naid/110002673618/。然而，即使这些对我也没有太大帮助。所以我从基础开始自学。如果有人感兴趣：https://aboutskila.wordpress.com/2013/06/14/lalrk-first-sets/，战斗将继续 :-)

- greenoldman

---

我希望能够找到一种算法来计算这些。我可能会尝试逆向工程这个。 - paulotorrens

@paulotorrens，从“Aho，A.V.，Ullman，J.D.：The Theory of Parsing, Translation, and Compiling，Volume I: Parsing”开始（它大约是1970年左右的经典著作，被Dragon Book遗漏了这个算法）。解释有点简短，但很扎实，基于此，您应该能够编写自己的程序。 - greenoldman