《編譯原理》LR 分析法與構造 LR(1) 分析表的步驟 - 例題解析

《編譯原理》LR 分析法與構造 LR(1) 分析表的步驟 - 例題解析

筆記

直接做題是有一些特定步驟,有技巧。但也必須先了解一些基本概念,本篇會通過例題形式解釋概念,會容易理解和記憶,以及解決類似問題。

如果只想做題可以直接下拉至習題部分。

(一)關于狀態

對于產生式 A→aBcD,就可以分解為下面幾個不同的識別狀態:

(1)A→.aBcD
(2)A→a.BcD
(3)A→aB.cD
(4)A→aBc.D
(5)A→aBcD.

“.” 的左部符號表示已被識別出來的那部分句柄符號

狀態(1)表示:處于句柄的頭
狀態(2)表示:已經識別出字符 a,等待 形成以 B 為產生式左部的右部
狀態(3)表示:剛剛進行了一次規約,即把關于 B 的產生式右部規約成 B
狀態(4)表示:已經識別出字符 c,等待 形成以 D 為產生式左部的右部
狀態(5)表示:已經到達句柄的尾巴,可以把 aBcD 規約為產生式左部的符號 A

(二)什么是 LR(k) 分析法?

字面意思理解:

字符 含義
L 表示 從左到右 掃描輸入串
R 表示利用 最右分析方法 來識別句子,即構造一個 最右推導的逆過程
k 表示向右查看輸入串符號的個數

LR 分析過程是規范歸約的過程

規范規約是最右推導的逆過程,最右推導是規范推導,所以 最左規約是規范規約。

LR 分析法根據當前分析棧中的符號串和向右順序查看輸入串的 k 個符號就可以唯一確定分析器的動作是移進還是歸約、利用那個產生式進行歸約。

當沒有指明 k 是幾的時候,默認為 1

(三)文法的拓廣?

文法的拓廣是對現有文法,添加一個 S',并對文法進行展開。

例如:

對于文法 G[E]:
E → E+T|T
T → T*F|F
F → i|(E)

可以把它拓廣為

