编译原理四种文法的判断(LR(0),SLR(1),LALR(1),LR(1))
米西米西米老鼠
编辑于 2023年12月27日 06:49

1.LR(0)文法

  • 判断LR(0)文法的关键是构造一个LR(0)项目集族和相应的状态转移图。

  • 检查是否存在移进-归约冲突或归约-归约冲突。如果没有冲突,该文法是LR(0)。

2.SLR(1)文法(简化的LR(1)文法):

  • 首先构造LR(0)项目集族和状态转移图。

  • 使用文法的FOLLOW集合来帮助决定在哪些状态上进行归约操作。

  • 如果在任何状态下,对于任何输入符号,都只有一个明确的动作(移进或归约),则文法是SLR(1)。

3.LR(1)文法

  • 构造LR(1)项目集族和相应的状态转移图。LR(1)项目包括LR(0)项目以及一个向前看符号。

  • 检查是否存在移进-归约冲突或归约-归约冲突。如果没有冲突,该文法是LR(1)。

4.LALR(1)文法(查找-前的LR(1)文法):

  • 首先构造LR(1)项目集族和状态转移图。

  • 合并那些核心项目相同但向前看符号不同的状态,从而得到一个更小的状态集。

  • 检查合并后的状态集中是否存在冲突。如果没有冲突,文法是LALR(1)。