Open AlexiaChen opened 4 years ago
一般来说编译原理总体分成前端和后端两大部分，前端是指词法分析，语法分析，以及语义分析之类的类型检查。后端是代码生成，优化，寄存器分配等等。
现在前端的理论知识研究早已经基本完备，没多少值得研究的地方了，所以都是固定的套路和模式，性能差距都不会很大（递归下降的LL文法对CPU分支预测友好），后端还有很多可优化的地方。
很多很多大家平时常用的编译器的前端时至今日都还是手写的，所以连lex/yacc那种都不是，而更多是ad-hoc的手写lexer以及递归下降+运算符优先级的手写parser。这方面主流并没有特别积极的跟进技术的发展。 C++的就是手写递归下降LL（1）文法，但是C++的 LL（1）跟平常不一样，就是它有回溯，是变种。然后当然也还有一些前端是用lex/yacc系的做法，例如Ruby的parser；或者是用ANTLRv3那样的LL(∞)的做法，例如Groovy的parser。（注意ANTLR的LL(*)不是给定k的LL(k)而比后者更强，因为其lookahead允许无限多，本质上跟PEG类似）。ANTLRv4是ALL(∞)。
从语法分析上，自底向上方面其实GLR系的算法早就有了，实现上也越来越好，早就比yacc/bison用的LALR(1)好。 而自顶向下方面在2000后也有 PEG、LL(∞) （ANTLRv3）和 ALL(∞) （ANTLRv4）的发展，颇有抢回地盘的趋势。
Parsing 算法大致分为两派，自顶向下和自底向上。
其中自顶向下分析（可维护性，可读性更好，方便手写）也就是一般人认为的递归下降分析，一般实现自顶向下分析器都要求parsing 是线性运行时间，所以大多数top-down parser 也就是predict parser 即预测分析器，因为这种parser 在运行时每次都要至少向前看一个符号（然后去查每个产生式的predictive set）才能决定用哪个产生式（递归下降是把所有跳转条件都放在了if(lookhead == xxx) 上），即predict parser 是由“向前看”（预测）来驱动的。去看《Language Implementation Patterns》中给出的LL(1) parser 的模板代码，马上就理解了。同时因为它总是把左边先看到的符合产生式的一串符号构建成一个语法树，所以也叫LL(k) parsing，其中第二个L就是最左推导的意思，而k 是指最多向前看几个符号（至少一个，有时需要多个），且k 为常数（可以用环形缓冲区实现）。当加入回溯策略时，这个k 就可以是无穷大了。LL(1)、LL(2) 和更大的k 之间有什么区别对于新手来说确实不好判断，所以我建议你可以从top-down parser 开始自己给一门语言写个parser，开始只选择几个特性来写，然后逐步添加grammar。
相对照来说，自底向上分析（可读性差，不推荐手写，纯学术上的产物，推荐用生成器生成）就对应LR(k) parser 了。它和LL(k) 不一样的地方在于：
shift、reduce 就是这种算法中的两个动作：shift（吞入下一个符号），reduce（将已近吞入的、最右侧的、符合某个产生式的一串符号构建成一个语法树）。但是有时候你会发现在某一步parser 不知道应该shift 还是reduce，这时候SLR 就发挥作用了，它通过向前看一个符号来解决这个冲突。所以说：LL通过预测驱动，而LR通过预测来解决冲突。
下面这张图应该是想告诉你理论上每种grammar class（以及对应的parsing algirithm）之间描述能力（解析能力）的差别。而且这张图讨论的应该是grammar class 而不是language class。纯理论地来看，它们之间解析能力的差异是很难看出来的，所以给几个例子，如图：
推荐用LLVM解决。
编译器前端
一般来说编译原理总体分成前端和后端两大部分，前端是指词法分析，语法分析，以及语义分析之类的类型检查。后端是代码生成，优化，寄存器分配等等。
现在前端的理论知识研究早已经基本完备，没多少值得研究的地方了，所以都是固定的套路和模式，性能差距都不会很大（递归下降的LL文法对CPU分支预测友好），后端还有很多可优化的地方。
前端
很多很多大家平时常用的编译器的前端时至今日都还是手写的，所以连lex/yacc那种都不是，而更多是ad-hoc的手写lexer以及递归下降+运算符优先级的手写parser。这方面主流并没有特别积极的跟进技术的发展。 C++的就是手写递归下降LL（1）文法，但是C++的 LL（1）跟平常不一样，就是它有回溯，是变种。然后当然也还有一些前端是用lex/yacc系的做法，例如Ruby的parser；或者是用ANTLRv3那样的LL(∞)的做法，例如Groovy的parser。（注意ANTLR的LL(*)不是给定k的LL(k)而比后者更强，因为其lookahead允许无限多，本质上跟PEG类似）。ANTLRv4是ALL(∞)。
从语法分析上，自底向上方面其实GLR系的算法早就有了，实现上也越来越好，早就比yacc/bison用的LALR(1)好。 而自顶向下方面在2000后也有 PEG、LL(∞) （ANTLRv3）和 ALL(∞) （ANTLRv4）的发展，颇有抢回地盘的趋势。
Parsing 算法大致分为两派，自顶向下和自底向上。
其中自顶向下分析（可维护性，可读性更好，方便手写）也就是一般人认为的递归下降分析，一般实现自顶向下分析器都要求parsing 是线性运行时间，所以大多数top-down parser 也就是predict parser 即预测分析器，因为这种parser 在运行时每次都要至少向前看一个符号（然后去查每个产生式的predictive set）才能决定用哪个产生式（递归下降是把所有跳转条件都放在了if(lookhead == xxx) 上），即predict parser 是由“向前看”（预测）来驱动的。去看《Language Implementation Patterns》中给出的LL(1) parser 的模板代码，马上就理解了。同时因为它总是把左边先看到的符合产生式的一串符号构建成一个语法树，所以也叫LL(k) parsing，其中第二个L就是最左推导的意思，而k 是指最多向前看几个符号（至少一个，有时需要多个），且k 为常数（可以用环形缓冲区实现）。当加入回溯策略时，这个k 就可以是无穷大了。LL(1)、LL(2) 和更大的k 之间有什么区别对于新手来说确实不好判断，所以我建议你可以从top-down parser 开始自己给一门语言写个parser，开始只选择几个特性来写，然后逐步添加grammar。
相对照来说，自底向上分析（可读性差，不推荐手写，纯学术上的产物，推荐用生成器生成）就对应LR(k) parser 了。它和LL(k) 不一样的地方在于：
shift、reduce 就是这种算法中的两个动作：shift（吞入下一个符号），reduce（将已近吞入的、最右侧的、符合某个产生式的一串符号构建成一个语法树）。但是有时候你会发现在某一步parser 不知道应该shift 还是reduce，这时候SLR 就发挥作用了，它通过向前看一个符号来解决这个冲突。所以说：LL通过预测驱动，而LR通过预测来解决冲突。
下面这张图应该是想告诉你理论上每种grammar class（以及对应的parsing algirithm）之间描述能力（解析能力）的差别。而且这张图讨论的应该是grammar class 而不是language class。纯理论地来看，它们之间解析能力的差异是很难看出来的，所以给几个例子，如图：
后端
推荐用LLVM解决。
参考