Compiler Ch5 LL Parser 編譯系統 學習筆記
凌晨1:21
Compiler Ch5 LL Parser
First L: 由左到右處理input
Second L: 執行left derivation
LL(K): K代表向前探查K個token
LL(1)
由左到右處理字串，再對句型執行最左推導語法樹，只需向前查看(偷偷看)1個token，就可以推導出來的文法，即是LL(1)，當 parser 遇到多種可能的推導方式時，偷偷的看 Predict Set ，找出對應Token ，持續parse直到$
如何計算 Predict Set (所有可能的下一個token)
如果 A -> ABCD
ANS = First(ABCD) #找出第一個terminal
if (ABCD -> λ): #如果會derive 出 lumbda
ANS = ANS 聯集 Follow(A) #那就要再從follow找terminal
return(ANS) #回傳答案
Lumbda 不算是 Terminal ， 所以不能算在Set裡
如何確認 Grammer 是 LL(1)
如果 S -> A | B
要符合 LL(1) 的 grammer 有以下條件
- First(A) 跟 First(B) 交集為空
- 兩者至多一個可 derive lumbda
- if B -> lumbda , First(A) 跟 Follow(S) 交集為空
- if A -> lumbda , First(B) 跟 Follow(S) 交集為空
Example
Rule：
S -> A C $
C -> c | λ
A -> a B C d | B Q
B -> b B | λ
Q -> q | λ
建表
| Rule Number | A | X1X2…Xn | First(X1X2…Xn) | Derive empty | Follow | Ans |
|---|---|---|---|---|---|---|
| 1 | S | AC$ | abqc$ | N | abqc$ | |
| 2 | C | c | c | N | c | |
| 3 | C | λ | Y | d$ | d$ | |
| 4 | A | aBCd | a | N | a | |
| 5 | A | BQ | bq | Y | c$ | bqc$ |
| 6 | B | bB | b | N | b | |
| 7 | B | λ | Y | cd$ | cqd$ | |
| 8 | Q | q | q | N | q | |
| 9 | Q | λ | Y | cd$ | c$ |
檢查條件
檢查4種條件，若都符合即是LL(1)
Recursive-Descient Parser with LL(1)
這種parser搭配LL(1)，大致結構就是LL方式判斷，依照rule去match terminal，若是nonterminal，則call它的rule繼續match，遞迴下去求得解答或是判斷出syntax error
