Управляющая таблица

Теперь мы можем вычислить множество сверток R :

R = empty set; for (each state I in T) { for (each item [A->w.] in I) { R+={(I, A->w)}; } }

Таким образом, алгоритм построения управляющей таблицы автомата состоит из следующих шагов:

• Пополнение грамматики
• Построение множества состояний
• Построение множества переходов
• Построение множества сверток

Для того, чтобы построить таблицу анализатора для грамматики, поступим следующим образом:

1. для каждого ребра I->X J мы поместим в позицию [I, X] таблицы
   • shift J , если X - терминал,
   • goto J , если X - нетерминал.

2. для каждого состояния I , содержащего ситуацию [S'->S.] мы поместим accept в позицию [I,$]
3. для состояния, содержащего ситуацию [A->w.] (правило номер n с точкой в конце правила), поместим reduce n в позицию [I, Y] для каждого терминала Y .
4. пустая ячейка означает ошибочную ситуацию

Приведем управляющую таблицу для грамматики G0:

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

---

---