SLR、CLR和LALR解析器|集3

在本文中，我们将讨论自底向上解析器的组成部分SLR解析器、CLR解析器和LALR解析器。 单反解析器 SLR解析器与LR（0）解析器类似，只是简化了条目。减少的生产量只写在生产量减少的变量的后面。 SLR解析表的构建-

1. 构造C={I ₀ 我 _1. , ……. 我 _N }，G’的LR（0）项集合。
2. 第一州由第二州构成。状态i的解析操作确定如下：
   • 如果[A->？.A？]在我 _我 和GOTO（我 _我 a）=I _J ，然后将动作[i，a]设置为“移位j”。这里一定是终点站。
   • 如果[A->？.]在我 _我 ，然后将操作[i，a]设置为“减少a->？”所有的a都在后面（a）；这里A可能不是S。
   • 是[S->S.]在I中 _我 ，然后将操作[i，$]设置为“接受”。如果上述规则产生了任何冲突行为，我们说该语法不是SLR。
3. 使用以下规则为所有非终端A构造状态i的goto转换： 如果GOTO（我） _我 A）=I _J 然后GOTO[i，A]=j。
4. 规则2和规则3未定义的所有条目都会出错。

如： 如果在解析表中有多个条目，则称为冲突。

Consider the grammar E -> T+E | T
                     T ->id
    Augmented grammar - E’ -> E
                E -> T+E | T
                T -> id

附注1 –对于GATE，我们不必绘制表格，在GOTO图中，只需查找一个状态中同时发生的reduce和shift。。在两个缩减的情况下，如果两个缩减产品的后续内容有共同之处，则会导致表中出现多个条目，因此不是SLR。在一次换班和一次减产的情况下，如果在减产后的终端上从该状态进行转到操作，则会导致多个条目，因此不是SLR。 附注2 –每一个单反语法都是明确的，但它们都有许多不是单反的明确语法。 CLR解析器

在SLR方法中，我们使用的是LR（0））项。在CLR解析中，我们将使用LR（1）项。LR（k）项被定义为使用长度为k的lookahead的项。因此，LR（1）项由两部分组成：LR（0）项和与该项相关的lookahead。 LR（1）解析器是更强大的解析器。 对于LR（1）项，我们修改了闭包和转到函数。 关闭操作

Closure(I)
repeat 
    for (each item [ A -> ?.B?, a ] in I )
        for (each production B -> ? in G’)
          for (each terminal b in FIRST(?a))
            add [ B -> .? , b ] to set I;
until no more items are added to I;
return I;

让我们用一个例子来理解它——

转到操作

Goto(I, X)
Initialise J to be the empty set;
for ( each item A -> ?.X?, a ] in I )
    Add item A -> ?X.?, a ] to se J;   /* move the dot one step */
return Closure(J);    /* apply closure to the set */

例如- LR（1）项目

Void items(G’)
Initialise C to { closure ({[S’ -> .S, $]})};
Repeat
    For (each set of items I in C)
        For (each grammar symbol X)
            if( GOTO(I, X) is not empty and not in C)
                Add GOTO(I, X) to C;
Until no new set of items are added to C;

GOTO图的构造

• 第一州 ₀ -关闭增强LR（1）项目。
• 使用I ₀ 在DFA的帮助下查找所有LR（1）项集合
• 将DFA转换为LR（1）解析表

解析表的构造- 输入–增广语法G’

1. 构造C={I ₀ 我 ₁ , ……. 我 _N }，G’的LR（0）项集合。
2. 第一州由第二州构成。状态i的解析操作确定如下： i） 如果[A->？.A？，b]在i中 _我 和GOTO（我 _我 a）=I _J ，然后将动作[i，a]设置为“移位j”。这里一定是终点站。 ii）如果[A->？，A]在I中 _我 A.≠ S、 然后将操作[i，a]设置为“减少a->？”。 iii）是[S->S，$]是在I中 _我 ，然后将操作[i，$]设置为“接受”。 如果上述规则产生了任何冲突行为，我们称其语法为 不是CLR。
3. 状态i的goto转换是使用以下规则为所有非终端A构造的：if goto（i _我 A）=I _J 然后GOTO[i，A]=j。
4. 规则2和规则3未定义的所有条目都会出错。

如：

Consider the following grammar 
    S -> AaAb | BbBa
    A -> ?
    B -> ?
    Augmented grammar - S’ -> S
                  S -> AaAb | BbBa
                  A -> ?
                  B -> ?
    GOTO graph for this grammar will be - 

笔记 –如果一个状态有两个缩减，并且都具有相同的前瞻性，那么它将在解析表中的多个条目中出现冲突。如果一个状态有一个归约，并且它们在一个终端上与归约的前向状态相同，那么它将导致解析表中的多个条目发生冲突。 LALR解析器 LALR解析器与CLR解析器相同，但有一个区别。在CLR解析器中，如果两个状态仅在前瞻中不同，那么我们将在LALR解析器中合并这些状态。最小化后，如果解析表没有冲突，语法也是LALR。 如：

consider the grammar S ->AA
                     A -> aA | b
    Augmented grammar - S’ -> S
                        S ->AA
                        A -> aA | b

重要提示 1.即使CLR解析器没有RR冲突，但LALR可能包含RR冲突。 2.如果状态数LR（0）=n1， 状态数SLR=n2， 状态数LALR=n3， 状态数CLR=n4， n1=n2=n3<=n4

本文由 帕鲁尔·夏尔马