Изменения
→Канонические LR(1)-таблицы
</wikitex>
=== Канонические LR(1)-таблицы ===
В алгоритме будут использоваться структуры, описанные в [http://neerc.ifmo.ru/wiki/index.php?title=LR(k)-%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B8#.D0.A3.D0.BF.D1.80.D0.B0.D0.B2.D0.BB.D1.8F.D1.8E.D1.89.D0.B0.D1.8F_.D0.BF.D1.80.D0.BE.D0.B3.D1.80.D0.B0.D0.BC.D0.BC.D0.B0_.D0.B0.D0.BD.D0.B0.D0.BB.D0.B8.D0.B7.D0.B0.D1.82.D0.BE.D1.80.D0.B0 конспекте про LL(k) грамматики]
==== Алгоритм ====
<font color=green>// вход: <tex>G'</tex> {{---}} расширенная грамматика</font>
<font color=green>// выход: таблица канонического таблицы <tex>LRACTION</tex>-анализа с функциями и <tex>ACTIONGOTO</tex> и канонического <tex>gotoLR</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>
<tex>\mathtt{fillArray}(ACTION,</tex> <font color=red>'''ошибкаError'''</font><tex> ):</tex>
'''foreach''' <tex>I_i \in (E(G))\</tex>
'''if''' <tex>[A\rightarrow \alpha\cdot a\beta, b] \in I_i</tex> '''and''' <tex>GOTO(I_i,a) = I_j</tex> <font color=green>// здесь <tex>a</tex> {{---}} терминал</font> <tex>ACTION[i,a] = </tex> <font color=#C98300>'''переносShift''' (<tex>j</tex></font>)
'''if''' <tex>[A\rightarrow \alpha\cdot, a] \in I_i</tex> '''and''' <tex>A\neq S'</tex>
<tex>ACTION[i,a] = </tex> <font color=#C98300>'''сверткаReduce''' (<tex>A \rightarrow to a</tex></font>)
'''if''' <tex>[S'\rightarrow S\cdot, \char36] \in I_i</tex>
<tex>ACTION[i,\char36] = </tex> <font color=green>'''принятиеAccept'''</font> '''if''' <tex>gotoGOTO(I_i,A) = I_j</tex> <tex>gotoGOTO[i,A]\leftarrow j</tex>
Если в процессе построения обнаружатся конфликтующие действия {{---}} это значит, что грамматика не принадлежит классу LR(1)
