Главная Промышленная автоматика.


Рис. 4.2. Частичные деревья разбора.

либо начинается нетерминальным символом, то х-префикс входной цепочки.

В нашем примере мы начнем с дерева, состоящего из одной вершины, помеченной 5. Затем применим первое 5-правило, расширяя дерево так, чтобы оно было совместимо с данной входной цепочкой. Здесь применим правило S - >aSbS, чтобы расширить начальное дерево до дерева, изображенного па рис. 4.2, а. Так как активной вершиной дерева в этот момент станет а и первый входной символ тоже а, мы передвинем входной указатель на второй входной символ и сделаем нетерминал S, стоящий непосредственно справа от а, новым активным символом. Затем развернем этот символ S с помощью первой альтернативы и получим дерево на рис. 4.2, б. Так как новый активный символ а совпадает со вторым входным символом, передвинем входной указатель на третий входной символ.

Теперь развернем самый левый нетерминал S на рис. 4.2, t;, но на этот раз нельзя применить ни первую, ни вторую альтер-

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

Далее можно с помощью третьей альтернативы для S развернуть самый левый символ S на рис. 4.2, в и получить рис. 4.2, г. (Первые две альтернативы снова несовместимы с входом.) Пятый входной символ-с, и потому входной указатель можно передвинуть на один символ вправо. (Мы предполагаем, что конец входной цепочки обозначается маркером.) Однако дерево на рис. 4.2, г порождает дополнительные символы, а именно bS, которых нет во входной цепочке, так что теперь мы знаем, что при поиске правильного разбора входной цепочки пошли по неверному пути.

Если вспомнить МП-анализатор из разд. 4.1.1, то окажется, что мы прошли через последовательность конфигураций Со, С, Cg, Cg, Cq, С7, и из С, переход невозможен.

Итак, нам придется искать какую-то другую левовыводимую цепочку. Сначала посмотрим, нет ли другой альтернативы для правила, использованного при построении дерева на рис. 4.2,г из предыдущего дерева. Оказывается, такой альтернативы нет, так как для получения рис. 4.2, г из рнс. 4.2,0 использовалось последнее 5-правило S-с.

Тогда мы возвращаемся к дереву рис. 4.2,6 и переставляем указатель на позицию 3. Проверяем, есть ли еще альтернативы правила, использованного при построении дерева на рис. 4.2,0 из предыдущего дерева. Видим, что их нет, так как мы применяли правило S--6. Поэтому мы возвращаемся к рис. 4.2,6, переставляя входной указатель на позицию 2. При переходе к рис. 4.2,6 от рис. 4.2, а применялась первая альтернатива, так что теперь испытаем вторую альтернативу и получим дерево на рис. 4.3,а.

Входной указатель можно передвинуть вперед на позицию 3, поскольку порожденный си.мвол а совпадает с входным символом а D позиции 2. Далее, чтобы развернуть самый левый символ S на рис. 4.3, а и получить рис. 4.3,6, можно применить только третью альтернативу. Входные символы в позициях 3 и 4 совпадают теперь с порожденными, так что можно передвинуть входной указатель на позицию 5. К нетерминалу S на рис. 4.3,6 можно применить только третью альтернативу и получить рис. 4.3,6. Последний входной символ совпадает с самым правым символом на рис. 4.3, в. Таким образом, мы знаем теперь, что на рис. 4.3, е изображен правильный разбор входной цепоч-

справа от а, и сдвинуть входной указатель на один символ вправо. Если а не совпадает с текущим входным символом, вернуться к вершине, к которой применялось предыдущее правило, вернуть, куда надо, входной указатель, если это необходимо, и испытать следующую альтернативу. Если альтернатив больше нет, вернуться к следующей предыдущей вершине, и т. д.

Всякий раз мы пытаемся сохранить совместимость построенного дерева с входной цепочкой, т. е. если ха~крона дерева, построенного к данному моменту, где цепочка а либо пуста,



Рис. 4-3. Дальнейшие попытки разбора.

Испытаны. В этот момент можно остановиться и, если нужный разбор не обнаружен, выдать сообщение о том, что входная цепочка сннтакснчески неправильна.

В описанной процедуре есть коварная ловушка. Если грамматика леворекурсивна, то процесс может никогда не остановиться. Например, допустим, что Лес - первая альтернатива для Л. Тогда это правило будет применяться всякий раз, когда надо развернуть Л.

Можно возразить, сказав, что этой проблемы можно было бы избежать, испытывая альтернативу Аа последней. Однако левая рекурсия может оказаться гораздо более тонкой и включать несколько правил. Например, первым Л-правилом могло бы быть A-hSC. Тогда если S ~ АВ - первое 5-правило, то мы получим Л=>5Сг>Л5С, и эта картина будет повторяться. Даже если будет найдено подходящее упорядочение правил, на синтаксически неправильных входных цепочках леворекурсивные циклы будут встречаться снова и снова, так как все предыдущие выборы будут безуспешными.

Вторая попытка свести иа нет эффект левой рекурсии могла бы состоять в том, чтобы ограничить число вершин проме-

