构造文法 G(E) : E → aE | bE | a ,的 LR(0)项目集规范族;(记得对文法进行增广)
时间: 2024-05-23 11:09:10 浏览: 145
LR(0).rar_LR(0)_构造它的LR(0)_项目集规范族
5星 · 资源好评率100%
好的,我明白了。对于文法 G(E):E → aE | bE | a,构造增广文法为 G’(E’):E’ → E,E → aE | bE | a$。
接下来,我们可以使用以下步骤构造 LR(0)项目集规范族:
1. 初始化第一个项目集{[E’ → .E]},并将其添加到项目集规范族中。
2. 对于每个项目集 I,以及每个文法符号 X,执行以下操作:
a. 针对每个项目[A → α.Xβ],将[B → .γ](B为任意文法符号,γ为任意文法符号串)添加到 I 中,其中 X = B。
b. 对于每个添加到 I 中的项目[B → .γ],计算闭包{[B → .γ]},并将其添加到 I 中。
c. 如果新的项目被添加到 I,则重复步骤 2 直到没有新的项目被添加为止。
3. 对于项目集规范族中的每个项目集 I,进行状态转移的操作:
a. 对于每个终结符 a,如果存在项目[A → α.aβ],将其加入到I的a后继状态中。
b. 对于每个非终结符 A,如果存在项目[A → α.Bβ],将{[B → .γ]}中的所有项目加入到I的B后继状态中。
4. 重复步骤 2 和 3,直到没有新的状态被添加到项集规范族为止。
根据以上步骤,我们可以得到项目集规范族:
I0:
[E’ → .E]
[E → .aE]
[E → .bE]
[E → .a]
I1:
[E’ → E.]
I2:
[E → a.E]
[E → .aE]
[E → .bE]
[E → .a]
I3:
[E → b.E]
[E → .aE]
[E → .bE]
[E → .a]
I4:
[E → aE.]
I5:
[E → bE.]
其中点号(.)表示在哪个位置加入新的符号,即表示尚未处理的部分在产生式右边中的位置。I0 是起始项目集,I1 是规范状态族中的唯一接受状态。接下来的 I2 到 I5 是状态转移操作从起始状态到接受状态的所有过渡状态。
阅读全文