输入文法,输出规范LR的LR(1)项目集规范族以及对应的规范LR分析表 算法思路
时间: 2024-06-02 07:12:40 浏览: 17
算法思路:
1. 构造文法的增广文法,并将其转化为LR(0)项目集规范族。
2. 对LR(0)项目集规范族进行扩展,得到LR(1)项目集规范族。
3. 为每个LR(1)项目集规范族构造对应的规范LR分析表。
具体步骤如下:
1. 构造增广文法
将文法的起始符号S添加到右部,构造增广文法。即:
S' -> S
S -> ...
2. 构造LR(0)项目集规范族
首先,构造初始项目集,即包含S' -> .S的项目集I0。
然后,对于每个项目集I,找出其中每个项目A -> α.Bβ,对于B的每个可能的后继符号a,构造新的项目B -> .γ,其中γ是从Bβ中移除所有可能的空产生式后,加上a后的结果。
将所有新生成的项目加入到I中,得到新的项目集I'。
重复以上步骤,直到项目集不再增加。
最终得到的所有项目集构成LR(0)项目集规范族。
3. 构造LR(1)项目集规范族
对于每个LR(0)项目集规范族I,以及其中的每个项目A -> α.Bβ,对于B的每个可能的后继符号a和α的每个前缀α',构造新的项目[A, α'] -> α'.B.aβ。
将所有新生成的项目加入到I中,得到新的项目集I'。
重复以上步骤,直到项目集不再增加。
最终得到的所有项目集构成LR(1)项目集规范族。
4. 构造规范LR分析表
对于每个LR(1)项目集规范族I,以及其中的每个项目[A, α'] -> α'.B.aβ,根据B所在的状态和a所在的终结符号,在对应的分析表中填写动作或转移。
具体来说,如果B是非终结符号,则在对应的状态下填写一个转移,转移的目标状态是包含[B, a]的LR(1)项目集规范族;如果B是终结符号,则在对应的状态下填写一个规约动作,规约的产生式是[B -> β],其中β是从α'.B.aβ中移除所有可能的空产生式后的结果。
最终得到的分析表即为规范LR分析表。
以上就是构造规范LR分析表的算法思路。
相关推荐
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![py](https://img-home.csdnimg.cn/images/20210720083646.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)