Метод. E : = E(M) - {e} U {e(e, тг)тг G adj (e) - {end(e}}; V := {P0(M)} U{P G V(M) Этг G E P инцидентна дуге п}; Fin := V П [Fin(M) U {beg(e) end(e) G Fin(M)}].

Начальный участок предложения назовем инициальным маршрутом. Используем этот термин в следующей лемме, которая доказывает эквивалентность графа, создаваемого алгоритмом 2, входному автомату.

Лемма 3. Пусть M - магазинный автомат, e G E+(M), L = L(Eps(ExtG(M), e)). Тогда L = L(ExtG(M)). Следовательно, L = L(M).

Доказательство. Достаточно указать, что существует сюръективное отображение множества инициальных маршрутов графа G = ExtG(M) на множество инициальных маршрутов графа G = Eps(G, e), при котором маршрут T графа G и его образ T имеют одинаковые заряды и пометки, а вершины end(T) и end(T) одновременно являются или не являются заключительными.

Произвольный маршрут T в графе G можно представить в виде

T = T0eniTi ... ennTn,

где n > 0, T0 не содержит дуги e, для i = 1,... ,n участок nT не содержит дуги e и либо пуст, либо п G adj(e). Расширим понятие вычеркивания следующим образом: e(e, T) = T0e(e, ni)T .. .e(e, nn)Tn. Оно и будет искомым сюръективным отображением. В самом деле, из конструкции графа G следует, что T = e(e,T), где T - инициальный маршрут графа G, есть инициальный маршрут в G, причем u(T) = u(T), p(T) = n(T) и вершины end(T) и end(T) одновременно являются или не являются заключительными. инициальных маршрутов, не принадлежащих множеству

{e(e,T) T - инициальный маршрут графа G}, граф G, по построению, не имеет □

Лемма 4. Если M есть ДМА и e G E+ (M), то

Automaton(Eps(ExtG(M), e))

является ДМА.

Доказательство. Дуга e не является стирающей, так как она принадлежит мно жеству E+(M). Вследствие детерминированности автомата M вершина beg(e) является начальной вершиной только одной дуги - нечитающей нестирающей дуги e. Алгоритм 2 заменяет эту дугу некоторым подмножеством A С {e(e, en) G adj(e)}. Дуги множества A отличаются от дуг автомата M, имеющих начальную вершину end(e), только своей начальной вершиной. Предположение, что из за дуг множества A нарушается свойство детерминированности, означало бы, что оно нарушается и дугами из adj(e). Однако исходный автомат является детерминированным □

Из теоремы 1 следует, что можно без ограничения общности предполагать однозначность рассматриваемых ДМА.

Алгоритм 3. Преобразование ДМА в ДАНРВ.

Вход. Однозначный ДМА M = (K, Т., Г, Z(i, S,po, F).

Выход. Магазинный автомат

RealTimeCharging(M) = (K, Е, Г, Z0, 5,p0, F).

Шаг 1. G := ExtG(M).

Шаг 2. Пока E+(G) = 0, выполнять следующие два действия: выбрать дугу б е E+(G) П {п adj(n) П E+(G) = 0}; G : = Eps(G, б).

Шаг 3. Положить автомат RealTimeCharging(M) равным Automaton(G).

Лемма 5. Пусть M - однозначный ДМА и E+(M) = 0. Тогда существует такая дуга б е E+(M), что adj (б) П E+(M) = 0.

Доказательство. Предположим, что для любой б е E+(M) пересечение adj (б) П E+(M) непусто. Тогда существует последовательность б1, бп+1, где n = E+(M), б! е E+(M) и 6j+i е adj(б) ПE+(M) для j = 1,... ,n. Отсюда имеем соотношения endj) = beg(бj+!), j = 1,... ,n. Так как, кроме того, каждая дуга множества E+(M) является нейтральной или накапливающей, б! . . . бп+! есть марш рут. Так как его длина больше E+(M), для некоторых k и l, 1 < k <l < n + 1, имеет место равенство бк = б\. Но тогда бк ... б1-! есть нечитающий нейтральный или накапливающий цикл, что противоречит однозначности автомата M □

Теорема 2. Если M - однозначный ДМА, то:

1)алгоритм 3 заканчивает работу;

