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

гл. 3. ТЕОРИЯ ПЕРЕВОДА

3.4. синтаксический анализ

\-(q, а, $£-ЬТ*, 64264)

еЕ + Та, 64264) h (q, $£ + r*f, 642646) h (q, $£ + r, 6426463) h (9, e, $£, 64264631) h(9, 64264631)

Таким образом, для входной цепочки а + анализатор Л1ра выдает правый разбор 64264631. □

В гл. 4 мы рассмотрим детерминированное моделирование недетерминированного правого анализатора. В разд. 5.2 обсудим важный подкласс КС-грамматик, называемых LR-грамма-тиками (вход читается слева (left) направо и выдается правый (right) разбор), для которых соответствующий МП-преобразователь можно сделать детерминированным, позволив ему заглядывать па входе на несколько символов вперед, LR-грамматики- это те, которые анализируются снизу вверх (по дереву вывода от кроны к корню) естественным образом и притом детерминированно. Как и в случае левого разбора, существуют грамматики, для которых возможен детерминированный, но не естественный правый анализ; их мы обсудим в следующем разделе,

3.4.4. Сравнение нисходящего разбора с восходящим

Если рассматривать недетерминированные анализаторы, то сравнивать по существу нечего, так как по теоремам 3.11 и 3.12 для каждой КС-грамматики возможен как левый, так и правый анализ. Однако, если поставить важный вопрос о том, существуют ли для данной грамматики детерминированные анализаторы, то тут дело обстоит не так просто.

Определение. Назовем КС-грамматику G левоанализируелюй, если существует такой ДМП-преобразователь Р, что

T(P) = {(xS, л)(х, л)€Г?}

и правоанализируемой, если существует такой ДМП-преобразо- ватель Р, что

тр) = {(х$, л)(х, л)ет?}

В обоих случаях ДМП-преобразователю разрешается использовать концевой маркер для указания правого конца входной цепочки.

Заметим, что все КС-грамматики лево- и правоанализируемЫ в неформальном смысле, но в данном формальном определений отражен именно детерминизм.

Мы обнаружим, что классы лево- и правоанализирусмых грам-тик несравнимы, т. е. ни один из них не является подмноже-вом другого. Это удивительно с точки зрения разд. 8.1, где лет показано, что LL-грамматики, которые можно детерминиро-анно левоанализировать естественным образом, образуют под-эножество LR-грамматик, которые можно детерминированно ппавоанализировать естественным образом. Приведем примеры грамматик, лево- (право-) анализируемых, но не право- (лево-) анализируемых.

Пример 3.26. Пусть грамматика Gj определена правилами

(1) S~BAb (2) SCAc (3) АВА (i) Аа

[Ъ) В->а (6) Са

