資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學在編譯器設計中，LR(0)專案的規範集合是什麼？
對於文法G，LR(0)專案由一個產生式組成，在這個產生式中，符號點(.)被插入到產生式右部的某個位置。
例如 - 對於產生式S → ABC，生成的LR(0)專案將是：
S →∙ ABC
S → A ∙ BC
S → AB ∙ C
S → ABC ∙
產生式S → ε只生成一個專案，即S →∙
規範LR(0)集合有助於構建稱為簡單LR(SLR)分析器的LR分析器。
要為文法建立規範LR(0)集合，需要三樣東西：
- 增廣文法
- 閉包函式
- goto函式
增廣文法 - 如果文法G的開始符號是S，則增廣文法是一個新的文法G'，它有一個新的開始符號S'。它還將包含產生式S' → S。
閉包 - 對於上下文無關文法G，如果I是文法G的專案或狀態集，則：
I中的每個專案都在closure(I)中。
如果規則A → α.Bβ是closure(I)中的一個規則，並且B有另一個規則B → γ，則closure(I)將包含A → α.Bβ和B → .γ
閉包的計算
過程closure(I)
- 開始
- 重複
- 對於I中的每個規則A→α∙Bβ和G中的B→γ
- 將B→∙γ新增到I
- 直到無法再向I新增元素；
- 結束
- goto(I,X)：如果I中存在產生式A→α∙Xβ，則goto(I,X)定義為A→αX∙β專案的集合的閉包，其中I是專案集，X是文法符號（非終結符）。
構造LR(0)專案規範集合的演算法
- 開始
- C = {closure(S′ → ∙ S)}
- 重複
- 對於C中的每個元素集I和每個文法符號X，使得goto(I, X)不為空且不在C中
- 新增goto(I, X)到C
- 直到無法再向C新增元素集
- 結束
示例 - 考慮文法
B → Ba | b
求closure(I)和goto(I)
解答
設B →∙ Ba
由於點後出現B。因此，將把左部為B且右部開頭有點的其他產生式新增到閉包中，即，B →∙ B也新增到closure(I)。
∴ Closure(I) 將是 B → ∙ Ba (1)
B → ∙ b (2)
因為點後在(1)中我們有B
∴ goto(I, B) 將是 B → B ∙ a
因為點後在(2)中我們有b
∴ goto(I, b) 將是 B → b ∙
5K+ 次瀏覽
