Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 67
Текст из файла (страница 67)
должно быть очевидно, что последовательность совместимых частичных левых разборов единственна и включает все совместимые частичные левые разборы в естественном лексикографиче- СКОМ ПОРЯДКЕ. Лемма 4.1, Пусть 6=- (Х, Х, Р, 5) — нг леворекурсивная грамуио1пика. Тогда найдется такая константа с, что если А =Ц шВа и )со)=п, то 1 с"+''). До к азат еяьство.
Пусть 4Р1ч'=й, Рассмотримдерево 0 ле. ного вывода А =Ф'ьвВа. Допустим, что существует путь от корня к листу длины, большей, чем й(а+2). Пусть и,— вершина, намеченная нетерминалом В, явно указанным в цепочке шВа, Если уч вк нв Рнс. 4.3. Дерено вывода !З. этот путь Оканчивается листом, расположенным справа от п„то путь к и, должен быть не менее длинным. Это следует из того, что В левом выводе правило всегда применяется к самому левому нетерминалу. Поэтому прямой предок каждой вершины, расположенной справа от п„является предком вершины и,. Дерево Р показано на рис. 4.5.
Таким образом, если в Т! есть путь длины, большей, чем н(п+2), то можно найти Один такой путь, достигающий и., или Вер|пины, расположенной слева от п,. Тогда на этом пути можно найти й+! посяедовательных вершин па, ..., па+1, каждая иа которых порождает один и тот же кусок цепочкй соВ. Все пря- 1 )у у у у~: и эависнт от и.
Однако пока нам дсстатонно н этого рсэуаьтата, а потом мм с его помощью докажем более сильное утверждение. 331 Гл. 4. Овгпие метОды синтАксическОГО АнАлизА 4.1 СИНТАКСИЧЕСКИЙ АНАЛИЗ С ВОЗВРАТАМИ мые потомки вершины п, (1(1~й), расположенные слева от п,„„порождают г. Следовательно, можно найти две вершины из п„..., пь„- с одной и той же меткой, и легко видеть, что эта метка — леворекурсивный нетерминал, Отсюда заключаем, что в Р нет путей„длина которых больше й(гг+2). Пусть ! — длина самой длинной из правых частей правил грамматяки 6.
Тогда Р имеет не более !Ам+11 внутренних вершин. Поэтому если А=>гигВа, то г«!Агв+гг. Возьмем с=-!А; лемма доказана. Е) Следствие. Пусть 6 =- (Р), Х, Р, 5) — нг леворгкурсивная грамматика. Тогда найдется такая константа с', что если 5 =ФгигВа и иг ~ г, то ) а ) ~ с' ( пг ). Доказательство. Мы показали (см. Рис. 4.5), что длина пути от корня к вершине и, не превосходит й((иг(+2).
Поэтому !а)~й1()аг(+2). Возьмем с'= 3й!. Лемма 4.2. Пусть 6 =-(Р), Х, Р, 5) — КС-грамматика, нг содержащая бесполезных нпперминалов, и ш=а,ач ... а„Е Х'. Последовательность совместимых с иг левых разборов конечна тогда и только тогда, когда 6 не леворекурсивна. Доказательство. Если 6 леворекурсивна, то ясно, что для некоторой терминальной цепочки последовательность совместимых с нею левых разборов бесконечна.
Допустим, что 6 не леворекурсивна. Тогда по лемме 4.1 длина каждого совместимого с иг левого разбора не превосходит с"4'. Таким образом, число совместимых с иг левых разборов конечно. () Определение. Пусть 6 = (Х, Б, Р, 5) — КС-грамматика и у— последовательность индексов альтернатив (т. е.
нетерминалов с номерами) и терминалов. Пусть л — частичный левый разбор, совместимый с иг. Будем говорить, что у описывает л, если выполняется следующее условие: (1) Пустьл=р,... рь и 5=-а, р,-оа; Р,~аг ... в~~ах. Пусть аг=-хг()г, где Рг — либо г, либо начинается нетермипалом. Тогда У = Аг,ш,Аг,гзг... Аг игь, гДе Аг — инДекс пРавила (альтеРнативы), пРименеиного пРи пеРеходе от ау, к сгх, н игт — такой сУффикс цепочки хт, что ху=-ху гшр Лемма 4.3. Пусть 6=-(Р), г., р, 5) — не лвворгкурсивная гром. матика и л„л„..., лн ... — последовательность совместимых с иг чаопичных левых разборов. Допустим, что ни один из разборов л„..., лг не является левым разбором цгпо«ки иг.
Пуапь 5,=Ьа и 5 . ОР. Запишем а и )) в виде ха, и у!)1 соотвггп. пг лг 41 ствгнно, где каждая из цепочек а, и()г — либо г, либо начинаетсх 332 нгтерминалом. Тогда в алгоритме 4..1 (4, 1, г, 5й )-'(у, 1, уг, а13) )-'И !., т„М) где 1, = ~ х ~ + 1, 1, = ~ у ~ + 1, а у, и у, оп исывают соотвгтсгпвгнно лг и лг,.
доказательство. Доказательство проводится индукцией по г'. Базис, 4=0, тривиален. Для доказательства шага индукции рассмотрим отдельно два случая. Случай 1: л;.,— продолжение разбора л,. Пусть первый символ цепочки а,— это нетерминал А, а его альтернатнвы— б„..., б . Если цепочка хб, пе совместима с входной цепочкой, то в случае замены алгоритмом 4.1 нетерминала А цепочкой б,, правила (г), (д) и (е г) гарантируют, что следующей будет испытана альтернатива б 4;.
Так как мы предположили, что лг+4— продолжение разбора лг, то нужная альтернатива нетерминала А впоследствии будет испытана. После того как по правилу (б) произойдет сдвиг по входу, будет достигнута конфигурация (4,1„У (15)у Случай 21 лг; — модификация разбора лг. Все неиспытанные альтернативы нетермииала А сразу приводят к возврату, и по правилам (д) и (е В1) содержимое магазина С1 в конце концов будет описывать частичный левый разбор лт, упоминаемый в определении модификации. Тогда, как в случае 1, будет достигнута конфигурация (г), 1„т„()13). Е) Теорема 4.1. Алгоритм 4.1 дает левый разбор цепочки иг, если он существует, а в противном случае выдает сообщение об оигибке.
Д о к а з а т е л ь с т в о, Из леммы 4,3 видно, что алгоритм' перебирает все совместимые частичные левые разборы до тех пор, пока не обнаружится левый разбор входной цепочки или не будут исчерпаны все совместимые частичные левые разборы.
По лемме 4.2 число таких разборов конечно, так что алгоритм Рано или поздно остановится. () 4А 4, Временийя и емкостнея сложность нисходящего енепизетора Рассмотрим Вычислительную машину, у которой емкость памяти, необходимая для хранения конфигураций алгоритма 4.1, пропорциональна сумме длин обоих магазинов; это предположение вполне разумно. Разумно также предположить, что время, затрачиваемое на вычисление конфигурации С, по конфигурации С;, если Сг)- С„ не зависит от этих конфигураций.
Пока. жем, что при этих предположениях алгоритм 4.1 требует линей- ЗЗЗ ГЛ. 4. ОБЩИЕ МЕТОДЫ СИНТАКСИЧЕСКОГО АНАЛИЗА ной емкости памяти и нс более чем экспоненциального времени работы, рассматриваемых как функции от длины входной цепочки. Для доказательства нам понадобится следующая лемма, усиливающая лемму 4.1. Лемма 4.4. Пусть 6=(Х, Х, Р, Л) — не леворекурсивнпя грпл1- матика, Тогда найдется такая константа с, 1то если А =>'и и (а(~ )1, 1ло 4 <с(и). Доказательство. По лемме 4.1 найдется такая константа с,, что если А-.У'е, то 1 =.с,.
Пусть чг !ч=-14 и ! — длина самой длинной из правых частей правил. По лемме 2.16 множество 1ч можно представить в виде (А„А„..., АА,), где 1 > 4, если А1=)' Ауа. Индукцией по параметру р=-йл — ! докажем, что (4.1,1) если А =->га н )п)==л)~!, то 1<Ыс,!и! — 11с, Базис. Базис, р=-О, выполняется автоматически, так как мы предполагаем, что и Ъ 1. Шаг индукции.
Допустим, что (4.1.1) истинно для всех значений параметра йл — !' < р. Рассмотрим это утверждение для параметра йл — 1.= р. Пусть первым шагам упоминаемого в нем вывода был А;Э Х1 ... Х, для г<1. Тогда можно записать а=а, ...
а„где Х,„=>4 и, 1-- т - г и 4=-1+1,+... +1,„. Пусть а, =и, =... = а,,—.-.е и сс, =~=в. Так как 4хчье, то такое число з существует. Исследуем отдельно два случая. Случай 1: Х,— нетерминал, скажем А . Тогда А, =>" А Х4+, ... Х„, так что д >1. Так как я)а,) — д < р, то в силу (4.1.!) 1',<Ыс4';сс, ( — а(с4. Так как )и„! <(44! для в+1 <т<г, то из (4.1,1) следует, что 4 <'Ыс,)п ! всякий раз, когда з+1<т .г и и =~е. Разумеется, не более 1 — ! цепочек из п4, ..., а, пусты, так что суммирование чисел ! по тем т, для которых а =е, даст число, не превосходящее (! — 1)с,. Таким образом, 4 = 1+ 1, +... -!- 1', (1+(1 — !) с,+Ыс,!а! — д(с, Ыс, ~ и) — (д — 1) 1с, < Ыс1 ! а ) — 1 1с, Случай 2: Х,— терминал.
В качестве упражнения предлагаем показать, что в этом случае 1< 1+Ыс, (~!и ! — 1) ( й!с, ( а ( — 11с,. Из (4.!.1) вытекает, что если 5=>1п и (а!) 1, то 4< Ыс, ~и~. Возьмем с — Ыс,; лемма доказана. П 334 4Л. СИНТАКСИЧЕСКИЙ АНАЛИЗ С ВОЗВРАТАМИ Следствие 1. Пусть 6 = (11', ль Р, Ь) — не лсворекурсивная г пмматика. Тогда найдется такая константа с', что если Б=:;>','4оАа и Н4~е, то 1<с'(4в!. Д о к а з а т е л ь с т в о. Согласно следс1 вию леммы 4.1, найдется такая константа с", что (п)<с"!и4!. По лемме 4.4 1' с!4вАп !.
Так как ! п1Ап ) < (2+ с") !4е ), то выбор с'=-с (2+с") дает нужный результат. Следствие 2. Пусть 6 — --(14, Б, р, 5) — не леворекурсивная граммптикп. Тогда найдел1ся такая константа я, что если л — частичный левый разбор, совл4естимый с целочкой 4о, и 5„=='> хсс, где и — либо е, либо нпчинаели:я нетерминплом, то /л/:й (!4о/-!-1).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
