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

НОЙ емкости памяти и не более чем экспоненпиального времени работы, рассматриваемых как функции от длины входной цепочки. Для доказательства нам понадобится следующая лемма, усиливающая лемму 4.1.

Лемма 4.4. Пусть G-(N, 2, Р, 3) - не леворекурсивная грамматика. Тогда найдется такая константа с, что если Л-У а и а 1, то ic\a.\.

Доказательство. По лемме 4.1 найдется такая константа Ci, что если Аето ic,. Пусть #N==fe и /-длина самой длинной из правых частей правил. По лемме 2.16 множество N можно представить в виде {Лр, Л, ..., Л., где / > I, если Л,-=>-Луа. Индукцией ио параметру pkn~j докажем, что

(4.1.1) если Aj=a н \а\---=п1, то i Нсу\а\ -jlCi

Базис. Базис, р = 0, выполняется автоматически, так как мы предполагаем, что /г 1.

Шаг индукции. Допустим, что (4.Ы) истинно для всех значений параметра kn - j<p. Рассмотрим это утверждение для параметра kn - j = p. Пусть первым шагом упоминаемого в нем вывода был AjzXy ... для rl. Тогда можно записать a = ai ... а„ где Х.га, 1<т<г и i - 1 + ц + ... + г,,;. Пусть ау = а- ... = e и а,фе. Так как афе, то такое

число S существует. Исследуем отдельно два случая.

Случай 1: Х-нетерминал, скажем Л. Тогда Л- • - -г- гак что g > j. Так как k\a g<p, то в силу (4.1.1) rj<fe/ciaj-g/Ci-Так как к, < а для s+l<m<r, то из (4.1.1) следует, что ir<klcy\a всякий раз, когда s+lmr и афе. Разумеется, не более /-1 цепочек из «1, ...,г пусты, так что суммирование чисел по тем т, для которых а = е, даст число, не превосходящее (1-\)Су. Таким образом,

1=1 + 4+...+rV < 1 + (/ - 1) Ci + klCy I а I-glCy klCy\a\ - (g-\)lCi klCy\a\ - }lCy

Случай 2: X -терминал. В качестве упражнения предлагаем показать, что в этом случае г < 1 (а - 1)< klc-y\a\~jlCy.

Из (4.1.1) вытекает, что если S=a и а 1, то Ысу\а\. Возьмем c = klCy\ лемма доказана. □

Следствие 1. Пусть G = (N, S, Р, S) -не леворекурсивная грамматика. Тогда найдется такая константа с\ что если S=\wAa и тфе, то i-c\w\.

Доказательство. Согласно следствию леммы 4.1, найдется такая константа с", что ас"Е£. По лемме 4.4 с I wAa\. Так как wAa К (2 + с") \w\, то выбор с = с (2 + с") дает нужный результат. □

Следствие 2. Пусть G = (N, S, Р, S)~~не леворекурсивная грамматика. Тогда найдется такая константа к, что если л-частичный левый разбор, совместимый с цепочкой w, и 3=Фха, где а-либо е, либо начинается нетерминалом, то я ( + 1),

Доказательство. Если хфе, то по следствию I I л j с л: . Так как х лу , то я &i> . В качестве упражнения можно показать, что если х = е, то \ л\с. Поэтому В любом случае л с( лу + 1). □

Теорема 4.2. Существует такая константа с, что алгоритм 4.1 для входной цепочки w длины п\ использует не более СП ячеек, если для каждого символа из обеих магазинных цепочек, входящих в конфигурации, требуется только одна ячейка.

Доказательство. Не считая символа $, содержимое магазина L2 является частью левовыводимой цепочки а, для которой S->а, где зх - частичный левый разбор, совместимый с ЛУ. В силу следствия 2 леммы 4.4 л ( лу -f 1). Так как длины правых частей правил ограничены, скажем величиной /, то \a\<Ckl(\w\\)2kl\w\. Следовательно, длина магазина i2 превосходит 2/г/1 лу + 1.

Магазин L1 содержит часть левовыводимой цепочки сс (весь терминальный префикс или его часть) и л индексов. В силу следствия 2 леммы 4.4 длина магазина L1 не превосходит 2/г (/+1) (te!+1). Таким образом, сумма длин обоих магазинов пропорциональна лу. П

Теорема 4.3. Существует такая константа с, что алгоритм 4.1 при обработке входной цепочки w длины пХ делает не более с"" элементарных операций, при условии что вычисление одного шага алгоритма 4.1 требует фиксированного числа элементарных операций.

Доказательство. В силу следствия 2 длина каждого частичного левого разбора, совместимого с w, не превосходит <1П для некоторого с. Таким образом, число различных частичных левых разборов, совместимых с w, не больше с, где с - некоторая константа. Алгоритм 4.1 в промежутках между конфигурациями, в которых содержимое магазина Ы описывает



последовательные частичные левые разборы, вычисляет самое большее п конфигураций. Общее число конфигураций, вычисляемых алгоритмом 4.1, не превосходит, таким образом, пс. Из формулы бинома непосредственно следует, что пс(с-\-1)". Остается выбрать с{с-\-\)т, где т -максимальное число элементарных операций, требуемых для вычисления одного шага алгоритма 4.1. □

Теорему 4.3 в некотором смысле нельзя усилить, т. е. существуют не леворекурсивные грамматики, при работе с которыми алгоритм 4.1 затрачивает экспоненциальное время, поскольку эти грамматики имеют с" частичных левых разборов, совместимых с некоторыми цепочками длины п.

