设有如下文法 G: <S>—>a<S><S>b <S>—>a<S><S><S> <S>—>c (1)计算该文法的LR(0)项目集规范族,构造识别相应文法的所有规范句型活前缀的 DFA。 (2)该文法是LR(0)文法吗?若是,给出其LR(0)分析表。 给出计算过程
时间: 2024-06-02 20:05:58 浏览: 30
(1)计算该文法的LR(0)项目集规范族,构造识别相应文法的所有规范句型活前缀的 DFA。
首先计算该文法的所有LR(0)项目:
```
I0:
S' -> ·S
S -> ·aSSb
S -> ·aSSS
S -> ·c
I1:
S' -> S·
I2:
S -> a·SSb
S -> a·SSS
I3:
S -> c·
I4:
S -> aS·Sb
S -> aS·SSS
I5:
S -> aSS·b
S -> aSS·S
I6:
S -> aSSb·
```
然后构造该文法的LR(0)项目集规范族:
```
I0:
S' -> ·S
S -> ·aSSb
S -> ·aSSS
S -> ·c
I1:
S' -> S·
I2:
S -> a·SSb
S -> a·SSS
I3:
S -> c·
I4:
S -> aS·Sb
S -> aS·SSS
I5:
S -> aSS·b
S -> aSS·S
I6:
S -> aSSb·
```
接下来,我们需要构建该文法的DFA,来识别所有规范句型的活前缀。构建方法如下:
- 令初始状态为 I0。
- 对于每个状态,对其中所有LR(0)项目的点后面跟着的符号进行分类,每种符号对应一个转移状态。对于同一符号,如果它对应的状态之前已经出现过,那么就不需要新建状态了。直到所有的状态没有新的转移出现为止。
- 在DFA中,用状态编号表示状态,用圆圈表示状态。对于每个状态,如果它包含一个由非终结符开头的LR(0)项目,则把这个非终结符画在圆圈中间。如果它包含一个由终结符开头的LR(0)项目,则不需要在圆圈中间画任何东西。
- 对于每条从状态 i 到状态 j 的转移,标上转移条件。
最终得到DFA如下:
![LR(0)DFA](https://img-blog.csdnimg.cn/20211020101144951.png)
根据DFA中每个状态的可归约性,可以得到该文法是SLR(1)文法。
(2)该文法是LR(0)文法吗?若是,给出其LR(0)分析表。
该文法不是LR(0)文法。因为状态I4存在移入-归约冲突,所以不能构造出LR(0)分析表。
相关推荐
![application/pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![application/msword](https://img-home.csdnimg.cn/images/20210720083327.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![application/msword](https://img-home.csdnimg.cn/images/20210720083327.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)