(1) АХХ, если в Р есть правило Л-Ха, где а-какая-нибудь цепочка;

(2) X(iK, если в Р есть правило ЛаХКр для некоторых аир; кроме того, и 5ц$;

(3) ХрЛ, если в Р есть правило Л-*-аХ, где а - какая-нибудь цепочка.

Покажите, что эти отношения и отношения предшествования Вирта-Вебера связаны следующим образом: (а)

(б) и{($,5), (5, $)}ц.

(в) >-p>X*n((Nu2)x2)

( - обозначает транзитивное, а »- рефлексивное и транзитивное замыкание).

**5.3.21. Докажите неразрешимость проблемы: является ли данная грамматика грамматикой расширенного предшествования (т. е. грамматикой {?п, /г)-предшествования для некоторых т и п)}

*5.3.22. Докажите, что если G-грамматика слабого предшествования, то G - грамматика расширенного предшествования (для некоторых тип).

5.3.23. Покажите, что а G FOLLOWj (Л) тогда и только тогда, когда Л<«а, Аа илн А}>а.

5.3.24. Обобщите лемму 5.3 на грамматики расширенного предшествован и я.

5.3.25. Предположим, что условия расширенного предшествования ослаблены так, что допускается конфликт a<w naw, если он порождается только пунктами (16) и (26). Разработайте алгоритм разбора типа „перенос-свертка" для грамматик, удовлетворяющих этому ослабленному определению.

Проблема для исследования

5.3.26. Найдите преобразования, позволяющие превращать грамматики в грамматики простого или слабого предшествования.

Открытая проблема

5.3.27. Порождается ли каждый язык простого предшествования грамматикой простого предшествования, у которой начальный символ не встречается в правых частях правил? Хорошо, если бы это было так, ибо в противном случае мы могли бы пытаться сделать свертку, когда в магазине %S, а на входе

(а) отношение не рефлексивно, не симметрично и не транзитивно;

(б) отношение <• не иррефлексивно н не транзитивно;

(в) отношение •> не иррефлексивно и не транзитивно.

*5,3.5. Покажите, что каждое регулярное множество определяется грамматикой простого предшествования. Указание: Убедитесь в том, что Ваша грамматика обратима.

*5.3.6. Покажите, что каждая обратимая грамматика {рг, п)-предшествования является LR-грамматикой.

*5.3.7. Покажите, что каждая грамматика слабого предшествования является LR-грамматикой.

5.3.8. Докажите, что алгоритм 5.12 правильно производит правый разбор.

5.3.9. Докажите, что G - грамматика предшествования тогда и только тогда, когда она-грамматика (1,1)-предшествования.

5.3.10. Докажите лемму 5.3(1).

5.3.11. Докажите, что алгоритм 5.14 правильно производит правый разбор.

5.3.12. Постройте алгоритм правого разбора для обратимых грамматик {т, п)-предшсствовання.

5.3.13. Докажите следствие теоремы 5.17.

*5.3.14. Покажите, что алгоритм 5.15 строит грамматику простого предшествования, эквивалентную исходной грамматике.

5.3.15. Для тех грамматик из упр. 5.3.1, которые являются грамматиками слабого предшествования, постройте эквивалентные грамматики простого предшествования,

*5.3.16. Докажите, что язык L{аО"1" 1} U {&0"12" « > 1} не является языком простого предшествования. Указание: Подумайте о том, как вел бы себя на цепочках вида aCl" и bOl" правый анализатор, построенный алгоритмом 5.12, если бы язык L определялся грамматикой простого предшествования.

*5.3.17. Постройте грамматику (2,1)-предшествования для языка из упр. 5.3.16.

