algorithm - 解析上下文无关文法

我知道自下而上的语法分析器比自上而下的语法分析器更好,因为它可以接受左递归语法,还有什么其他原因使我们更喜欢自下而上的语法分析而不是自上而下的语法分析?

最佳答案

从理论上讲,对于任何k,LL(k)文法总是LR(k)文法的严格子集,因此确定性预测自下而上解析器可以接受比确定性预测自上而下解析器更严格的文法集这也意味着任何ll(k)语法也是lr(k)。
另外,一个棘手的证明表明,任何确定性CFL(确定性下推自动机接受的CFL)都有LR(1)语法,这意味着LR语法与那些具有有效的基于堆栈的解析算法的语言精确对应。
这就是说,如果你允许更多的一般解析算法,如昂格尔的算法,厄利的算法,或CYK算法,然后自上而下和自下而上的方法存在解析任意CFGs。不过,这些算法可能比预测方法慢得多,因此它们通常不用于编程语言。
希望这有帮助!

本文翻译自 https://stackoverflow.com/questions/9019323/

网站遵循 CC BY-SA 4.0 协议,转载或引用请注明出处。

标签 algorithm parsing ll lr


相关文章:

android - 尝试在Android中解析Json,获取arraylist异常

parsing - 尝试使用Golang在命令行上解析stdout

c# - 为什么AngleSharp不为交错文本生成TextNode?

python - 创建LL(1)语法时出现问题

algorithm - 从语法生成第一集

algorithm - 说明令牌流上最左边的派生

java - 备忘录似乎未按预期工作

algorithm - 用于存储同步数据的分布式算法

python - 用Python方法将对列表转换为字典

java - 在二维数组中寻找最短路径