设有如下文法 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 15:05:58 浏览: 33
(1)首先计算该文法的LR(0)项目集规范族:
I0:
<S>' -> .<S>
<S> -> .a<S><S>b
<S> -> .a<S><S><S>
<S> -> .c
I1:
<S>' -> <S>.
I2:
<S> -> a.<S><S>b
<S> -> .a<S><S>b
<S> -> .a<S><S><S>
<S> -> .c
I3:
<S> -> a<S>.<S>b
<S> -> .a<S><S>b
<S> -> .a<S><S><S>
<S> -> .c
I4:
<S> -> a<S><S>.b
<S> -> .a<S><S>b
<S> -> .a<S><S><S>
<S> -> .c
I5:
<S> -> a<S><S><S>.
I6:
<S> -> a<S>.<S><S>b
<S> -> .a<S><S>b
<S> -> .a<S><S><S>
<S> -> .c
I7:
<S> -> a<S><S>b.
I8:
<S> -> a<S><S><S>.
I9:
<S> -> a<S><.S>b
<S> -> .a<S><S>b
<S> -> .a<S><S><S>
<S> -> .c
I10:
<S> -> a<S><.S><S>
I11:
<S> -> a<S><.S>b
I12:
<S> -> a<S><<.S>b
<S> -> a<S>.<S>b
I13:
<S> -> a<S><<.S><S>
I14:
<S> -> a<S><<.S>b
I15:
<S> -> a<S><<.S><S>
I16:
<S> -> a<S><<.<S>>b
I17:
<S> -> a<S><<.<S>>b
I18:
<S> -> a<S><<.<S>>b
然后我们可以根据这个项目集规范族构造出识别该文法的所有规范句型活前缀的 DFA,具体构造过程见下图:
![image.png](https://cdn.nlark.com/yuque/0/2021/png/97322/1623005783898-5dcf-4d43-af2d-83f9335bb7e2.png#align=left&display=inline&height=394&margin=%5Bobject%20Object%5D&name=image.png&originHeight=788&originWidth=890&size=54815&status=done&style=none&width=445)
(2)接下来判断该文法是否为LR(0)文法。我们可以根据LR(0)自动机的状态转移表来判断是否存在冲突。由于状态转移表较大,这里不方便展示。我们可以看到,在状态I4中存在归约-移进冲突,因此该文法不是LR(0)文法。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.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)