LR(1)-разбор — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 70: Строка 70:
 
Добавим в пункт второй компонент: терминальный символ. Таким образом, LR(1)-ситуации будут выглядеть следующим образом:  
 
Добавим в пункт второй компонент: терминальный символ. Таким образом, LR(1)-ситуации будут выглядеть следующим образом:  
  
$[A\rightarrow\alpha\cdot\beta, a]$, где первая часть - продукция, а вторая - терминал или маркер конца входной строки $\char36$. Здесь $a$ называется '''предпросмотром''' (англ. ''lookahead'') ситуации, а число 1 в LR(1) означает его длину.
+
$[A\rightarrow\alpha\cdot\beta, a]$, где первая часть {{---}} продукция, а вторая {{---}} терминал или маркер конца входной строки $\char36$. Здесь $a$ называется '''предпросмотром''' (англ. ''lookahead'') ситуации, а число 1 в LR(1) означает его длину.
Теперь мы будем выполнять свёртку в соответствии с продукцией $A\rightarrow\alpha$, только в том случае, если находимся в ситуации $[A\rightarrow\alpha\cdot\beta, a]$ и $a$ - входной символ.
+
Теперь мы будем выполнять свёртку в соответствии с продукцией $A\rightarrow\alpha$, только в том случае, если находимся в ситуации $[A\rightarrow\alpha\cdot\beta, a]$ и $a$ {{---}} входной символ.
 
