Для доказательства uiara индукции предположим, что теорема верна для п. Рассмотрим вывод

Х...Xf+Xf...X-a-i,. .йд

Хр,. .XjYf... YiXj-i.. .Х-а.. Мд

jB котором на последнем шаге X/ заменяется цепочкой У...У, Поэтому Ху 1, ..., Xi-терминалы, причем случай 1 не исключается.

По предположению индукции Xy+i<»Xy или Xj+fXj. Поэтому Ху+1<« в силу леммы 5.3(1). К тому же Ху находится в одном из трех отношений с символом справа от него (которым может быть а,). Таким образом, K-i»>Xy i либо К, г при j =1. Так как У... Kj -правая часть правила, то Уг = -1=- • .. ~ К. Наконец, Xj-+j<JX(- или X/+i4=X для p<i<ij по предположению индукции. Теорема доказана. □

Следствие 1. Если G - грамматика предшествования, то утверлсдение (1) теоремы 5.14 можно усилить, добавив слова „точно одно из отношений <• или Утверждения (1) - (4)

можно усилить, добавив слова „и не выполняются никакие другие отношения.

Доказательство. Непосредственно следует из определения грамматики предшествования. □

Следствие 2. Каждая грамматика простого предшествования однозначна.

Доказательство. Надо лишь заметить, что для любой отличной от S правовыводимой цепочки р предыдущая право-выводимая цепочка а, для которой а=:>/.р, определяется однозначно. Из следствия 1 вытекает, что основу цепочки р можно однозначно определить, просматривая эту цепочку (ограниченную концевыми маркерами) слева направо, пока впервые не обнаружится отношение •>, а затем возвращаясь назад до ближайшего Основа лежит между ними. Так как грамматика простого предшествования обратима, то нетерминал, к которому надо свернуть основу, находится однозначно. Таким образом, а определяется по р однозначно. □

Заметим, что так как мы оперируем с приведенными грамматиками, нетрудно доказать, что этот и последующие алгоритмы тратят на разбор линейное время. Доказательства оставляем в качестве упражнений.

Теперь опишем, как по грамматике простого предшествования строить детерминированный правый анализатор.

Алгоритм 5.12. Построение алгоритма типа „перенос-свертка" для грамматик простого предшествования.

Вход. Грамматика простого предшествования G(N, 2, Р, 5), в которой правила занумерованы числами от 1 до р.

Выход. d - {f,g), алгоритм разбора типа „перенос-свертка" для грамматики С.

Метод.

(1) Алгоритм Я использует символ $ в качестве маркера дна магазина и правого концевого маркера входной цепочки.

(2) Функция переноса / зависит только от верхнего символа магазина и самого левого символа необработанной части входной цепочки. Поэтому зададим / только на (N U 2 U {$}) X (2 U {$}), за исключением одного случая (правило (в)):

(а) /(X, й)= перенос, если Х<а или Xja,

(б) /(X, а)-свертка, если Ха,

(в) f{$S, $)-допуск 1),

(г) / (X, а)-ошибка в остальных случаях.

(Правила реализуются с помощью матрицы предшествования.)

(3) Функция свертки g зависит только от верхней части магазинной цепочки, включающей основу и еще один символ ниже нее. Оставшаяся необработанной часть входной цепочки иа g не влияет. Поэтому зададим g только на (NU 2 и {$})*:

(а) (X,,XA i...Xi, e) = i, если Х, ,,<Х, Ху.Ху для k > 1 и А-Xf,X .. .Xj - правило с номером i. (Заметим, что функция g участвует только тогда, когда Xj5>a, где а -текущий входной символ.)

(б) g{oc, е) -ошибка в остальных случаях. □

Пример 5.35. Построим алгоритм разбора типа „перенос - свертка" U = (f, g) для грамматики G с правилами

(1) S-

(2) 5-

aSSb

Отноп1ення предшествования для грамматики G приведены на рис. 5.И. Функцию переноса f можно вычислить с помощью матрицы предшествования. Функция свертки g определяется так:

(1) g{XaSSb)=ly если Х€{5, а, $},

