-->

为什么有LR(0)分析器而不是LL(0)解析器?(Why are there LR(0) parse

2019-08-16 17:05发布

我一直在阅读上无论是在维基百科,并注意到,虽然LR(0)分析器存在,还有为LL(0)分析器没有这样的事情。

从我读,我明白,在LL(K)的K / LR(K)表示解析器可以有多少个字符看到, 超出了当前的字符,它的目前的工作。

所以我的问题是,为什么没有这样的东西作为LL(0)语法分析器即使LR(0)存在?

Answer 1:

差异有什么k个在LR(k)随LL(k)的意思做。

在LL(K),解析器维护有关自上而下,从左向右描绘出一个最左推导解析信息。 解析器的工作原理是反复查看当前非终结符,然后检查所述输入流的下面k个令牌,以确定应该使用哪个生产。 因此,如果你有一个LL(0)语法分析器,解析器将不得不预计使用在当前非终结纯粹基于其生产。 这仅仅是可能的,如果每个非终结符号只有一个与之相关联的生产,这意味着该语法要么产生恰好一个字符串或根本没有字符串(通过进入一个循环)。 因此,尽管在数学上被良好定义的,LL(0)解析从未在实践中使用。

在LR(K),解析器工作自下而上。 它维护符号的堆叠,与当前沿“状态”,然后连续地决定是否进行换档 (在堆栈的顶部推进另一符号)或减少 (弹出从堆栈符号的一些数量和施加的生产相反)。 的LL(k)和LR(k)的解析器之间的一个主要区别是LR(k)的语法分析器如何决定执行哪个动作。 在LR(k)的解析器,什么样的决定,以此为基础进行前瞻的下面k个代币都和解析器的当前状态下一秒 其结果是,一个LR(0)分析器还能让有些智能决定哪些行动来执行,即使它不能看到任何前瞻令牌,因为解析器的当前状态,可以编码的信息在哪里的生产量巨大解析器是什么,它能真实地希望看到作为输入的下一个令牌(即便是解析器不能直接看这些令牌)。

总之,LL(0)是极其微弱的,因为解析器纯粹的基础上的当前非终结决定,这意味着它不能采取基于可用于该生产许多不同的行动之一。 一个LR(0)分析器是体面的强大,因为解析器基地的选择上其内部状态,通常是足够详细,让下一步该怎么做解析器做出明智的决定。

还有一个其他原因LL(0)较弱,而LR(0)是相当强大。 在一个LL(0)的解析器,该解析器必须立即决定哪个制作应该被执行,这意味着,解析器必须猜测制作完全盲目。 在一个LR(0)的解析器,该解析器可以判定它是时间,以降低前的多个符号移位。 因此,分析器,没有任何先行,可以暂时抛开其即将使用的减少,直到它看到输入足够的令牌后得到一个有意义的字符串的结构决定。 这是更一般的事实的特殊情况,任何LL(k)文法自动是LR(K)。

希望这可以帮助!



文章来源: Why are there LR(0) parsers but not LL(0) parsers?