(q, i, ар, у)Н(9» ссЛ, /у)

При условии, ЧТО А-j-p - правило из Р с номером / и р - первая правая часть в линейном упорядочении, определенном в (1), которая является суффиксом цепочки ар. Номер этого правила записывается в L2. Если шаг 1 применим, повторить его. В противном случае перейти к шагу 2.

Шаг 2. Перенос

(я, ct, y)\-(q, /-fl, аа;, sy)

при условии, что 1фП\\. Перейти к шагу 1. Если i = п-\-\, перейти к шагу 3.

При выполнении шага 2 i-й входной символ переносится в верхнюю часть магазина Л1, позиция входного указателя увеличивается и в магазин L2 записывается s, чтобы указать, что сделан перенос.

Шаг 3. Допускание

(q, rt+1, $5, v)l-( rt+1, $5, v)

Выдать Я (у), где h - гомоморфизм, определенный равенствами h(s)=e, h(l) = j для всех номеров правил, h(y) - обращенный правый разбор цепочки w. После этого остановиться. Если шаг 3 неприменим, перейти к шагу 4.

Шаг 4. Переход в состояние возврата

(q, п+1, а, у)\-{Ь, rt+1, а, у)

при условии, что аф$3. Перейти к шагу 5.

Шаг 5. Возврат

(а) (&, i, аА, jy)\-{q, аВ, ky)

если А->р - правило из Р с номером /, а следующим правилом в упорядочении (1), правая часть которого является суффиксом цепочки ар, является правило В->-Р с номером k. (Заметим, что арар.) Перейти к шагу 1. (Здесь происходит возврат к предыдущей свертке и делается попытка свертки с помощью следующей альтернативы.)

(б) (Ь, п+1, аА, jy)\-(b, п+\, ар, у)

если Л--р - правило из Р с номером / и для цепочки ар пе остается никакой другой свертки. Перейти к шагу 5. (Если других сверток не существует, надо «взять назад» данную свертку н продолжать возврат, оставляя входной указатель на позиции п+\.)

если i:

(b, i, аА, !y)\-(q, /+1, ара, sy)

rt-fl, Л-i-p - правило из P с номером / и для ар не остается никакой другой свертки. Здесь символ aai перено-

Одна такая лозушка оказывается тогда, когда грамматика содержит циклы, т, е. выводы вида Л~>""Л для некоторого нетерминала Л. Число частичных деревьев может быть в этом случае бесконечным, так что грамматики с циклами мы исключим из рассмотрения. Трудности создаются также е-правилами, так как тогда можно проделать произвольное число сверток, при которых пустая цепочка «свертывается» к нетерминалу. Восходящий разбор можно расширить так, чтобы он охватывал грамматики с -правилами, но пока для простоты мы предпочитаем обходиться без е-правил.

Алгоритм 4.2. Восходящий разбор с возвратами.

Вход. КС-грамматика G (N, S, P,S) без циклов и -правил (все ее правила занумерованы от 1 до р) и входная цепочка

Выход. Один обращенный правый разбор, если он существует, и слово «ошибка» в противном случае. Метод.

(1) Произвольным образом упорядочить правила.

(2) Алгоритм будет изложен в терминах 4-компонентных конфигураций, подобных тем, что использовались в алгоритме 4.1. В конфигурации (s, /, а, Р)

(а) S представляет состояние алгоритма,

(б) / представляет текущую позицию входного указателя (предполагается, что (/г + 1)-м входным символом служит правый концевой маркер $),

(в) а-содержимое магазина L1 (верх которого расположен справа)

(г) р - содержимое магазина L2 (верх которого расположен слева).

Как и раньше, алгоритм может находиться в одном из трех состояний b или f. В магазине L1 будет храниться цепочка терминалов и нетерминалов, из которой выводится часть входной цепочки, расположенная слева от входного указателя. В магазине L2 будет храниться история переносов и сверток, необходимых для получения из входной цепочки содержимого магазина L1.

(3) Начальная конфигурация алгоритма -(, 1$, е).

(4) Сам алгоритм работает так. Начинаем с попытки применить шаг 1.

