Разработка компиляторов

       

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


Теперь мы можем вычислить множество сверток 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:

()x ,$SL
0s2s23
1r2r2r2r2r2
2s2s164
3acc
4s5s7
5r1r1r1r1r1
6r3r3r3r3r3
7s3s28
8r4r4r4r4r4



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