Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 61
Текст из файла (страница 61)
теОРия пгРЕВОЛА 3.4. СИНТАКСИЧНСКИИ АНАЛИЗ Вообще правый разбор цепочки ш в грамматике б=()ч, 2, Р,б) это последовательность правил, с помощью которых можно евер. путь цепочку ш к начальному символу Е. В терминах деревьев выводов правый анализ цепочки ш представляет собой последа. вательность отсечений основ, сводящую дерево вывода с кро. ной ш к одной вершине, помеченной 5. В сущности это равно. сильно процессу „заполнения" дерева вывода, начииающемусв с одной только кроны и идущему от листьев к корню. Позтолт) с процессом порождения правого разбора часто ассоцинруетсв термин „восходящий" анализ. По аналогии с СУ-схемой Т„отображающей цепочки из Е (б) в их левые разборы, можно определить СУ-схему Т,„отобрг. жающую цепочки в правые разборы. В ней из элементов перевода устранены терглиналы, а номера правил выводов пишутся справа. Доказательство того, что эта СУ-схема кор.
ректно определяет нужный перевод, оставляем в качествв упражнения. Что касается восходящего анализа, то иас прежде всего интересует МП-преобразователь, реализующий схему Т„. По аналогии с расширснным МП-автоматом определим расширенный МП-преобразователь. Определение. Расширенным МП-преобразователем назовев восьмерку Р=(«г', Х, Г, б, б, О„Е«, Р), где все символы паин. маются так же, как прежде, по только б теперь обозначает отображение конечного подмножества множества «г х (Х () (е)) к Г* в множество конечных подмножеств множества «гхГ" г4г3«. Кон. фигурации определяются так же, как прежде, по обычно подразумевается, что верх магазина расположен справа, и запись (д, аш, ()я, х) )- (р, ш, ру, ху) означает, что 6(о, а, я) содержит (р у у).
Расширенный МП-преобразователь Р называется детермини. роганным, если (1) 4Ь 6(т), а, я) ~ 1 для всех оЕ«г, а ЕХ П(е) и яЕГ', (2) цепочки я и (3 не являются суффиксами одна другой, если б(д, а, я) ~ 8 и 6(о, Ь, р) э« 8 для 6=а или Ь=г. Определение. Пусть б = (1«, Х, Р, Е) — КС-грамматика. Обо. значим через Мо расширенный недетсрминированный МП-пре. образователь ((д), Х, ХНА(! (6), (1, ..., р), б, о, $, 8), прнчеи верх магазина расположен справа и б определяется так: (1) 6(о, е, я) содержит (о, А, 1), если А — я — правило из Р С НОМЕРОМ 4', (2) 6(о, а, е) =((о, а, е)) для всех аЕХ, (3) б (д, е, $5) = ((д, е, е)).
302 -пр МП п«еобразователь содержит элементы алгоритма раз бо а, называем емого алгоритмом типа перенос — свертка. На такте, ующем правилу (2), М, переносит входной символ Всякий раз, когда наверху магазина появляется тветствующ . магазин. но М„может свеРнУть ее по пРавилУ (1) и выдать номеР и авила, и использованного при свертке.
Затем М, может продолжать пе переносить в магазин входные сгтмволы, пока в его части не появится новая основа. Эта основа свертыверхней част вается, а и , а на выход выдается номер соответствующего правила. М йствует так до тех пор, пока в магазине пе останется М„де ств только н ЫЮ~ЬН~~ СИМВОЛ С МЗРКЕ„„ „, м вилу ( (3) М может перейти тогда в конфигурацию с пустым магазином. Теорема 3.12. Пусть б =- (Х, Х, Р, 5) — КС-граммаптика.
Тогда т,(М,) =((ш и )(с=> ш) Д о к а з а т е л ь с т в о. Доказательство аналогично доказательству леммы 2.25; оставляем его в качестве упражнения. Пример 3.26. Правым анализатором для грамматики б, будет Мо«((у) Х )л(ц«'11(Ц (1 2 6) б (т ~ 8) 6 (д, е, Е + Т) = ((41, Е, 1) ) б (д, е, Т) =. ((д, Е, 2)) б (0, е, Т «Р) =- ((д, Т, 3)) б (д, е, Р) =- ((у, Т, 4)) 6 (д, е, (Е)) « — - ((д, Р, 5)) 6 (о, е, а) =((о, Р, б)) 6(д, Ь, е) =((д, Ь, е)) для всех Ь 6Х 6(о, е, 6Е) =-((4), е, е)) Для входной цепочки а+а«а анализатор Мо«лтожет среди других сделать такую последовательность тактов: (о, а-';а «а, $, е) (- (о, +а «а, 3а, е) (†(д, -(- а а, $Р, 6) )- («г, +а«а, $Т, 64) (- (д, +а«а, $Е, 642) (- (~у, а «а, 6Е + «642) )- (тт, «а, $Е+а, 642) )- (о, «а„6Е+Р, 6426) ( — (о, «а, $Е+ Т, 64264) 303 ГЛ.
3. ТЕОРИЯ ПЕРЕВОДА зл. синтлксическин Анллиз )- (д, а, $Е+Т», 64264) )- (д, е, $Е-(-Т«а, 64264) )- (Ч, е, 5Е-1- Т» Р, 642646) 1 — (д, е, $Е+Т, 6426463) )- (д, е, 5Е, 64264631) )- (д, е, е, 6426463!) Таким образом, для входной цепочки а+а»а анализатор Мо, выдает правый разбор 64264631. Г) В гл. 4 мы рассмотрим детерминированное моделирование недетерминированного правого анализатора. В равд. 5.2 обсу. дим важный подкласс КС-грамматнк, называемых Ы-грамма., тиками (вход читается слева (1сй) направо и выдается правый ~ (г|кП!) разбор), для которых соответствующий МП-преобразова. ~ тель можно сделать детерминированным, позволив ему заглядывать па входе на несколько символов вперед, 1.Й-грамма.
тики — это те, которые анализируются снизу вверх (по дереву вывода от кроны к корню) естественным образом и притом детерминнрованно. Как и в случае левого разбора, существуют грамматики, для которых возможен детерминированный, но яе естественный правый анализ; их мы обсудим в следующем разделе. 3.4.4. Сравнение нисходящего разбора с восходящим Если рассматривать недетермвнираванные анализаторы, то сравнивать по существу нечего, так как по теоремам 3.11 и 3.12 для каждой КС-грамматики возможен как левый, так и правый анализ.
Однако, если поставить важный вопрос о тои, существуют ли для данной грамматики детерминированные анализаторы, то тут дело обстоит не так просто. Определение. Назовем КС-грамматику б левоанализируемой, если существует такой ДМП-преобразователь Р, что т(Р) ==-((х$, и) )(х, и) Е Т~ и правоанализируемой, если существует такой ДМП-преобразо. ватель Р, что т (Р) = ((х$, и) ! (х, и) Е То) В обоих случаях ДМП-преобразователю разрешается использовать концевой маркер для указания правого конца входной цепочки.
Заметим, что все КС-грамматики лево- и правоанализируемм в неформальном смысле, но в данном формальном определении отражен именно детерминизм. ЗО4 1ы обнаружим, что классы лево- и правоанализирусмых грамматик равнимы, т. е. ни один из них не является подмножеством д „другого, Зто удивительно с точки зрения равд. 8.1, где показано, что 1(-грамматики, которые можно детерминиробудет ванно ° а„но левоаналнзировать естественным образом, образуют подмно ство (.К-грамматик, которые можно детерминярованно воанализировать естественным образом. Приведем примеры амматик, лево- (право-) анализируемых, но не право- (лево-) анализируемых. пример 3.26. Пусть грамматика 6, определена правилами (! )  — ВАЬ (2)  — САс (3) А — ВА (4) А — а (5)  — а (6) С вЂ” а Ь(6,) =аа+Ь+аа'с. Можно показать, что 6, не является ни нп 1В-грамматикой, потому что до тех пор, пока мы не увидим последний символ цепочки, не известно, каким нетерминалом В или С порождается первый символ а.
Однако можно «неестественно» получить левый разбор произвольной входной цепочки с помощью ДМП-преобразователя. Рассмотрим в качестве входной цепочки а"+»Ь (и~О). Тогда ДМП- преобразователь может сделать левый разбор 15(35)"4, помещая в магазнн все символы а до тех пор, пока он не увидит Ь. Прн этом ва выходе ничего не порождается. Когда Ь появится, ДМП-преобразователь может выдать 15 (35) "4, подсчитав и с помощью занесенных в магазин символов а. Подобным же образом для входа а""с можно получить 26(35)"4 на выходе. В любом случае вся хитрость в том, чтобы отложить порождение выхода до того, как появится Ь или е Теперь попытаемся убедить читателя, что не существует ДМП- преобразователя, способного порождать правильные правые разборы для всех входных цепочек. Допустим, что ДМП-преобразователь М порождаст правые разборы 55"43" 1 для цепочки а" +»Ь " 55"43"2 для цепочки а""с.
Докажем неформальпо, что такой преобразователь невозможен. Зто доказательство существенно опиРается на результаты работы Гинзбурга и Грейбах 119661, где показано, что (а"Ь»1п ' 1) и (а»Ь» )и~1) не является детерми"яроваиным КС-языком. Знакомство с э1ой работой поможет при пост остроснии формального доказательства. Можно доказать следующие утверждения: либо ег (1) Пусть а' поступает на вход преобразователя М.
Тогда о его выход пуст, либо он выдает 5 или 6, н преобразователь М лвв т аож"о «обмануть», подав на вход с илн Ь соответственно и сдетем самым его выход ошибочным. 30» ГЛ. ». ТЕОРИЯ ПЕРЕВОДА зл. сиитАксический АиАлвз 307 (2) По мере того как символы а поступают на вход М, ояя должны так или иначе запасаться в магазине.
Точнее, можно показать, что найдУтсЯ такие числа 1 и й, магазинные цепочки а и )$ и состояние д, что (у„а»'~Р, 2„е)Г-» (д, г, р»гх, г)') для всех Р~~О, где д» и 2,— начальные состояние и магазинный сим. вол преобразователя М. (3) Если после и + )р символов а на входе М появляется одпя символ Ь, то М не может выдать 4 до тех пор, пока не сотрет магазинную ленту вплоть до а. В противном случае мы могли бм «обмануть» М, предварительно поместив на вход дополнительные ) символов а, в то время как М будет выдавать то же количество чисел 5, которое он выдавал раньше, так что оба выхода правильными быть пе могут.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
