詞法分析器-->output: 記號 --> 語法分析器 -->output: AST 抽象語法樹
context-free 上下文無關
Top-down 自頂向下:
意思就是從production rules的開始符號開始出發(fā)浇冰，所以叫Top--down.
如果可以推導出input String 那么就算成功拼弃。底下的例子就是從E 先 嘗試第一個Production
E - > T+E 然后再第二個Production。镶奉。哟沫。
Recursive Descent由于算法用到了Backtrack 效率有點差匕得，所以需要線性時間的算法掠河，引出了 LL(1)
Recursively Descent: 遞歸下降 ?也叫預測分析 ?Easy to implement.
Idea: 每個Non-Terminal 構造一個 分析函數(shù)， 失敗的就backtrack灯节。?
上面情況前看一個符號會發(fā)現(xiàn)有好幾種情況循头。[上述沒有使用前看符號的Recursive descent]
如果對上述使用LL(1)的話 我們需要使用Left-factor ?因為上面情況前看一個符號會發(fā)現(xiàn)有好幾種情況
某種意義說recursive descent = LL(0)
所以我們需要使用Left-factor before LL(1)?
遞歸下降 無限循環(huán)問題： ?S---> Sa
一直進入S绵估，需要使用Elimination left recursive.
Bottom-up parsing: ?也叫LR parsing, 不需要Left Factorized.自底向上。First/Follow set
Shift-Reduce:
w is a string of terminals 因為 bottom-up parse 的right-most derivation in reverse性質贷岸。
左邊是被parsed后的結果壹士，右邊是要parse的input。從右往左是parsing偿警，從左往右是reverse order ?derivation? 那么rightmost derivation的話 X->beta 卻沒有改變w躏救，只能證明w是一個terminals.
Predictive Parsing:
deterministic
LL(1)分析算法： 從左向右讀， 最左推導螟蒸，用一個前看符合盒使。 分析高效，Linear Time, Debug信息準確七嫌。Main: idea ? Table Driven Algorithm.?
這里只前看一個符號少办，比如T看到哦 是個Int，然后就會很confusing诵原。有2種possible情況
這樣的話又要需要試錯然后backtrack英妓。。
需要Left-factorization:
用表把不同場景應該怎么parse記錄一下
First/Follow sets
First: 如果能夠從這個non-terminal x derive 出一個Production such that 第一個字母是a.
那么a就在x的firstset绍赛。
Follow: A不能夠Derive出t, 但是t是A的production后的第一個字母蔓纠。t in followset of(A)
這里還有一個重點： A --> e 表示A可以通過一系列move變成e=消失了。
Follow：
Look at where the symbol is used! Also: Follow(x) is subset of FollowB 炒雞重要
For each non-terminal and token, there's only 1 procedure that could lead to success.
總結：
所以其實Parser的任務就是判斷input的這個東西符不符合這個語言的production rules
要么我能夠從production rules開始推導出你這個語句吗蚌，可以你就是valid腿倚。[top down].
要么你從這個語句能夠推導回我的production rule的起點：E. 那么你就是valid [bottom up]
然后中間各種predictive， 那些都是為了加速parsing的過程蚯妇。
當然敷燎，最后要output出一個AST 語法樹！Ｂ嵫浴硬贯！
