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
First & Follow set
下午6:04Compiler Ch4-Grammer
First and follow
是兩個很重要的Function，用來建構top-down 跟 bottom-up Parser
假設rule是以下這些
S -> ABc
A -> a | B
B -> b | λ
1.First(T)
定義：
將 T (可以是terminal 或 nonterminal) 展開時，可能遇到的第一個 terminal symbol 所成的集合
所以First(A) = { a , b , λ }
First(B) = { b , λ }
2.Follow(T)
定義：
接在T( nonterminal ) 後所有可能的第一個terminal
在開始算Follow之前，先把$(input right end marker)放到Start symbol後
所以Follow(B) = { c , $}
Follow(A) = First(B) + Follow(B) = { b , c }
在算Follow(A)時，即是在找接在A之後的第一個terminal有哪些，
而 S->ABc 因此去尋找B的First set，即是在找A後的第一個terminal，
會發現 First(B) 有 λ，因此當B->λ時，A後的第一個Terminal在Follow(B)內，以此類推。