*5.3,18. Постройте грамматику простого предшествования для языка {Oal" /г> 1} [) {0"Ь\" \ /1> 1}.

*5.3.19. Покажите, что каждую КС-грамматику без й-правпл можно преобразовать в эквивалентную грамматику (1,1)-пред-шествования.

5.3.20. Для КС-грамматики G"(N, 2, Я, 5) определим отношения К, \1 я р:

11;1.л\ли АНАЛИЗ БЕЗ ВОЗВРАТОВ

Упражнения на программирование

5.3.28. Напишите программу, строящую отношения предшествования Вирта - Вебера для КС-грамматики G. Примените Вашу программу к грамматике языка ПЛ 360, данной в приложении.

5.3.29. Напишите программу, строящую для входной КС-грамматики О алгоритм разбора типа ,переиос-свертка", если G - грамматика простого предшествования. Примените Вашу программу к построению анализатора для языка ПЛ 360.

5.3.30. Напишите программу, проверяющую, является ли грамматика обратимой грамматикой слабого предшествования.

5.3.31. Напишите программу, .строящую алгоритм разбора типа „перенос -свертка" для обратимых грамматик слабого предшествования.

Замечания по литературе

Разбор методом „перепое -свертка" появился впервые в работе Флойда [1961], В трактовке этого метода мы следовали статье Ахо и др. [1972]. Грамматики простого предшествования были определены Виртом и Вебером 11966] и независимо Пэром [!9С4]. Метод простого предн1естиования использовался в компиляторах для нескольких языков, включая Euler (Внрт и Вебер, 1966], Алгол W [Бауэр и др., 1968] и ПЛ 350 [Вирт, 1968]. Фишер [1969] доказал, что каждый КС-язык, ие содержащий е, порождается (не обязательно обратимой) грамматикой нредшествовання (упр. 5.3.19).

Расширенное предшествование было предложено Виртом и Вебером. Грэй [1969] указал, что некоторые нз ранних определений расшнреииого предшествования некорректны. При т-\-п > 3 расширенное {т, п)-предшествование, по-видимому, принесет на практике мало пользы из-за больших затрат памяти. Методы сокращения обьема таблицы анализатора расширенного предшествования изучал Мак-Киман [19С6]. Грэхем [1970] доказала интересную теорему о том, что каждый детерминнровапный язык определяется обратимой грамматикой (2,1)-нредшество8ания.

Грамматики слабого предшествования введены Ихбиа и Морзе [1970]. Теорема 5.19 взята нз статьи Ахо и др. [1972].

Для анализаторов типа „перенос -свертка" возможны несколько схем нс-правленин ошибок. В ходе разбора этого типа можно объявить об ошибке как в фазе переноса, так и в фазе свертки. Если об ошибке сообщает функция переноса, то можно попытаться делать изменения, вставки или удаления, как при LL- илн LR-разборе. Если ошибка встречается при свертке, то можно использовать заранее составленный список ошибочных правил, применяя его к верхней части магазина.

Техника исправления ошибок для грамматнк простого предшествования рассматривалась Виртом [1968] и Лейинусом [1970]). Чтобы усилить способность анализатора простого предшествования обнаруживать ошибки, Ленннус предложил, в частности, проверять после того, как сделана свертка, выполняется ли допустимое отношение предшествования между символами X и Л, где Л - новый нетерминал наверху магазина, а X -символ, расположенный сразу под ним.

)См. также [Ахо и Ульман, 1972], [Грэхем и Роудз, 1975]. -Лриж. перев

5.4. ДРУГИЕ КЛАССЫ ГРАММАТИК

5.4. ДРУГИЕ КЛАССЫ ГРАММАТИК, АНАЛИЗИРУЕМЫХ МЕТОДОМ «ПЕРЕНОС ~ СВЕРТКА»

Рассмотрим еще несколько подклассов LK-грамматик, для которых существуют алгоритмы синтаксического анализа типа перенос - свертка". Это грамматики ограниченного правого контекста, грамматики смешанного предшествования и грамматики операторного предшествования. Мы рассмотрим также язык Флойда-Эванса, который по существу является языком программирования, предназначенным для записи алгоритмов детерминированного разбора.

5.4.1. Грамматики ограниченного правого контекста

Хотелось бы расширить изученный выше класс грамматик слабого предшествования, ослабив требование обратимости. Совсем устранить это требование нельзя, так как экономный алгоритм разбора для класса всех грамматик предпюствования не известен. Но многие грамматики можно анализировать, используя слабое предшествование для локализации правого конца основы, а затем, если грамматика не является обратимой, с помощью локального контекста найти левый конец основы и определить, каким нетерминалом ее заменить.

Широкий класс грамматик, анализируемых подобным способом, образуют грамматики (т, Аг)-ограниченного правого контекста (ОПК). Неформально G (N, 2, Я, S) будет (т,/г)-ОПК-грамматикой, если для каждого правого вывода

aAw afjw

