Теория языков программирования методов трансляции (стр. 15 )

2)  Пусть множество , где ни одна из цепочек не начинается с , если k£i заменим – правила правилами:

,

где – новый нетерминал. Правые части всех – правил начинаются теперь с терминала или с , для которого k>i.

3)  Если i=n, то полученную грамматику считаем результатом и останавливаемся, в противном случае i=i+1 и j=1.

4)  Заменим каждое правило правилами , где для всех - правил. Так как правая часть каждого правила начинается уже с терминала или для к>j, то правая часть каждого - правила будет теперь обладать этими свойствами.

5)  Если j=i-1, перейти к шагу 2), в противном случае положить i=i+1 и перейти к шагу 4).

На основании вышесказанного можно однозначно доказать теорему, что каждый КС-язык определяется нелеворекурсивной грамматикой.

Определение.

КС-грамматика G = (N, S, Р, S) называется грамматикой в форме Грейбах, если в ней нет е- правил и каждое правило из Р, отличное от S®e, имеет вид А®aa, где аÎS, aÎN*.

3.11.  Автоматы с магазинной памятью

Автоматы с магазинной памятью являются естественной моделью синтаксического анализатора КС-языков.

Автомат с магазинной памятью – это односторонний распознаватель, в потенциально бесконечной памяти которого элементы информации хранятся и используются так же, как и патроны автоматического оружия, т. е. в каждый момент доступен только верхний элемент магазина (рис. 3.11).

				Входная лента
		Управляющее Устройство с конечной памятью
						Магазин

Рис. 3.11. Автомат с магазинной памятью

Все КС-языки определяются недетерминированными автоматами с магазинной памятью, а практически все языки программирования определяются детерминированными автоматами с магазинной памятью.

3.11.1.  Основные определения

Определение.

Автомат с магазинной памятью (МП-автомат) – это семерка

,

где - конечное множество символов состояния, представляющих всевозможные состояния управляющего устройства;

S - конечный входной алфавит;

G - конечный алфавит магазинных символов;

d - отображение множества во множество конечных подмножеств множества ;

- начальное состояние управляющего устройства;

- символ, находящийся в магазине в начальный момент (начальный символ);

- множество заключительных состояний.

Конфигурацией МП-автомата Р называется тройка содержащая ,

где - текущее состояние устройства;

- неиспользованная часть входной цепочки; первый символ цепочки находится под входной головкой; если , то считается, что вся входная лента прочитана;

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

Такт работы МП-автомата Р будет представляться в виде бинарного отношения ⊢, определенного на конфигурациях. Будем писать

⊢,

если множество содержит , где , , , и .

Если а=е, то говорят о том, что МП-автомат Р, находясь в состоянии q и имея а в качестве текущего входного символа, расположенного под входной головкой, а Z – в качестве верхнего символа магазина, может перейти в состояние , сдвинуть головку на одну ячейку вправо и заменить верхний символ магазина цепочкой g магазинных символов. Если g=е, то верхний символ удаляется из магазина, тем самым магазинный список сокращается.

Если а=е, будем называть этот такт е-тактом. В е-такте текущий входной символ не принимается во внимание и входная головка не сдвигается. Однако состояние управляющего устройства и содержимое памяти можут измениться. Заметим, что е-такт может происходить тогда, когда вся цепочка прочитана.

Начальной конфигурацией МП-автомата Р называется конфигурация вида , где , т. е. управляющее устройство находится в начальном состоянии, входная лента содержит цепочку, которую нужно распознать, и в магазине есть только начальный символ .

Заключительная конфигурация – это конфигурация вида , где и .

Говорят, что цепочка w допускается МП-автоматом Р, если ⊢* для некоторых и .