LL(k)文法
LL(1)
為什麼需要FIrst和Follow,以及如何根據First與Follow生成預測分析表
步驟
首先生成First,再結合First生成Follow, 最後根據First與Follow生成預測分析表
LL(1),LR(0),SLR(1),LALR(1),LR(1)對比
http://blog.csdn.net/linraise/article/details/9237195
LR(0)的介紹
從左分析,從棧頂歸約,
LR(0) -> SLR的必要性
對于LR(0),由于分析中一遇到終态就歸約,一遇到First集就移進,如果有一下狀态I1,I1包含兩個文法:
F->Y·+
F->Y·
那LR(0)就無法确定到底是移進還是歸約了。
這就是為什麼我們要引入SLR解決reduce-shift conflict(盡管不能完全解決該問題).
SLR的介紹
如果不僅考慮First,而且把Follow集也考慮在内,就可以一定程度上解決reduce-shift conflict.
還是以上文法:
F->Y·+B
F->Y·
如果FOLLOW(F) = {a, b},那麼當我們遇到a與b時,就可以選擇歸約F;當我們遇到+時,就可以選擇移進操作。
SLR -> LR(1)的必要性
SLR不能完全解決reduce-shift confict.
同樣還是上面的文法:
F->Y·+B
F->Y·
如果 FOLLOW(F) = {a, b, +},那當我們遇到 + 符号時,就無法确定到底是選擇移進操作得到F->Y+·B,還是歸約F。
SLR不能完全解決reduce-shift conflict. 這就是為什麼我們要選擇LR(1) / LALR(1)了
LR(1)的介紹
https://parasol.tamu.edu/~rwerger/Courses/434/lec10.pdf
LALR table 構造
關鍵
合并同心集
合并前
合并後
構造方法: 見中文第二版P.169下方[算法 4.56]
reduce-shift reduce 移進-歸約沖突
LR(0)不能解決移進-歸約沖突(不知道該移進還是歸約)
SLR
寫出First、Follow,并得出LR(0)
根據中文版P.161畫出SLR table.
本文參與 騰訊雲自媒體分享計劃 ,歡迎熱愛寫作的你一起參與!
本文分享自作者個人站點/部落格
https://www.jianshu.com/u/68cbc4294f4c
複制
如有侵權,請聯系 [email protected] 删除。