Шаг 1. Попытка свертки

сится в магазин Ы, а символ s поступает в L2. Перейти к шагу 1.

(Мы вернулись к предыдущей свертке и, так как других сверток нет, попробуем сделать перенос.)

(г) ф, i, аа, sy)[-{b, ( - 1, а, у)

если наверху магазина L2 находится символ переноса s. (Здесь в позиции i исчерпаны все альтернативы и надо «взять назад» операцию переноса. Входной указатель сдвигается влево, терминальный символ устраняется из L1, а символ переноса fins L2). Если этот шаг невыполним, объявить об ошибке. □

Пример 4.4. Применим описанный алгоритм восходящего разбора к грамматике G с правилами

(1) Е-В + Т

(2) Е~Т

(3) T-TF

(4) T~F

(5) F~a

Если наверху магазина L1 появится Е-\-Т, то сначала попытаемся сделать свертку, используя £+Г, а потом -используя Е~Т. Если же появится 7"*, то сначала попробуем X-TiF, а потом T-*F. Для входа а»а восходящий алгоритм пройдет через конфигурации

(q, и $, e)Y-(q. 2, $а, s)

1-Й. 2, $Р, 5s)

Н {q. 2, $Г, 45s)

(9, 2, $£, 245s)

-(9, 3, s245s)

1-(9, 4, ss245s)

i-(f?. 4, 5ss245s)

I-(9. 4, $EiT, 45ss245s)

\-(q, 4, 245ss245s)

\-{b, 4, 245ss245s)

4, $£*r, 45ss245s)

l-(ij, 4, 5ss245s)

1-(&, 4, $£*t2, ss245s)

+ (&, 3, s245s)

\-{b, 2, $£, 245s)

