Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 68
Текст из файла (страница 68)
Доказательство. Если х~е, то по следствию ! !Н)<с'(х). Так как !х!<!Н4), то !л)<с')4о!. В качестве упражнения можно показать, что если х=е, то !л)<с'. Поэтому в любом случае )л)<су(!4о)+1). Г2 Теорема 4.2. Суи(ествует тпкая константа с, что алгоритм 4.1 для входной цепочки и4 длины и) 1 использует не более сл ячеек, если для каждого символа из обеих магазинных цепочек, входяилих в конфигурации, требуется только одна ячейка. Д о к а з а т е л ь с т в о, Нс считая символа Ч, содержимое магазина Б2 является частью левовыводимой цепочки а, для ко. торой Я к==а а, где я — частичный левый разбор, совместимый с и1.
В силу следствия 2 леммы 4.4 (л(<й((4о)+!). Так как длины правых частей правил ограничены, скажем величиной 1, то ) и! <Ы()4в)+!) <2Ы) ш(. Следовательно, длина магазина Б2 превосходит 2Ы )4о)+1. Магазин ! 1 содержит часть левовыводимой цепочки и (весь терминальный префикс или его часть) и (л) индексов. В силу следствия 2 леммы 4.4 длина магазина ТА не превосходит 2у(1+1)(!в~+!). Таким образом, сумма длин обоих магазинов пропорциональна )4о). и Теорема 4.3.
Суи(ествует шакал константа с, что алгоритм 4.1 лри обработке входной цепочки и4 длины л"'-! делает не более с" элементарных операций, лри условии что вычисление одного шага алгоритма 4.! требует фиксированного числа элементарных операций. Доказательство. В силу следствия 2 длина каждого частичного левого разбора, совместимого с ш, не превосходит сгл для некоторого с,.
Таким образом, число различных частичных левых разборов, совместимых с и4, не больше с,", где с,— некоторая константа. Алгоритм 4.1 в промежутках между конФигурациями, в которых содержимое магазина П описывает 335 ГЛ. 4. ОБЩИЕ МЕТОДЫ СИНТАКСИЧЕСКОГО АНАЛИЗА 4.!. СИНТАКСИЧЕСКИИ АНАЛИЗ С ВОЗВРАТАМИ последовательные частичные левые разборы, вычисляет самое большее и конфигураций. Общее число конфигураций, вычисзяемых алгоритмом 4.1, не превосходит, таким образом, пс,". Из формулы бинома непосредственно следует, что пс," .(с,+1)'. Остается выбрать с=(с,+1)и, где и — максимальное число злсментарных операций, требуемых для вычисления одного шага алгоритма 4.1. С) Теорему 4.3 в некотором смысле нельзя усилить, т.
е. су>цествуют пе леворекурсивные грамматики, при работе с которыми алгоритм 4.1 затрачивает экспоненциальиое время, по- :кольку эти грамматики имеют с" частичных левых разборов, совместимых с некоторыми цепочками длины и. Пример 4.3. Пусть 6=((5), (а, Ц, Р, 5), где Р состоит из правил 5- а55)е. Пусть Х(п) — число различных левых разборов цепочки а", а У(п) — число частичных левых разборов, овместимых с а". Функции Х(п) н 1'(п) определяются рскуррентными соотношениями (4.1,2) Х (О) = 1 л-! Х (и) = ~ч ', Х (!' )Х (и — 1 — !) 4=.0 (4,1,3) 1'(О) =2 Р (и) = 1 (п — 1) + ~ч", Х (!) «'(и — 1 — !) >=О Равенство (4.1.2) вытекает нз того, что каждый вывод цепочки а" при и)! начинается правилом 5- а55.
Остальные п — 1 символов а можно так или иначе распределить 'между двумя нетерминаламн 5. В равенстве (4,1.3) У(п — 1) отражает возможность того, что после первого шага 5=~а55 второй негерминал 5 больше не участвует в выводе, а суммирование отражает возможность того, что из первого 5 выводится а' для некоторого !. Формула 1'(О) =-2 вытекает из того, что пустой вывод н вывод 5=!>е совместимы с цепочкой е.
Из упр. 2.4.29 получаем Х(п)= — ( ") гак что Х(п)=>:2" '. Позтому л-! 1'(и) =. 1'(и — 1)+ ~~.", 2!"'1'(и — ! — !) >=О откуда, разумеется, следует„что 1'(и) =г: 2". зз6 Этот пример выявляет главную проблему, возникающую при нисходяц«ем анализе с возвратами. Число шагов, необходимых для разбора с помощью алгоритма 4.1, может быть огромным, Нзвестно несколько приемов, помогающих слегка ускорить этот алгоритм.
Мы укажем некоторые из них. (!) Можно упорядочить правила так, чтобы наиболее вероятные альтернативы испытывались первыми. Однако это не поможет в тех случаях, когда входная цепочка синтаксически неправильна, так что придется перебрать все возможности. Определение. Для КС-грамматики 6=((л(, т, Р, 5) определим функции Г1115Т»(а) = (х (а=Э! х() и ! х ) =й или сл=~* х и ) х ( < й) Ниаче говоря, множество Г1к5Т»(а) состоит из всех терминальных префиксов длины й (или меньше, если из 4» выводится терминальная цепочка длины, меньшей й) терминальных цепочек, выВоДИМЫХ ИЗ 4». (2) Можно заглядывать вперед на следующие й входных символов, чтобы определить, надо ли использовать данную альтернативу.
Например, с атой целью можно для каждой альтернативы а заготовить множество Р(ПЭТ»(а). Если внемне содержится ни один префикс оставшейся части входной цепочки, можно сразу отвергнуть и и опробовать следующую альтернативу. Этот прием очень полезен, когда данная входная цепочка принадлежит Е(6) и когда оиа не принадлежит 1, (6). В гл. 5 мы увидим, что для некоторых классов грамматик с помощью заглядывания вперед можно полностью устранить необходимость возвратов, (3) Можно добавить некоторую «бухгалтери«о» (учет), позволяющую ускорить возвраты. Например, если мы знаем, что последние и примененных правил не имеют прил«енил«ых следуюп«их альтернатив, то в случае неудачи можем при возврате пропустить зги альтернативы, сразу вернувшись к тому месту, где есть применимая альтернатива. (4) Можно ограничить количество допустимых возвратов.
Методы такого рода излагаются в гл. 6. Другая трудная проблема, связанная с возвратным анализом, †е слабые возможности в смысле локализации оп«ибок. сели входная цепочка синтаксически неправильна, то компиля- ТОР должен объявить, какие входные символы причастны к ошибке. Кроме того, когда найдена ошибка, компилятор должен исправить ее так, чтобы анализ мог продолжаться н Об>нару- живать другие ошибки, если они попадутся. зз7 338 339 гл. и ошцие методы синтдксического Анялизд Если входная цепочка построена синтаксически неправильно, то алгоритм с возвратами просто объявит об ошибке, оставив входной указатель на первом входном символе. Чтобы получи~ь более подробную информацию об ошибках, в грамматику можно вставить специальные правила, порождающие ошибки.
Вти правила применяются для порождения цепочек, содержащих распространенные синтаксические оп|ибки, и благодаря им синтаксически неправильные цепочки становятся правильными с точки зрения новой грамматики. Появление в выходе номера такого правила служит сигналом, локализующим о«пибку во входной цепочке. Однако с практической точки зрения алгоритмы синтаксического анализа, излагаемые в гл. 5, обладают большими способностями к обнаружению ошибок, чел«возвратные алгоритмы с правилами, порождающими ошибки. 4 т.а. Восходящий разбор Существует общий подход к разбору, в некотором смысле противоположный подходу, принятому при нисходящем разборе.
Алгоритм нисходящего разбора можно представлять себе как построение дерева разбора методом проб и ошибок, которое начинается сверху в корне и продолжается вниз к листьям, В противоположность этому алгоритм восходящсго разбора начинает с листьев (т. е. с самих входных сяхшолов) и пытается построить дерево разбора, восходя от листьев к корню. Ь)ы опишсм восходящий разбор в виде алгоритма синтаксического аналкза, который называют алгоритмом типа «перенос— свертказ.
Оп представляет собой но существу правый анализатор, который перебирает всевозможные обращенные правые выводы„совместимые с входной цепочкой. Один шаг алгоритма состоит в считывании цепочки, расположенной в верхней части магазина, чтобы выяснить, образуют ли верхние символы правую часть какого-нибудь правила. Если да, то производится свертка, заменяющая эти символы левой частью того самого правила.
Если возможна более чем одна свертка, то эти свертки упорядочиваются произвольным образом и применяется псрвая из них. Если свертка невозможна, то в магазин переносится следующий входной символ и процесс продолжается, как прежде. Всегда псред переносом делается попытка свертки. Если мы дошли до конца цепочки, а свертка все еще невозможна, то надо вернуться к последнему шагу, на котором была сделана свертка.
Если здесь возможна другая свертка, надо испытать ее. Рассмотрим грамматику с правилами  — АВ, А аЬ и  — аЬа. Пусть аЬаЬа — входная цепочка. Сначала перенесем в магазин первый символ а. Так как свертка пока невозможна, «Л. СИНТАКСИЧЕСКИЙ АНЛЛИЗ С ВОЗВРЛТАМН перенесем в магазин символ Ь. Затем цепочку аЬ, расположенную наверху магазина, заменим на А. Получили частичное дерево, показанное на рис.
4.6, а. Так как А нельзя больше свернуть, перенесем в магазин а. Свертка опять невозможна, поэтому гперенесем Ь. Тогда можно свернуть аЬ к А. Теперь получаем частичное дерево на рис. 4.6, б. Переносим в магазин символ а и обнаруживаем, что свертка невозможна. Возвращаемся к последней позиции, в которой з Ряс, 4,0. Частяяяые деревья восходящего разбора. была сделана свертка, а именно когда в магазине была цепочка АаЬ (здесь Ь вЂ” верхний символ) и мы заменили аЬ на А, с частичное дерево было таким, как на рис. 4.6, а.
Так как другая свертка здесь невозможна, сделаем перенос вместо ~~~ртки. В магазине окажется Лаба. Тогда можно свернуть аЬа к В, получив при этом рис. 4.6, г. Далее заменим АВ на В и получим завершенное дерево, показанное иа рис. 4.6, г. агат метод можно рассматривать как процедуру прослеживания всевозможных последовательностей тактов недетермннированного правого анализатора для данной грамматики. Однако так же, как в случае нисходящего разбора, надо избегать ситуаций, в которых число возможных последовательностей тактов бесконечно ГЛ. 4. ОБЩИЕ МЕТОДЪ| СИНТАКСИЧЕСКОГО АНАЛИЗА 4.!.
СИНТАКСИЧЕСКИЙ АНАЛИЗ С ВОЗВРАТАМИ Одна такая ловушка оказывается тогда, когда грамматика содержит циклы, т. е. выводы вида А=о+А для некоторого нетерминала А. Число частичных деревьев может быть в этом случае бесконечным, так что грамматики с циклами мы исключим из рассмотрения, Трудности создаются также е-правилами, так как тогда можно проделать произвольное число сверток, при которых пустая цепочка «свертывается» к кетерминалу. Восходящий разбор можно расширить так, чтобы он охватывал грамматики с е-правилами, но пока для простоты мы предпо. читаем обходиться без е-правил, Алгоритм 4.2.
Восходящий разбор с возвратами, Вход. КО-грамматика П>=(«~, Х, Р, 5) без циклов и е-правил (все ее правила занумерованы от 1 до р) и входная цепочка п>=а>а«...а„(н) 1). Выход. Один обращенный правый разбор, если он существуег, и слово «ошиб>ка» в противном случае. Метод. (1) Произвольным образом упорядочить правила.
(2) Алгоритм будет изложен в терминах 4-компонентных конфигураций, подобных тем, что использовались в алгоритме 4.!. В конфигурации (з, |, а, ()) (а) е представляет состояние алгоритма, (б) | представляет текущую позицию входного указателя (предполагается, что (о+1)-м входным символом служит правый концевой маркер $), (в) а — содержимое магазина В! (верх которого расположен справа) (г) (« — содержимое магазина А2 (верх которого расположен слева).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
