資料結構
網路
關係資料庫管理系統(RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究(c) 解析輸入字串 id + id * id。
解答
步驟1 - 構造增廣文法
(0) E′ → S
(1) E → E + E
(2) E → E ∗ E
(3) E → (E)
(4) E → id
步驟2 - 查詢閉包和 goto 函式以構造 LR(0) 專案。
Closure(E′ → ∙ E) =
在 I9 上應用 goto
∵ 在 I9 上無法應用 goto，因為 E → (E). 中的點位於最後一個位置。
步驟3 - FOLLOW 的計算
應用規則 (1) FOLLOW
FOLLOW(B) = {$} (1)
- E → E + E
將 E → E + E 與 A → αBβ 比較
∴ α = ε，B = E，β = +E
∵ FIRST(β) = FIRST(+E) = {+}
∴ FOLLOW 的規則 (2a)
FOLLOW(E) = {+} (2)
應用規則 (3)
將 E → E + E 與 A → αB 比較
∴ A = E，α = E+，B = E
FOLLOW(E) = {FOLLOW(E)} (3)
- E → E ∗ E
應用 FOLLOW 的規則 (2) 和規則 (3)，我們得到
FOLLOW(E) = {*} (4)
FOLLOW(E) = {FOLLOW(E)} (5)
- E → (E)
應用規則 (2)
將 E → (E) 與 A → αBβ 比較
∴ FOLLOW(E) = {)} (6)
規則 (3) 無法應用於此產生式
因為 E → (E) 無法與 A → αB 比較
- E → id
FOLLOW 的規則 (2) 和 (3) 無法應用於 E → id。因為 E → id 無法與 A → αBβ 和 A → αB 比較。
組合 (1) 到 (6)，我們得到
FOLLOW(E) = {$, +, *, )}
步驟4 - 構造 SLR 解析表
在解析表中，衝突發生在第 7 行、第 8 行和列 *、+。
在 Action[7, +]， Action[7, *]
Action[8, +]， Action[8, *] 出現移進-歸約衝突。
結合性和優先順序規則可以消除此衝突。
解析字串 id + id * id
| 棧 | 輸入 | 動作 |
|---|---|---|
| 0 | id + id * id $ | 移進 |
| 0 id 3 | + id * id $ | 根據 E → id 歸約 |
| 0 E 1 | +id * id $ | 移進 |
| 0 E 1 + 4 | id * id $ | 移進 |
| 0 E 1 + 4 id 3 | * id $ | 根據 E → id 歸約 |
| 0 E 1 + 4 E 7 | * id $ | 衝突，即 s5 或 r1 ∴ * 的優先順序高於 + ∴ Action[7,*] = s5 所以，移進-歸約，即 s5 |
| 0 E 1 + 4 E 7 * 5 | $ | 移進 |
| 0 E 1 + 4 E 7 * 5 id 3 | $ | 根據 E → id 歸約 |
| 0 E 1 + 4 E 7 * 5 E 8 | $ | 根據 E → E * E 歸約 |
| 0 E 1 + 4 E 7 | $ | 根據 E → E + E 歸約 |
| 0 E 1 | $ | 接受 |
上述解析解決了 Action[7, *] 中的衝突問題。
所以，Action[7, *] = s5 而不是 r1。
類似地，解析字串 id + id + id。
| 棧 | 輸入 | 動作 |
|---|---|---|
| 0 | id + id + id $ | 移進 |
| 0 id 3 | + id + id $ | 根據 E → id 歸約 |
| 0 E 1 | +id + id $ | 移進 |
| 0 E 1 + 4 | id + id $ | 移進 |
| 0 E 1 + 4 id 3 | +id $ | 根據 E → id 歸約 |
| 0 E 1 + 4 E 7 | +id $ | 衝突，即 Action[7, +] = s4 或 r1。∴ + 是左結合的。0E1 + 4E7 將在移進 + 之前歸約 ∴ Action[7, +] = r1 ∴ 根據 E → E + E 歸約 |
| 0 E 1 | +id $ | 移進 |
| 0 E + 4 | id $ | 移進 |
| 0 E + 4 id 3 | $ | 根據 E → id 歸約 |
| 0 E + 4 E 7 | $ | 根據 E → E + E 歸約 |
| 0 E 1 | $ | 接受 |
因此，上述解析展示瞭如何解決 Action[7, +] 處的移進歸約衝突
所以，Action[7, +] = r1 而不是 s4
類似地，其他條目，例如 Action[8, +] 和 Action[8, *] 可以透過採用字串來解決。
id * id * id 和 id * id + id
解決方案是 Action[8, +] = r2 和
Action[8, *] = r2。
5K+ 次瀏覽
