数据结构
网络
关系数据库管理系统 (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+ 次浏览
