Теория и реализация языков программирования




Конструирование LR(1)-таблицы - часть 4


Проследим последовательность создания этих множеств более подробно.

  1. Вычисляем I0 = closure({[E'
    .E, $]}).
    1. Ситуация [E'
      .E, $] попадает в него по умолчанию как исходная.
    2. Если обратиться к обозначениям функции closure, то для нее
      \begin{align*} & \alpha = \beta = e, \quad B=E, \quad a=\$,\\ & first(\beta a) = first(\$) = \{ \$ \}. \end{align*}

      Значит, для терминала $ добавляем ситуации на основе правил со знаком E в левой части правила. Это правила

      \begin{align*} & E \rightarrow E + T \text{ и } E \rightarrow T \end{align*}

      и соответствующие им ситуации

      \begin{align*} & [E \rightarrow. E + T, \$] \text{ и } [E \rightarrow . T, \$] \end{align*}

    3. Просматриваем получившиеся ситуации. Для ситуации [E
      .E + T, $] ? = +, поэтому first(?a) = first(+$) = {+}. На основе этого добавляем к I0

      [E

      E + .T, +] и [E
      .T, +].
    4. Для ситуации [E
      .T, $] ? = e, first(?a) = {$}. Поэтому добавляем к I0

      [T

      . T * F, $] и [T
      .F, $].
    5. Подобно этому для ситуации [E
      .T, +] ? = e, first(?a) = {+}. Поэтому добавляем к I0

      [T

      .T * F, +] и [T
      .F, +].
    6. Из ситуации [T
      . T * F, +] ? = *, first(?a) = {*}: Поэтому добавляем к I0


      увеличить изображение
      Рис. 4.9. 

      [T

      .T * F, *] и [T
      .F, *]
    7. Далее из ситуации [T
      .F, *] получаем ситуацию [F
      . id, *]. из ситуации [T
      . F, $] - ситуацию [F
      . id, $], а из ситуации [T
      . F, +] - [F
      . id, *].

Таким образом, все 14 искомых ситуаций I0 получены.

Возвращаемся в головную функцию items, включаем I0 в множество C и исследуем непустые итоги применения функции goto(I0; X), где

X \in \{E', E, T, F, +, *, \$, id\}
.

Если посмотреть на вид правил в функции goto(I0; X), то видно, что X должен встретиться в правой части хотя бы одного правила. Для E0 таких правил у нас нет, поэтому значение функции goto(I0, E') пусто.

Возьм_м goto(I0; E). E встречается после точки в правых частях двух ситуаций из I0, значит бер_м эти два правила и переносим в них точки на один символ вправо (пока есть куда - не уперлись в запятую), получаем:

[E'

E., $]

и

[E

E. + T, $|+]

Вычислим от каждой из этих ситуаций функцию closure. Но, поскольку справа от точки здесь либо пустая цепочка, либо терминал, то никаких новых ситуаций не возникает. Дальше отслеживаем, может ли куда-то сдвинуться точка дальше на право и по какому символу. Если может, строим соответствующее множество (рис. 4.9). И т.д.




Содержание  Назад