l{G = aabаас. Можно показать, что Gj не является ни LL-, нн LR-грамматикой, потому что до тех пор, пока мы не увидим последний символ цепочки, не известно, каким нетерминалом В или С порождается первый символ а.

Однако можно «неестественно» получить левый разбор произвольной входной цепочки с помощью ДМП-преобразователя. Рассмотрим в качестве входной цепочки аЬ (дО). Тогда ДМП-преобразователь может сделать левый разбор 15(35)"4, помещая в магазин все символы а до тех пор, пока он не увидит Ь. При этом ва выходе ничего не порождается. Когда Ъ появится, ДМП-преобразователь может выдать 15 (35)"4, подсчитав п с помощью занесенных в магазин символов а. Подобным же образом для входа аЧ можно получить 26(35)"4 на выходе. В любом случае вся хитрость в том, чтобы отложить порождение выхода до того, как появится Ь или с.

Теперь попытаемся убедить читателя, что не существует ДМП-преобразователя, способного порождать правильные правые разборы для всех входных цепочек. Допустим, что ДП-преобразо-ватель М порождает правые разборы 55"43"1 для цепочки аЪ и 6543"2 для цепочки а"с. Докажем неформально, что такой преобразователь невозможен. Это доказательство существенно опирается па результаты работы Гинзбурга и Грейбах [1966], где показано, что {б["6"п>1уи {а"Ь2"а>Ц не является детерминированным КС-языком. Знакомство с этой работой поможет при построении формального доказательства. Можно доказать следующие утверждения:

л У о} поступает на вход преобразователя М. Тогда • "00 его выход пуст, либо он выдает 5 или 6, и преобразователь М.

жно «обмануть», подав на вход с или Ъ соответственно и сде-

в Тем самым его выход ошибочным.



(2) По мере того как символы а поступают на вход М, они должны так или иначе запасаться в магазине. Точнее, можно показать, что найдутся такие числа / и , магазинные цепочки а и Р и состояние q, что (д, а+>, Z, * {q, е, а, ef) длд всех рО, где q. и Z, - начальные состояние и магазинный сим-вол преобразователя М.

(3) Если после k + jp символов а на входе М появляется один символ &, то М не может выдать 4 до тех пор, пока не сотрет магазинную ленту вплоть до а. В противном случае мы могли бы «обмануть» М, предварительно поместив на вход дополнительные / символов а, в то время как М будет выдавать то же количество чисел 5, которое он выдавал раньше, так что оба выхода правильными быть не могут.

(4) После того как магазин сократится до цепочки а, преобразователь М уже не может «помнить», сколько символов было на входе, потому что теперь конфигурации преобразователя М для разных значений р (где k-\-jp - число символов а) отличаются только их состояниями. Таким образом, М не знает, сколько теперь надо выдать чисел 3. П

Пример 3.27. Пусть определяется правилами

(3) (5)

~АЬ АВ

(2) (4)

-Ас а

L(G. = ab-\-ac. Легко показать, что G2 - правоанализир\с-мая грамматика. С помощью рассуждений, аналогичных проведенным в упр. 3.26, можно показать, что G не левоанализируема. □

Теорема 3.13. Классы лево- и правоанализируемых грамматик несравнимы.

Доказательство. Примеры 3.26 и 3.27. □

Несмотря на эту теорему, восходящий синтаксический анализ, как правило, привлекательнее нисходящего, так как для данного языка программирования часто легче написать правоанализируе-мую грамматику, чем левоанализируемую. К тому же, как отмечалось, LL-грамматики содержатся в классе LR-грамматик. В следующей главе мы увидим также, что естественное моделирование недетерминированного МП-преобразователя в случае, когда он является правым анализатором, работает для более общего класса грамматик (в некотором смысле, который там будет разъяснен), чем в случае левого анализатора.

) Здесь подразумевается, что верх магазина расположен слева.-Я/"-перев.

Опнако с точки зрения процесса трансляции левый анализ педпочтительнее. Мы покажем, что каждый простой СУ-перевод можно выполнить с помощью

(\) мП-преобразователя, дающего левые разборы входных цепочек, за которым следует

(2) ДМП-преобразование, отображающее левые разборы в выходные цепочки данного СУ-перевода.

Интересно, что существуют простые СУ-переводы, для которых в приведенном выше утверждении нельзя заменить «левый разбор» на «правый разбор».

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

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

Определение. Пусть G-(N, 2, Р, S)-КС-грамматика. Определим язык Vf левых и язык правых разборов грамматики G:

= {n\Sj(=>w для некоторой w£L{G)] {л; IS =Ф„ш для некоторой w£L{G)\

Обозначения „=> и можно распространить на СУ-схемы, договорившись, что (а, р)„=>(у, 6) тогда и только тогда, когда (а, р)~>*(у, б) причем на каждом шаге этого вывода заменяется самый левый нетерминал первой компоненты выводимой пары и примененные при этом правила, из которых удалены элементы перевода, образуют последовательность л. Аналогично Для СУ-схемы определяется =Ф„.

Определение. СУ-схема называется семантически однозначной, если в ней нет двух различных правил вида А -*-а, р и Л --а, у.

о семантически однозначной СУ-схеме для каждого правила водной грамматики есть точно один элемент перевода.

"Рема 3.14. Пусть r = (N, S, Л, S)-семантически одно-ачнал простая СУ-схема. Тогда существует такой ДМП-/гре-

очГТб2*f " "" "" некоторой



Доказательство. Пусть P = {{q\, {1, р}, N U А, А, й, q, 5, 0), где 1, р-номера правил входной грамматики, а S определяется так:

(1) Пусть Л-а-правило входной грамматики с номером i и A-oLy р-единственное соответствующее правило схемы. Тогда b{q, iy A)(qy р, е).

(2) b{qy b)-{q, е, b) для всех ЬА.

МП-преобразователь Р детерминированный, потому что правило (1) применяется только тогда, когда наверху магазина находится нетерминал, а правило (2) применяется только тогда, когда наверху выходной символ. Корректность преобразователя Р следует из утверждения, которое легко доказывается индукцией: [q, л, Л, ) Н * е, у) тогдаитолько тогда, ког-

да существует такая цепочка xS*, что (Л, Л)д=>(л;, у). Доказательство оставляем в качестве упражнения. □

Чтобы описать СУ-перевод, ие выполнимый никаким ДЛШ-преобразователем, отображающим где G-входная грамматика, в соответствующие выходы этого перевода, нам понадобится следующая лемма.

Лемма 3.15. Не существует такого ДШ1-преобразователя Р, что т{Р) = {(ж, wcw)\w{a, b}*\.

Доказательство. Здесь символ с играет роль правого концевого маркера. Допустим, что Р для входа w выдает неко-торую непустую цепочку, скажем dx, где d £ {а, Ь}. Пусть d означает символ, противоположный d. Посмотрим, как работает Р с цепочкой wdc в качестве входа. Он должен выдать некоторую цепочку, но эта цепочка должна начинаться символом d. Следовательно, Р не отображает wdc в dwcwd, как требуется. Таким образом, Р не может ничего выдать на выходе, пока не будет достигнут правый концевой маркер с. В этот момент Р будет находиться в состоянии (у и хранить в магазине цепочку х,-

Неформально должна быть по существу цепочкой w, и тогда, стирая а, Р может выдать w. Но стоит ему стереть а, как он уже не может «вспомнить» всю цепочку w, чтобы напечатать ее на выходе. Формальное доказательство леммы аналогично рассуждениям в примере 3.26. Здесь мы дадим набросок доказательства.

Рассмотрим входные цепочки вида w=a. Существуют такие числа / и ky состояние q и цепочки аир, что, прочитав на входе fir/+"*c, Р помещает в магазин ар" и переходит в состояние t/-Тогда Р должен стереть содержимое магазина вплоть до а к том} моменту, когда он выдает wc. Но так как а от ш не зависит, то выдать W уже невозможно. □

Теорема 3.15. Существует простая СУ-схема Т - X, А, - которой нет такого ДМП-преобразоей-

теля р! Ч1П0 т(Р) = {(л, x)\{Sy 5)=Ф„(а), х) для некоторой цепочки ш}-

Доказательство. Пусть Т определяется правилами

(1) SSa, aSa

(2) S~Sb,bSb

(3) SCyC

Тогда Lf3(l+2)*, где G - входная грамматика. Если положить h{l)=u и /1(2)6, то требуемым переводом т(Р) будет {(За, h{a)ch{0L))\a\l, 2j-*[. Если бы ДМП-преобразователь р, о котором говорится в теореме, существовал (с правым концевым маркером или без него), то можно было бы построить ДМП-преобразователь, определяющий перевод {(шс, wcw)\w£{a, 6}*}, а это противоречит лемме 3.15. П

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

3.4.5. Грамматическое покрытие

Пусть Gj -КС-грамматика. Можно считать, что грамматика G подобна Gj с точки зрения процесса разбора, если (G2)-L(GJ и левый и/или правый разбор цепочки, порождаемой грамматикой Gj, можно выразить в терминах ее разбора в грамматике G. В таком случае говорят, что G покрывает Gj. Покрывающие грамматики можно использовать несколькими способами. Например, если язык программирования описан «трудно» анализируемой грамматикой, то было бы желательно найти покрывающую грамматику, анализируемую «легче». К тому же несколько изучаемых далее алгоритмов разбора работают только тогда, когда грамматика находится в некоторой нормальной форме, например в нор-льной форме Хомского или в такой, где нет левой рекурсии. jjнpoизвoльнaя грамматика, а Ga -ее какая-то нормаль-был Желательно, чтобы разборы в грамматике Gj можно

необ° восстановить по разборам в G. В этом случае нет в (j-ocTH уметь восстанавливать разборы в G по разборам

«во*. Ф°Рального определения того, что подразумевается под в д "°лением» разборов в одной грамматике по разборам 1щ yf воспользуемся понятием гомоморфизма между разбора- Редставляющими собой цепочки определенного вида. Можно





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