Изменения
Нет описания правки
=== Построение множеств LR(1)-ситуаций ===
<wikitex>
Метод построения похож на метод для $LR(0)$-разбора, с двумя изменёнными функциями: $closure(I)$ {{---}} замыкание множества пунктов, и $GOTOgoto(X,I)$ {{---}} функция переходов в автомате по символу $X$.
{{Лемма
|id=lemmaclosure
====Псевдокод====
<wikitex>
Псевдокод построения множеств $closure$ и $GOTOgoto$, а также множества пунктов $items$:
<code>
Set<Item> closure(Set<Item> I):
J.add($[B\rightarrow\cdot\gamma,b]$);
changed = '''true'''
'''until''' !not changed;
'''return''' J;
</code>
<code>
Set<Item> GOTOgoto(Set<Item> I, X):
Set<Item> $J$=$\varnothing$;
'''for''' $[A\rightarrow\alpha\cdot X\beta, a]\in I$
'''for''' Set<Item> $I\subset C$
'''for''' $X \in symbols(G')$ <font color="green">//по всем символам грамматики</font>
'''if''' $GOTOgoto(I,X)\neq\varnothing$ and $GOTOgoto(I,X)\not\subset C$ C.add($GOTOgoto(I,X)$);
changed = '''true'''
'''until''' !not changed;
'''return''' C;
</code>
[[Файл:lr1_sets.png|400px|thumb|Рис. 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$ будет вычисление функции переходов автомата $GOTOgoto(I_0,X)$ для всех символов $X$ грамматики $G'$:
При $X=S$:
$$I_4 = \{[C\rightarrow d\cdot,c/d]\}$$
На этом завершается выполнение цикла из процедуры $items$ для $I_0$.
$$GOTOgoto(I_1, *)=\varnothing$$$$I_5 = GOTOgoto(I_2, C) = closure(\{[S\rightarrow CC\cdot,\char36]\})=\{[S\rightarrow CC\cdot,\char36]\}$$$$I_6 = GOTOgoto(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 = GOTOgoto(I_2, d) = closure(\{[C\rightarrow d\cdot ,\char36]\}) = \{[C\rightarrow d\cdot ,\char36]\}$$На этом рассмотрение $GOTOgoto(I_2)$ завершено, переходим к $GOTOgoto(I_3)$:$$I_8 = GOTOgoto(I_3, C) = closure(\{[C\rightarrow cC\cdot ,c/d]\}) = \{[C\rightarrow cC\cdot ,c/d]\}$$В множествах $I_4$ и $I_5$ все пункты имеют точки в крайнем положении справа, следовательно эти множества не имеют $GOTOgoto$ $$GOTOgoto(I_6, c) = I_6$$$$GOTOgoto(I_6, d) = I_7$$$$I_9 = GOTOgoto(I_6, C) = \{[C\rightarrow cC\cdot,\char36]\}$$Остальные множества пунктов не дают нам значений $GOTOgoto$, процедура $items$ завершает работу.
</wikitex>
=== Канонические LR(1)-таблицы ===
==== Алгоритм ====
<font color=green>// вход: <tex>G'</tex> {{---}} расширенная грамматика</font>
<font color=green>// выход: таблица канонического <tex>LR</tex>-анализа с функциями <tex>ACTION</tex> и <tex>GOTOgoto</tex></font>
'''function''' <tex>\mathtt{getLR1LexTable}(G'):</tex>
<tex> C'(G') \leftarrow \{I_0,I_1..I_n\}</tex> <font color=green>// множество канонических пунктов для <tex>G'</tex></font>
'''if''' <tex>[S'\rightarrow S\cdot, \char36] \in I_i</tex>
<tex>ACTION[i,\char36] = </tex> "принятие"
'''if''' <tex>GOTOgoto(I_i,A) = I_j</tex> <tex>GOTOgoto[i,A]\leftarrow j</tex>
Если в процессе построения обнаружатся конфликтующие действия - это значит, что грамматика не принадлежит классу <tex>LR(1)</tex>
! rowspan="2" | Состояние
! colspan="3" | $ACTION$
! colspan="2" |$GOTOgoto$
|-
|$c$