[~(q> 3, $r*, s45s)

[-((7, 4, ss45s)

I-(9, 4, $TF, 5ss45s)

h(9, 4, $r, 35ss45s)

\-{q, 4, $£, 235ss45s)

[-(t, 4, $£, 235ss45s) □

Корректность алгоритма 4.2 можно доказать способом, аналогичным тому, которым было показано, что нисходящий алгоритм работает правильно. Мы дадим здесь лишь набросок доказательства, оставляя большую часть деталей в качестве упражнения.

Определение. Пусть G = (N, 2, Р, 5) -КС-грамматика. Будем называть п частичным правым разбором, совместимым с w, если существуют такие а (N и 2)* и префикс х цепочки w, что ayRX.

Лемма 4.5. Пусть G -КС-грамматика без циклов и без е-пра-вил. Тогда найдется такая константа с, что число частичных правых разборов, совместимых с входной цепочкой длины п, не превосходит с\

Доказательство. Упражнение. П

Теорема 4.4. Алгоритм 4.2 правильно находит правый разбор цепочки W, если он существует, и сигнализирует об ошибке в противном случае.

Доказательство. По лемме 4.5 число частичных правых разборов, совместимых с входной цепочкой, конечно. В качестве упражнения предлагаем показать, что пока алгоритм 4.2 не найдет разбор входной цепочки, оп перебирает в естественном порядке все частичные правые разборы. А именно, каждый частичный правый разбор кодируется последовательностью индексов правил и символов переноса (s), и алгоритм 4.2 рассматривает все такие кодирующие последовательности в лексикографическом порядке. Этот лексикографический порядок определяется порядком символов, в котором S находится на последнем месте, а упорядочение индексов правил задается шагом 1 алгоритма 4.2. Заметим, что не каждая последовательность таких символов будет кодом совместимого частичного правого разбора. □

Так же, как для алгоритма 4.1, можно показать, что длины ЛЕагазииных списков в конфигурациях алгоритма 4.2 линейно зависят от длины входной цепочки.

Теорема 4.5. Пусть для каоюдого символа из магазинных цепочек, участвующих в конфигурациях алгоритма 4.2, требуется только одна ячейка, и пусть число элементарных операций, неооходимых для вычисления одного шага алгоритма 4.2, ограни-ено. Тогда для входной цепочки длины п алгоритму 4.2 требуются емкость памяти с,п и время с, где с, и с~некотооые foHcmaHmbi.

Доказательство. Упражнение. □

Какую последовательность шагов сделает алгоритм 4.2, если более длинная альтернатива считается первой, а входной цепочкой является

(а) аЬ}

(б) abab}

Что будет, если первой считать болеекороткую альтернативу?

4.1.3. Покажите, что каждая КС-грамматика без циклов, не порождающая пустой цепочки, правопокрывается грамматикой, для которой работает алгоритм 4.2, но может не левопокрываться грамматикой, для которой работает алгоритм 4.1.

*4.1.4. Покажите, что рекуррентные соотношения

D(d) = (D(rf~in+l

определяют функцию D (d) ~ ]k% где k-некоторое вещественное число, а наименьшее целое число > л;. Здесь ft = 1,502837... ,

4.1.5. Дополните доказательство следствия 2 леммы 4.4.

4.1.6. Модифицируйте алгоритм 4.1 так, чтобы можно было отказаться от использования альтернативы, если из левовыводи-мой цепочки, получающейся после ее применения, нельзя вывести k очередных входных символов, где ft-фиксированное число.

4.1.7. Модифицируйте алгоритм 4Л так, чтобы он работал для произвольной грамматики, наложив ограничения на рост длин магазинов Ы а L2.,

**4.1.8. Дайте необходимое н достаточное условие, которому должна удовлетворять входная грамматика для того, чтобы алгоритм 4.1 никогда не оказывался в состоянии возврата.

4.1.9. Докажите лемму 4.5.

4.1.10. Докажите теорему 4.5.

4.1.11. Модифицируйте алгоритм 4.2 так, чтобы он работал для произвольной грамматики, наложив ограничения на длины магазинов L1 и L2.

4.1.12. Модифицируйте алгоритм 4.2 так, чтобы он работал быстрее, введя в него проверку того, что частичный правый разбор вместе с частью входной цепочки, расположенной справа от указателя, не содержат ни одной из цепочек длины ft,которые не Могут быть частью правовыводимой цепочки.

4.1.13. Модифицируйте алгоритмы 4.1 и 4.2 так, чтобы они Могли Возвращаться к любой спеднально выделенной конфнгу-

Известно несколько модификаций основного алгоритма восходящего разбора, ускоряющих его работу,

(1) Можно добавить „заглядывание вперед" так, что если обнаруживается, что следующие k символов справа от входного указателя не могут следовать за Л ни в какой правовыводимой цепочке, то в этот момент не надо делать свертку, соответствующую Л-правилу.

(2) Можно попытаться упорядочить сыртки так, чтобы наиболее вероятные из них делались первыми.

(3) Можно добавить информацию, позволяющую определять, приведут ли некоторые свертки к успеху. Например, если первая свертка использует правило Л -... а,, где % - первый входной символ, и мы знаем, что нет такой цепочки (/£2*, что S=*Ay, то эту свертку можно сразу исключить. Вообще мы хотим быть уверены в том, что если $а - содержимое магазина L1, то а-префикс правовыводимой цепочки. Хотя проверить это, вообще говоря, сложно, некоторые понятия (такие, как предшествование, обсуждаемое в гл. 5), помогают исключить многие цепочки а, которые могли бы появиться в LI.

(4) Можно модифицировать алгоритм так, чтобы ускорить возвраты. Например, можно записать информацию, позволяющую сразу восстановить предыдущую конфигурацию, в которой была сделана свертка.

Некоторые из этих соображений изучаются в упр. 4.1.12- 4.1.14 и 4.1.25. Замечания по поводу обнаружения н исправления ошибок, относящиеся к нисходящему возвратному алгоритму, применимы и к восходящему алгоритму.

УПРАЖНЕНИЯ

4.1.1. Пусть G определяется правилами

S~AS\a A~bSA\b

Какую последовательность шагов сделает алгоритм 4.1, если альтернативы рассматриваются в том порядке, как они записаны, а входной цепочкой является

(а) Ьа?

(б) baba?

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

4.1.2. Пусть G состоит из правил

5-5Л Л АаА\Ь