КС-грамматики и МП-автоматы

Синтаксический анализ

КС-грамматики и МП-автоматы

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

Вывод, в котором в любой сентенциальной форме на каждом шаге делается подстановка самого левого нетерминала, называется левосторонним. Если S ^*u в процессе левостороннего вывода, то u - левая сентенциальная форма. Аналогично определяется правосторонний вывод. Будем обозначать шаги левого (правого) вывода посредством _l ( _r).

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

Упорядоченным помеченным деревом называется упорядоченный граф (V, E), основой которого является дерево и для которого определена функция f: V F (функция разметки) для некоторого множества F.

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

• корень дерева D помечен S;
• каждый лист помечен либо a T, либо e;
• каждая внутренняя вершина помечена нетерминалом A N;
• если X - нетерминал, которым помечена внутренняя вершина и X₁,..., X_n - метки ее прямых потомков в указанном порядке, то X X₁...X_k - правило из множества P;
• Цепочка, составленная из выписанных слева направо меток листьев, равна w.

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

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

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

• Q - конечное множество состояний, представляющих всевозможные состояния управляющего устройства;
• T - конечный входной алфавит;
• - конечный алфавит магазинных символов;
• D - отображение множества QЧ(T {e})Ч в множество конечных подмножеств QЧ ^*, называемое функцией переходов;
• q₀ Q - начальное состояние управляющего устройства;
• Z₀ - символ, находящийся в магазине в начальный момент (начальный символ магазина);
• 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 называется конфигурация вида (q₀, w, Z₀), где w T^*, т.е. управляющее устройство находится в начальном состоянии, входная лента содержит цепочку, которую нужно проанализировать, а в магазине находится только начальный символ Z₀.

Заключительная конфигурация - это конфигурация вида (q, e, u), где q F, u ^*, т.е. управляющее устройство находится в одном из заключительных состояний, а входная цепочка целиком прочитана.

Введем транзитивное и рефлексивно-транзитивное замыкание отношения , а также его степень k 0 (обозначаемые ⁺, ^* и ^k соответственно).

Говорят, что цепочка w допускается МП-автоматом M, если (q₀, w, Z₀) ^*(q, e, u) для некоторых q F и u ^*.

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

Пример 4.1. Рассмотрим МП-автомат

у которого функция переходов D содержит следующие элементы:

 

D(q₀, a, Z) = {(q₀, aZ)},

D(q₀, b, Z) = {(q₀, bZ)},

D(q₀, a, a) = {(q₀, aa), {q₁, e)},

D(q₀, a, b) = {(q₀, ab)},

D(q₀, b, a) = {(q₀, ba)},

D(q₀, b, b) = {(q₀, bb), (q₁, e)},

D(q₁, a, a) = {(q₁, e)},

D(q₁, b, b) = {(q₁, e)},

D(q₁, e, Z) = {(q₂, e)}.

 

Нетрудно показать, что L(M) = {ww^R|w {a, b}⁺}, где w^R обозначает обращение («переворачивание») цепочки w.

Иногда допустимость определяют несколько иначе: цепочка w допускается МП-автоматом M, если (q₀, w, Z₀) ^*(q, e, e) для некоторого q Q. В таком случае говорят, что автомат допускает цепочку опустошением магазина. Эти определения эквивалентны, ибо справедлива

Теорема 4.1. Язык допускается магазинным автоматом тогда и только тогда, когда он допускается (некоторым другим автоматом) опустошением магазина.

Доказательство. Пусть L = L(M) для некоторого МП-автомата M = (Q, T, , D, q₀, Z₀, F). Построим новый МП-автомат M', допускающий тот же язык опустошением магазина.

Пусть M' = (Q {q₀', q_e}, T, {Z₀'}, D', q₀', Z₀', ), где функция переходов D' определена следующим образом:

• Если (r, u) D(q, a, Z), то (r, u) D'(q, a, Z) для всех q Q, a T {e} и Z ;
• D'(q₀', e, Z₀') = {(q₀, Z₀Z₀')};
• Для всех q F и Z {Z₀'} множество D'(q, e, Z) содержит (q_e, e);
• D'(q_e, e, Z) = {(q_e, e)} для всех Z {Z₀'}.

