B→B(B)| e 构造该拓广文法的LR(0)项目集规范族C;判断该文法是否为SLR(1)文法,说明理由。
时间: 2023-09-03 19:26:08 浏览: 60
### 回答1:
首先,拓广文法的产生式为 S' -> S,其中 S 为原文法的起始符号。将该文法进行拓广后,可以得到以下的拓广文法:
S' -> S
S -> B(B) | ε
然后,我们可以使用 LR(0) 项目集规范族构造该文法的 LR(0) 自动机。具体过程如下:
1. 构造初始项目集 I0:
S' -> .S
2. 根据 I0 中的项目,使用扩展规则扩展出其他项目集:
I0:
S' -> .S
S -> .B(B)
S -> .ε
I1:
S' -> S.
3. 对于每个项目集,根据文法中的符号进行状态转移,直到不能再进行状态转移为止:
I0:
S' -> .S
S -> .B(B)
S -> .ε
I1:
S' -> S.
S -> B.(B)
S -> .ε
I2:
S -> B(B).
4. 根据每个项目集中的项目,构造 LR(0) 自动机的状态和转移表:
状态 项目集 转移
--------------------------------------------
I0 S' -> .S go to I1
S -> .B(B)
S -> .ε
I1 S' -> S. accept
I2 S -> B(B). reduce by S -> B(B)
S -> .ε reduce by S -> ε
--------------------------------------------
接下来,我们需要判断该文法是否为 SLR(1) 文法。首先,构造该文法的 LR(0) 自动机的 ACTION 和 GOTO 表,如下所示:
状态 ACTION GOTO
--------------------------------------------
I0 B(B) -> shift to I2 S -> goto I3
ε -> accept
I1 $ -> accept
I2 ) -> reduce by S -> B(B) $ -> reduce by S -> B(B)
) -> reduce by S -> ε $ -> reduce by S -> ε
--------------------------------------------
由于该文法没有出现冲突,所以我们只需要检查每个状态的 FOLLOW 集是否满足 SLR(1) 文法的条件即可。对于该文法,可以得到 FOLLOW 集如下:
S' -> $
S -> ), $
可以发现,在状态 I0 中,存在冲突。因为在该状态下,ACTION 表中既有 shift 操作,又有 reduce 操作,而它们所对应的符号的 FOLLOW 集是相交的。因此,该文法不是 SLR(1) 文法。
综上所述,该文法不是 SLR(1) 文法。
### 回答2:
首先,我们先构造该拓广文法的LR(0)项目集规范族C。
拓广文法的初始项目为 S' → ·B,将该项目加入初始项目集 I0 中。
对于每个项目集 Ii,我们按照以下算法来扩展新的项目集:
1. 对于每个项目 A → α·Bβ,在 B 的非终结符的每个产生式 B → γ,添加新项目 B → ·γ。如果该项目是新的,则将其加入该项目集 Ii,并继续扩展该项目集。
2. 对于每个项目 A → α·,将该项目的闭包加入该项目集 Ii。
使用以上算法,我们可以扩展出所有的项目集,并得到该文法的LR(0)项目集规范族C。
接下来我们要判断该文法是否为SLR(1)文法。
对于SLR(1)文法,要求每个项目 A → α·Bβ 和终结符 a,都满足以下条件:
1. 若存在产生式 B → γ,则 FOLLOW(B) ∩ FIRST(βa) = ∅。
2. 若存在产生式 B → γ,且 ε ∈ FIRST(β),则 FOLLOW(B) ∩ FOLLOW(A) ≠ ∅。
其中,FOLLOW和FIRST集合的定义如下:
- FOLLOW(A):为文法中A的FOLLOW集合,表示在A的右侧可能出现的所有终结符。
- FIRST(β):为串β的FIRST集合,表示串β可能的首个终结符。
根据上述条件,我们来分析该文法的情况:
文法的产生式有:
1. B → B(B)
2. B → ε
根据第一个产生式,我们可以得到:
- FOLLOW(B) = {(), $}
- FIRST(B(B)) = {(}
所以,FOLLOW(B) ∩ FIRST(B(B)) = ∅。因此,第一个条件满足。
接下来,我们来判断第二个条件是否满足。
根据第一个产生式,ε ∈ FIRST(B(B))。 因此,FOLLOW(B) ∩ FOLLOW(B) ≠ ∅。所以,第二个条件也满足。
综上所述,该文法满足SLR(1)文法的要求。
注:请注意,由于题目给出的是非终结符 B 的产生式 B → B(B),所以在判断 FOLLOW(B) 时,我们需要考虑 B(B) 的 FIRST 集合。在判断 FOLLOW(A) 时,由于文法中只有产生式 A → B,所以我们没有必要判断 FOLLOW(A) ∩ FOLLOW(A) ≠ ∅。
### 回答3:
对于拓广文法B'→B,首先构造该文法的LR(0)项目集规范族C:
C0:
B'→.B
B→.B(B)
B→.e
C1:
B'→B.
C2:
B→B.(B)
B→.B(B)
B→.e
C3:
B→B(B.)
C4:
B→B(B). (结束态)
接下来判断该文法是否为SLR(1)文法:
1. 首先判断每个项目集的分析动作是否唯一:
- C0中,B'→.B后面可以跟B'→B,即移进动作;B→.B(B)后面可以跟B→B(B),即移进动作;
- C1中,B'→B.后面可以跟#,即接受动作;
- C2中,B→B.(B)后面可以跟B→B(B),即规约动作;B→.B(B)后面可以跟B→B(B),即移进动作;
- C3中,B→B(B.)后面可以跟),即规约动作;
- C4中,B→B(B).后面可以跟),即规约动作。
由此可见,每个项目集的分析动作都是唯一的。
2. 再判断归约-规约冲突:
- C2中的B→B.(B)后面可以跟),表示可以进行B→B(B)的规约;而在C3中,B→B(B.)后面也可以跟),表示可以进行B→B(B)的规约。这样就存在归约-规约冲突。
综上所述,该文法不是SLR(1)文法。原因是它存在归约-规约冲突。