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

Пример 4.9. Пусть G - грамматика с правилами

S"

Пусть таЬааЬ - входиая цепочка. Таблица разбора цепочки приведена в примере 4.8.

Так как St, то w£L{G). Чтобы найти левый разбор цепочки аЬааЬ, вызовем процедуру gen(l, 5, S). При этом обнаружится, что А принадлежит tu и t и существует правило S-AA. Тогда будет выдано число I (номер правила S-AA) и затем вызваны gen(l, 1, А) и gen(2, 4, А). Вызов gen(l, 1, А) даст правило номер 6. Так как Sfy, At и Л--четвертое правило, то gen (2, 4, Л) выдаст 4 и вызовет gen (2, 1, 5), а затем gen (3, 3, Л).

Продолжая в том же духе, получим левый разбор 164356263.

Заметим, что G - неоднозначная грамматика; в самом деле, цепочка abaab имеет более одного левого разбора. В общем случае нельзя по таблице разбора получить все разборы входной цепочки за менее чем экспоненциальное время, так как у нее может быть экспоненциальное число разборов. □

Заметим, что алгоритм 4.4 можно сделать более быстрым, если при построении таблицы разбора помещать указатели в те элементы, которые приводят к появлению новых элементов (см. упр. 4.2.21).

4.2.2. Алгоритм Эрли

В этом разделе мы изложим метод синтаксического анализа, позволяющий для произвольной КС-грамматики разобрать входную цепочку за время O(rt), использовав при этом емкость памяти 0(/г), где длина входной цепочки. Кроме того, если грамматика однозначная, то время квадратичное, и для большинства грамматик языков программирования алгоритм можно модифицировать так, чтобы время и емкость стали линейными функциями от длины входной цепочки (упр. 4.2.18). Сначала мы неформально опишем основной алгоритм, а потом покажем, что вычисление можно организовать так, что получатся указанные выше границы сложности.

Основная идея алгоритма состоит в следующем. Пусть G - (N, 2, Р, 5) -КС-грамматика и waa ... -входная цепочка из 2*. Объект вида [АХХ ... X-X+j ... Х,, I] иа-

зовем cwm at{weri, относящейся К цепочке ш, если А~Ху . ..Х~ правило из РиО</<я. Точка между и Х является метасимволом, не принадлежащим пи N, ни 2. Число k может быть любым целым числом от нуля (в этом случае точка -первый символ) до т (в этом случае она- последний символ)).

Для каждого 0</<rt мы построим такой список ситуаций /у, что [А-аф, i] принадлежит !j для 0<г< / тогда н только тогда, когда для некоторых у и б существуют выводы 5=:>*уЛ6, у ==>*й ... «j и a=yaiy ... а. Таким образом, между второй компонентой ситуации и номером списка, в котором она появляется, заключена часть входной цепочки, выводимая из а. Другие условия, налагаемые на ситуацию, просто гарантируют возможность применения правила Л--*ар в выводе некоторой входной цепочки, совпадающей с w ло позиции /.

Последовательность списков /„, Iу, /„ будем называть

стеком разбора для входной цепочки w. Заметим, что w принадлежит L{G) тогда и только тогда, когда в /, есть ситуация вида [Sa., 0].

Опишем алгоритм, который по произвольной данной грамматике порождает список разбора любой входной цепочки.

Алгоритм 4.5. Алгоритм Эрли.

Вход. КС-грамматика G(N, X, Р, S) и входная цепочка w = aya2 ... а, из 2*.

Выход. Список разбора /д, /j, 1„ для цепочки w. Метод. Сначала строим 1:

(1) Если S-a-правило из Р, включить в [S0] в Z. Далее выполнять шаги (2) и (3) до тех пор, пока в /<, можно

включать новые ситуации.

(2) Если [В-i-V, Oj принадлежит Z), включить в ситуацию [Л~>аВр, 0] для всех [Л ->а*Лр, 0], уже принадлежащих /д.

(3) Допустим, что [Л-j-a-Bj, 0] принадлежит /„. Для каждого правила, из Р вида Ву включить в ситуацию [В-*-у, 0] (если она еще не там).

После того как построены 1, -к строится /у:

(4) Для каждой ситуации [5-а-ар, iJ из /у , для которой включить в /у ситуацию [В-аа-р, 1].

Далее выполнить ишги (5) и (6), пока в }у можно включать новые ситуации.

(5) Пусть [Л-а-, i] принадлежит . Искать в ситуации вида [Б-а-Лр, к]. Для каждой из них включить в / ситуацию [5->аЛ.р, к].

) Если правило имеет вид Д -то ситуация будет такой:

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



(6) Пусть [Л-а,Вр, i] принадлежит Ij. Для каждого В-у из Р включить в Ij ситуацию [В--у, /].

Заметим, что рассмотрение ситуации, в которой справа от точки стоит терминал, на шагах (2), (3), (5) и (6) не дает новых ситуаций.

Итак, алгоритм состоит в построении /у для 0</<п. □ Пример 4.10. Рассмотрим грамматику G с правилами