жуточного дерева в зависимости от длины входной цепочки. Если нам дана КС-грамматика G = (N, S, Р, 5), у которой N - ft, и входная цепочка w длины /г, то можно показать, что для W € (С) существует хотя бы одно дерево вывода, в котором длины всех путей не больше kn. Таким образом, можно было бы ограничить поиск деревьями, глубина (длина наибольшего пути) которых не превосходит kn.

Однако для некоторых грамматик число деревьев глубины может слишком быстро расти с ростом d. Рассмотрим, например, грамматику G с правилами 5-+55е. Для нее число деревьев выводов глубины d задается рекуррентными соотношениями

D{d) = {D{dl)Y+{

Значения функции D{d) для ti от 1 до 6 приведены на рис. 4.4.

D (d) растет очень быстро, быстрее, чем 2". (См. также упр. 4.1.4.) В результате любую грамматику, в которой встречаются два правила такого вида, нельзя разумно проанализи-

D{d)

458 330

Рис. 4.4. Значения D (d).

ровать с помощью описанного варианта алгоритма нисходящего разбора.

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

•1*3. Алгоритм нисходящего разбора

Теперь мы готовы описать наш алгоритм нисходящего разбора с возвратами. В алгоритме используются два магазина {LI и 2) и счетчик, в котором хранится текущая позиция входного указателя. Чтобы точно описать алгоритм, воспользуемся несколько стилизованными обозначениями, похожими на те, что

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

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



cc(Su/)*» где / - множество индексов альтернатив, p6(Nu2)*. Шесть типов шагов определяются так:

(а) Разрастание дерева

(9, i, а, ЛР)[-(9, i, ai. TiP)

где Л-*-Vi - правило из Р и у -первая альтернатива нетерминала Л. Этот шаг соответствует разрастанию частичного дерева вывода, при котором применяется первая альтернатива самого левого нетерминала дерева.

(б) Успешное сравнение входного символа с порожденным символом

{q, /, а, afj)[-{q, аа, Р)

при условии, что аа {in). Если i-й входной символ совпадает с очередным порожденным терминальным символом, то он передается из L2 в Ll, а позиция входного указателя увеличивается на единицу.

(в) Успешное завершение

(q, п+ 1, а, $)Ь ( п-\-\, а, е)

Достигнут конец входной цепочки и найдена левовыводимая цепочка, совпадающая с входной. Левый разбор входной цепочки восстанавливается по цепочке а с помощью такого гомоморфизма h, что h(a) = e для всех а £2, /г(Л/) -р, где р-номер правила Л-у и у - г-я альтернатива нетерминала Л.

(г) Неудачное сравнение входного символа с порожденным символом

(<7, 1, а, йР) Ь (Ь, 1, а, аР) (афа)

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

(д) Возврат по входу

{Ь, /, аа, Р)[-{Ь, i - l, а, йР)

для всех аЪ. В состоянии возврата входные символы переносятся назад из Ll в L2.

(е) Испытание очередной альтернативы

(&, г, аЛу, 7у, Р)Ь

(i) (q, i. 7/+1 Р), если + i -(/-h 1)-я альтернатива нетерминала Л. (Заметьте, что уу в L2 заменяется на Vy+j.)

(ii) Следующая конфигурация невозможна, если г= 1, Л 5 и S имеет только / альтернатив. (Это условие указывает на го, что всевозможные левовыводимые це-

употреблялись при описании конфигураций МП-преобразователя.

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

Вход. Не леворекурсивная КС-грамматика G = (N, S, Р, S) и входная цепочка w = aya (/0). Предполагается, что правила из Р занумерованы числами 1, 2, ...,/?.

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

Метод.

(1) Для каждого нетерминала АЦ упорядочить его альтернативы. Пусть Л,--индекс г-й альтернативы нетерминала Л. Например, если Л -a.J ... -все Л-правила из Р и альтернативы упорядочены так, как записаны, то Л - индекс альтернативы а, А-индекс альтернативы и т. д.

(2) Четверкой (s, i, а, р) будем обозначать конфигурацию алгоритма:

(а) S обозначает состояние алгоритма;

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

(в) а представляет содержимое первого магазина (Ы)\

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

Будем считать, что верх первого магазина расположен справа, а верх второго магазина - слева. Магазин L2 служит для представления „текущей" левовыводимой цепочки, т. е, той, которая получилась к данному моменту в результате развертки нетерминалов. В соответствии с неформальным описанием нисходящего разбора в разд. 4.1.1 верхний символ магазина Ш будет символом, помечающим активную вершину порожденного к данному моменту дерева вывода. В магазине представлены текущая история проделанных выборов альтернатив и выходные символы, по которым прошла входная головка. Алгоритм находится в одном из трех состояний q, Ь или /, где q-состояние нормальной деятельности, b-состояние возврата, /-заключительное состояние.

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

(4) Существует шесть типов шагов. Эти шаги будут описаны в терминах их воздействия на конфигурацию алгоритма. Ядро алгоритма - вычисление последовательных конфигураций, определяемое через „отношение перехода" [-. Запись (s, i, а, Р) (s\ i\ а, р) означает, что если (s, i, а, р)-текущая конфигурация, то нужно перейти в следующую конфигурацию (s, f, а, р)-Если не оговорено противное, то i - число от 1 до я -f Ь





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 [53] 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101

0.002