КС-грамматики и МП-автоматы
Пусть G = (N, T, P, S) - контекстно-свободная грамматика. Введем несколько важных понятий и определений.
Вывод, в котором в любой сентенциальной форме на каждом шаге делается подстановка самого левого нетерминала, называется левосторонним. Если S



Упорядоченным
графом называется пара (V, E), где V есть множество вершин, а E - множество линейно упорядоченных списков дуг, каждый элемент которого имеет вид ((v, v1), (v, v2), ..., (v, vn)). Этот элемент указывает, что из вершины v выходят n дуг, причем первой из них считается дуга, входящая в вершину v1, второй - дуга, входящая в вершину v2, и т.д.
Упорядоченным помеченным деревом называется упорядоченный граф (V, E), основой которого является дерево и для которого определена функция f : V

разметки) для некоторого множества F.
Упорядоченное помеченное дерево D называется деревом вывода (или деревом разбора) цепочки w в КС-грамматике G = (N, T, P, S), если выполнены следующие условия:


X

Грамматика G называется неоднозначной, если существует цепочка w, для которой имеется два или более различных деревьев вывода в G.
Грамматика G называется леворекурсивной, если в ней имеется нетерминал A такой, что существует вывод A



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

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








Конфигурацией МП-автомата называется
тройка (q, w, u), где




Такт работы МП-автомата M будем представлять в виде бинарного отношения










Начальной конфигурацией МП-автомата M называется конфигурация вида (q0, w, Z0), где w

Заключительная конфигурация - это конфигурация вида (q, e, u), где q



в одном из заключительных состояний, а входная цепочка целиком прочитана.
Введем транзитивное и рефлексивно-транзитивное замыкание отношения





Говорят, что цепочка w допускается МП-автоматом M, если (q0, w, Z0)




Язык, допускаемый (распознаваемый, определяемый) автоматомM (обозначается L(M)) - это множество всех цепочек, допускаемых автоматом M.
Пример 4.1. Рассмотрим МП-автомат

у которого функция переходов D содержит следующие элементы:
D(q0, a, Z) = {(q0, aZ)},
D(q0, b, Z) = {(q0, bZ)},
D(q0, a, a) = {(q0, aa), {q1, e)},
D(q0, a, b) = {(q0, ab)},
D(q0, b, a) = {(q0, ba)},
D(q0, b, b) = {(q0, bb), (q1, e)},
D(q1, a, a) = {(q1, e)},
D(q1, b, b) = {(q1, e)},
D(q1, e, Z) = {(q2, e)}.
Нетрудно показать, что L(M) = {wwR|w

обозначает обращение («переворачивание») цепочки w.
Иногда допустимость определяют несколько иначе: цепочка w допускается МП-автоматом M, если (q0, w, Z0)


Теорема 4.1. Язык допускается магазинным автоматом тогда и только тогда, когда он допускается (некоторым другим автоматом) опустошением магазина.
Доказательство. Пусть L = L(M) для некоторого МП-автомата M = (Q, T,

Пусть M' = (Q












F и Z






Автомат сначала переходит в конфигурацию (q0, w, Z0Z0') в соответствии с определением D' в п.2, затем в (q, e, Y 1...Y kZ0'), q





Обратно, пусть M = (Q, T,


Построим автомат M', допускающий тот же язык по заключительному состоянию.
Пусть M' = (Q









Q, (qf, e)

Нетрудно показать по индукции, что L = L(M'). __
Одним из важнейших результатов теории контекстно-свободных языков является доказательство эквивалентности
МП-автоматов и КС-грамматик.
Теорема 4.2. Язык является контекстно-свободным тогда и только тогда, когда он допускается магазинным автоматом.
Доказательство. Пусть G = (N, T, P, S) - КС-грамматика. Построим МП-автомат M, допускающий язык L(G) опустошением магазина.
Пусть M = ({q}, T, N






Фактически, этот МП-автомат в точности моделирует все возможные выводы в грамматике
G. Нетрудно показать по индукции, что для любой цепочки w

вывод S


Обратно, пусть M = (Q, T,


Пусть G = ({ [qZr] | q, r




- Если (r, X1...Xk) D(q, a, Z), k1, то
для любого набора s1, s2, ..., sk состояний из Q; - Если (r, e) D(q, a, Z), то [qZr]aP, aT{e};
- S [q0Z0q]P для всех qQ.
Нетерминалы и правила вывода грамматики определены так, что работе автомата M при обработке цепочки w соответствует левосторонний вывод w в грамматике G.
Индукцией по числу шагов вывода в G или числу тактов M нетрудно показать, что (q, w, A)


Тогда, если w





w






МП-автомат M = (Q, T,










Язык, допускаемый ДМП-автоматом, называется детерминированным КС-языком.
Так как функция переходов ДМП- автомата содержит не более одного элемента для любой тройки
аргументов, мы будем пользоваться записью D(q, a, Z) = (p, u) для обозначения D(q, a, Z) = {(p, u)}.
Пример 4.2. Рассмотрим ДМП-автомат

у которого функция переходов определяется следующим образом:
D(q0, X, Y ) = (q0, XY ), X


D(q0, c, Y ) = (q1, Y ), Y

D(q1, X, X) = (q1, e), X

D(q1, e, Z) = (q2, e).
Нетрудно показать, что этот детерминированный МП-автомат допускает язык L = {wcwR|w

К сожалению, ДМП-автоматы имеют меньшую распознавательную способность, чем МП-автоматы. Доказано, в частности, что
существуют КС-языки, не являющиеся детерминированными КС-языками (таковым, например, является язык из примера 4.1).
Рассмотрим еще одну важную разновидность МП-автомата.
Расширенным автоматом с магазинной памятью назовем семерку M = (Q, T,



во множество конечных подмножеств множества QЧ

МП-автомата остаются такими же, как для обычного.
Теорема 4.3. Пусть M = (Q, T,

Расширенный МП-автомат M = (Q, T,

- Множество D(q, a, u) содержит не более одного элемента для любых q Q, aT{e}, Z*;
- Если D(q, a, u), D(q, a, v)и uv, то не существует цепочки x такой, что u = vx или v = ux;
- Если D(q, a, u), D(q, e, v), то не существует цепочки x такой, что u = vx или v = ux.
Теорема 4.4. Пусть M = (Q, T,

ДМП-автомат и расширенный ДМП-автомат лежат в основе рассматриваемых далее в этой главе, соответственно, LL и LR-анализаторов.