{{Определение
 
{{Определение
 
|id=defValid  
 
|id=defValid  
Строка 83: Строка 83:
 
=== Построение множеств LR(1)-ситуаций ===
 
=== Построение множеств LR(1)-ситуаций ===
 
<wikitex>
 
<wikitex>
Метод построения похож на метод для $LR(0)$ - разбора, с двумя изменёнными функциями: $CLOSURE(I)$ - замыкание множества пунктов, и $GOTO(X,I)$ - функция переходов в автомате по символу $X$.
+
Метод построения похож на метод для $LR(0)$-разбора, с двумя изменёнными функциями: $closure(I)$ {{---}} замыкание множества пунктов, и $GOTO(X,I)$ {{---}} функция переходов в автомате по символу $X$.
 
{{Лемма
 
{{Лемма
 
|id=lemmaclosure  
 
|id=lemmaclosure  
|statement= $$\forall{b} | b\in FIRST(\beta\alpha): [A\rightarrow\alpha\cdot B\beta, a]\in I\Rightarrow [B\rightarrow\cdot\gamma, b]\in CLOSURE(I)$$
+
|statement= $$\forall{b} | b\in FIRST(\beta\alpha): [A\rightarrow\alpha\cdot B\beta, a]\in I\Rightarrow [B\rightarrow\cdot\gamma, b]\in closure(I)$$
 
Другими словами, при построении замыкания вторая часть добавленных пунктов должна принадлежать $FIRST(\beta\alpha)$
 
Другими словами, при построении замыкания вторая часть добавленных пунктов должна принадлежать $FIRST(\beta\alpha)$
 
|proof= Рассмотрим пункт вида $[A\rightarrow\alpha\cdot B\beta, a]$ в множестве пунктов, допустимых для некоторого активного префикса $\gamma$. Тогда существует правое порождение $S\Rightarrow^{*}\delta Aax\Rightarrow\delta\alpha B\beta ax$, где $\gamma=\delta\alpha$. Предположим, что $\beta ax$ порождает строку терминалов $by$. Тогда для каждой продукции вида $\forall{B\rightarrow\eta}\exists{\eta}$ мы имеем порождение $ S\Rightarrow^{*}\delta Bby\Rightarrow\delta\eta by$. Таким образом, $[B\rightarrow\cdot\eta,b]$ является допустимым для $\gamma$. Заметим, что $b$ может быть первым терминалом, порожденным из $\beta$, либо, возможно что $\beta$ порождает $\epsilon$ слева: $\beta ax\Rightarrow^{*}by$, следовательно $b=a$. Таким образом, $b\in FIRST(\beta ax)$. Поскольку $x$ не может содержать первый терминал из $by$, то $FIRST(\beta ax)=FIRST(\beta a)$
 
|proof= Рассмотрим пункт вида $[A\rightarrow\alpha\cdot B\beta, a]$ в множестве пунктов, допустимых для некоторого активного префикса $\gamma$. Тогда существует правое порождение $S\Rightarrow^{*}\delta Aax\Rightarrow\delta\alpha B\beta ax$, где $\gamma=\delta\alpha$. Предположим, что $\beta ax$ порождает строку терминалов $by$. Тогда для каждой продукции вида $\forall{B\rightarrow\eta}\exists{\eta}$ мы имеем порождение $ S\Rightarrow^{*}\delta Bby\Rightarrow\delta\eta by$. Таким образом, $[B\rightarrow\cdot\eta,b]$ является допустимым для $\gamma$. Заметим, что $b$ может быть первым терминалом, порожденным из $\beta$, либо, возможно что $\beta$ порождает $\epsilon$ слева: $\beta ax\Rightarrow^{*}by$, следовательно $b=a$. Таким образом, $b\in FIRST(\beta ax)$. Поскольку $x$ не может содержать первый терминал из $by$, то $FIRST(\beta ax)=FIRST(\beta a)$
Строка 94: Строка 94:
 
====Псевдокод====
 
====Псевдокод====
 
<wikitex>
 
<wikitex>
Псевдокод построения множеств $CLOSURE$ и $GOTO$, а также множества пунктов $items$:
+
Псевдокод построения множеств $closure$ и $GOTO$, а также множества пунктов $items$:
 
<code>
 
<code>
   Set<Item> CLOSURE(Set<Item> I):
+
   Set<Item> closure(Set<Item> I):
 
       '''bool''' changed;
 
       '''bool''' changed;
 
       Set<Item> $J$=$I$;   
 
       Set<Item> $J$=$I$;   
Строка 114: Строка 114:
 
       '''for''' $[A\rightarrow\alpha\cdot X\beta, a]\in I$
 
       '''for''' $[A\rightarrow\alpha\cdot X\beta, a]\in I$
 
           J.add($[A\rightarrow\alpha X\cdot\beta, a]$);
 
           J.add($[A\rightarrow\alpha X\cdot\beta, a]$);
       '''return''' $CLOSURE(J)$;
+
       '''return''' $closure(J)$;
 
</code>
 
</code>
 
<code>
 
<code>
 
   Set<Set<Item>> items($G'$):
 
   Set<Set<Item>> items($G'$):
 
       '''bool''' changed;
 
       '''bool''' changed;
       Set<Set<Item>> $C$ = $\{CLOSURE({S'\rightarrow\cdot S,\char36})\}$;   
+
       Set<Set<Item>> $C$ = $\{closure({S'\rightarrow\cdot S,\char36})\}$;   
 
       '''repeat'''
 
       '''repeat'''
 
           changed = '''false''';
 
           changed = '''false''';
Строка 137: Строка 137:
 
* $S\rightarrow CC$
 
* $S\rightarrow CC$
 
* $S\rightarrow cC|d$
 
* $S\rightarrow cC|d$
Запустим процедуру $items(G')$. Она начинается с вычисления $CLOSURE([S\rightarrow S', \char36])$. Это правило вида $[A\rightarrow\alpha\cdot B\beta, a]$, где $A=S';\alpha=\epsilon;B=S;\beta=\epsilon;a=\char36$. Т.к. в таком случае $FIRST(\beta\alpha) = {\char36}$, то мы добавим только правило $[S\rightarrow\cdot CC,\char36]$.
+
Запустим процедуру $items(G')$. Она начинается с вычисления $closure([S\rightarrow S', \char36])$. Это правило вида $[A\rightarrow\alpha\cdot B\beta, a]$, где $A=S';\alpha=\epsilon;B=S;\beta=\epsilon;a=\char36$. Т.к. в таком случае $FIRST(\beta\alpha) = {\char36}$, то мы добавим только правило $[S\rightarrow\cdot CC,\char36]$.
  
Продолжив вычислять замыкание таким образом, мы добавим во множество пунктов $[C\rightarrow\cdot C, c]$, $C\rightarrow\cdot C, d]$, $C\rightarrow\cdot d, c]$, и $C\rightarrow\cdot d, d]$. Т.к. ни один из новых пунктов не имеет вид $[A\rightarrow\alpha\cdot B\beta, a]$ (справа от точки во всех пунктах терминалы), то функция $CLOSURE$ завершает свою работу и начальное множество пунктов в данном случае равно:
+
Продолжив вычислять замыкание таким образом, мы добавим во множество пунктов $[C\rightarrow\cdot C, c]$, $C\rightarrow\cdot C, d]$, $C\rightarrow\cdot d, c]$, и $C\rightarrow\cdot d, d]$. Т.к. ни один из новых пунктов не имеет вид $[A\rightarrow\alpha\cdot B\beta, a]$ (справа от точки во всех пунктах терминалы), то функция $closure$ завершает свою работу и начальное множество пунктов в данном случае равно:
  
 
[[Файл:lr1_sets.png|400px|thumb|Рис. 1 Множества пунктов и их переходы]]
 
[[Файл:lr1_sets.png|400px|thumb|Рис. 1 Множества пунктов и их переходы]]
Строка 146: Строка 146:
  
 
При $X=S$:
 
При $X=S$:
$$CLOSURE({[S'\rightarrow S\cdot,\char36]}) = \varnothing$$
+
$$closure({[S'\rightarrow S\cdot,\char36]}) = \varnothing$$
 
Мы не добавили ни одного пункта, т.к. точка является крайней справа. Таким образом,  
 
Мы не добавили ни одного пункта, т.к. точка является крайней справа. Таким образом,  
 
$$I_1: \{[S'\rightarrow S\cdot,\char36]\}$$
 
$$I_1: \{[S'\rightarrow S\cdot,\char36]\}$$
 
При $X=C$:
 
При $X=C$:
$$I_2 = CLOSURE(\{[S\rightarrow C\cdot C,\char36]\})$$
+
$$I_2 = closure(\{[S\rightarrow C\cdot C,\char36]\})$$
 
$$I_2 = \{[S\rightarrow C\cdot C,\char36],[C\rightarrow\cdot cC,\char36],[C\rightarrow\cdot d,\char36]\}$$
 
$$I_2 = \{[S\rightarrow C\cdot C,\char36],[C\rightarrow\cdot cC,\char36],[C\rightarrow\cdot d,\char36]\}$$
 
При $X=c$:
 
При $X=c$:
$$I_3 = CLOSURE(\{[C\rightarrow c\cdot C,c/d]\})$$
+
$$I_3 = closure(\{[C\rightarrow c\cdot C,c/d]\})$$
 
$$I_3 = \{[C\rightarrow c\cdot C,c/d],[C\rightarrow\cdot cC,c/d],[C\rightarrow\cdot d,c/d]\}$$
 
$$I_3 = \{[C\rightarrow c\cdot C,c/d],[C\rightarrow\cdot cC,c/d],[C\rightarrow\cdot d,c/d]\}$$
 
При $X=d$:
 
При $X=d$:
$$I_4 = CLOSURE(\{[C\rightarrow d\cdot ,c/d]\})$$
+
$$I_4 = closure(\{[C\rightarrow d\cdot ,c/d]\})$$
 
$$I_4 = \{[C\rightarrow d\cdot,c/d]\}$$
 
$$I_4 = \{[C\rightarrow d\cdot,c/d]\}$$
 
На этом завершается выполнение цикла из процедуры $items$ для $I_0$.  
 
На этом завершается выполнение цикла из процедуры $items$ для $I_0$.  
 
$$GOTO(I_1, *)=\varnothing$$
 
$$GOTO(I_1, *)=\varnothing$$
$$I_5 = GOTO(I_2, C) = CLOSURE(\{[S\rightarrow CC\cdot,\char36]\})=\{[S\rightarrow CC\cdot,\char36]\}$$
+
$$I_5 = GOTO(I_2, C) = closure(\{[S\rightarrow CC\cdot,\char36]\})=\{[S\rightarrow CC\cdot,\char36]\}$$
$$I_6 = GOTO(I_2, c) = CLOSURE(\{[C\rightarrow c\cdot C,\char36]\})$$
+
$$I_6 = GOTO(I_2, c) = closure(\{[C\rightarrow c\cdot C,\char36]\})$$
 
$$I_6=\{[C\rightarrow c\cdot C,\char36],[C\rightarrow \cdot cC,\char36],[C\rightarrow \cdot d,\char36]\}$$
 
$$I_6=\{[C\rightarrow c\cdot C,\char36],[C\rightarrow \cdot cC,\char36],[C\rightarrow \cdot d,\char36]\}$$
 
Обратим внимание, что $I_6$ отличается от $I_3$ только правыми частями пунктов. Такое явление является частым в $LR(1)$ - анализе, из-за него результирующая таблица будет неоправданно большой. $LALR$-анализ борется с этим явлением.
 
Обратим внимание, что $I_6$ отличается от $I_3$ только правыми частями пунктов. Такое явление является частым в $LR(1)$ - анализе, из-за него результирующая таблица будет неоправданно большой. $LALR$-анализ борется с этим явлением.
 
Продолжим:
 
Продолжим:
$$I_7 = GOTO(I_2, d) = CLOSURE(\{[C\rightarrow d\cdot ,\char36]\}) = \{[C\rightarrow d\cdot ,\char36]\}$$
+
$$I_7 = GOTO(I_2, d) = closure(\{[C\rightarrow d\cdot ,\char36]\}) = \{[C\rightarrow d\cdot ,\char36]\}$$
 
На этом рассмотрение $GOTO(I_2)$ завершено, переходим к $GOTO(I_3)$:
 
На этом рассмотрение $GOTO(I_2)$ завершено, переходим к $GOTO(I_3)$:
$$I_8 = GOTO(I_3, C) = CLOSURE(\{[C\rightarrow cC\cdot ,c/d]\}) = \{[C\rightarrow cC\cdot ,c/d]\}$$
+
$$I_8 = GOTO(I_3, C) = closure(\{[C\rightarrow cC\cdot ,c/d]\}) = \{[C\rightarrow cC\cdot ,c/d]\}$$
 
В множествах $I_4$ и $I_5$ все пункты имеют точки в крайнем положении справа, следовательно эти множества не имеют $GOTO$  
 
В множествах $I_4$ и $I_5$ все пункты имеют точки в крайнем положении справа, следовательно эти множества не имеют $GOTO$  
 
$$GOTO(I_6, c) = I_6$$
 
$$GOTO(I_6, c) = I_6$$

Версия 21:47, 14 сентября 2015

<wikitex> В некоторых случаях SLR-разбор может выдать неправильный результат. В таких случаях используют более сложные методы, такие как LR(1) и LALR-разбор. Рассмотрим первый из них. </wikitex>

Отличия от SLR-разбора

<wikitex> Основным отличием LR(1)-разбора от SLR-разбора является использование предпросмотра (англ. lookahead) символов.

Приведём пример ситуации, в которой SLR-разбор не справится с задачей:

Рассмотрим грамматику вида: $ S \to L=R | R \\ L \to *R | id \\ R \to L $

Покажем её канонический LR(0)-набор:

$I_0$ $I_1$ $I_2$ $I_3$ $I_4$ $I_5$ $I_6$ $I_7$ $I_8$ $I_9$

$S' \to \cdot S \\ S \to \cdot L = R \\ S \to \cdot R \\ L \to \cdot * R \\ L \to \cdot id \\ R \to \cdot L$

$S' \to S \cdot$

$S \to L \cdot = R \\ R \to L \cdot$

$S \to R \cdot$

$L \to * \cdot R \\ R \to \cdot L \\ L \to \cdot * R \\ L \to \cdot id$

$L \to id \cdot$

$S \to L = \cdot R \\ R \to \cdot L \\ L \to \cdot * R \\ L \to \cdot id$

$L \to * R \cdot$

$R \to L \cdot$

$S \to L = R \cdot$

Рассмотрим ситуацию $I_2$. Если SLR-парсер находится в $I_2$ и очередной входной символ равен $=$, то парсер выполняет свёртку в соответствии с продукцией $R \to L$, что неверно, т.к. в этой грамматике не выводится выражение $R=\ldots$ и парсер должен был выполнить перенос, а не свёртку.

Чтобы решить эту проблему, необходимо хранить в ситуации больший объём информации, который позволит не делать таких ошибочных свёрток. </wikitex>

Канонические LR(1)-ситуации

<wikitex> Основная идея заключается в том, чтобы хранить в ситуациях больше информации, чтобы не производить некорректных свёрток. Добавим в пункт второй компонент: терминальный символ. Таким образом, LR(1)-ситуации будут выглядеть следующим образом:

$[A\rightarrow\alpha\cdot\beta, a]$, где первая часть — продукция, а вторая — терминал или маркер конца входной строки $\char36$. Здесь $a$ называется предпросмотром (англ. lookahead) ситуации, а число 1 в LR(1) означает его длину. Теперь мы будем выполнять свёртку в соответствии с продукцией $A\rightarrow\alpha$, только в том случае, если находимся в ситуации $[A\rightarrow\alpha\cdot\beta, a]$ и $a$ — входной символ.

Определение:
Назовём LR(1)-ситуацию $[A\rightarrow\alpha\cdot\beta, a]$ допустимой (англ. valid) для активного префикса $\gamma$, если существует правое порождение $S\Rightarrow^{*}\delta A w\Rightarrow\delta\alpha\beta w$, где верно одно из трёх:
  • $\gamma=\delta\alpha$
  • $a$ является первым символом $w$
  • $w=\epsilon$ и $a=\char36$

</wikitex>

Построение множеств LR(1)-ситуаций

<wikitex> Метод построения похож на метод для $LR(0)$-разбора, с двумя изменёнными функциями: $closure(I)$ — замыкание множества пунктов, и $GOTO(X,I)$ — функция переходов в автомате по символу $X$.

Лемма:
$$\forall{b}
Доказательство:
[math]\triangleright[/math]

Рассмотрим пункт вида $[A\rightarrow\alpha\cdot B\beta, a]$ в множестве пунктов, допустимых для некоторого активного префикса $\gamma$. Тогда существует правое порождение $S\Rightarrow^{*}\delta Aax\Rightarrow\delta\alpha B\beta ax$, где $\gamma=\delta\alpha$. Предположим, что $\beta ax$ порождает строку терминалов $by$. Тогда для каждой продукции вида $\forall{B\rightarrow\eta}\exists{\eta}$ мы имеем порождение $ S\Rightarrow^{*}\delta Bby\Rightarrow\delta\eta by$. Таким образом, $[B\rightarrow\cdot\eta,b]$ является допустимым для $\gamma$. Заметим, что $b$ может быть первым терминалом, порожденным из $\beta$, либо, возможно что $\beta$ порождает $\epsilon$ слева: $\beta ax\Rightarrow^{*}by$, следовательно $b=a$. Таким образом, $b\in FIRST(\beta ax)$. Поскольку $x$ не может содержать первый терминал из $by$, то $FIRST(\beta ax)=FIRST(\beta a)$

Значит, $b\in FIRST(\beta a)$.
[math]\triangleleft[/math]

</wikitex>

Псевдокод

<wikitex> Псевдокод построения множеств $closure$ и $GOTO$, а также множества пунктов $items$:

 Set<Item> closure(Set<Item> I):
     bool changed;
     Set<Item> $J$=$I$;   
     repeat
         changed = false;
         for $[A\rightarrow\alpha\cdot B\beta, a]\in I$
             for $(B\rightarrow\gamma)\in G'$
                 for $b\in FIRST(\beta\alpha)$
                     J.add($[B\rightarrow\cdot\gamma,b]$);
                     changed = true
     until !changed;
     return J;

 Set<Item> GOTO(Set<Item> I, X):
     Set<Item> $J$=$\varnothing$;   
     for $[A\rightarrow\alpha\cdot X\beta, a]\in I$
         J.add($[A\rightarrow\alpha X\cdot\beta, a]$);
     return $closure(J)$;

 Set<Set<Item>> items($G'$):
     bool changed;
     Set<Set<Item>> $C$ = $\{closure({S'\rightarrow\cdot S,\char36})\}$;   
     repeat
         changed = false;
         for Set<Item> $I\subset C$
             for $X \in symbols(G')$ //по всем символам грамматики
                 if $GOTO(I,X)\neq\varnothing$ and $GOTO(I,X)\not\subset C$
                     C.add($GOTO(I,X)$);
                     changed = true
     until !changed;
     return C;

</wikitex>

Пример

<wikitex> Рассмотрим следующую грамматику $G'$:

  • $S'\rightarrow S$
  • $S\rightarrow CC$
  • $S\rightarrow cC|d$

Запустим процедуру $items(G')$. Она начинается с вычисления $closure([S\rightarrow S', \char36])$. Это правило вида $[A\rightarrow\alpha\cdot B\beta, a]$, где $A=S';\alpha=\epsilon;B=S;\beta=\epsilon;a=\char36$. Т.к. в таком случае $FIRST(\beta\alpha) = {\char36}$, то мы добавим только правило $[S\rightarrow\cdot CC,\char36]$.

Продолжив вычислять замыкание таким образом, мы добавим во множество пунктов $[C\rightarrow\cdot C, c]$, $C\rightarrow\cdot C, d]$, $C\rightarrow\cdot d, c]$, и $C\rightarrow\cdot d, d]$. Т.к. ни один из новых пунктов не имеет вид $[A\rightarrow\alpha\cdot B\beta, a]$ (справа от точки во всех пунктах терминалы), то функция $closure$ завершает свою работу и начальное множество пунктов в данном случае равно:

Рис. 1 Множества пунктов и их переходы

$$I_0: \{[S'\rightarrow \cdot S, \char36],[S\rightarrow\cdot CC,\char36],[C\rightarrow\cdot C, c/d],[C\rightarrow\cdot d, c/d]\}$$ Следующим шагом процедуры $items$ будет вычисление функции переходов автомата $GOTO(I_0,X)$ для всех символов $X$ грамматики $G'$:

При $X=S$: $$closure({[S'\rightarrow S\cdot,\char36]}) = \varnothing$$ Мы не добавили ни одного пункта, т.к. точка является крайней справа. Таким образом, $$I_1: \{[S'\rightarrow S\cdot,\char36]\}$$ При $X=C$: $$I_2 = closure(\{[S\rightarrow C\cdot C,\char36]\})$$ $$I_2 = \{[S\rightarrow C\cdot C,\char36],[C\rightarrow\cdot cC,\char36],[C\rightarrow\cdot d,\char36]\}$$ При $X=c$: $$I_3 = closure(\{[C\rightarrow c\cdot C,c/d]\})$$ $$I_3 = \{[C\rightarrow c\cdot C,c/d],[C\rightarrow\cdot cC,c/d],[C\rightarrow\cdot d,c/d]\}$$ При $X=d$: $$I_4 = closure(\{[C\rightarrow d\cdot ,c/d]\})$$ $$I_4 = \{[C\rightarrow d\cdot,c/d]\}$$ На этом завершается выполнение цикла из процедуры $items$ для $I_0$. $$GOTO(I_1, *)=\varnothing$$ $$I_5 = GOTO(I_2, C) = closure(\{[S\rightarrow CC\cdot,\char36]\})=\{[S\rightarrow CC\cdot,\char36]\}$$ $$I_6 = GOTO(I_2, c) = closure(\{[C\rightarrow c\cdot C,\char36]\})$$ $$I_6=\{[C\rightarrow c\cdot C,\char36],[C\rightarrow \cdot cC,\char36],[C\rightarrow \cdot d,\char36]\}$$ Обратим внимание, что $I_6$ отличается от $I_3$ только правыми частями пунктов. Такое явление является частым в $LR(1)$ - анализе, из-за него результирующая таблица будет неоправданно большой. $LALR$-анализ борется с этим явлением. Продолжим: $$I_7 = GOTO(I_2, d) = closure(\{[C\rightarrow d\cdot ,\char36]\}) = \{[C\rightarrow d\cdot ,\char36]\}$$ На этом рассмотрение $GOTO(I_2)$ завершено, переходим к $GOTO(I_3)$: $$I_8 = GOTO(I_3, C) = closure(\{[C\rightarrow cC\cdot ,c/d]\}) = \{[C\rightarrow cC\cdot ,c/d]\}$$ В множествах $I_4$ и $I_5$ все пункты имеют точки в крайнем положении справа, следовательно эти множества не имеют $GOTO$ $$GOTO(I_6, c) = I_6$$ $$GOTO(I_6, d) = I_7$$ $$I_9 = GOTO(I_6, C) = \{[C\rightarrow cC\cdot,\char36]\}$$ Остальные множества пунктов не дают нам значений $GOTO$, процедура $items$ завершает работу. </wikitex>

Канонические LR(1)-таблицы

Алгоритм

// вход: [math]G'[/math] — расширенная грамматика
// выход: таблица канонического [math]LR[/math]-анализа с функциями [math]ACTION[/math] и [math]GOTO[/math]
function [math]\mathtt{getLR1LexTable}(G'):[/math]
   [math] C'(G') \leftarrow \{I_0,I_1..I_n\}[/math] // множество канонических пунктов для [math]G'[/math]
   [math]\mathtt{fillArray}(ACTION,[/math]"ошибка"[math] ):[/math]
   foreach [math]I_i \in (E(G))\[/math]
       if [math][A\rightarrow \alpha\cdot a\beta, b] \in I_i[/math] здесь [math]a[/math] - терминал
           [math]ACTION[i,a] = [/math] "перенос [math]j[/math]"
       if [math][A\rightarrow \alpha\cdot, a] \in I_i[/math] && [math]A\neq S'[/math] 
           [math]ACTION[i,a] = [/math] "свертка [math]A\rightarrow a[/math]"
       if [math][S'\rightarrow S\cdot, \char36] \in I_i[/math]
           [math]ACTION[i,\char36] = [/math] "принятие"
       if [math]GOTO(I_i,A) = I_j[/math]
           [math]GOTO[i,A]\leftarrow j[/math]

Если в процессе построения обнаружатся конфликтующие действия - это значит, что грамматика не принадлежит классу [math]LR(1)[/math]

Таблица, построенная в результате применения алгоритм называется канонической таблицей [math]LR(1)[/math] - анализа.

Пример

<wikitex> Рассмотрим следующую грамматику $G$:

  1. $S\rightarrow CC$
  2. $C\rightarrow cC$
  3. $C\rightarrow d$

Приведем каноническую таблицу синтаксического анализа для этой грамматики:

Состояние $ACTION$ $GOTO$
$c$ $d$ $\char36$ $S$ $C$
$0$ $s3$ $s4$ $1$ $2$
$1$ ok
$2$ $s6$ $s7$ $5$
$3$ $s3$ $s4$ $8$
$4$ $r1$ $r3$
$5$ $r1$
$6$ $s6$ $s7$ $9$
$7$ $r3$
$8$ $r2$ $r2$
$9$ $r2$

</wikitex>

Источники информации

  • Альфред Ахо, Рави Сети, Джеффри Ульман. Компиляторы. Принципы, технологии, инструменты. Издательство Вильямс, 2003. Стр. 331-338.