编译器前端基础
关于龙书
本篇介绍的基本概念来自于经典的龙书（Compilers Principles, Techniques and Tools））。而整个龙书，不幸地是，很多技术概念完全是以 类C 语言为前提做的介绍，从名字上，从章节目录上感到应该有帮助，实际没用。
另外对于 LR，LL 这些，似乎专注于做一个通用编译器的生成器，而不是编译器，而现在既然已有大量的通用生成器，但21世纪以来编程语言的发展趋势，是手写编译器，这背后一个重要原因机器性能的发展带来的质的变化：编译器性能得到了释放，手写可以得到更定制化地，更丰富特性地满足语言要求目标的复杂编译器。
在完成对于这些概念学习后，我得到的最大收获是这些东西确实没什么用。这里就不得不提一下计算机科学领域和某些领域一样，很喜欢把一些平常的概念，易见的规律冠以专有名词，搞得明明一眼明了的简单事情变得特别抽象，下面就有一个鲜活的例子。
因此我们对于这些概念的介绍也将专注于背后的算法思想，而不是照本宣科。
再探 First Set && Follow Set
显然，但有必要强调，不管是 First Set 还是 Follow Set 针对得都是 非终结符（non-terminal）
在提这两个概念的时候，我们假设语法规则以巴科斯范式（Backus Normal Form）的形式给出
First Set
是指，对于一个非终结符号，它的每条产生式（production）的首个（first）终结符（terminal）的集合 （包括特殊的 ε 符号）
Follow Set
是指，对于一个非终结符号，在所有产生式构成的语法上，紧跟在该非终结符后面的终结符（包括特殊的 $ 符号表示语法的终结）
Shift-reduce
LR（Leftmost rightmost-derivation）parsing 的核心操作是 shift-reduce ，它是一个有栈结构的优先状态机，要么暂时处理不了推入栈中，要么弹出栈中元素向上合并。
在手写编译器过程中，LR完全是用不上的，但可以在一点上发挥重要作用，就是按照操作符的优先级处理中缀表达式：就是把用二元中缀操作符处理成树型结构。
可以用后缀表达式也就是逆波兰式（Reverse Polish Notation，RPN）也就是后根序（Post-order，LRN（left right node））遍历的形式方便地表示这棵树。
如下是代码片段，完整见1
/// Return Reverse Polish Notation (RPN) form (or Post-order, LRN(left right node) traversal)
pub fn parse_infix_expr<O: Bop, T>(bops: Vec<O>, pris: Vec<T>) -> InfixExpr<O, T> {
debug_assert_eq!(bops.len() + 1, pris.len());
debug_assert!(bops.len() > 0);
// Resort the Infix expression by precedence (they don't change left most expr srcloc)
let mut out_bop_stack = Stack::from(bops);
let mut out_pri_stack = Stack::from(pris);
let mut staging_bop_stack: Stack<O> = stack![];
let mut expr_stack = stack![InfixExpr::E(out_pri_stack.pop().unwrap())];
// out_bop_stack would be same with out_pri_stack in size.
while !(out_bop_stack.is_empty() && staging_bop_stack.is_empty()) {
// Reduce
if out_bop_stack.is_empty()
|| !staging_bop_stack.is_empty()
&& staging_bop_stack.peek().unwrap().precedence()
// >= for left associative operator
>= out_bop_stack.peek().unwrap().precedence()
{
let bop = staging_bop_stack.pop().unwrap();
let rhexpr = expr_stack.pop().unwrap();
let lfexpr = expr_stack.pop().unwrap();
expr_stack.push(lfexpr.combine(bop, rhexpr));
}
// Shift
else {
staging_bop_stack.push(out_bop_stack.pop().unwrap());
expr_stack.push(InfixExpr::E(out_pri_stack.pop().unwrap()));
}
}
expr_stack.pop().unwrap()
}
LL
LL （Leftmost leftmost derivation）parsing 是一个从上到下的解析过程。
最常见的问题是左递归，就是某个非终结符的某个产生式的第一项是一个非终结符，这个非终结符直接或间接地会导会这个非终结符本身。
但这些都是形式推导方面的问题，通过重构生成式，使得终结符出现在产生式第一项可以解决这个问题。
LL(1)
参考2
LL(n)
基于状态机而不是形式符号推导
在手写编译器过程中，几乎不会考虑到形式推导里面的什么左递归什么二元歧义。
引用
