Анализ кадра управляющей программы

 

Анализ кадра, написанного в контекстно-свободной грамматике, осуществляется с помощью автоматов с магазинной памятью – МП-автоматов.

В отличие от автоматной грамматики в правой части правил контекстно-свободной грамматики допускается цепочка терминалов, а также цепочка нетерминалов, возможно пустая.

Например:

В составлении правил контекстно-свободной грамматики есть только два ограничения:

• правая часть правила должна начинаться из терминала;

• для одинаковых нетерминалов в левой части разные правила должны иметь разные первые терминалы в правой части, например:

; .

МП-автомат задается тремя множествами, которые размещаются в памяти.

1. Множество входных символов T_i (терминалов входного языка), а также конечный маркер ⊣, что указывает на окончание цепочки терминалов, которые поступают со сканера.

2. Множество магазинных символов:

• нетерминалы, которые загружаются в память и потом выталкиваются из нее по правилам грамматики;

• терминалы из правил, которые стоят не на первом месте;

• маркер дна магазина

3. Множество управляющих воздействий, генерируемых МП-автоматом.

При работе МП-автомата выполняются стандартные процедуры:

1) операции, выполняемые над входом:

СДВИНУТЬ, т.е. перейти к анализу следующего терминала в цепочке;

ЗАДЕРЖАТЬ, т.е. текущий терминал задерживается для участия в следующем цикле работы;

2) операции над магазинной памятью:

ВЫТОЛКНУТЬ, т.е. из стековой памяти выталкивается верхний символ – терминал или нетерминал;

ЗАМЕНИТЬ – из магазина удаляется верхний символ и вместо него вводится другой символ или цепочка;

3) служебные операции:

ОТВЕРГНУТЬ – равносильна сигналу «Ошибка ввода» (все пустые места в управляющей таблице отвечают этой операции);

ДОПУСТИТЬ – МП-автомат работает как распознаватель соблюдения правил грамматики;

ВЫДАТЬ {z_i} – автомат генерирует сигнал управления, если цепочка терминалов, которые поступили, позволяет выдачу соответствующего сигнала управления.

Работа автомата заканчивается тогда, когда проанализированы все терминалы, которые поступили на вход, и маркер дна магазина находится вверху (магазин пустой).