自己动手开发编译器（七）递归下降的语法分析(3)

这个表达式类似于我们上篇末尾得到的无歧义二元运算符的文法。但这个文法存在左递归：E产生的第一个符号就是E本身。我们想像一下，如果在编写E的递归下降解析函数时，直接在函数的开头递归调用自己，输入字符串完全没有消耗，这种递归调用就会变成一种死循环。所以，左递归是必须要消除的文法结构。解决的方法通常是将左递归转化为等价的右递归形式：

F → id
E → FG
G → + FG
G → ε

大家应该牢牢记住这个例子，这不仅仅是个例子，更是解除大部分左递归的万能公式！我们将要在编写miniSharp语法分析器的时候一次又一次地用到这种变换。

由于LL(k)文法不能带有左递归和左公因式，很多常见的文法转化成LL(k)之后显得不是那么优雅。有许多程序员更喜欢使用LR(k)文法的语法分析器。LR代表从左到右扫描和最右推导。LR型的文法允许左递归和左公因式，但是并不能用于递归下降的语法分析器，而是要用移进-归约型的语法分析器，或者叫自底向上的语法分析器来分析。我个人认为LR型语法分析器的原理非常优雅和精妙，但是限于本篇的定位我不准备介绍它。我想任何一本编译原理书里都有详细介绍。当然如果未来我的VBF库支持了LR型语法分析器，我也许会追加一些特别篇，谁知道呢？

希望大家看了今天这篇文章之后，都能用递归下降法写出一些LL(k)文法的语法分析器来。下一篇我将介绍使用C#和VB中神奇的Linq语法来“组合”出语法分析器来，敬请期待！

希望大家继续关注我的VBF项目：https://github.com/Ninputer/VBF 和我的微博： 多谢大家支持！

以上就是关于递归下降的全部内容，相信你一定会非常满意。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/shenmilingyu/article-1094-3.html