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

дерево разбора цепочки w следующим „нисходящим" образом. Начнем с корня, помеченного 5. Тогда дает правило, которое надо применить к S. Допустим, что - номер правила S-*~Xy. . .X;;. Присоединим k потомков к вершине, помеченной 5, и пометим их Х, Х, Х. Если X,- - первый слева нетерминал в цепочке Х.-.Х, то первыми /-1 символами цепочки W должны быть Xj...X. i. Правило с номером должно тогда иметь вид X;->Yy. . .Yi, и можно продолжить построение дерева разбора цепочки w, применяя ту же процедуру к вершине, помеченной X/. Продолжая в том же духе, можно постро[ть все дерево разбора п,епочки w, соответствующее левому разбору л.

Допустим теперь, что даны КС-грамматика G = (N, 2, Р, 5), в которой правила занумерованы от I до /?, и цепочка wH*, для которой мы хотим построить левый разбор. Можно считать, что известны корень и крона дерева разбора и нам остается „всего лишь" восполнить промежуточные вершины. Стратегия левого нисходящего разбора предлагает пытаться заполнять дерево разбора, начиная с корня, и двигаться слева направо, направляясь к кроне.

Легко показать, что существует простая СУ-схема, отображающая цепочки языка L{G) в их левые (или правые, если угодно) разборы. Мы определим здесь такую СУ-схему, хотя предпочитаем исследовать МП-преобразователь, реализующий соответствующий перевод, потому что от него легко перейти к реальному выполнению этого перевода.

Определение. Пусть G(N, 2, Р, S) - КС-грамматика, в которой правила занумерованы от 1 до р. Определим СУ-схему Tf (или 7, если G подразумевается) как пятерку (N, 2, {I, ..., р}, R, S), где R состоит из таких правил Л->сх, р, что Л-*-а - правило из Р с номером i, а р = /а, где а - это цепочка а, из которой устранены все терминалы.

Пример 3.23. Пусть Gq - обычная наша грамматика с правилами, занумерованными, как в примере 3.22. Тогда T - -({£, Т, F}, { + , (, ), а], {1, 6}, Е), где R состоит

из правил

Е-Е + Т, \ЕТ Е-Т,- 2Т Т~уТ-Е, 3TF T->F, 4F

Е~(Е), ЬЕ Е-йу 6

Пара деревьев, изображенная иа рис. 3.10, задает перевод цепочки а»(а + а). □

Оставляем в качестве упражнения доказательство следующей теоремы:

Теорема 3.10. Пусть G = (N, 2, Р, 8)--КС-грамматта. Тогда Т=-{{, я)(5я=?>£г}.

Доказательство. Можно доказать индукцией, что Л)=Фг (> ) "оДЗ только тогда, когда Л л=Фс - □


Рис. 3.10. Перевод схемой Tf. а -вход; б - выход.

С помощью конструкции, подобной конструкции леммы 3.2, можно для любой грамматики G построить недетерминированный МП-преобразователь, работающий как левый анализатор Для G.

Определение. Пусть G--(N, 2, Р, S) -КС-грамматика, в которой правила занумерованы от 1 до р. Пусть Ml (или уИ, если G подразумевается) - недетерминированный МП-преобразо-ватель ({}, 2, nu2, {1, 2, р], 6, s, 0), где 6 определяется так:

