Nol*_*rin 72 grammar parsing recursive-descent context-free-grammar ll-grammar
我最近正在努力教自己解析器(语言/无上下文语法)是如何工作的,除了一件事以外,大部分解析器似乎都有意义.我特别关注LL(k)语法,其中两个主要算法似乎是LL解析器(使用堆栈/解析表)和递归下降解析器(简单地使用递归).
据我所知,递归下降算法适用于所有LL(k)语法,可能更多,而LL解析器适用于所有LL(k)语法.然而,递归下降解析器显然要比LL解析器简单得多(正如LL一个比LR一个简单).
所以我的问题是,使用任何一种算法时可能遇到的优点/问题是什么？为什么有人会选择LL而不是递归下降,因为它适用于同一组语法并且实现起来比较棘手？
Dan*_*wak 94
LL通常是一种比递归下降更有效的解析技术.事实上,在最坏的情况下,一个天真的递归下降解析器实际上将是O(k ^ n)(其中n是输入大小).一些技术,例如memoization(产生Packrat解析器)可以改进这一点,并扩展解析器接受的语法类,但总是存在空间权衡.LL解析器(据我所知)总是线性时间.
另一方面,你的直觉是正确的,即递归下降解析器可以处理比LL更大的语法类.递归下降可以处理任何LL(*)(即无限前瞻)语法以及一小组模糊语法.这是因为递归下降实际上是PEG或Parser Expression Grammar的直接编码实现.具体来说,析取运算符(a | b)不是可交换的,意味着a | b不相等b | a.递归下降解析器将按顺序尝试每个替代方案.因此,如果a输入相匹配,它会succede即使b 会匹配的输入.这样可以else简单地通过正确排序析取来处理经典的"最长匹配"歧义,例如悬挂问题.
尽管如此,可以使用递归下降来实现LL(k)解析器,以便它以线性时间运行.这通过基本上内联预测集来完成,以便每个解析例程在恒定时间内确定给定输入的适当生产.不幸的是,这种技术消除了处理整个类的语法.一旦我们进入预测性解析,像悬挂else这样的问题就不再那么容易解决了.
至于为什么LL会被选择而不是递归下降,它主要是效率和可维护性的问题.递归下降解析器明显更容易实现,但它们通常更难维护,因为它们所代表的语法不存在于任何声明形式中.大多数非平凡的解析器用例都使用解析器生成器,如ANTLR或Bison.使用这些工具,算法是直接编码的递归下降还是表驱动的LL(k)并不重要.
令人感兴趣的是,它也值得研究递归上升,它是一种在递归下降之后直接编码的解析算法,但能够处理任何LALR语法.我还将深入研究解析器组合器,它是一种将递归下降解析器组合在一起的功能性方法.