Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 75
Текст из файла (страница 75)
Так как момгно исследовать только те ситуации из 1, „которые удовлетворяю1 этому условию, то на каждую включаемую ситуацию тратится лишь фиксированное время, а кроме того, фиксированное время надо потратить на список 17 как таковой для исследования а и нахождения первой ситуации в 17 ,, содержащей ам Теперь рассмотрим каждую ситуацию из 1; и затратй времени на нее в случаях, когда применяется шаг (5) или (6).
Шаг (6) можно выполнить за фиксированное время, так как надо только исследовать таблицу, связанную с 1м которая говорит о том, включены ли уже все [А а, !! для соответглвующего А, За фиксированное время таблица исследуется, и, если необходимо, в 1, включается фиксированное число ситуаций. Этим исчерпывается все время, затрачиваемое па рассматриваемую ситуацию. Если применяется шаг (5), то в некотором списке 1„для й(1' надо просмотреть все ситуации, содержащие В для некоторого конкретного В. Каждый раз, когда обнаруживается такая ситуация, в список 1, включается другая ситуация, и это время относится к включаемой ситуации, а пе к рассматриваемой! Чтобы показать, что время, затрачиваемое па любую ситуацию из любого списка, ограничено сверху фиксированным числом, достаточно заметнтть что по лемме 4.6 для однозначной грамматики предпринимается лишь одна попытка включить ситуацию в список.
Отсюда следует также, что на шаге (5) не надо тратить время на проверку того, появилась ли уже в списке соответствующая ситуация. Теорема 4.10. Если исходная грамматика однозначна, то алгоритлс 4.5 лгожно выполнить для входной цепочки длины и за 0 (и-') разумно определенных элементарных операций. Дока вате л ьств о. Формализацию приведенного выше рассуждения и понятия элементарной операции оставляем в качестве упражнения.
() Теорема 4.11. В случае произвольной КС-грамматики алгоритм 4.5 можно выполнить для входной цепочки длины и за 0(п') разумно определенных элементарных операций. Доказательство. Упражнение. П Заключительная часть анализа алгоритма Эрли касается ме. тода построения разбора по законченному списку разбора. Для К2. ТАБЛИЧНЫЕ МЕТОДЫ СИНТАКСИЧЕСКОГО АНАЛИЗА этого мы опишем алгоритм 4.6, порождающий по такому списку правый разбор.
Правый разбор выбран потому, что в этом случае алгоритм несколько упрощается. Небольшое изменение алгоритма позволит находить левый разбор. Будем предполагать для простоты, что исходная грамматика не содержит циклов. Если в грамматике есть циклы, то некоторые входные цепочки могут иметь сколь угодно много разборов. Однако алгоритм 4.6 можно модифицировать так, чтобы приспособить его к грамматикам с циклами (упр. 4.2.231. Следует отметить, что, как н в случае алгоритма 4.4, можно упростить алгоритм 4.6, снабдив указателями каждую ситуацию, включаемую в список алгоритмом 4.5.
Они указывают одну или две ситуации, которые привели к включению этой ситуации в список. Алгоритм 4.6. Построение правого .разбора по списку разбора. Вход. КС-грамматика В==()ч, Х, Р, й) без циклов, правила которой занумеровашя числами от ! до р, входная цепочка ш=-а,... а„и список разбора 1„1„..., 1„для цепочки ш. Выход, Правый разбор я цепочки го или сообщение об ошибке, Метод. Если в 1„нет ситуации вида [ — а, 0], то го!(ь(6), Поэтому надо выдать сигнал „ошибка" и остановиться. В противном случае положить я =-е и выполнить процедуру 11 ([3— а, О), л).
Процедура !4 ([Л вЂ” () °, 11, /) определяется так: (1) Если Ь вЂ” номер правила Л р, то пусть значением переменной я будет цепочка, начинающаяся номером й, за которым следует предыдущее значение я. (Мы предполагаем, что и — глобальная переменная.) (2) Если (1 = — Х,Х,... Х, положить 1г=-т и 1=-1. (3) (а) Если Х Ем, вычесть 1 из )г и из 1. (б) Если Х Ей[, найти в 1, ситуацию [Մ— у °, г) для некоторого г, для которого [А — Х,Х,... Х, ° Х„... Х„, 1) входит в 1,.
Затем выполнить Й ([Х вЂ” у °, г(, 1), вычесть 1 из й и положить 1=-Г. (4) Повторять шаг (3), пока не станет й=О. После этого остановиться. С) Работа алгоритма 4.6 состоит в прослеживании правого вывода входной цепочки с помощью списка разбора, позволяющего определять правила, примененные в ходе вывода. Вызов процеду ы аргументами [А 6 ., !) и 1 добавляет к левому концу р ~~кУщего частичного разбора номер правила А — ~У. Если ()=о  — ьй1о,й,о,...
В о„где В„..., В,— все вхождения нетер- 367 ГЛ. 4. ОВЩИЕ МЕТОДЫ СИНТАКСИЧЕСКОГО АНАЛИЗА мниалов в цепочку 6, то процедура к определяет первое правило, использованное при развертке В,(1((~з), скажем В, — рм и позицию во входной цепочке (о, непосредственно предшествующую первому терминальному символу, выводимому из В,. Затем делаются рекурсивные вызовы процедуры к в следующем порядке: Т(([В, Р, ' (1 1.) В([В,,-!),, '.-11- ) Р([В, Рг., (а! Уг) где (1) 1,=) — )о,(, (2) 1, =(а, — !о ! длн '-Ц~' Пример 4.11. Применим алгоритм 4.6 к списку разбора из примера 4,10, чтобы получить правый разбор иходной цепочки (а+ а)» а. Вначале можно выполнить 11 ([Š— Т °, 0], 7).
На шаге (1) переменная я принимает значение 2 (номер правила Š— Т). Затем полагаем 2=-1 и 1=-7 и выполняем шаг (Зб), В 7, находим ситуацию [Т вЂ” Е» Т, 01, а в 7е — ситуацию [Š— ° Т, 01. Таким образом, будет выполнена процедура 1(([Т вЂ” Е»Т °, 01, 7), в результате чего к я будет добавлен слева номер 3 и станет я — 32. Согласно этому вызову процедуры )7, на шаге (2) надо положить к-=3 и 1=-7. Затем выполняется шаг (Зб) для й = 3. Находим [Т вЂ” Е, 61 в 7, и [Т Е» ° Т, 01 в 7, и вызываем Т(([Т- Е °, 6[, 7). После завершения этого вызова положим й= 2 и 1= — 6. На шаге (За) придется рассмотреть» и положить й = — 1 и 1=-5.
Далее находим [Š— (Е) °, О! в У, и [7 -- Е»Т, 01 в (а и, следовательно, вызываем Т(([Е (Е), О[, 5). Продолжая в том же духе, получаем правый разбор 64642156432. Вызовы процедуры К показаны на рис. 4.10, где они наложены на дерево вывода цепочки (а-(-и)»а. () Теорема 4.12. Алгоритм 4.6 правильно находит правый разбор цепочки и,...
и„, если тиковой существует, и его можно вьлполнигпь за грел(я 0(п."), Д о к а з а т е л ь с т в о, Прямой индукцией по порядку вызовов процедуры )( можно показать, что порождается правый разбор. Эту часть доказательства мы оставляем в качестве упражнения. зьз УПРАЖНЕНИЯ По аналогии с доказательством (еоремы 4.10 можно показать, что на вызов Й ([А Р, (1, 1) расходуется время 0 (()' — ()'), если сначала показать, что шаг (Зб) требует О()'--() элементар- ных операций.
Для этого нужно предварительно обрабатывать списки так, чтобы для рассмотрения всех ситуаций из 1,, вто- рая компонента которых равна 1, требовалось фиксированное е г(((е + т э 0),7) т в((т- рет,01,7) ! П((Е-+(Е) Ч01,5) Т й((Т»Р;61,7) ! ,Е1 МГЕ.+Г+Еь В,4) Е к((Е. а;81,71 К((Т-еГ',11,2) Т ~ Е Г(((Е»ТЧ514) В(Ьк-+а, (з,п) Г Т П((Т-~ Кч оз,4) а г мф'»аь31„4) ! а Рис. 4ЛС. Диаграмма вмполмеаиа алгоритма 4.С. время. Иными словами, в каждом списке нужно связать ситуа- ции с общей второй компонентой и ввести заголовок, указыва- ющий первый элемент списка.
Зту обработку можно очевидным образом проделать за время 0(п'). Затем па шаге (Зб) исследуются ситуации списка 7, со вто- рой компонентой г = 1, 1 — 1,..., (, пока не обнаружится нужная иая ситуация вида [Хв- у „г1. Проверка того, что получена н ж- ая ситуация, занимает фиксированное время, так как все у ситуации со второй компонентой ( можно найти в списке 7, за Фи«снрованное время. Общее количество времени, потраченного иа шаге (Зб), пропорционально, таким образом, 1 — 1. (1 ЗПРАжняння 4 2 1 Пусть 6 определяется правилами — АЯ!Ь, А — ВА!и. помощью алгоритма 4.3 постройте таблицы разбора следующих цепочек: (а) ЬЬиаЬ, (б) иЬиЬаЬ, (в) ииЬЬа. 369 Гл.
4. Оеща!е метОды гинтАксичегкОГО АнАлизл РПРАЖНЕ ННЯ 371 370 4.2.2. С помо ... С помощью алгоритма 4.4 получите левые разборы для тех цепочек из упр. 4.2.1, которые принадлежат языку 1.16), 4.2.3. С помо и мощью алгоритма 4.5 постройте по грамматике 6 пения. из упр. 4.2.! списки разбора для цепочек из этого же упраж- 4.2 4. С помощью алгоритма 4.6 постройте правые разборы для тех цепочек из упр.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
