LL(*)解析器是如何工作的?

12

我找不到关于LL(*)解析器的完整描述,例如ANTLR。

我想知道LL(k)解析器和LL(*)解析器之间的区别以及它们为什么不能支持左递归语法,尽管它们很灵活。

2个回答

5

这里有一篇文章(作者是antlr的作者Terence Parr),讲解LL(*)语法分析:文章,并且提供了一个很好的例子,说明什么是LL(*)但不是LL(k),其中k可以是任何数字。

另一个很好的参考资料(更加详尽)是“ANTLR权威指南”,同样由Terence Parr编写,原始的期刊文章介绍了antlr的工作原理[pdf]


文章链接目前不可用。 - LeeR
更新了链接以引用新的维基。该文章也可以在网络档案馆中找到。 - tonio

1

每当你看到这个时,通常是为了解析语言而向前查看的令牌数量。

对于LR分析器来说也是一样的。

因此,k是解析器在做出决策之前获取的最大令牌数。 请注意,k越高,除非使用生成器(ANTLR、yacc、bison等),否则解析器将越难。

LL分析器采用自上而下的方法,这意味着它将寻找最深的树。 因此,左递归会产生一个无限深的树,并破坏解析器。

据我所知,大多数语言使用LR分析器。


网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接