資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究檢查使用示例中構建的 SLR 分析表，字串 id * id + id 是否被接受。
解決方案
最初，LR 分析器處於狀態 0。
在字串末尾新增 $，即 id * id + id $。
| 棧 | 輸入字串 | 原因 |
|---|---|---|
| 0 | id ∗ id + id $ | Action [0, id] = s5 ∴ 移入 id 和狀態 5 |
| 0 id 5 | ∗ id + id $ | Action [5,∗] = r6. ∴ 根據 F → id 進行歸約。goto(0, F) = 3 |
| 0 F 3 | ∗ id + id $ | Action [3,∗] = r4, 根據 T → F 進行歸約。goto(0, T) = 2 |
| 0 T 2 | ∗ id + id $ | Action [2,∗] = s7, 移入 ∗，7 |
| 0T2*7 | id + id $ | Action [7, id] = s5, 移入 id，5 |
| 0T2*7 id 5 | +id $ | Action [5, +] = r6, 根據 F → id 進行歸約。goto(7, F) = 10 |
| 0T2*7 F 10 | +id $ | Action [10, +] = r3S, 根據 T → T ∗ F 進行歸約，goto(0, T) = 2 |
| 0 T 2 | +id $ | Action [2, +] = r2, 根據 E → T 進行歸約。goto(0, E) = 1 |
| 0 E 1 | +id $ | Action [1, +] = s6, 移入 +，6 |
| 0 E 1 + 6 | id $ | Action [6, id] = s5, 移入 id，5。 |
| 0 E 1 + 6 id 5 | $ | Action [5, $] = s6, 根據 F → id 進行歸約，goto(6, F) = 3 |
| 0 E 1 + 6 F 3 | $ | Action [3, $] = r4, 根據 T → F 進行歸約，goto(6, F) = 9 |
| 0 E 1 + 6 T 9 | $ | Action [9, $] = r1, 根據 E → E + T 進行歸約，goto(0, E) = 1 |
| 0 E 1 | $ | Action [1, $] = accept |
在第一行，棧頂為 0，要處理的符號為 id。因此，檢查第 0 行和 id 列，即 Action [0, id] = s5，即從字串中移入 id 和狀態 5 到棧中。
在第二行，Action [5, *] = r3 表示根據產生式編號 6（即 F → id）進行歸約。從棧中彈出 id 並壓入 F。然後檢視 goto (0, F) = 3，所以將 3 壓入棧中。在第七行，Action [10, +] = r3，即根據產生式編號 3（即 T → T ∗ F）進行歸約。
從棧中彈出T2 * 7F10，將 T 壓入棧中。然後檢視 goto [0, T] = 2。所以，將 2 壓入棧中。在最後一行，Action [1, $] = accept。這意味著分析器將接受該字串。
SLR 分析表的演算法
SLR 分析表有兩個部分
- Action（動作）
- goto（轉移）
可以使用以下演算法填充 Action 和 goto 表：
演算法
輸入 - 增廣文法 G′
輸出 - SLR 分析表
方法
- 最初構造一組專案
C = {I0, I1, I2 … … In}，其中 C 是文法的 LR (0) 專案集。
- 解析動作基於每個專案或狀態 I1。
各種動作如下：
- 如果 A → α ∙ a β 存在於 Ii 中，並且 goto (Ii, a) = Ij，則設定 Action [i, a] = shift j”。
- 如果 A → α ∙ 存在於 Ii 中，則對所有符號 a 設定 Action [i, a] 為“reduce A → α”，其中 a ∈ FOLLOW (A)。
- 如果 S′ → S ∙ 存在於 Ii 中，則動作表 Action [i, $] 中的條目為“accept”。
- SLR 表的 goto 部分可以填充如下：狀態 i 的 goto 轉移僅考慮非終結符。如果 goto (Ii, A) = Ij，則 goto [i, A] = j
- 所有未由規則 2 和 3 定義的條目都被視為“錯誤”。
更新於：2021 年 11 月 8 日
2K+ 次瀏覽
廣告