(1) Е-Т + Е

(2) Е-Т

(3) Т-ЕТ

(4) TF

(5) F{E)

(6) F~a

и входную цепочку + На шаге (1) включаем вситуа-

ции [Е-Т + Е, 0] и [Е-*Т, 0]. Рассмотрение этих ситуаций приводит к включению в посредством шага (3) ситуаций [7-уЕиТ, 0] и [7-F, 0]. Продолжая этот процесс, добавляем [Е-{Е), 0] и [Р-.-.а, 0]. Другие ситуации уже нельзя включить в Iq.

Теперь построим 1. По правилу (4) включаем [Р-*-(•£),0], так как Тогда правило (6) позволяет включить [Е-•Т-\-Е,\], [£-..Г, 1], [Г -.РГ, 1], [Г -.Р, 1], [F-(E), \] и [F-а, 1]. Теперь в уже нельзя включить новые ситуации.

Чтобы построить /д, заметим, что а2 = а и по правилу (4) ситуацию [F-j-a*, 1] нужно включить в I.. Затем по правилу (5) рассмотрим эту ситуацию, перейдем к списку и поищем в нем ситуации, в которых F стоит непосредственно справа от точки. Две такие ситуации найдутся, и мы включим [Т-Е-Т, 1] и [Г-*-Р, 1] в /д. Рассмотрение первой из них не дает ничего, а вторая заставляет обратиться к в поисках ситуаций, содержащих -Г. Еще две ситуации [Е-~Т*+Е, 1] и [Е-Т*, 1] включаются в /g. Снова первая не дает ничего, а вторая приводит к включению [Е-+(Е), 0] в 1. Теперь никакие ситуации нельзя включить в /д, так что список завершен.

Содержимое всех списков приведено на рис. 4.9.

Так как ситуация [Е-*-Т*, 0] включена в последний список, входная цепочка (а + а)>:-а принадлежит L (G). П

При анализе алгоритма Эрли мы будем действовать по следующему плану. Сначала докажем корректность упомянутой ранее неформальной интерпретации ситуаций. Затем покажем, что если грамматика G однозначная, то при разумном понятии элементарной операции время выполнения алгоритма квадратично зависит от длины входной цепочки. Наконец, покажем, как по списку разбора построить разбор и фактически как это сделать за квадратичное время.

[F-[Т-[Т-

• Т + Е, 0]

• Т, 0]

• F-rT, 0]

• F, 0]

0]

• а, 0]

Т+Е, И •Т + Е, 3] -Т, 3]

[F-\F [F-]Т-[T-f, 3] [F~.(E), 31 [F--a, 3]

[TF-4:.T, 0] [T~.FT, 6] [T~F, 6]

•(). 6] •a, 6]

[F-[E-[E [T-[T-[F-[F"

-iE), 0] •T + E, \] -T, 1] . -F-T, 1] > -F, I] •(E), 1] •a, 1]

[F-a, 3]

[T~F.:iT, 3]

[T-F-, 3] [E-T-+E, 3] [E-T-, 3] {E-T-\-E., 1] [P->(£•), 0]

\T-\T. [T-\E [E-

a., 6] >P.*r, 6] F-, 6] F-T-, 0] T--\ E, 0] 0]

