Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 110
Текст из файла (страница 110)
ц ля епочки 0" " илн ветственно. ! ) Д " способ †свертыва такие состав щ ляю ие выводимой ругой цепочки,.которые не являются основами. Оп деление. Если 6=(Ь(, до Р, 3) — КС-грамматика и в ней ре А ан, то цепочка () называется состпэля- есть вывод З~*аАу=эафу, то Х . Х б дем говорить, что чки ан. ПстьХ,... Аи ставляющие выводимой цепочки Х,...Х„, удем г ая Х ... Х расположена левее состэвляющей — Т б азом если грамматика одиозна, составляющая правовыво' либо 1=- ! и й < .
аким о разом, однозначная, то основа †сам левая димой цепочки. Пример 6.9. Рассмотрим грамматику 6 с правилами 5 — ОАВЬ ) ОаВс А — а В=В!) 1 6 — это егулярное множество Оа! ( + ), ' Ь с) но 6 — не).й-грамс 6 жсн восходящий разбор, если реше- матика. д . О нако для возможен в ставляющей, отложить до ние вопроса о том, является ли а соста ходной символ Иными тех пор, п , пока не прочтем последний вх епочк вида Оа!" можно свернуть к ОаВ словамн, входную цепочку вид , еле ет за ней Ь или с. первом независимо от того, ду епочка ОаВЬ сначала 'свертывается к цеп в о ом сл чае цепочка и с ОаВ сразу свертывается к 5. При этом, КОНЕЧНО, МЫ НЕ ПОЛУЧИМ 1 тр у' 1и левого, ни правого разбора.
() Пусть 6=-(., =. Ч, Х, Р 5) — КС-грамматика, правила которой за- нумерованы числами от 1 до р, и пусть (б.2.1) 5 = я, =~ а, => а, =>... ==> а„=-. и ля 0:! 'и пусть яг=ргАгб, и — вывод цепочки гэ Иэ 5. Для '< у м ., кото ое применялось к явно А, у; — правило с номером р!, р УказанномУ вхождению А, в Яг и дало Я„„=чб,тг ! аг в я ~а можно представить парой чисел (рп 1;), где (6.2*1) можно представить цепочкой, со- Таким образом, вывод ! .
*, м ж стоящей из и пар чисел (б.2.2) (р„!.)(р, !)" (Р.-ь .-) ) й, то вторые компоненты пар це- Еслп вывод правый или левы, р (б.2.2) казывающие позицию нетерминала, разверты не писать. мого на очередном шаге вывода, можно ГЛ. Е. АЛГОРИТМЫ РАЗБОРА С ОГРАНИЧВННЫМИ ВОЗВРАТАМИ нисходя Опйеделение. Назовем цепочку пар вида (6.2.2) (обоб одяи!им разбором цевочки се. Ясно, что левый азбо— и(еннрси р р част у д щего разбора. Аналогично назовем обращеиив; цепочки вида (6.2.2), т. е.
цепочку (ре-т~ н-т) (рч-в~ !ч-ч) (рп !т) (ре~ !е) то (обобщенным) восходящим разбором цепочки ти. Таким образпм;-' правый разбор — частный случай восходящего разбора. тебю е, Если ослабить ограничение на просмотр входной р у щ е, чтобы она читалась только слева направо цепочки,",, тить возв аты на вхо во, и допус р оде, то детерминированный разбор становится,'" возможным для таких грамматик, которые нельзя анализировать,-",: .
просматривая вход только слева напр во. а 6.3.2. Аивпизаторы с двумя магазинами В вве ем в качестве модели некоторых алгоритмов с возвратами мы д м автомат с двумя магазинами, причем второй ступает также в . ол ро магазин вы- в .роли входной ленты. Детерминированная версия этого устройства родственна анализатору с двумя магазинами .' который применялся в алгоритмах 4.1 и 4.2 и .
для общего нисхо' дящего и восходящего анализа. Мы наложим на это й устро ство " ограничения, благодаря которым оно будет вести себя как восходящий анализатор, использующий предшествование. г амматики б= Определение. Двухмагазинным (восходящим) анализатором р б=(Ь), Т, Р, 5) назовем конечное множество правил ром для (, Й) (Т, ), де сс„о, у и 6 — цепочки символов нз' Ь) 04 () (5), причем 5 — новый символ, концевая маркер. Каждое правило (сс, р) (у, 6) должно иметь один из двух видов: либо. (1) 6 —.— Х6 для некоторого Хбр)ОТ и у=-аХ, либо вила из Р. (2) а=-ув для некоторого БЕ(р(цХ)' 6=А~~.
А Г и в — пра- В общем случае правило (сс, р)- (у, 6) говорит о том, что если а †верхн цепочка первого магазина и 6 †верхн цепочка второго магазина, то можно заменить сс на у в первом магазине и р на 6 — во втором. Правило типа (1) соответствует переносу в алгоритме, анализирующем методом „перенос †свертка". Правило типа (2) соответствует шагу свертки. Существенное различие состоит в том, что символ А, являющийся левой частью применяемого правила грамматики, помещается на верх второго магазина а не п , а не первого.
Зто соглашение налагает ограничения на возвраты. Можно перемещать символы из первого магазина во второй (который функционирует как входная лента), но только 544 ЕЛЬ ВОСХОДЯЩИЯ РАЗВОР С ОГРАНИЧВННЫМИ ВОЗВРАТАМИ в моменты сверток. Разумеется, правила типа (1) позволяют символам в любой момент перемещаться из второго магазина .в первый. Конфигурацией двухмагазииного анализатора Т называется тройка (а, )3, и), где аб$(г!0Х)*, рб()ч) 0Х)'9, а п — цепочка пар, состоящих из целого числа и номера правила. Таким образом, п может быть частью разбора некоторой цепочки из А'. (б).
Мы пищем (а, )5, и) ) — (а', р', и'), если (1) а = сета„р= Щ, (а„р,) (у, 6) — правило анализатора Т; (2) сс'=ссср, )5'=6(),; (3) тс'=и, если (а„рв) (у, 6) — правило типа 1; если это— правило типа 2 и применяется 1-е правило грамматики, то :с'=п(1, !), где 1=)сс') — 1'). Заметим, что верх первого магазина расположен справа, а второго магазина — слева. Обычным образом по отношению )-г определим отношения )-',', )-т и ! — г. Когда можно, будем опускать индекс 'Т.
Переводом, определяемым анализатором Т, назовем множество т (Т) = ((ю, п)1(6, тв3, е))-'(6, б 5, лЦ. Назовем анализатор Т корректным для грамматики б, если для каждой цепочки в Е !. (б) найдется такой ее восходящий разбор и, что (тв, и) Е т(Т).
Можно элементарно показать, что если (и, п) бт(Т), то и — восходящий разбор цепочки ю. Анализатор Т назовем детерминированным, если выполнено следующее условие, Пусть (а„рт) (уо 6,) и(сс„ре) (у„бв)— такие правила, что одна из цепочек а„а, является суффиксом другой, а одна из цепочек Ь'„ (), является префиксом другой; тогда у, = у, и 6, = 6,. Таким образом, для каждой конфигурации С существует не более одной такой конфигурации С', что С) — С'. Пример 6.!О.
Рассмотрим грамматику б с правилами (1) Я аЯА (2) 3 ЬЮА, (3) 3- Ь (4) А- а Эта грамматика порождает иедетерминироваиный КС-язык (теЬа" ~сей(а+6)' и п=)ю)). Можно построить (недетерминированный) двухмагазинный преобразователь, который будет анализировать цепочки в соот- ') оДИНВЦВ ВЫЧИтаЕтСЯ ПОтОНу, ЧТО цЕПОЧКа а' СОДЕРжИт КОНЦЕВОЙ маркер.
545 ГЛ, В. АЛГОРИТМЫ РАЗБОРА С ОГРАНИЧВННЫМИ ВОЗВРАТАМИ ветствии с грамматикой 6, сначала помещая всю входную цепочку в первый магазин, а затем разбирая ее по существу справа налево. Правила анализатора Т таковы: . 'Ф (!) (е, Х)-+.(Х, е) для всех ХЕ(а, 6, 5, А) (любой символ можно перенести из второго магазина в первый), (2) (а, е)-+ (е, А) (а можно свернуть к А), (3) (Ь, е)-~-(е, 5) (Ь можно свернуть к 5), (4) (а5А, е)-+(е, 5), (б) (65А, е)-~(е, 5)." (Последние два правила анализатора допускают свертки, соответствующие.правилам (1) и (2) грамматики 6.) Заметим, что анализатор Т недетерминированный и для каждой входной цепочки можно получить много разборов.
Один из восходящих разборов цепочки аййаа представляется такой последо-- вательностью конфигураций: 'А; ($, аЬЬаа$, е) ) — ($а, ЬЬаа$, е) ) — ($аЬ, Ьаа$, е) ) — ($аЬЬ, аа$, е) )- ($аЬ, 5аа$, (3, 2)) ) — ($аЬ5,аа$, (3, 2)) )-($а65а, а$, (3, 2)) )-($а65аа, $, (3, 2)) ) — ($а65а, А$, (3, 2)(4, 4)) 1 — ($аЬ5, АА$, (3, 2) (4,4) (4, 3)) ) — ( 65А„А$, (3, 2) (4, 4) (4, 3)) ( — ($а, 5А$, (3, 2) (4, 4)(4, 3) (2, 1)) 1 — ($а5, А$, (3, 2) (4, 4)(4, 3) (2,!)) 1 — ($а5А, $, (3, 2) (4, 4) (4, 3) (2, 1)) 1 — ($, 5$, (3, 2) (4, 4) (4, 3) (2, 1)(1, О)) Цепочка (3, 2) (4, 4) (4, 3) (2, 1) (1, О) образует восходящий разбор цепочки аЬЬаа, соответствующий выводу 5 =:;>а5А =Фа65АА =:;> а65аА ==> а65аа =Р аййаа П Двухмагазиппый анализатор имеет особенность, отличающую его от обычных алгоритмов типа „перенос — свертка"'.
Может оказаться, что такой анализатор работает и для неоднозначной грамматики, игнорируя некоторые из возможных в ней выводов. Пример 6.11. Пусть 6 определяется правилами 5 — А)В А--- аА ~а  — Ва ~а 6 — неоднозначная грамматика для языка а+. Если игнорировать нетерминал В и В-правила, то детерминированный двухмагазин- взь восходящин РАзвоР с огРАничвнными, возвехтхми ный анализатор для 6 образуется из правил (е, а) — (а, е) (а, $) (е, А$) (а, А) (аА, е) (аА, $) — (е, А$) ($, А) ($А е1 ($А $)„' ($, 5$) гл 6.2.3. Отношения продшоствонвння Колмервуэрн Двухмагазннный анализатор можно устроить так, чтобы способ его работы был отчасти похож на разбор методом предшествовапия.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
