資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學什麼是 LR 解析器？
LR 解析器是一種自底向上解析器，用於解析上下文無關文法。LR 解析通常被稱為 LR(K) 解析，其中
- L 代表從左到右掃描輸入
- R 代表最右推導
- K 是用於制定解析決策的向前檢視的輸入符號數。
LR 解析器是一種移進-規約解析器，它利用確定性有限自動機，透過從底部到頂部讀取棧來識別所有可行的字首。
它決定哪個控制代碼（如果有的話）是可行的。右句型的一個可行字首是指包含控制代碼但控制代碼右邊沒有符號的字首。
因此，如果構建了一個識別右句型可行字首的有限狀態機，它可以用來指導移進規約解析器中的控制代碼選擇。
因為 LR 解析器使用 DFA 來識別可行字首以管理控制代碼的選擇，所以它必須跟蹤 DFA 的狀態。因此，LR 解析器棧包含兩種型別的符號——狀態符號可以識別 DFA 的狀態，而語法符號則表示文法符號。
解析器從 DFA 的初始狀態 I0 開始，位於棧頂。解析器透過考慮下一個輸入符號 'a' 和棧頂的狀態符號 Ii 來工作。
如果在 DFA 中存在從狀態 Ii 到 'a' 的轉移到狀態 Ij，則符號 a 後跟狀態符號 Ij 推入棧中。
如果在 DFA 中不存在從 Ii 到 a 的轉移，並且棧頂的狀態 Ii 標識一個可行字首，該字首包含控制代碼 A → a，則解析器透過彈出 α 並將 A 推入棧來進行規約。
這類似於在 DFA 中從 Ii 到 α 進行反向轉移，然後在 A 上進行正向轉移。解析器的每個移進操作都對應於 DFA 中對終端符號的轉移。
因此，DFA 的當前狀態和下一個輸入符號決定了解析器是移進下一個輸入符號還是進行規約。
如果可以生成一個表，將每個狀態和輸入符號對對映為“移進”、“規約”、“接受”或“錯誤”之一，則可以得到一個用於管理解析階段的表。這樣的表被稱為解析“動作”表。
更新於：2021年11月1日
2K+ 次瀏覽
廣告