Пример 4.3. Пусть G--({5, {а, Ь}, Р, 5), где Р состоит из правил 5->£2sse. Пусть X (/г) -число различных левых разборов цепочки а", а У (п) - число частичных левых разборов, совместимых с а". Функции Х{п) н У (п) определяются рекуррентными соотношениями

(4.1.2)

(4.1.3)

(0)-1

Х(/г)- S X{i)X (n-\ - i)

Г(0)-2

У(п)У(п~\)ЛЪХ{1)У(п~\-1)

1 = 0

Равенство (4.1.2) вытекает из того, что каждый вывод цепочки й:" при /г1 начинается правилом S-aSS. Остальные п - 1 символов а можно так или иначе распределить между двумя нетерминалами S. В равенстве (4,1.3) У (п-1) отражает возможность того, что после первого шага S=aSS второй нетерминал 5 больше не участвует в выводе, а суммирование отражает возможность того, что из первого S выводится а для некоторого /. Формула К(0)=2 вытекает из того, что пустой вывод и вывод Se совместимы с цепочкой е.

Из упр. 2.4.29 получаем

V / ч 1 /2fi\

так что Х(/г)2"". Поэтому

K(ft)>K(ft-1)+ S 2-y{n~~l - i)

откуда, разумеется, следует, что К(/г)>2. □

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

(1) Можно упорядочить правила так, чтобы наиболее вероятные альтернативы испытывались первыми. Однако это не поможет в тех случаях, когда входная цепочка синтаксически неправильна, так что придется перебрать все возможности.

Определение. Для КС-грамматики G(N, S, Р, S) определим функции

РШ5Т;(а) = {л:а=Ф*л:р и л: = й или a=*x и x</j}

Иначе говоря, множество FIRST (а) состоит из всех терминальных префиксов длины k (или меньше, если из а выводится терминальная цепочка длины, меньшей k) терминальных цепочек, выводимых из а.

(2) Можно заглядывать вперед на следующие k входных символов, чтобы определить, надо ли использовать данную альтернативу. Например, с этой целью можно для каждой альтернативы а заготовить множество FIRST; (а). Если в немне содержится ни один префикс оставшейся части входной цепочки, можно сразу отвергнуть а и опробовать следующую альтернативу. Этот прием очень полезен, когда данная входная цепочка принадлежит L{G) и когда оиа не принадлежит L{G). В гл. 5 мы увидим, что для некоторых классов грамматик с помощью заглядывай ия вперед можно полностью устранить необходимость возвратов.

(3) Можно добавить некоторую «бухгалтерию» (учет), позволяющую ускорить возвраты. Например, если мы знаем, что последние т примененных правил не имеют применимых следующих альтернатив, то в случае неудачи можем при возврате пропустить эти альтернативы, сразу вернувшись к тому месту, где есть применимая альтернатива.

(4) Можно ограничить количество допустимых возвратов. Методы такого рода излагаются в гл. 6. .

Другая трудная проблема, связанная с возвратным анализом,- его слабые возможности в смысле локализации ошибок. Если входная цепочка синтаксически неправильна, то компиля-ор должен объявить, какие входные символы причастны к ошибке. Кроме того, когда найдена ошибка, компилятор должен исправить ее так, чтобы анализ мог продолжаться и обнаруживать другие ошибки, если они попадутся.



Если входная цепочка построена синтаксически неправильно, ТО алгоритм с возвратами просто объявит об ошибке, оставив входной указатель на первом входном символе. Чтобы получить более подробную информацию об опшбках, в грамматику можно вставить специальные правила, порождающие ошибки. Эти правила применяются для порождения цепочек, содержащих распространенные синтаксические ошибки, и благодаря им синтаксически неправильные цепочки становятся правильными с точки зрения новой грамматики. Появление в выходе номера такого правила служит сигналом, локализующим ошибку во входной цепочке. Однако с практической точки зрения алгоритмы синтаксического анализа, излагаемые в гл. 5, обладают большими способностями к обнаружению ошибок, чем возвратные алгоритмы с правилами, порождающими ошибки.

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

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

Мы опишем восходящий разбор в виде алгоритма синтаксического анализа, который называют алгоритмом типа «перенос-свертка». Оп представляет собой ио существу правый анализатор, который перебирает всевозможные обращенные правые выводы, совместимые с входной цепочкой. Один шаг алгоритма состоит в считывании цепочки, расположенной в верхней части магазина, чтобы выяснить, образуют ли верхние символы правую часть какого-нибудь правила. Если да, то производится свертка, заменяющая эти символы левой частью того самого правила. Если возможна более чем одна свертка, то эти свертки упорядочиваются произвольным образом и применяется первая из них.

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

Рассмотрим грамматику с правилами S -> АВ, А -аЬ и В-i-aba. Пусть ababa-входная цепочка. Сначала перенесем в магазин первый символ а. Так как свертка пока невозможна,

перенесем в магазин символ Ь. Затем цепочку аЬ, расположенную наверху магазина, заменим на А. Получили частичное дерево, показанное на рис. 4,6, а.

Так как А нельзя больше свернуть, перенесем в магазин а. Свертка опять невозможна, поэтому [перенесем Ь. Тогда можно свернуть аЬ к А. Теперь получаем частичное дерево на рис. 4.6,6.

Переносим в магазин символ а и обнаруживаем, что свертка невозможна. Возвращаемся к последней позиции, в которой


/\ /1\

Рис. 4.6. Частичные деревья восходящего разбора.

была сделана свертка, а именно когда в магазине была цепочка Aab (здесь b-верхний символ) и мы заменили аЬ на Л, т. е. частичное дерево было таким, как на рис. 4.6, а. Так как другая свертка здесь невозможна, сделаем перенос вместо свертки. В магазине окажется АаЬа. Тогда можно свернуть aba к В, получив при этом рис. 4.6, в. Далее заменим АВ на S и получим завершенное дерево, показанное на рис. 4.6, г.

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





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