262
правки
Изменения
м
Нет описания правки
====Пример====
<wikitex>
Рассмотрим следующую грамматику $G\Gamma'$:
* $S'\rightarrow S$
* $S\rightarrow CC$
* $S\rightarrow cC|d$
Запустим процедуру $items(G\Gamma')$. Она начинается с вычисления $closure([S\rightarrow S', \char36])$. Это правило вида $[A\rightarrow\alpha\cdot B\beta, a]$, где $A=S';\alpha=\varepsilon;B=S;\beta=\varepsilon;a=\char36$.
Т.к. в таком случае $FIRST(\beta\alpha) = {\char36}$, то мы добавим только правило $[S\rightarrow\cdot CC,\char36]$.
[[Файл: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()$ будет вычисление функции переходов автомата $goto(I_0,X)$ для всех символов $X$ грамматики $G\Gamma'$:
#При $X=S$:
В алгоритме будут использоваться структуры, описанные в [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\Gamma'</tex> {{---}} расширенная грамматика</font>
<font color=green>// выход: таблицы <tex>ACTION</tex> и <tex>GOTO</tex> канонического <tex>LR</tex>-анализа</font>
'''function''' <tex>\mathtt{getLR1LexTable}(G\Gamma'):</tex> <tex> C'(G\Gamma') \leftarrow \{I_0,I_1..I_n\}</tex> <font color=green>// множество канонических ситуаций для <tex>G\Gamma'</tex></font>
<tex>\mathtt{fillArray}(ACTION,</tex> '''Error'''<tex> ):</tex>
'''foreach''' <tex>I_i \in (E(G))\</tex>