2)RealTimeCharging(M) является ДМА и эквивалентен M.

Доказательство. Первое утверждение теоремы следует из леммы 5, второе - из лемм 3 и 4 □

§2. Ядро бесконтекстной грамматики и синтаксический анализ

Слово "грамматика"в данном параграфе обозначает приведенную [Aho -Ullman 72] бесконтекстную грамматику

G =(N, Е, P, S),

где N - нетерминальный алфавит, Е - терминальный алфавит, S е N - начальный символ, P - правила. Положим V = N U Е. Условимся обозначать нетерминальные символы большими, а терминальные маленькими буквами нача ла латинского алфавита.

Здесь рассматриваются только правовыводимые сентенциальные формы. Для краткости они упоминаются как сентенциальные формы. Алгоритм синтаксиче ского анализа обозначается словом "анализатор".

Пункт 2.1 вводит понятия ядра и характеристики бесконтекстной грамматики. Характеристика является модификацией ядра, удобной для построения недетерминированного анализатора, работающего как LR(1) анализатор для каждого из случаев разбора анализируемой цепочки. В пункте 2.2 определяется сам анализатор и доказывается, что он корректен. В пункте 2.3 рассматриваются прие -мы оптимизации анализатора, обоснование которых базируется на представлении

анализатора преобразователем с магазинной памятью и, следовательно, определенным образом обобщенным, "преобразующимТЗграфом. Здесь затрагивается один из сложнейших и интереснейших вопросов теории синтаксического анализа - вопрос уменьшения таблиц, используемых ЬР(к)анализатором. Наш подход вскрывает суть явлений, обусловливающих громоздкость ЬР(к)таблиц, и указывает границы достижимого при сокращении этих таблиц. Отмечается, что вместе с приемом расщепления грамматики, разработанным под руководством автора, сформулированные в пункте 2.3 приемы дают практически приемлемый метод построения ЬР(1)анализаторов. При этом наш метод применим к любой ЬР(1)-грамматике, а его эффект заключает в себе действие ранее известных спосо бов оптимизации ЬР(1)анализаторов (например, оптимизация анализатора, предусматриваемая ЬЛЬР(1)методом, полностью учитывается нашим методом).

2.1. Ядро и характеристика бесконтекстной грамматики. Для бесконтекстной грамматики определяется понятие структуры. Это один из вариантов линй -ной записи дерева вывода. Таким образом, структура представляет информацию, которую извлекает анализатор, причем представляет удачно в том смыс ле, что весьма точно указывает схему вычисления, выполняемого анализатором преобразователем с магазинной памятью.

В терминах структур для грамматик определяются понятия канона и ядра, ана -логия которых с одноименными понятиями, введенными в главе 1, достаточно яс на. В целом получается система понятий, позволяющая доказать известный факт об эквивалентности бесконтекстных грамматик и магазинных автоматов таки ми построениями, которые обеспечивают тесное соответствие всех особенностей эквивалентных устройств и, главное, возможность дотошно выяснить это соот ветствие. В данном параграфе фактически дается построение по бесконтекстной грамматике эквивалентного магазинного автомата. Ему в определенном смысле родственно построение грамматики по автомату, рассмотренное в [Вылиток 98].

2.1.1. Структуры. Каноны

Назовем грамматику

Augm(G) = (N U {So}, £ U (±>, P U {So - ±S±}, So), где S0, ± G V, пополнением грамматики

G = (N, £,P,S).

Правилу

So - ±S ±

грамматики Augm(G) сопоставим номер 0. Пусть P = s. Занумеруем правила грамматики G в некотором порядке номерами 1,..., s. Обозначим ре правило грамматики Augm(G) записью

0 < р < s, np > 0, Xpj G V U {S0, ±} для 1 < j < np. Обозначим через

Struct (G)