文法 G[E']:
E' → E
E → E+T|T
T → T*F|F
F → i|(E)

此時可能會有疑問,不就是加了個開始符號,有什么意義呢?為什么要再加個開始符號呢?

加開始符號是為了狀態的表示,這樣原來的 S 會成為右部,可以表示 .S 和 S.

那同一非終結符的右部有多種情況為什么不展開呢?

這里是說拓廣文法,是添加開始符號,可以展開可以不展開,但是一般默認要展開,一般一道題不會只讓求拓廣文法,而是為了后面。一般題目中是說 “求該文法的拓廣文法并編號”,此時請一定要展開。展開后應該是這樣:

1.E'→E
2.E → E+T
3.E → T
4.T → T*F
5.T → F
6.F → i
7.F → (E)

(四)什么是項目?項目有哪些分類?等價狀態?

上面提到拓廣文法,展開,以及編號。

先看例題:

對于文法 G[S]:
S → vI:T
I → I,i
I → i
T → r

可以把它拓廣并編號,如下:

文法 G[S']:
1.S' → S
2.S → vI:T
3.I → I,i
4.I → i
5.T → r

它的全部 LR(0) 項目,如下:

1.S' → .S
2.S' → S.
3.S → .vI:T
4.S → v.I:T
5.S → vI.:T
6.S → vI:.T
7.S → vI:T.
8.I → .I,i
9.I → I.,i
10.I → I,.i
11.I → I,i.
12.I → .i
13.I → i.
14.T → .r
15.T → r.

對上面 LR(0) 項目進行分類

類型 包含 特點
規約項目 2, 7, 11, 13, 15 . 在右部的末尾
接收項目 2 . 在開始符號的末尾
移進項目 3, 5, 9, 10, 12, 14 . 后面跟著終結符,表移進
待約項目 1, 4, 6, 8 . 后面跟著非終結符,表等待后面非終結符的規約,簡稱待約

誰和誰是等價狀態?

例如:

待約項目 4 即 S→v.I:T 它的含義是等待棧頂規約出 I,但尚未識別對應 I 的那些句柄的任何符號;

項目 8 即 I→.I,i 和項目 12 即 I→.i 的含義也是期待棧頂形成 I 的句柄,所以這三個項目的含義是一樣的,即 4, 8, 12 三個狀態是等價的。

同理:項目 6 即 S → vI:.T 和項目 14 即 T → .r 也是等價的

為什么它們是等價狀態?怎么判斷等價狀態?

上面有說因為他們表示的含義是一樣的,并且會發現等價肯定涉及至少一個待約項目,以及一個 . 在最左端的移進項目。

這是因為,待約項目是 . 后面跟非終結符,這個 . 是在非終結符的前面;當存在該非終結符的產生式時,且 . 在最左端的時候。因為 . 在最左端,其實也是相當于在該非終結符的前面。所以是一個等價的狀態。

(五)LR 分析表介紹

LR 分析器的關鍵部分是 分析表的構造。分析表有以下幾種:

規范的 LR 分析表:

  • LR(0),能力最弱,局限性較大,但理論上最重要。
  • LR(1),它功能最強,但代價也最大。

簡單的 LR 分析表:

  • 簡稱 SLR ,最容易實現,但功能最弱。

向前看的 LR 分析表:

  • 簡稱 LALR,功能和代價處于前兩者之間,適用于絕大多數程序語言的文法

總結: LR(0) 功能最弱,功能弱是說當文法中產生式比較復雜,出現某些問題時,無法解決。這些問題一部分可以由 SLR 分析法解決。但還有一部分 SLR 解決不了,可以用 LR(1) 來解決。

(六)關于 “展望

在規范歸約過程中,一方面記住已移進和歸約出的整個符號串,即記住 “歷史”,另一方面根據所用的產生式推測未來可能碰到的輸入符號,即對未來進行 “展望”。

當一串貌似句柄的符號串呈現于分析棧的頂端時,根據所記載的 “歷史” 和 “展望” 材料,來確定棧頂的符號串是否構成句柄。

為了記住分析的 “歷史” 和匯集 “展望” 的信息,LR 分析法這樣處理:

將歸約過程的 “歷史” 和 “展望” 材料綜合抽象成某些狀態,存放在一個狀態棧中,棧中每個狀態都概括了從分析開始直到某一歸約階段的全部“歷史”和“展望”材料。

LR(1) 分析法這樣處理:

首先,明白了在 LR(1) 分析法中展望是為了解決其他分析法解決不了的問題。簡單的說就是,狀態會出現沖突,我們不能只通過后 1 個輸入串符號,直接確定選用哪個產生式,這是嚴重的錯誤。

所以 展望(向前搜索符) 是通過展望后面的內容,所以展望對應的終結符,應該 屬于該非終結符的 FOLLOW 集(確切的說,屬于 FOLLOW 集中的具體哪個個終結符,應該根據產生式的推導過程確定,通過語法樹來分析,是比較直觀的方法。也可以直接通過求該非終結符后的 FIRST 集來確定,但要注意是對誰求 FIRST 集,可表示為 FIRST(βa),例題中會提到),來幫助唯一確定選擇產生式。

拓展注:這里提到的 FOLLOW 集和 FIRST 集不是沖突的,因為我們要求的向前搜索符時 FOLLOW 集的子集,有時候不能確定,所以用 FIRST(βa), β 表示由誰哪個非終結符推導的,這個非終結符的后面的剩余串,a 表示它上一個狀態中的向前搜索符。它倆拼接起來的串,對該串求 FIRST 集。
那么可能會有疑問,利用上一個狀態?那第一個狀態呢?第一個狀態是固定的 S'→S,#
其實 # 就是 S 的 FOLLOW 集中的唯一的元素,它也是開始符號的向前搜索符
所以說 FOLLOW 集和 FIRST(βa) 是都可以求的,FIRST(βa) 是準確的向前搜索符,它是 FOLLOW 集的一部分

在 LR(1) 中,用

狀態, 終結符
例如:S' → # (#表示開始符號FOLLOW集會提到那個符號,有的地方用 $,是一樣的 )

這種形式是表式展望,終結符就是展望的后面的終結符,具體的下面例題中還會提到。

(七)終極例題 - LR(1) 分析表的構造

給定文法 G[S]:

S→L=R | R
L→*R | id
R→L

回答以下問題:

(1)文法的拓廣并編號
(2)LR(1) 項目集規范族所對應的識別活前綴的 DFA
(3)構造 LR(1) 分析表

解析:

1)文法的拓廣并編號:

拓廣文法 G[S']:

(0)S'→S
(1)S→L=R
(2)S→R
(3)L→*R
(4)L→id
(5)R→L

2)LR(1) 項目集規范族所對應的識別活前綴的 DFA*

這里就涉及到 “展望” 這個知識點了

向前搜索符的 FIRST 集求法:

求法 FIRST(βa)

  • β 表示由誰哪個非終結符推導的,這個非終結符的后面的剩余串
  • a 表示它上一個狀態中的向前搜索符。

對于 I0
首先 S' → .S, # 這個是固定的,就是第一個狀態的核心項目
下面對 S 求向前所有符都沒問題,都是 #
到了 L→.*R,這里,求向前搜索符,使用 FIRST(βa)
應該是求 FIRST(=R#) 所以就是 = 了

為什么是 =R#?

因為 β 表示由誰哪個非終結符推導的,這里就是上面狀態【S→.L=R, #】這個非終結符 L 的后面的剩余串是 =R,a 表示它上一個狀態中的向前搜索符,就是 #,拼接起來就是 =R#。

(圖片來源:中國大學慕課 -《編譯原理》哈爾濱工業大學 陳老師)

該 DFA 有窮自動機的解釋:

(1)這樣表示形式就是自動機,每個方框表示一個狀態,從 I0 到 I13 所以共有 14 個狀態。
(2)每個狀態中包含的多個項目,都是等價的。
(3)每個項目中逗號后面的終結符或者 # 表示展望的終結符。
(4)關于畫出 DFA 的步驟:

  • 以 I0 為例,首先對于 0 號產生式 S' → S,可知應該有 S' → .S 和 S' → S. 兩個狀態,因為 S' 是開始符號,展望是屬于 FOLLOW 集的,展望應該是 #,可以得出 S' → .S, #
  • 因為 .S 表示等待規約出 S 的狀態。并且 S→L=R,所以 .S 和 .L=R 是兩個等價的狀態。但需要注意的是此時的 FOLLOW 集應該 S 的 FOLLOW 集,而不是 L 的,也不 R 的
  • 同理,因為有 S→R,則 .S 和 .R 是兩個等價的狀態。
  • 有了 .R,應該繼續去找 R 為左部的產生式,因為有 R→L,所以 .S 和 .L 是兩個等價的狀態。
  • 注意: 在找 R 的展望終結符時,展望 是通過展望后面的內容,所以展望對應的終結符,應該 屬于該非終結符的 FOLLOW 集(確切的說,屬于 FOLLOW 集中的具體哪個個終結符,應該根據產生式的推導過程確定,通過語法樹來分析,是最直觀的方法)


(圖片來源:中國大學慕課 -《編譯原理》哈爾濱工業大學 陳老師)

可以看出來 R 的展望應該有兩種情況,一個是 =,一種是 #

但此時,我們通過 S → R 找到的 R,所以應該是 #

不斷循環通過,將 . 后移,判斷下一個狀態,找出等價狀態,直到判斷完成。

3)構造 LR(1) 分析表

根據自動機即可構造 LL(1) 分析表:


(圖片來源:中國大學慕課 -《編譯原理》哈爾濱工業大學 陳老師)

LL(1) 分析表解釋補充:

(1)內容 LL(1) 分析表 = 動作表 (ACTION) + 狀態轉移表(GOTO)

(2)動作表 中的每一個元素 ACTION[S,a] 規定了當 棧頂狀態 為 S,且面臨輸入符號 a 時應采取的動作。根據自動機中的終結符邊可判斷。

(3)狀態轉換表 中的每一個元素 GOTO[S,x] 規定了當狀態 S 面對文法符號位 x 時的下一個狀態。根據自動機中的非終結符邊可判斷。

(4)動作表 的列對應所有終結符加上 #

(5)狀態轉換表 的列對應所有非終結符,不包括 S',因為 S 就是開始符號,S' 是為了使 “接收狀態” 易于識別,所引入的。

(6)動作表 中例如:

  • ACTION[0, *] 的 S4 表示移進,入棧,就是當前狀態為 0,當輸入串為 ,則將狀態 4 移進狀態棧,將 移進文法符號棧
  • ACTION[5, =] 的 r4 表示符合產生式 4,將棧頂符號 id 規約為產生式左部
  • acc 表示接收

(7)狀態轉換表 中例如:

  • GOTO[0, S] 的 數字為 1 表示轉入 1 狀態,置當前文法符號棧頂為 S,棧頂狀態為 1

(8)構造 LL(1) 分析表的步驟,重要 !!!:

  • 確定對應行 ,行就是所有狀態
  • 確定對應列 ,列有兩部分 ACTION 表和 GOTO 表,ACTION 表中列是所有終結符,以及 #。 GOTO 表的對是所有非終結符,不包括 S'
  • !!!GOTO 表的構造:判斷當前輸入串,如果存在自動機的邊,且邊為非終結符就把狀態編號填入 GOTO 表
  • !!!ACTION 表的構造:

    • 查找該狀態中是否有 . 在最后的狀態,如果有先根據向前搜索符確定哪一列,再用 rn,填入表示,r 的含義是規約,n 表示的是產生式的序號;如果沒有則說明沒有沒有 r
    • 判斷是否存在該狀態輸出的邊,如果存在則用 Sn 表示,S 表示移進,入棧,n 表示下一個狀態的序號

(9)上面也更深入的了解了展望的意義,首先,展望是存在一個狀態中的,終結符,對應的應該為是當前等價的狀態,操作也就應該是移進。如果是自動機的邊,就是說不是當前狀態了,所以對應的是規約。


總結

易錯點:

  • 展望對應的終結符 是通過展望后面的內容,所以展望對應的終結符,應該 屬于該非終結符的 FOLLOW 集(確切的說,屬于 FOLLOW 集中的具體哪個個終結符,應該根據產生式的推導過程確定,通過語法樹來分析,是最直觀的方法)
  • 各教材描述可能存在差異,但思想是相同的
    • 比如 $ 和 #
    • 比如展望終結的表示方法,有的分開寫,有的直接用或
posted @ 2019-06-22 23:21 肖朋偉 閱讀(...) 評論(...) 編輯 收藏
内蒙古快3开奖结果