(2) (Х)-2, если Х€{5, а, $[.

(3) (а) = ошибка в остальных случаях.

) Заметим, что это правило имеет приоритет над правилами (2а) и (26), когда ХЗ и

Для входной цепочкн ассЬ алгоритм Л сделает такую последовательность шагов:

($. ассЬ$, е) \- ($а, ссЬ$, е) \-{$ас, сЬ$, е) К ($«5, сЬ$, 2) \-($aSc, b$, 2)

b, 22) \-{$aSSb, 22) $, 221)

В конфигурации {$ас, сЬ$, е), например, будет / (с, с)-свертка и g{ac\ е) = 2. Поэтому

($ас, сЬ$, e)l-{$aS, cb, 2)

Посмотрим, как ведет себя Л па цепочке асЬ, не принадлежащей языку L{G). Для этой цепочки алгоритм Л сделает последовательность шагов

{$, асЬ$, е)Ца, сЬ$, е) Ь$, е) Ь$, 2) $, 2)

[- ошибка

В конфигурации {$aSb, $, 2) будет /(&,$) = свертка. Так как ip<ia и а=8лЬ, то свертку можно сделать только, если aSb-правая часть какого-нибудь правила. Однако такого правила нет, и поэтому g{aSb, е) ошибка.

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

Теорема 5.15. Алгоритм 5.12 строит корректный алгоритм разбора типа „перенос-свертка для грамматики простого предшествования.

Доказательство. Теорема непосредственно следует из теоремы 5.14, свойства обратимости и конструкции алгоритма 5.12. Детали доказательства оставляем в качестве упражнения. □

Интересно изучить классы языков, порождаемых грамматиками предшествования и грамматиками простого предшествования. Оказывается, каждый КС-язык, не содержащий пустой цепочки е, определяется грамматикой предшествования, но не каждый такой КС-язык определяется грамматикой простого предшествования. Кроме того, для каждого КС-языка, не содержащего е, можно найти обратимую КС-грамматику без е-правил. Таким образом, если от грамматик требуется, чтобы они были обратимыми и грамматиками предшествования, то это уменьшает их порождающую способность. Каждая грамматика простого предшествования является ЬК(1)-грамматикой, но ЬК(1)-язык {аО111} и {ОТ-I i 1} не определяется никакой грамматикой простого предшествования (это будет показано в разд. 8.3).

5.3.3. Грамматики расширенного предшествования

Отношения предшествования Вирта-Вебера, определенные для пар символов, можно расширить на пары цепочек. Определим расширенные отношения предшествования - между цепочками из т символов и цепочками из п символов. Наше определение ориентировано на некоторый подразумеваемый алгоритм разбора тина „перенос - свертка".

Для понимания мотивов введения расширенного предшествования вспомним две роли, которые играют отношения предшествования в алгоритме типа „перенос-свертка".

(1) Пусть аХ-это т верхних символов магазина (причем X-самый верхний) и аи) -следующие п входных символов. Если aX<aw или аХ Jaw, то а надо перенести в магазин. Если aXaw, то надо сделать свертку.

(2) Допустим, что Хр.. .ХХу - цепочка в магазине и «1.. .а-необработанная часть входной цепочки в тот момент, когда вызывается процедура свертки (т. е. Х.. .Xi*>а-у.. .aJ. Если основой является Х-.-Х, то нам хочется, чтобы было

т+/т+/~1- • -Xj-i-i XjXji.. .Ха,.. .a j

для k> }\ и

т+к- fc-hi <?fc • -Хау.. .(2„ jl)

Таким образом, процедура разбора для обратимой грамматики раснщренного предшествования аналогична процедуре, соответствующей грамматике простого предшествования Вирта - Вебера, за исключением того, что отношение предшествования между символами X и К определяется цепочками аХ и Кр, где

) Предполагаем, что X;.X;--i.. .XjCi.. .с„-;- -X;.X;. i.. .X;. „4.i, если

а состоит ИЗ т-1 символов, расположенных слева от X, а р-из п-1 символов, расположенных справа от У.

Символы переносятся в магазин до тех пор, пока между цепочкой наверху магазина и оставшейся необработанной частью входной цепочки не встретится отношение Тогда возвращаемся по магазину назад, проходя отношения пока впервые не встретится <<. Между < и •> лежит основа.

Эти замечания мотивируют следующее определение.

