先推薦一些編譯原理的材料：
- mooc上斯坦福的compilers課程
- 《形式語言與自動(dòng)機(jī)導(dǎo)論》(An Introduction to Formal Languages and Automata)
- 《parsing techniques》
編譯原理這方面目前只學(xué)了遞歸下降和各類LL玷过，嘗試做一個(gè)簡(jiǎn)單編譯器(估計(jì)這坑填不完了...)乓梨，感覺還是沒有backtracking的遞歸下降和SLL(1)最實(shí)用驻售。這里大概總結(jié)一下遞歸下降。
最最最重要的是试吁，什么文法能用疗垛？
- 首先肯定是CFG文法
- 對(duì)于一個(gè)合法的sentence纹笼，有且只有一個(gè)derivation tree與之對(duì)應(yīng)饱普，即只有一種parsing方法
- production rule右邊不能存在空串
- 不能出現(xiàn)left recursive的文法。left recursive的文法可以改寫成right-recursion
- 還有最容易忽略的prefix free吕漂，對(duì)于
T -> A | B這樣的文法亲配，A不能是B的前綴，B也不能是A的前綴惶凝。若有這樣的文法吼虎，可以使用left factoring來消除。
消除空串的方法可以看《形式語言與自動(dòng)機(jī)導(dǎo)論》（An Introduction to Formal Languages and Automata）的第六章苍鲜。
消除left recursive的一般方法如下：
對(duì)于如下文法 S -> S a | S b ... | A | B ...
都可以改成如下等價(jià)文法:
S -> A S' | B S' ...
S' -> a S' | b S' ...
非prefix free文法就要在parse的時(shí)候特殊處理了思灰，這里自然是要backtracking了。
例如對(duì)于文法 S -> a | ab
parse函數(shù)在確認(rèn)完a后混滔，需要嘗試確認(rèn)b洒疚，然后一直parse下去看看能不能成功歹颓，
如果不能成功parse整個(gè)sentence，就放棄這條路油湖，使用S -> a來parse巍扛。
下面放遞歸下降的parse代碼。當(dāng)然乏德，實(shí)際寫的時(shí)候肯定沒那么簡(jiǎn)潔电湘，因?yàn)橐幚礤e(cuò)誤的情況。
- E -> T
bool E() { return T(); }
- E -> A + B
bool E() { return A() && Term('+') && B(); }
// 其中Term(char c)確認(rèn)當(dāng)前指向的字符是否為參數(shù)c
- E -> A | B
bool E() {
Token * save = next;
return A() || ((next == save), B());
}
