Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 62
Текст из файла (страница 62)
(4) После того как магазин сократнтся до цепочки а, преобргзователь М уже не может «помнить», сколько символов было еа входе, потому что теперь конфигурации преобразователя М для разных значений р (где й+)р — число символов а) отличаются только их состояниями. Таким образом, М не знает, сколько теперь надо выдать чисел 3, () Пример 3.27. Пусть 6, Определяется правилами (!) В -- АЬ (2)  — Ас (3) А — АВ (4) А — а (5)  — а 1.(6,) =а Ь+а'с. Легко показать, что 6,— правоанализирзс. мая грамматика.
С помощью рассуждений, аналогичных проведенным в упр. 3.26, можно показать, что 6, не левоанализируема. Теорема 3.13. Классы лево- и правоанализируелых гражлатих несравнимы. Д о к а з а т е л ь ство. Примеры 3. 26 и 3. 27. Несмотря на эту теорему, восходящий синтаксический анализ, как правило, привлекательнее нисходящего, так как для данного языка программирования часто легче написать правоанализируе. мую грамматику, чем левоанализируемую.
К тому же, как от~:е. чалось, 1).-грамматики содержатся в классе (.1«-грамматик. В еле. дующей главе мы увидим также, что естественное моделирование недетерминированного МП-преобразователя в случае, когда он яз. ляется правым анализатором, работает для более общего класс» грамматик (в некотором смысле, который там будет разъяснен) чем в случае левого анализатора.
») Эдесь подразумевается, что верх мага»ива рясположев слева.— НРк" п«р«в, „н ко с точки зрения процесса трансляции левый анализ предпочтит ительнее. Мы покажем, что каждый простой СУ-перевод можно но выполнить с помощью (1) МП-преобразователя, дающего левые разборы входных це„очек, за которым следует (2) ДМП-преобразование, отображающее левые разборы в выходные цепочки данного СУ-перевода. Ннтересно, что существуют простые СУ-переводы, для которых в прн приведенном выше утверждении нельзя заменить «левый разбор» на «правый разбор». Если компилятор транслирует так, что вначале строится полный разбор, который потом превращается в объектный код, то указанное обстоятельство достаточно для доказательства того, что существуют переводы, требующее на промежуточной стадии именно левого разбора.
Однако многие компиляторы строят дерево разбора вершина за вершиной и вычисляют перевод в каждой вершине, когда она построена, Мы утверждаем, что если перевод нельзя вычислить прямо по дереву разбора, то его нельзя вычислять вершина эа вершиной, когда само построение вершин идет снизу вверх. Это обсуждается подробно в гл.
9, и мы просим читателя подождать до этой главы с формализацией материала, связанного с переводом <вершина за вершиной». Определение. Пусть 6 —. (1х, Х, Р, В) — КС-грамматика. Определим язык 1,У левых и язык 1.о правых разборов грамматики 6: Ц=- (я ~ Вм.=зги для некоторой шит(.(6)) 1.о= (и" ) 5 =1>„ге для некоторой шЕ 1.(6)) Обозначения „=О и =>м можно распространить на СУ-схемы, договорившись, что (а, р) — >(у, 5) тогда и только тогда, когда (и р) ь" (у, б), причем на каждом шаге этого вывода заменяется самый левый нетерминал первой компоненты выводимой пары и примененные при этом правила, из которых удалены элементы перевода, образуют последовательность и. Аналогично длЯ СУ-схемы определяется »„.
Определение. СУ-схема называется семантически однозначной, ес«ш в пей нет двух различных правил вида А — и () и А — а у В семантически однозначной Су-схеме для каждого правила вхо н"одной грамматики есть точно один элемент перевода. Теорема 3,14. 17усть Т = ()ч, Х, А, 11, В) — семантически одно"Ростая СУ-схел«а, Тогда суи«гствует такой ДМП-пргРазователь Р, что т, (Р) = ((и, У) ) (5, В) м==;>(х, У) длл некотоРой йепочки х а т.'). ГЛ. 3. ТЕОРИЯ ПЕРЕВОДА ».Е. СИНТАКСИЧЕСКИЙ АНАЛИЗ Доказательство, Пусть Р=((ч), (1 " * Р) !е!0Л Л б, 11, 5, 8), где 1, ..., р — номера правил входной грамматики, а А определяется так: (1) Пусть А — а — правило входной грамматики с номером 1 и Л вЂ” а, () — -единственное соответствующее правило схемы, Тогдз б(у, 1, А) =(д, )\, е).
(2) б(д, е, Ь) =-(д, е, Ь) для всех Ь ЕЛ. МП-преобразователь Р детерминированный, потому что пря. вила (1) применяется только тогда, когда йаверху магазина находится нетерминал, а правило (2) применяется только тогда, когда наверху выходной символ. Корректность преобразова. тела Р следует из утверждения, которое легко доказывается индукцией: (д, и, Л, е) ) — '(д, е, е, у) тогда и только тогда, кот.
да существует такая цепочка хЕТ', что (А, А)п=!>(х, у). Доказательство оставляем в качестве упражнения. П Чтобы описать СУ-перевод, не выполнимый никаким ДМП. преобразователем, отображающим (,о, где 6 — входная грамматика, в соответствующие выходы этого перевода, нам понадобится следующая лемма. Лемма 3.13. Не суи(ествует такого ДМП-преобразователя Р, что т(Р)=((пю, ввсв) (вЕ(а, Ь)"). До к азател ьство. Здесь символ с играет роль правого концевого маркера. Допустим, что Р для входа в выдает некоторую непустую цепочку, скажем йх, где й Е (а, Ь).
Пусть «Гозиачает символ, противоположный «(. Посмотрим, как работает Р с цепочкой Ыс в качестве входа. Он должен выдать некоторую цепочку, но эта цепочка должна начинаться символом а. Следовательно, Р не отображает Ыс в йвяехеч(, как требуется. Таким образом, Р не может ничего выдать на выходе, пока не будет достигнут правый концевой маркер с.
В этот момент Р будет находиться в состоянии д и хранить в магазине цепочку о» Неформально и должна быть по существу цепочкой в, и тогда, стирая а, Р может выдать вя. Но стоит ему стереть ее, кях он уже нс может «вспомнить» всю цепочку в, чтобы напечатать ее на выходе. Формальное доказательство леммы аналогичвв рассуждениям в примере 3.26. Здесь мы дадим набросок доказя. тельства.
Рассмотрим входные цепочки вида в=а'. Существуют такие числа ! и Ь, состояние е) и цепочки а и (), что, прочитав на входе аГЕ«АС, Р ПОМЕЩаЕт В Матаэнн арп И ПЕРЕХОДИТ В СОСТОЯНИЕ Ч' Тогда Р должен стереть содержимое магазина вплоть до а к том)' моменту, когда он выдает вне. Но так как и от вне зависит, то выдать в уже невозможно, !") Теорема 3.13 Существует простая СУ-схелга Т = ,(Ь( ~, б, )е>, 5), для которой нет такого ДМП-преобразсватеея Р, что т(Р)=((яя, х)~(5, 5)==;>п(в, х) для некоторой цепочки в).
доказательство. Пусть Т определяется правилами (1) 5 5а, а5а (2) 5 — 5Ь, Ь5Ь (3) 5 — с, с Тогда 1~==3(1+2)', где б — входная грамматика. Если положить Ь(1)=а и Ь(2)=Ь, то требуемым переводом т(Р) будет ((3а, Ь(а)ясй(а)) ~ а Е(1, 2)'). Если бы дМП-преобразователь Р, о котором говорится в теореме, существовал (с правым концевым маркером или без него), то можно было бы построить ДМП-преобразователь, определяющий перевод ((вс, ввсв) (вЕ (а, Ь)'), а это противоречит лемме 3.13.
Итак, мы заключаем, что интересны как левый, так и правый анализ. Оба онн будут изучаться в последующих главах. Синтаксический анализ другого типа, обладающий чертами и нисходящего, и восходящего анализа,— анализ по левому участку— рассматривается в упражнениях. 3.4.5. Грамматическое покрытие Т! . усть 6,— КС-грамматика. Можно считать, что грамматика б, подобна б, с точки зрения процесса разбора, если 1.(бе) =-Т.(61) и левый и/или правый разбор цепочки, порождаемой грамма- тикой б„можно выразить в терминах ее разбора в грамматике 6,.
В таком случае говорят, что б, покрывает 6,. Покрывающие грамматики можно использовать несколькими способами. Напри- мер, если язык программирования описан «трудно» анализируемой гРамматико, матик, ана кой, то было бы желательно найти покрывающую грам- У. анализируемую «легче». К тому же несколько изучаемых далее алга тика нахо ит ритмов разбора работают только тогда когда грамма- мальиой о, одится в некоторой нормальной форме, например в норф рме Хомского или в такой, где нет левой рекурсии.
, — Роизвольная грамматика, а 6, — ее какая-то нормаль- сли 6 Р, то желательно, чтобы разборы в грамматике 6 можно ная фо ма восстановить по разборам в 6 . В этом случае нет ыло легко 1 ости уметь восстанавливать разборы в б, по разборам ходимос е 1 ля формального определения того, что подразумевается под нием» разборов в одной грамматике по разборам становле оспользуемся понятием гомоморфизма между разбораРугой, во представля ляющнми собой цепочки определенного вида.
Можно ГЛ, Э. ТЕОРИЯ ПЕРЕВОДЛ привлечь и другие, более сильные, отображения; некоторые иэ них рассматриваются в упражнениях. Определение. Пусть 6,=(!>)„Х, Р„Ь;) и 6,— ()4„Т,, Р„5,) КС-грамматики и й(б,) =-1,(б,). Будем говорить, что 6., лееопэ. крывает б„если найдется такой гомоморфизм й, отображающяй Р,вР;,что (1) если 5,„=01е, то 5,„1я1=>пй (2) ДлЯ кажДого и, Дла котоРого Ь;я=>п|, сУЩествУет такса разбор и, что 5„,;-Фп| и й(п ) =-и. Будем говорить, что б, праеопокрыеает б„если найдется такой гомоморфизм й, отобража|ощий Р, в Р„, что (1) ЕСЛИ 5,-— >„|Э, тО 5|=ФЛ|п|ПЛ (2) для каждого и, для которого 5,=О ю, существует такой разбор и', что 5|~, ю и й(и')=и.
Пример 3.28. Пусть 6,— грамматика с правилами (1) 5 — 051 (2) 5 — 01 а б,— эквивалентная ей грамматика в нормальной форме Хо>|. ского с правилами (1) 5 — АВ (2) Ь' — АС (3)  — 5С (4) А — 0 (5) С- ! Мы видим, что 6, левопокрывает б„соответствующий гомо. морфнзм определяется равенствами й(1) — -- 1, й(2) = 2, й(3) =-й(4) =й (5) =-е. Например, 5 мммь=>е, 0011, й(1432455) = 12 и 51,=!>е, 0011 6, также и правопокрывает б„причем подходит тот же гоме- морфизм й.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
