Compiler CH6 Bottom-Up Parsing
Compiler CH6 Bottom-Up Parsing
Overview
- bottom-up parser
- started from parser tree’s leaves, move to its root
- traces a rightmost derivation in reverse
- replace rule’s RHS with its LHS
- top-down parser
- started from parser tree’s root toward its leave
- trace a leftmost derivation
- replace rule’s LHS with its RHS
Ex.
LR parsing
- 由左至右處理輸入字串
- 並以最右邊優先衍生的推導順序
名詞解釋
- Bottom-up
- 因為parser從terminal symbol開始工作直到grammar’s goal symbol
- shift-reduc
- shift symbol onto the parse stack
- reduce 留在stack頂端的那些符號組成的字串 變成grammar’s non-terminal
- LR(k)
- 如上
handle Pruning
informally, a substring
- matches the body of production
- whose reduction repre. 1 step along the reverse of a rightmost derivation
Ex.
formally
- 用production來作為handle,簡化表示
- 如果grammar unambiguous,所有的right-sentential form 都只有一個handle
handle pruning
Shift-Reduce Parsing
4 action
- shift: 將下一個input symbol移至stack top
- reduce: 從stack頂端向下,相當於將字串由右而左的縮減回nonterminal
- accept: 表示是否成功
- error: 發現syntax error 並呼叫error recovery routine
stack imple.
ex.
ex2.
LR(0) table construction
shift
- 對每個production,用dot標示辨識到的字串
- 找出closure
- 如果production的第一個symbol是nonterminal
- 把這個nonterminal的production也加入closure
- 名詞定義
- kernal items
- nonkernal items
- GOTO
- 去找item,把dot往X方向移動
- 決定有限狀態機轉換的模式
Ex.
- 對一個狀態,找出closure
- dot向右移動,定義下一個狀態
- 可以reduce的狀態,用雙框框刮起來(就是dot在做右邊)
- 可以reduce的狀態,用雙框框刮起來(就是dot在做右邊)
- 得到shift的table
CFSM
- 最右優先匹配
completing LR(0)
state 2, 4, 6 reduced
- 因為是LR(0)就不用看下一個狀態,直接reduce
Ex.
- pop出多少個symbol,就要回退多少狀態
- 其實就是看reduced的production有多少個symbol
- 龍書
- accept在action,要看狀態和$
- 綠書
- accept在goto
- symbol其實可以用state來代替
- 所以可以省略
- 所以可以省略
conflict
存在同時shift和reduce的情況
有兩個東西可以同時reduce
if grammar ambiguous
- 編譯器沒辦法處理
if compiler的問題 - lookahead
ambiguous grammar
state 5
- reduction like left-associateve
- shift like right-associative
可以reduced到兩個東西
- 5, 7
- 讓scanner處理
有兩個走向
- Exprs -> E a | F b
- 需要看最後一個symbol是甚麼
- a or b
SLR(k) table construction
避免先加減後乘除
- 如果是LR(0),遇到符合的直接reduced,但下一個是times優先權應該比較高
- SLR(k)
檢查symbol有沒有對應到production左式的follow set
- 再reduced
LALR(k) table construction
看item走的路徑決定follow
可以由LR(0), LR(1)建構出來
- LR(0)比較好做
- 用一個圖記錄狀態轉移的過程,如上
Propagation Graph
點是一個item
- 建構出所有vertex,follow為空
- 起始production的follow,放$
- 建出所有的邊,根據LR(0)
- 只看目前狀態內的follow
- 就根據follow的規則走
- 如果可以推導到empty 就加一個邊
- 只看目前狀態內的follow
Ex.
Compiler CH6 Bottom-Up Parsing
https://z-hwa.github.io/webHome/[object Object]/Compiler/Compiler CH6 Bottom-Up Parsing/