262
правки
Изменения
м
→Канонические LR(1)-таблицы
==== Алгоритм ====
<font color=green>// вход: <tex>\Gamma'</tex> {{---}} расширенная грамматика</font>
<font color=green>// выход: таблицы таблица <tex>ACTION</tex> и <tex>GOTOT</tex> канонического <tex>LR(1)</tex>-анализа</font>
'''function''' <tex>\mathtt{getLR1LexTable}(\Gamma'):</tex>
<tex> C'(\Gamma') \leftarrow \{I_0,I_1..I_n\}</tex> <font color=green>// множество канонических ситуаций для <tex>\Gamma'</tex></font>
<tex>\mathtt{fillArray}(ACTIONT,</tex> '''Error'''<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>GOTOgoto(I_i,a) = I_j</tex> <font color=green>// здесь <tex>a</tex> {{---}} терминал</font> <tex>ACTIONT[i,a] = </tex> '''Shift'''(<tex>j</tex>)
'''if''' <tex>[A\rightarrow \alpha\cdot, a] \in I_i</tex> '''and''' <tex>A\neq S'</tex>
<tex>ACTIONT[i,a] = </tex> '''Reduce'''(<tex>A \to a</tex>)
'''if''' <tex>[S'\rightarrow S\cdot, \char36] \in I_i</tex>
<tex>ACTIONT[i,\char36] = </tex> '''Accept''' '''if''' <tex>GOTOgoto(I_i,A) = I_j</tex> <tex>GOTOgoto[i,A]\leftarrow j</tex>
Если в процессе построения обнаружатся конфликтующие действия {{---}} это значит, что грамматика не принадлежит классу LR(1)
==== Пример ====
<wikitex>
Рассмотрим следующую грамматику $G\Gamma$:
# $S\rightarrow CC$
# $C\rightarrow cC$
! rowspan="2" style="background-color:#EEE;text-align:center"| Состояние
! colspan="3" style="background-color:#EEE;text-align:center" | $ACTION$
! colspan="2" style="background-color:#EEE;text-align:center" |$GOTOgoto$
|-
|style="background-color:#FFF;padding:2px 20px;text-align:center"|$c$