[F~a., [] [T-F.T, 1] [T-F., I] [ET.-\-E, 1] [E~T, 1] [Р-(Я.). 0]

[P-(£)-,0l [T~F-T, 0] [TF-, 0] [E-T.+E, 0] [E~T>, Oj

Рис. 4.9. Списки разбора для примера 4.Ш.



Пусть Ti (5)-длина кратчайшего вывода 5=>*уЛ6, Т2(5) - длина кратчайшего вывода y=>*«i ... а,-, Тз(5)-длина кратчайшего вывода а=Ф*а, + 1 ... ау. Тогда ранг набора .7 равен т,() + 2[/Ч-тЛ.7) + Тз(5)].

Теперь докажем (4.2.1). Если ранг набора J = [а, р, у, б. Л, /] равен 0. то (3) (J) = (3) = j = 0. Отсюда а-у = Ь = е ii Л = 5. Тогда нужно показать, что [5->Р, 0 входит в /(,. Однако это сразу следует из правила (1), так как правило 5- должно принадлежать Р.

Для доказательства шага индукции предположим, что набор параметров 5 для утверждения (4.2.1) имеет ранг / > О и (4.2.1) верно для наборов с меньшими рангами. Рассмотрим отдельно три случая, связанные с тем, что а может оканчиваться терминалом, нетерминалом и быть пустой цепочкой.

Случай и а -- аа для некоторого д 6 2. Так как а а,-+у. . .а, то attj. Рассмотрим набор 3 [а, ауР, у, б. А, i, j- IJ. Так как Л--аоуР принадлежит Р, то 5" служит набором параметров для (4.2.1) и его ранг, как легко видеть, равен /" - 2. Отсюда следует, что [Л->-aflyp, i] входит в По правилу (4) ситуация

[Л-сср, i] будет помещена в /у.

Случай 2: ааВ для некоторого SN. Существует такое число </, что а=>*a/+j ... и Б Q/+i ... ау. Исследуя набор йр, у, б. Л, (, Щ меньшего ранга, заключаем, что

[Л-сс-бр, ("] входит в I. Пусть 6i=>i - первый шаг в кратчайшем выводе В=*а\1 ... Uj. Возьмем набор О" \ц, е,уа, Рб, Б, /]. Так как 5=>*уЛб=>уайрб, то \(3")Ху{3)-\-\. Пусть Пу - минимальное число шагов вывода аа. .. . а и - минимальное число шагов вывода Б =ф* . . . Ду. Тогда х{3) Пуп. Так как Б => г] =>* я, . . . Яу, то Тд (.7") 1. Легко видеть, что Та (5") = т (J) + "i- Следовательно, т (5")+ Тз (5") = т, (5) Н- /г, Ч 1 = Тз (J) Н- Тз (З*)- 1. Таким образом, Ti(5")--2[/-j-T2(5") + Tg(5")] меньше г. По предположению индукции для Т заключаем, что [В-*-»!•, входит в /у, и так как [Л »-а.Бр, [] входит в 1, то но правилу (2) или (5) [Л->а.р, г] включается в /у.

Случай 3: а -е. В этом случае можно считать, что /" = / и з()0. Так как г > О, то длина вывода 5=:>*уЛб больше нуля. Если бы она равнялась нулю, то было бы Tj(-->)0, а тогда у -е, так что x(3)i = 0. Поскольку в этом случае, как уже отмечалось, i = j и Tj(.7)-0, то было бы г = 0.

Итак, можно найти SN и такие цепочки у, у", 6 и 6" из (Nu2)*, что S=yyB6z=yy"A6"8\ где Б-у"Лб" принадлежит Р, у~уу" б = и уВб - результат предпоследнего шага кратчайптего вывода 5=;>*уЛб. Возьмем набор 3 = [у", Л6", V , б, В, k, /], где k - такое число, что y=>*Oi ... % и у"=* А+1...Ду. Пусть наименьшие длины указанных выводов равны

Теорема 4.9. В списке разбора, построенном алгоритмом 4.5, [А а-р, i] принадлежит Ij тогда и только тогда, когда сс*а,-+у • • Uj и существуют такие цепочки у и б, что 5=Ф*уЛб

и Qy . . . Uf.

Доказательство. Необходимость. Эту часть теоремы докажем индукцией по числу ситуаций, которые включаются в /«, /i, ..., /у до того, как в /у включается [Л-♦а-р, t]. Для доказательства базиса (здесь это будет /д) заметим, что а=Ф*е для каждой ситуации, включенной в так что 5=>*уЛб при уе.

Для доказательства шага индукции допустим, что список /(, уже построен и предположение индукции верно для всех ситуаций, включенных в списки при ij. Пусть [Л-?-а«р, (J включается в Ij по правилу (4). Тогда a = aaj и [Л-*-а-аур, (] входит в /y j. По предположению индукции сс=Ф*а,-+1 ... ау и существуют такие цепочки у* и б, что5=$*уЛб и у * а. . .а. Отсюда следует, что а = auj*а.. ... Uj, и нужное утверждение выполняется при у = у и б = б.

Пусть теперь [Л--а-р, i\ включается по правилу (5). Тогда а -аВ для некоторого й N и [Л-а-йр, г] входит в для некоторого k. Кроме того, [В-т]-, k\ входит в /у для некоторой цепочки т] 6 (N и 2)*. По предположению индукции х\ а ... а и а*а,- т ... а. Поэтому а осБ =*а/+ ... а. В силу того же предположения существуют такие у и 6, что 5=>*уМб и у->*flj ... а,-. Остальная часть нужного нам утверждения выполняется опять при уу п Ь~Ь.

В последнем случае, когда [Л->а-р, (] включается по правилу (6), а --е и ( - /. Элементарную проверку нужного утверждения предоставляем читателю, так что первую часть теоремы считаем доказанной.

Достаточность. Эта часть состоит в доказательстве утверждения

(4.2.1) если 5=:>*уЛб, y*ai ... а,-, Л->ар принадлежит Р и a*ai+y ... aj, то [Л --а-р,- [] включается в список /у

Утверждение (4.2.1) надо доказать для всевозможных значений входящих в него параметров. Каждый набор параметров состоит из цепочек а, р, у и б, нетерминала Л и чисел ( и /, так как S и а . . . а фиксированы. Обозначим такой набор \а, р, у, 6, Л, /, /]. Заключение, которое нужно получить для этого набора, состоит в том, что [Л-*с.-р, /J включается в /у. Заметим, что в этом утверждении у и б не фигурируют явно.

Введем понятие ранга набора параметров и проведем доказательство индукцией по рангу. Ранг набора 5 [а, р, у, б, Л, I, /] вычисляется следующим образом:





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