LR(0)项目是产品G, 在产品右侧的某个位置带有点。
【LR(0)项的规范集合】LR(0)项用于指示在解析过程中, 已扫描了多少输入直到给定点。
在LR(0)中, 将reduce节点放置在整行中。
例
给定语法:
S → AAA → aA | b
添加增广产品并在G的每个产品的第一个位置插入“?”符号
S` → ?SS → ?AAA → ?aA A → ?b
I0状态:
将增产增加到I0状态并计算关闭
I0 =闭合(S`→?S)
将所有以S开头的产品添加到I0状态, 因为“?”后跟非终结符。因此, I0状态变为
I0 = S`→?S S→?AA
在修改后的I0状态中添加所有以“ A”开头的产品, 因为“?”后跟非终结符。因此, I0状态变为。
I0 = S`→?S S→?AA A→?aAA A→?b
I1 =转到(I0, S)=闭包(S`→S?)= S`→S?
在这里, 产量减少了, 所以状态接近了。
I1 = S`→S?
I2 =转到(I0, A)=闭包(S→A?A)
将所有以A开头的产品添加到I2状态, 因为“?”后跟非终结符。因此, I2状态变为
I2 = S→A?A A→?aA A→?b
转到(I2, a)=闭包(A→a?A)=(与I3相同)
转到(I2, b)=闭包(A→b?)=(与I4相同)
I3 =转到(I0, a)=闭包(A→a?A)
在I3中添加以A开头的作品。
A→a?A A→?aAA A→?b
转到(I3, a)=闭合(A→a?A)=(与I3相同)转到(I3, b)=闭合(A→b?)=(与I4相同)
I4 =转到(I0, b)=闭合(A→b?)= A→b?I5 =转到(I2, A)=闭合(S→AA?)= SA→A?I6 =转到(I3 , A)=闭合(A→aA?)= A→aA?
绘图DFA:
DFA包含7个状态I0至I6。
文章图片
LR(0)表
- 如果某个状态将要在终端上变为其他状态, 则它对应于换档。
- 如果一个状态将要在变量上移至其他状态, 则它对应于移动。
- 如果状态包含特定行中的最后一项, 则完全写入reduce节点。
文章图片
说明:
- S上的I0即将变为I1, 因此将其写为1。
- A上的I0即将到达I2, 因此将其写为2。
- A上的I2即将到达I5, 因此将其写为5。
- A上的I3将转到I6, 因此将其写为6。
- Ia上的I0, I2和I3将转到I3, 因此将其写为S3, 这意味着移位3。
- b上的I0, I2和I3将转到I4, 因此将其写为S4, 这意味着移位4。
- I4, I5和I6所有状态都包含最后一项, 因为它们在最右端包含?。因此, 将生产定为生产数量。
S→AA... (1)A→aA... (2) A→b... (3)
- I1包含驱动的最终项目(S`→S?), 因此操作{I1, $} =接受。
- I4包含驱动A→b?的最后一项, 并且生产对应于生产编号3, 因此在整行中将其写为r3。
- I5包含驱动S→AA?的最后一项, 并且生产对应于生产编号1, 因此在整行中将其写为r1。
- I6包含驱动A→aA?的最后一项, 并且该生产对应于生产编号2, 因此在整行中将其写为r2。