(О 6(ij, А) содержит (о, а, г), если А~*а-правило нз Р с номером г,

(2) 6(f?, а, а) = {((7, е,ё)) для всех а 2.

Назовем левым анализатором для G,



Для входа W анализатор Mi моделирует левый вывод в грам-матике G цепочки w из S. По правилам (1) М каждый pa:j „развертывает" нетерминал, расположенный наверху магазина, в соответствии с некоторым правилом из Р и одновременно выдает номер этого правила. Если наверху магазина находится терминальный символ, то Mi по правилу (2) проверяет, совпадает ли он с текущим входным символом. Таким образом, Л1; может производить только левый вывод цепочки w.

Теорема 3.11. Пусть G= (N, 2, Р, S) -КС-грамматика. Тогда e(Mi) = {(w, n)\S=>w}.

Доказательство. Еще одно элементарное упражнение на индукцию. Здесь предположение индукции состоит в том, что (q, Wy Л, e)h*(9. » ) тогда и только тогда, когда

Заметим, что Mf-это почти, но не совсем МП-преобразователь, который получается по лемме 3.2 из СУ-схемы Tf.

Пример 3.24. Построим левый анализатор для грамматики G. Здесь

Mi = ({q}, 2, NU2, {1, 2.....6}, 6, q, Е, 0}

6(9, г, +Г, 1), [q, Г,2)}

d{q,e, T){{q,TF, 3), (?, Р, 4)} 8{q,e, f}{{q, [Е], 5), [q, а, 6)} S{q, b, b) = {{q, e, e)\ для всех 62

Для входной цепочки а + аа левый анализатор М? может среди других сделать такую последовательность тактов: [q, ааа, Я. е) h {Я а + а*а, Е-\-Т, 1) h [q, ааа, Т-Т, 12) Н [q, tt-f ак-а, f+ Г, 124) h((7, аала, а + Г, 1246) Н(9, Л-а-уа, +Г, 1246) h (9, аъа. Г, 1246) h (9, Gx-a, r*P, 12463) h ((?, f *f, 124634) h (7, ai?, a*f, 1246346) h (. F, 1246346) h (9. Fy 1246346) h (£7, CE, a, 12463466) l-(7, 12463466) □

Левый анализатор представляет собой, вообще говоря, недетерминированное устройство. Чтобы пользоваться им на практике, нужно уметь моделировать его детерминированно. Для некоторьх грамматик (например, для тех, что содержат циклы) полное моделирование невозможно (в данном случае потому, что некоторые цепочки имеют бесконечно много левых разборов). Кроме того, естественное моделирование, которое мы рассмотрим в гл. 4, непригодно для более широкого класса грамматик, а именно для леворекурсивных грамматик. Нисходящий анализ налагает существенное ограничение: должна быть устранена левая рекурсия.

Существует естественный класс грамматик - они называются LL-грамматикамн (вход читается слева (left) направо и выдается левый (left) разбор) и рассматриваются в разд. 5.1,- для которых левый разбор можно сделать детерминированным с помощью простого приема, состоящего в том, что анализатор заглядывает на входе на несколько символов вперед и делает очередной шаг на основе того, что он при этом видит. LL-грамматикн - это тс, которые „естественным образом" анализируются детерминированным левым анализатором.

Можно рассмотреть более широкий класс грамматик, для каждой из которых возможен ДМП-преобразователь, реализующий СУ-схему Т. Он содержит все LL-грамматики и некоторые другие, которые можно анализировать только „неестественным" способом, т. е. таким, когда содержимое магазина не отражает в отличие от анализатора Mi последовательности шагов левого вывода. С точки зрения нисходящего анализа такие грамматики представляют только теоретический интерес, но мы кратко рассмотрим их в разд. 3.4.4.

3.4.3. Восходящий разбор

Займемся теперь правым разбором. Возьмем правый вывод в грамматике Go цепочки а-\-аа из В:

Е=Ф,Е + Т =,£ + Г*а

=4 £ +

=?>g £ -f а * а =3 Т -]-а»а

=>в a-i-o*a

Уча"т?ю обратном порядке последовательность правил, епочки а+й выводе, получаем правый разбор 64264631



Вообще правый разбор цепочки в грамматике (j=(N, S, Я,5) ЭТО последовательность правил, с помощью которых можно свер. путь цепочку w к начальному символу S. В терминах деревьев выводов правый анализ цепочки w представляет собой последо. вательность отсечений основ, сводящую дерево вывода с кро. ной W к одной вершине, помеченной S. В супшости это равно-сильно процессу „заполнения" дерева вывода, начинающемуся с одной только кроны и идущему от листьев к корню. Поэтому с процессом порождения правого разбора часто ассоциируется термин „восходящий" анализ.

По аналогии с СУ-схемой Т, отображающей цепочки из L{G] в их левые разборы, можно определить СУ-схему Т, отобра-жающую цепочки в правые разборы. В ней из элементов перевода устранены терминалы, а номера правил выводов пишутся справа. Доказательство того, что эта СУ-схема корректно определяет нужный перевод, оставляем в качестве упражнения.

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

Определение. Расширенным МП-преобразователсм назовем восьмерку Р -(Q, S, Г, Д, б, (/о, Zq, f), где все символы понимаются так же, как прежде, но только б теперь обозначает отображение конечного подмножества множества Q X (X \j {е})хТ* в множество конечных подмножеств множества СхГ*хД*. Конфигурации определяются так же, как прежде, ио обычно подразумевается, что верх магазина расположен справа, и запись (q, aw, pa, х) \- (р, ру, ху) означает, что 8{q, а, а) содержит (Р, Т.

Расширенный МП-преобразователь Р называется детерминированным, если

(1) #б((7, а, для всех qQ, a£i:\j{e} и аГ*,

(2) цепочки а и р не являются суффиксами одна другой, если 6{q, а, а)ф 0 и б [q, b, )Ф0 для Ь=а или Ь = е,

Определение. Пусть G = (N, 2, Р, S) -КС-грамматика. Обозначим через М? расширенный недетерминированный МП-преобразователь {{q}, 2, Nu2u{S}, {1, р}, 6, q, $, 0), причем верх магазина расположен справа и б определяется так:

(1) {q,e, а) содержит (q, Л, /), если Л-а -правило из Р с номером i,

(2) 6 [q, а, е) - {{q, а, е)\ для всех а € 2,

(3) biq,e,$S) = {{q,e,e)}.

от МП-преобразователь содержит элементы алгоритли раз-называемого алгоритмом типа перенос -свертка. На такте, птветствующем правилу (2), М, переносит входной символ ягазип. Всякий раз, когда наверху магазина появляется нова мг может свернуть ее по правилу (1) и выдать номер явила, использованного при свертке. Затем может про-"лжать переносить в магазин входные симйолы, пока в его пхней части не появится новая основа. Эта основа свертывается, а на выход выдается номер соответствующего правила. М действует так до тех пор, пока в магазине пе останется только начальный символ с маркером дна магазина. По правилу (3) Mr может перейти тогда в конфигурацию с пустым магазином.

Теорема 3.12. Пусть G = (N, 2, Р, S)~ КС-грамматика, Тогда

Доказательство. Доказательство аналогично доказательству леммы 2.25; оставляем его в качестве упражнения. □

Пример 3.25. Правым анализатором для грамматики Gp будет

M?- = ({9K 2. NU2U{S}, {1. 2, 6}, б, q, $, 0)

b{q, e,E + T)={{q,E, 1)} 6{q,e, T)={{q,E,2)\ t>(q,e,T-F) = {{q, T,S)\ b{q, e, F) = {{q, T, 4)\ 8{q,e, {E)) = {{q,F, 5)} 8{q, e, a) = {iq, F, 6)} 6{q, b, e) = \(q, b, e)) для всех 6 €2 6(9, e, $E) = {{q,e,e)}

Для входной цепочки a + aia анализатор Л1?о может среди Других сделать такую последовательность тактов:

(q,a-\~a*a, $,e)\-(q, -j-aa, $а, е) Ь- {q, $F, 6)

h(, +a-a, 64) h {q, $E, 642)

h(?, a*a, $£+, 642) [-(q, *a, $£ + a, 642) h (Q. E-{-F, 6426) \-(q, + 64264)





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.0019