語法分析的目的
? ? 詞法分析與語法分析處于編譯器的前端踪古，對輸入的源程序進(jìn)行分析。詞法分析钟沛，類似于將語句切分為關(guān)鍵字畔规、記號、操作符等助于語法分析識別的記號流讹剔；而語法分析油讯，是將記號流生成抽象語法樹详民，便于后面語義分析。
語法分析的工具
? ? 數(shù)學(xué)理論
? ? ? ? 上下文無關(guān)文法（CFG）
? ? 自頂向下分析
? ? ? ? 遞歸下降分析法
? ? ? ? LL分析算法
? ? 自底向上分析法
? ? ? ? LR分析算法
上下文無關(guān)文法
? ? 上下文無關(guān)文法G={T,N,P,S},T表示終結(jié)符集合陌兑，N表示非終結(jié)符集合沈跨，P表示一組運(yùn)算規(guī)則，S為唯一開始符號兔综。
? ? 對于一個句子饿凛，它首先由開始符號S為開端，并不斷地轉(zhuǎn)化為非終結(jié)符软驰，最終轉(zhuǎn)為終結(jié)符涧窒。而它們的轉(zhuǎn)化，并填充產(chǎn)生式規(guī)則集合锭亏。
? ? 非終結(jié)符只有E纠吴，而E可以推出：E->num,E->id,E->E+E,E->E*E；最后推出上圖左邊的式子慧瘤。一個具體的例子戴已，就是3+4*5這個例子。
? ? 對于上述文法锅减，使用最左推導(dǎo)：
? ? ? ? ? ? E->E+E,
? ? ? ? ? ? E->3+E,
? ? ? ? ? ? E->3+E*E,
? ? ? ? ? ? E->3+4*E,
? ? ? ? ? ? E->3+4*5.
? ? 對于語法分析程序糖儡，回復(fù)YES。
? ? 而另一種推導(dǎo)：
? ? ? ? ? ? E->E*E,
? ? ? ? ? ? E->E+E*E,
? ? ? ? ? ? E->3+4*5.
? ? 這兩種推導(dǎo)的結(jié)果是一樣的怔匣，但是表達(dá)式的運(yùn)算取決于語法分析樹的后序遍歷握联。
? ? 對于存在二義性的文法，編譯器是不可接受的每瞒，只能重寫文法金闽。
文法重寫
? ? 我們將上述文法重寫為左遞歸文法
? ? E-> E+T | T,
? ? T-> T*F | F,
? ? F-> id | num
? ? 根據(jù)上述文法，我們的表達(dá)式可以遞歸擴(kuò)展独泞，比如E->E+T呐矾，右邊的E又可以替換為E+T，所以我們得到E->E+E+T懦砂，累加符號就解決了蜒犯。同理，T=T*...F荞膘，連乘符號解決了罚随。
? ? 對于上述3+4*5的文法推導(dǎo)，為E->E+T->T+T->T+T*F->T+F*F->F+F*F羽资，而F為數(shù)字或者id淘菩，從而得到分析樹。
自頂向下分析法
????通過對文法的不斷推導(dǎo)，來匹配輸入的這個字符串是否為可匹配的文法潮改。譬如文法G，和輸入s汇在，通過G的不斷嘗試回溯生成t，以匹配文法s亩鬼。
? ? 例子：G -> N V N ,N -> a | b | c,V -> e | f雳锋。
? ? 輸入cfc羡洁，首先通過棧存儲開始符號G筑煮，并通過循環(huán)轉(zhuǎn)化為下一個推導(dǎo)咆瘟，N V N诽里，注意這里是從右往左入棧谤狡；隨后，對每一個棧頂?shù)姆墙K結(jié)符進(jìn)行嘗試焰宣，找到終結(jié)符匹配捕仔。比如轉(zhuǎn)化為a V N榜跌，與輸入第一位c匹配不上，觸發(fā)回溯嘗試下一個句子翻譯 b V N悄蕾，不斷往復(fù)直到匹配出cfc為止帆调。
????因為編譯器需要處理大量的程序番刊，回溯是一個比較昂貴的過程撵枢，避免回溯，就是在替換終結(jié)符的時候直接拿到對應(yīng)的終結(jié)符號潜必，按照寫代碼的理解磁滚，就是對符號集合存儲使用的是HashMap而不是Array垂攘。
遞歸下降分析算法
對每一個token晒他，對應(yīng)的是一個分析函數(shù)逸贾，而文法的未終結(jié)符之間都是分析函數(shù)的關(guān)聯(lián)铝侵。? ??
LL(1)分析算法
L采用左遞歸咪鲜，以及從左讀入一個前看符號的分析算法疟丙。
每次分析token輸入符號的時候，回溯將會造成大量的資源損耗发皿，此算法提出是基于表驅(qū)動的解決方案拂蝎，也就是通過當(dāng)前符號與輸入符號的映射來確定解析路徑。不需要使用next一個前看符號皇钞，而是使用correct一個前看符號夹界。
使用一個非終結(jié)符左看第一個符號生成FIRST集合可柿，進(jìn)而生成LL(1)表复斥。LL(1)表中表示的是第幾條產(chǎn)生式規(guī)則目锭。
