先推荐一些编译原理的材料：
- mooc上斯坦福的compilers课程
- 《形式语言与自动机导论》(An Introduction to Formal Languages and Automata)
- 《parsing techniques》
编译原理这方面目前只学了递归下降和各类LL，尝试做一个简单编译器(估计这坑填不完了...)，感觉还是没有backtracking的递归下降和SLL(1)最实用。这里大概总结一下递归下降。
最最最重要的是，什么文法能用？
- 首先肯定是CFG文法
- 对于一个合法的sentence，有且只有一个derivation tree与之对应，即只有一种parsing方法
- production rule右边不能存在空串
- 不能出现left recursive的文法。left recursive的文法可以改写成right-recursion
- 还有最容易忽略的prefix free，对于
T -> A | B这样的文法，A不能是B的前缀，B也不能是A的前缀。若有这样的文法，可以使用left factoring来消除。
消除空串的方法可以看《形式语言与自动机导论》（An Introduction to Formal Languages and Automata）的第六章。
消除left recursive的一般方法如下：
对于如下文法 S -> S a | S b ... | A | B ...
都可以改成如下等价文法:
S -> A S' | B S' ...
S' -> a S' | b S' ...
非prefix free文法就要在parse的时候特殊处理了，这里自然是要backtracking了。
例如对于文法 S -> a | ab
parse函数在确认完a后，需要尝试确认b，然后一直parse下去看看能不能成功，
如果不能成功parse整个sentence，就放弃这条路，使用S -> a来parse。
下面放递归下降的parse代码。当然，实际写的时候肯定没那么简洁，因为要处理错误的情况。
- E -> T
bool E() { return T(); }
- E -> A + B
bool E() { return A() && Term('+') && B(); }
// 其中Term(char c)确认当前指向的字符是否为参数c
- E -> A | B
bool E() {
Token * save = next;
return A() || ((next == save), B());
}