Определение. Пусть G = (N, S, Я, S) - приведенная КС-грамматика без е-правил. Определим отношения [пг, /г)-предшество-вания <, и •> на множестве (N U 2 и {$})" X (N U 2 и {$})". Пусть

$-5$=ф;ХД, , ... Х,,Лй, ... а,

=>гХ,Х, 1 ... XiiXfc ... Ха • -

- произвольный правый вывод. Тогда

(1) а<«р, если а состоит из последних т символов цепочки XpXp i ... X;,+j и либо

(а) р состоит из первых п символов цепочки Xf ... Ха ... а, либо

(б) Хй-терминал п р G FIRST (Х ... Ха ... а)\

(2) ар для всех таких /е > / 1, что а состоит из последних т символов цепочки ХХ. ...Ху+ и либо

(а) р состоит из первых п символов цепочки XyXy j ... AHi ... ау либо

(б) X.-терминал и р 6 FIRSTX,X, i ... Ха ... аУ,

(3) ХА-, ... Х,}>а,...а„.

Будем говорить, что G-грамматика [т, п)-предшествования, если G-приведенная КС-грамматика без е-правил и отношения <•, = и •> попарно не пересекаются. Из леммы 5.3 с очевидностью следует, что G - грамматика предшествования тогда и только тогда, когда она - грамматика (1,1)-предшествования. Детали, связапЕГые с концевыми маркерами, легко восстанавливаются. При п--=1 условия (16) и (26) не дают ничего нового.

Заметим также, что если пересечение отношенпй < и J= непусто только за счет условий (16) и (26), все равно для такой грамматики расширенного предшествования найдется алгоритм разбора тина „перенос - свертка". Можно было бы дать более сложное, по менее ограничительное определение, по мы предпочитаем оставить читателю в виде упражнения разработку такого класса грамматик.

Изложим теперь алгоритм, вычисляющий отношения расширенного предшествования. Его, очевидно, можно применять и для вычисления отношений предшествования Вирта - Вебера.

Алгоритм 5.13. Построение отношений (т, п)-п р е д-шествовання.

Вход. Приведенная КС-грамматика G=(N, 2, Р, S) безе-правил. Выход. Отношения (т, п)-предшествования <, и i> для грамматики G.

Метод. Начнем с построения множества всех подцепочек длины т + п, которые могут встретиться в такой цепочке ccpw, что $"5$" аЛьу=:>г и W - FIRST,, (г:г). Это осуществляется так:

(1) Положим c5 = {$"5"-S $«-5$"}. Эти две цепочки в S считаются „нерассмотренными".

(2) Если б-нерассмотренная цепочка из „рассмотрим" ее, выполнив следующие две операции.

(а) Если. 6 не имеет вида аЛх, где Ixjn, то ничего не делать.

(б) Если Ь - аАх, \х]п и Л € N, то добавить к , если их еще нет там, цепочки у, для которых в Р найдется такое правило Л-р, что у -подцепочка длины т + п цепочки ссрл;. Заметим, что так как G - приведенная грамматика, то \сфх\т-\-п. Добавленные к цепочки считаются нерассмотренными.

(3) Повторять шаг (2), пока в не останется нерассмотренных цепочек.

По множеству построим отношения J= и •>:

(4) Для каждой цепочки ссЛу из zf, для которой сс -т, и для каждого правила Л-р из Р положим а<»б, где б - первые п символов цепочки Ру либо Р начинается терминалом

и бе FIRST ЛРТ)-

(5) Для каждой цепочки аЛу из , для которой \a\~m, и для каждого правила А-)ХУ2 положим ббз, где 6j - последние т символов цепочки арХ, а бд - первые п символов цепочки УРаУ, либо К-терминал, а ЬУгюнекоторой цепочки Ell) G FIRST„ i (раУ).

(6) Для каждой цепочки aAw из , для которой

и для каждого правила Л-р из Р положим б где б - последние т символов цепочки ар. □

Пример 5.36. Рассмотрим грамматику G с правилами 5-05111011

Отношения (1,1)-предшествования для нее приведены на рис. 5.12. Так как 1 •> 1 и 1 1, то G не является грамматикой (1,1)-пред-шествования.

С помощью алгоритма 5.13 вычислим для G отношения (2,1)-предшествования. Начнем с вычисления . Вначале