в пополненной грамматике G-(Nu{5}. 2, P\J\S~S}, S) основу р и правило А-применяемое для свертки основы в цепочке a{5w, можно однозначно определить так:

(1) Цепочка apw просматривается слева направо, пока не будет прочитана основа.

(2) Решение о том, является ли б основой цепочки a\iw, где уб - префикс этой цепочки, принимается только по цепочке б, m символам слева от 6 и п символам справа от б.

(3) В качестве основы из кандидатур, предложенных в (2), выбирается самая левая подцепочка, расположенная справа от самого правого нетерминала цепочки aJw или включающая его.

Для удобства обозначений будем добавлять к каждой право-выводимой цепочке гп символов $ слева и п символов $ справа. Тогда можно быть уверенным в том, что в расширенной таким образом правовыводимой цепочке всегда найдутся по крайней Мере т символов слева от основы и п символов справа.

является (1, 0)-ОПК-грамматикой. Правовыводимые цепочки (отличные от 5 и 5) имеют вид аАЬс или аЬЧ для лО. Основами могут быть только аАс, Abb и Ь, так что основу любой правовыводимой цепочки можно однозначно определить, просматривая эту цепочку слева направо, пока не встретится цепочка аАс или Abb либо символ 6, слева от которого стоит а. Заметим, что ни один из символов Ь в цепочке Abb не может быть основой, поскольку слева от него стоит А или Ь. С другой стороны, грамматика Gg с правилами

5 -у аАс А~ЬАЬ\Ь

порождает тот же язык, но она даже не LR-грамматика. □ Пример 5.42. Грамматика G с правилами

S-aA\bB Л-ОЛ I 1 В~ОВ\\

является LR (0)-, но не ОПК-грамматикой, так как в правовы-воднмых цепочках qO"1 и 60"1 основой служит 1, но для выяснения того, какое нз правил А \ и В-1 применить для свертки основы, недостаточно знать ограниченное число символов, расположенных непосредственно слева от 1.

Для формального доказательства рассмотрим выводы

$«5$" ; $«0"5$" =Ф, $«60" 1 $*

По определению ОПК-грамматики а-$«аО«, а= у = $«;?0«, рб1 и y--w = x". Тогда а и а оканчиваются одними и теми же т символами О", w и у начинаются п символами $« и но аАуфуВх (А и В соответствуют в ОПК-

определении сами себе).

Грамматика с правилами

-аА \ ЬА 0л1

порождает тот же язык и является (О, 0)-ОПК-грамматикой. □

Условие (3) в определении ОПК-грамматики может сначала Показаться лишним. Но именно оно гарантирует, что если в пра-вошводимой цепочке а\Ьу самой левой подцепочкой, совпадающей с правой частью некоторого правила Л-р, является р и

Определение. G = (N, 2, Р, S) называется грамматикой (т, л)-ограниченного правого контекста (ОПК), если из условий

(1) $Si"=Gr aAw=>Gr и

(2) $"5$"=>Gv уВл:=>сгТб = аРу - правые выводы в пополненной грамматике G(Nu{5}, 2, PU{S-S}, S),

(3) \х\\у1

(4) последние т символов цепочек а и а, а также первые п символов цепочек w н у совпадают

вытекает, что аАу=уВх, т.е. а = у, А=В и ух.

Грамматика называется ОТЖ-грамматикой, если она является (т, п)-ОПК-грамматикой для некоторых тип.

Если мы считаем вывод (2) „настоящим", а (1) рассматриваем как возможную причину недоразумения, то условие (3) гарантирует, что левее „настоящей" основы б не встретится подцепочки, которую можно было бы принять за основу ф, окруженную последними пг символами цепочки а и первыми п символами цепочки W). Следовательно, в качестве основы можно выбирать самую левую цепочку, которая „выглядит как основа". Условие (4) гарантирует, что решение о том, является ли цепочка основой, можно принять, привлекая лишь т символов левого контекста и п символов правого контекста.

Как и для LR (й)-грамматик, пополненная грамматика включается в определение только на гот случай, когда S встречается в правой части какого-нибудь правила. Например, грамматика G с двумя правилами

S -i-Sala

без оговорки относительно пополненной грамматики была бы (1,0)-ОПК-грамматикой. Но так же, как в примере 5.22, не заглянув на один символ вперед, нельзя решить, как поступить с 5 в правовыводимой цепочке Sa. Поэтому мы не хотим считать G (1,0)-ОПК-грамматикой.

В дальнейшем мы докажем, что каждая (пг, /г)-ОПК-грамма-тика является ЕК{/г)-грамматикой. Но не для каждой LR (0)-грамматики найдутся такие числа т и п, чтобы она была {т, п)-ОПК-грамматикой, потому что LR-определение позволяет, говоря неформально, использовать в ходе разбора для принятия решения весь кусок правовыводимой цепочки слева от основы, а ОПК-определение ограничивает нас т символами. Разумеется, оба определения ограничивают использование части цепочки, расположенной справа от основы.

Пример 5.41. Грамматика G с правилами

S аАс А~уАЬЬ\Ь