Quadsim左递归消除演示Demo
左递归文法的方式，一直是编译原理里的老大难问题。quadsim这个小 demo，专门演示了怎么在 C 语言里搞定左递归，还蛮实用的。
左递归的麻烦点在于它让递归下降解析器容易陷进死循环，比如Expr → Expr + Term这样的写法，解析器一头栽进去就出不来了。quadsim里用的是比较常见的手法——把左递归改写成右递归，用中间态变量来兜底。
比如把上面那个式子改成：
Expr → Term E'
E' → + Term E' | ε这样就不会死循环，解析也清晰多了，思路也更适合前端习惯的语法方式。
整个 demo 用 C 写的，结构还挺清楚。压缩包里的源码对照起来看也方便，变量命名都比较直白，不用太多猜测。你要是正好在研究 语法器、递归下降 或者想自己写个简单 解释器，这个例子还蛮适合入门的。
哦对了，间接左递归也提了一点，虽然没展开讲，但代码结构预留了扩展的空间。要是你想在 C 里做点更复杂的文法改造，能省不少事。
如果你平时喜欢折腾编译原理相关的东西，或者刚好想了解下 Expr → Term + Term 这种结构到底怎么搞清楚，那这个 demo 还挺值得一看。
文件大小：5.27MB
评论区