КС-грамматики и МП-автоматы
Синтаксический анализ
КС-грамматики и МП-автоматы
Пусть G = (N, T, P, S) - контекстно-свободная грамматика. Введем несколько важных понятий и определений.
Вывод, в котором в любой сентенциальной форме на каждом шаге делается подстановка самого левого нетерминала, называется левосторонним. Если S 
*u в процессе левостороннего вывода, то u - левая сентенциальная форма. Аналогично определяется правосторонний вывод. Будем обозначать шаги левого (правого) вывода посредством l ( r).
Упорядоченным графом называется пара (V, E), где V есть множество вершин, а E - множество линейно упорядоченных списков дуг, каждый элемент которого имеет вид ((v, v1), (v, v2), ..., (v, vn)). Этот элемент указывает, что из вершины v выходят n дуг, причем первой из них считается дуга, входящая в вершину v1, второй - дуга, входящая в вершину v2, и т.д.
Упорядоченным помеченным деревом называется упорядоченный граф (V, E), основой которого является дерево и для которого определена функция f : V 
F (функция разметки) для некоторого множества F.
Упорядоченное помеченное дерево D называется деревом вывода (или деревом разбора) цепочки w в КС-грамматике G = (N, T, P, S), если выполнены следующие условия:
- корень дерева D помечен S;
- каждый лист помечен либо a
T, либо e; - каждая внутренняя вершина помечена нетерминалом A N;
- если X - нетерминал, которым помечена внутренняя вершина и X1, ..., Xn - метки ее прямых потомков в указанном порядке, то X X1...Xk - правило из множества P;
- Цепочка, составленная из выписанных слева направо меток листьев, равна w.
Грамматика G называется неоднозначной, если существует цепочка w, для которой имеется два или более различных деревьев вывода в G.
Грамматика G называется леворекурсивной, если в ней имеется нетерминал A такой, что существует вывод A +A 
для некоторой цепочки .
Автомат с магазинной памятью (МП-автомат) - это семерка M = (Q, T, 
, D, q0, Z0, F), где
- Q - конечное множество состояний, представляющих всевозможные состояния управляющего устройства;
- T - конечный входной алфавит;
- - конечный алфавит магазинных символов;
- D - отображение множества QЧ(T
{e})Ч в множество конечных подмножеств QЧ *, называемое функцией переходов; - q0 Q - начальное состояние управляющего устройства;
- Z0 - символ, находящийся в магазине в начальный момент (начальный символ магазина);
- F
Q - множество заключительных состояний.
Конфигурацией МП-автомата называется тройка (q, w, u), где
- q Q - текущее состояние управляющего устройства;
- w T* - непрочитанная часть входной цепочки; первый символ цепочки w находится под входной головкой; если w = e, то считается, что вся входная лента прочитана;
- u * - содержимое магазина; самый левый символ цепочки u считается верхним символом магазина; если u = e, то магазин считается пустым.
Такт работы МП-автомата M будем представлять в виде бинарного отношения 
, определенного на конфигурациях. Будем писать
если множество D(q, a, Z) содержит (p, v), где q, p Q, a T {e}, w T*, Z и u, v *.
Начальной конфигурацией МП-автомата M называется конфигурация вида (q0, w, Z0), где w T*, т.е. управляющее устройство находится в начальном состоянии, входная лента содержит цепочку, которую нужно проанализировать, а в магазине находится только начальный символ Z0.
Заключительная конфигурация - это конфигурация вида (q, e, u), где q F, u *, т.е. управляющее устройство находится в одном из заключительных состояний, а входная цепочка целиком прочитана.
Введем транзитивное и рефлексивно-транзитивное замыкание отношения , а также его степень k 
0 (обозначаемые +, * и k соответственно).
Говорят, что цепочка w допускается МП-автоматом M, если (q0, w, Z0) *(q, e, u) для некоторых q F и u *.
Язык, допускаемый (распознаваемый, определяемый) автоматом 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 
{a, b}+}, где wR обозначает обращение («переворачивание») цепочки w.
Иногда допустимость определяют несколько иначе: цепочка w допускается МП-автоматом M, если (q0, w, Z0) *(q, e, e) для некоторого q Q. В таком случае говорят, что автомат допускает цепочку опустошением магазина. Эти определения эквивалентны, ибо справедлива
Теорема 4.1. Язык допускается магазинным автоматом тогда и только тогда, когда он допускается (некоторым другим автоматом) опустошением магазина.
Доказательство. Пусть L = L(M) для некоторого МП-автомата M = (Q, T, , D, q0, Z0, F). Построим новый МП-автомат M', допускающий тот же язык опустошением магазина.
Пусть M' = (Q {q0', qe}, T, {Z0'}, D', q0', Z0', 
), где функция переходов D' определена следующим образом:
- Если (r, u) D(q, a, Z), то (r, u) D'(q, a, Z) для всех q Q, a T {e} и Z ;
- D'(q0', e, Z0') = {(q0, Z0Z0')};
- Для всех q F и Z {Z0'} множество D'(q, e, Z) содержит (qe, e);
- D'(qe, e, Z) = {(qe, e)} для всех Z {Z0'}.
Автомат сначала переходит в конфигурацию (q0, w, Z0Z0') в соответствии с определением D' в п.2, затем в (q, e, Y 1...Y kZ0'), q F в соответствии с п.1, затем в (qe, e, Y 1...Y kZ0'), q F в соответствии с п.3, затем в (qe, e, e) в соответствии с п.4. Нетрудно показать по индукции, что (q0, w, Z0) +(q, e, u) (где q F) выполняется для автомата M тогда и только тогда, когда (q0', w, Z0') +(qe, e, e) выполняется для автомата M'. Поэтому L(M) = L', где L' - язык, допускаемый автоматом M' опустошением магазина.
Обратно, пусть M = (Q, T, , D, q0, Z0, ) - МП-автомат, допускающий опустошением магазина язык L. Построим автомат M', допускающий тот же язык по заключительному состоянию.
Пусть M' = (Q {q0', qf}, T, {Z0}, D', q0', Z0', {qf}), где D' определяется следующим образом:
- D'(q0', e, Z0') = {(q0, Z0Z0')} - переход в «режим M»;
- Для каждого q Q, a T {e}, и Z определим D'(q, a, Z) = D(q, a, Z) - работа в «режиме M»;
- Для всех q Q, (qf, e) D'(q, e, Z0') - переход в заключительное состояние.
Нетрудно показать по индукции, что L = L(M'). __
Одним из важнейших результатов теории контекстно-свободных языков является доказательство эквивалентности МП-автоматов и КС-грамматик.
Теорема 4.2. Язык является контекстно-свободным тогда и только тогда, когда он допускается магазинным автоматом.
Доказательство. Пусть G = (N, T, P, S) - КС-грамматика. Построим МП-автомат M, допускающий язык L(G) опустошением магазина.
Пусть M = ({q}, T, N T, D, q, S, ), где D определяется следующим образом:
- Если A u P, то (q, u) D(q, e, A);
- D(q, a, a) = {(q, e)} для всех a T.
Фактически, этот МП-автомат в точности моделирует все возможные выводы в грамматике G. Нетрудно показать по индукции, что для любой цепочки w T* вывод S +w в грамматике G существует тогда и только тогда, когда существует последовательность тактов (q, w, S) +(q, e, e) автомата M.
Обратно, пусть M = (Q, T, , D, q0, Z0, ) - МП-автомат, допускающий опустошением магазина язык L. Построим грамматику G, порождающую язык L.
Пусть G = ({ [qZr] | q, r Q, Z } {S}, T, P, S), где P состоит из правил следующего вида:
- Если (r, X1...Xk) D(q, a, Z), k 1, то
для любого набора s1, s2, ..., sk состояний из Q;
- Если (r, e) D(q, a, Z), то [qZr] a P, a T {e};
- S [q0Z0q] P для всех q Q.
Нетерминалы и правила вывода грамматики определены так, что работе автомата M при обработке цепочки w соответствует левосторонний вывод w в грамматике G.
Индукцией по числу шагов вывода в G или числу тактов M нетрудно показать, что (q, w, A) +(p, e, e) тогда и только тогда, когда [qAp] +w.
Тогда, если w L(G), то S [q0Z0q] +w для некоторого q Q. Следовательно, (q0, w, Z0) +(q, e, e) и поэтому w L. Аналогично, если w L, то (q0, w, Z0) +(q, e, e). Значит, S [q0Z0q] +w, и поэтому w L(G). __
МП-автомат M = (Q, T, , D, q0, Z0, F) называется детерминированным (ДМП-автоматом), если выполнены следующие два условия:
- Множество D(q, a, Z) содержит не более одного элемента для любых q Q, a T {e}, Z ;
- Если D(q, e, Z)
, то D(q, a, Z) = для всех a T.
Язык, допускаемый ДМП-автоматом, называется детерминированным КС-языком.
Так как функция переходов ДМП-автомата содержит не более одного элемента для любой тройки аргументов, мы будем пользоваться записью D(q, a, Z) = (p, u) для обозначения D(q, a, Z) = {(p, u)}.
Пример 4.2. Рассмотрим ДМП-автомат
у которого функция переходов определяется следующим образом:
D(q0, X, Y ) = (q0, XY ), X {a, b}, Y {Z, a, b},
D(q0, c, Y ) = (q1, Y ), Y {a, b},
D(q1, X, X) = (q1, e), X {a, b},
D(q1, e, Z) = (q2, e).
Нетрудно показать, что этот детерминированный МП-автомат допускает язык L = {wcwR|w {a, b}+}.
К сожалению, ДМП-автоматы имеют меньшую распознавательную способность, чем МП-автоматы. Доказано, в частности, что существуют КС-языки, не являющиеся детерминированными КС-языками (таковым, например, является язык из примера 4.1).
Рассмотрим еще одну важную разновидность МП-автомата.
Расширенным автоматом с магазинной памятью назовем семерку M = (Q, T, , D, q0, Z0, F), где смысл всех символов тот же, что и для обычного МП-автомата, кроме D, представляющего собой отображение конечного подмножества множества QЧ(T {e})Ч * во множество конечных подмножеств множества QЧ *. Все остальные определения (конфигурации, такта, допустимости) для расширенного МП-автомата остаются такими же, как для обычного.
Теорема 4.3. Пусть M = (Q, T, , D, q0, Z0, F) - расширенный МП-автомат. Тогда существует такой МП-автомат M', что L(M') = L(M).
Расширенный МП-автомат M = (Q, T, , D, q0, Z0, F) называется детерминированным, если выполнены следующие условия:
- Множество D(q, a, u) содержит не более одного элемента для любых q Q, a T {e}, Z *;
- Если D(q, a, u) , D(q, a, v) и u v, то не существует цепочки x такой, что u = vx или v = ux;
- Если D(q, a, u) , D(q, e, v) , то не существует цепочки x такой, что u = vx или v = ux.
Теорема 4.4. Пусть M = (Q, T, , D, q0, Z0, F) - расширенный ДМП-автомат. Тогда существует такой ДМП-автомат M', что L(M') = L(M).
ДМП-автомат и расширенный ДМП-автомат лежат в основе рассматриваемых далее в этой главе, соответственно, LL и LR-анализаторов.