Автомат сначала переходит в конфигурацию (q₀, w, Z₀Z₀') в соответствии с определением D' в п.2, затем в (q, e, Y ₁...Y _kZ₀'), q F в соответствии с п.1, затем в (q_e, e, Y ₁...Y _kZ₀'), q F в соответствии с п.3, затем в (q_e, e, e) в соответствии с п.4. Нетрудно показать по индукции, что (q₀, w, Z₀) ⁺(q, e, u) (где q F) выполняется для автомата M тогда и только тогда, когда (q₀', w, Z₀') ⁺(q_e, e, e) выполняется для автомата M'. Поэтому L(M) = L', где L' - язык, допускаемый автоматом M' опустошением магазина.

 

Обратно, пусть M = (Q, T, , D, q₀, Z₀, ) - МП-автомат, допускающий опустошением магазина язык L. Построим автомат M', допускающий тот же язык по заключительному состоянию.

Пусть M' = (Q {q₀', q_f}, T, {Z₀}, D', q₀', Z₀', {q_f}), где D' определяется следующим образом:

• D'(q₀', e, Z₀') = {(q₀, Z₀Z₀')} - переход в «режим M»;
• Для каждого q Q, a T {e}, и Z определим D'(q, a, Z) = D(q, a, Z) - работа в «режиме M»;
• Для всех q Q, (q_f, e) D'(q, e, Z₀') - переход в заключительное состояние.

Нетрудно показать по индукции, что 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, q₀, Z₀, ) - МП-автомат, допускающий опустошением магазина язык L. Построим грамматику G, порождающую язык L.

Пусть G = ({ [qZr] | q, r Q, Z } {S}, T, P, S), где P состоит из правил следующего вида:

• Если (r, X₁...X_k) D(q, a, Z), k 1, то

для любого набора s₁, s₂,..., s_k состояний из Q;

• Если (r, e) D(q, a, Z), то [qZr] a P, a T {e};
• S [q₀Z₀q] P для всех q Q.

Нетерминалы и правила вывода грамматики определены так, что работе автомата M при обработке цепочки w соответствует левосторонний вывод w в грамматике G.

Индукцией по числу шагов вывода в G или числу тактов M нетрудно показать, что (q, w, A) ⁺(p, e, e) тогда и только тогда, когда [qAp] ⁺w.

Тогда, если w L(G), то S [q₀Z₀q] ⁺w для некоторого q Q. Следовательно, (q₀, w, Z₀) ⁺(q, e, e) и поэтому w L. Аналогично, если w L, то (q₀, w, Z₀) ⁺(q, e, e). Значит, S [q₀Z₀q] ⁺w, и поэтому w L(G). __

МП-автомат M = (Q, T, , D, q₀, Z₀, 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(q₀, X, Y) = (q₀, XY), X {a, b}, Y {Z, a, b},

D(q₀, c, Y) = (q₁, Y), Y {a, b},

D(q₁, X, X) = (q₁, e), X {a, b},

D(q₁, e, Z) = (q₂, e).

 

Нетрудно показать, что этот детерминированный МП-автомат допускает язык L = {wcw^R|w {a, b}⁺}.

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

Рассмотрим еще одну важную разновидность МП-автомата.

Расширенным автоматом с магазинной памятью назовем семерку M = (Q, T, , D, q₀, Z₀, F), где смысл всех символов тот же, что и для обычного МП-автомата, кроме D, представляющего собой отображение конечного подмножества множества QЧ(T {e})Ч ^* во множество конечных подмножеств множества QЧ ^*. Все остальные определения (конфигурации, такта, допустимости) для расширенного МП-автомата остаются такими же, как для обычного.

Теорема 4.3. Пусть M = (Q, T, , D, q₀, Z₀, F) - расширенный МП-автомат. Тогда существует такой МП-автомат M', что L(M') = L(M).

Расширенный МП-автомат M = (Q, T, , D, q₀, Z₀, 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, q₀, Z₀, F) - расширенный ДМП-автомат. Тогда существует такой ДМП-автомат M', что L(M') = L(M).

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