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

*5.1.34. Дайте алгоритм построения анализатора по левому участку для произвольной ЬС(й)-грамматики.

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

5.1.35. Найдите преобразования, позволяющие превращать не ЬЬ(/е)-грамматики в эквивалентные ЬГ(1)-грамматики.

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

5.1.36. Напишите программу, которая в качестве входа воспринимает произвольную КС-грамматику G н строит для нее таблицу, управляющую 1-предсказывающим анализатором, если (} ЬЬ(1)-грамматика.

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

5.1.38. Преобразуйте одну из грамматик, описанных в приложении, в эквивалентную ЬГ(1)-грамматику. Затем постройте для этой грамматики ГГ(1)-анализатор.

5.1.39. Напишите программу, проверяющую, является ли данная грамматика ГГ(1)-грамматикой.

Пусть Л1 -управляющая таблица для ЬГ(1)-грамматики G. Допустим, что мы анализируем входную цепочку и анализатор достиг конфигурации (ах, Ха, л). Если М{Х, а) = ошибка, то нам хотелось бы объявить о том, что в данной позиции входной цепочки встретилась ощибка, и перейти к процедуре исправления ошибок, изменяющей содержимое магазина и входной ленты так, чтобы можно было нормально продолжать разбор. Среди стратегий исправления ошибок возможны такие:

(1) Устранить а и попытаться продолжать разбор.

(2) Заменить а таким символом Ь, что М{Х, Ь) ошибка, и продолжать разбор.

(3) Вставить перед символом а во входной цепочке такой символ Ь, что M(X, Ь) ошибка, и продолжать разбор. Этим приемом надо пользоваться осторожно, так как легко впасть в бесконечный цикл.

(4) Читать далее входную цепочку, пока не обнаружится некоторый выделенный входной символ Ь. Выбрасывать из магазина символы до тех пор, пока не обнаружится такой символ X, что Х=:>*Ьр для некоторой цепочки р. Затем продолжить нормальный разбор.

А-ожно также для каждой пары (X, а), для которой НХ, (7)= ошибка, перечислить несколько возможных приемов исправления ошибки, начиная с наиболее обещающих из них. Вполне возможно, что в некоторых ситуациях наиболее разум-

\-{ау, BIS,A]>[S,B]$, 5643)

1- {а>, а [В, В] [S, Л]> [S, В] $, 56436)

НО, [B,B][S,A]>[S,B]$, 56436)

ЬО, [5,Л]>[5, В]$, 56436)

НО, [5. 5]>[5, 564362)

НО. > IS,B]$, 564362)

\-{е, [S,B]$, 564362)

Н(е. [S, Л]$, 5643624)

hie, [5, 5]$, 56436242)

Н{е, $, 56436242)

Читатель может легко проверить, что 56436242-действительно разбор но левому участку цепочки <aw(2>. □

*5.1.27. Покажите, что грамматика с правилами

S-A\B А-аАЬ\0 В~аВЬЬ\1

не является ЬС(й)-грамматикой ни для какого k. *5.1.28. Покажите, что грамматика

Е~Е + Т\Т

FP]F\P Р-{Е)\а

является ЬС(1)-грамматикой.

5.1.29. Постройте анализатор по левому участку для грамматики из упр. 5.1.28.

**5.1.30. Дайте алгоритм, проверяющий, является ли произвольная грамматика ЬС(1)-грамматикой.

**5.1.31. Покажите, что каждая ЬЬ(й)-грамматика является ЬС(А)-грамматикой.

5.1.32. Приведите пример ЬС(1)-грамматики, которая не является LL-грамматикой.

**5.1.33. Покажите, что если к грамматике G применяется алгоритм 2.14 для преобразования ее к нормальной форме Грейбах, то в результате получится грамматика, которая будет LL{k)-грамматикой тогда и только тогда, когда G -ГС(й)-грамматика. Следовательно, класс LC-языков совпадает с классом LL-язы- ков.



) А также независимо от этих авторов Фуксмаиом [1968], назвавшим эти грамматики разделенными.- Прим. перев.

) Классы грамматик, ориентированные на безвозвратный нисходящий анализ и обобн;аюп1,ие класс ТЬ(й)-грамматик, изучаются в работах Яжабека и Кравчика [1975], Нийхольта [1976], Непомнящей [1976], Анисимова [1974а, б], Никитченко и Шкнльняк [1975] и Шевченко [1974]. В последпнх четырех работах проблема разбора рассматривается в рамках некоторой общей схемы управления анализом, нредложениой Редько [1970]. Особого внимания заслуживают методы разбора „по текуИ1,ему символу", к которым относится алгоритм анализа для ТТ(1)-грамматик. П{}-виднмому, первый метод такого рода разработан Конвэем [1953]. Затем (кроме работ Кореньяка и Хопкрофтз [1966], Льюиса и Стирнза [1968]) следует упомянуть работы Фостера [1968. I970J, Вуда 11969], Вельбицкого и Ющснко [1970], Вельбицкого [1973. Фу маиа ([1976] и [Основы разработки трансляторов, 1974]), Комора [1972], Ахо н др. [1975], Кауфмана [1976] (см. дополнение переводчика к этому разделу).- Прим. перев.

ной символ. Рассмотрим несколько иной подход, который является естественным обобщением алгоритма разбора, соответствующего разделенной (т.е. простой LL(l)-j грамматике. Для разделенной грамматики шаг предсказания максимально прост: если а-текущий входной символ, А - верхний символ магазина и в грамматике есть правило А~аа, то в магазине надо заменить Л на а и сдвинуть входную головку. Идея обобщения такова. К Л-правилам разделенной грамматики разрешается добавить е-правило Л-е, а на шаге предсказания для текущих символов а я А разрешается применить правило А-е (т. е. удалить Л из магазина), если в грамматике нет правила вида А-аа. Классы грамматик, для которых работает такой метод разбора, изучались в работах Фуксмана (Ссновы разработки трансляторов, 1974] и [19761), Комора [19721, Кауфмана [1976], Ахо и др. [1975].

Определение. КС-грамматика G = (N, 2, Р, S) называется грамматикой в слабой нормальной форме Грейбах, если каждое правило из Р имеет вид Л-аа, где а 2, а N*, или Л- Если к тому же у нее правые части правил вида А-аа и Л--Ьр начинаются разными символами, т. е. афЬ, то она называется псевдоразделенной.

Для псевдоразделенной грамматики G = (N, Р, S) определим соответствующий простой h\U-распознаватель Mq={X, N, 6,5), у которого 2 и {$} -входной алфавит ($2), N-магазинный алфавит, S-начальный символ магазина и б-функция, отображающая (2u{$))xN в N*xiO, 1} (она описывает один такт его работы). Функция б задается равенствами

(1) б (а, А)={а, 1) тогда и только тогда, когда правило А-аа принадлежит Р;

(2) 6(7, Л) = (е, 0) тогда и только тогда, когда А-е принадлежит Р и в Р нет правила вида ЛЬр.

В парах («, 1) и (е, 0) вторая компонента указывает соответственно на наличие сдвига входной головки и его отсутствие. Для всех wl" и yN* положим {aw$, Ay) + {w$, ay) в случае (1) и (bw$, Ay)\-(bw$, у) в случае (2). Кроме того, если в равенстве (2) fo-S, положим (S, Лу)[--($, у). Языком L{Ma), распознаваемым Mq, назовем множество {dz; 2* (dz;$, 5) [-* ($, е)\.

Заметим, что если wL{Mq), то для цепочки w вычисление Mq соответствует ее левому выводу в G и w£L{G), т. е. (g)sL(G). Но не обязательно L{Mo)L{G).

Пример 1. Пусть - псевдоразделенная грамматика с правилами

S~aSA\e A~a\b

НЫЙ образ действий заключается во вставке символа, тогда как в других случаях более вероятно, что к успеху приведет устранение или изменение символа.

5.1.40. Разработайте алгоритм исправления ошибок для ЬЬ(1)-анализатора, 1Юстроенного в упр. 5.1.38.

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

LL(fe)-rpaMMaTHKH были впсрсые определены Льюисом и Стирнзом [1968]. В ранней версии их работы эти грамматики иазыпалнсь ТО()-грамматиками (по первым буквам слов lop-down-сверху вниз). Простые LL( 1)-грамматики впервые исследованы Корсньяком и Хопкрофтом [1966], которые называли их S-грамматиками ).

Теория LL(fe)-rpaMMaTHK была в значительной степени развита Розенкран-цем и Стирнзом [1970], в их статье можно иайти решения ysip. 5.1.21-5.1.24. ТЬ(Л)-грамматики и другие варианты грамматик, ориентированных на детерминированный нисходящий разбор, рассматривались Кнутом [1967], Курки-Суопио [19691, Вудом [1969а, 1970] и Чуликом [196812).

Льюис, Стирнз н Розенкранц построили компиляторы для Алгола и Фортрана, в которых иа этапе синтаксического анализа используется ТЦ1)-анали-затор. Подробности о компиляторе для Алгола можую найти в статье Льюиса и Розенкранца [1971], в ней также содержится LL( 1)-грамматика для Алгола 60.

ТС(;)-грамматики были впервые определены Розенкранцем и. Льюисом [1970], в их статье можно иайти ключ к упр. 5.1.27-5.1.34.

ДОПОЛНЕНИЕ

О МЕТОДАХ РАЗБОРА „ПО ТЕКУЩЕМУ СИМВОЛУ"

В. и. Агафонов

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



Упр. 4. Покажите, что 2-слаборазделенная грамматика является слаборазделенной.

Упр. S. Покажите, что 1-слаборазделенная грамматика является LL (1)-грамматикой.

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

Упр. 7. Покажите, что существует 2-слаборазделенная грамматика, которая не является 1-слаборазделенной. Указание. Рассмотрите грамматику G из примера 2.

Упр. 8. Постройте алгоритмы, проверяющие, является ли КС-грамматика G

(а) Гслаборазделенной,

(б) 2-слаборазделенной.

**Упр. 9. Покажите, что

(а) существует детерминированный язык, который не является слаборазделенным,

(б) существует слаборазделенный язык, который не является 2-слаборазделенным,

(в) существует 2-слаборазделенный язык, который не является 1-слаборазделенным (т. е. LL (1)-языком в силу упр. 5 и 6).

В работах Вельбицкого и Ющенко [1970] и Вельбицкого [1973] определены два метаязыка, предназначенные для описания детерминированных распознавателей, использующих один или несколько магазинов (они названы соответственно СМ- и R-мета-языком, причем второй язык является некоторым уточнением и развитием первого). Ограничиваясь случаем одного магазина, мы определим здесь метаязык (назовем его CMR-метаязыком), охватывающий основные черты этих формализмов.

Программа распознавателя, записанная на CMR-метаязыке, состоит из команд, роль которых аналогична роли команд ДМП-автомата (если 8 {q, а, Z) = {д, у) интерпретировать как Команду) или операторов метаязыка Флойда-Эванса (разд. 5.4.4). Задаются конечный алфавит состояний К (он же будет магазинным алфавитом), входной, или терминальный, алфавит 2, и каждая команда записывается в виде

ft--й->-Х

где kK, й2и{е}, у € К*, XeK\j{lx} (причем }хК) и 1Г,.- ооозначение операции, выполняемой командой над конфигурацией распознавателя. Конфигурация- имеет вид (ft, w, а), где Е К-состояние распознавателя, 2*-необработанная часть

Тогда Ма,=-({а, Ь}, {S, А], Ь, S), где

б(а, S) = {SA, 1) б(Ь, 5)-(, 0) б($, = 0) Ь{а, А) = {е, 1) 8{Ь,А)~{е, 1)

Легко убедиться, что L (G) = п> О, х{а, Ь}*, = н L(MG) = {fi)U{a"byn>l, Ь}*, у=-п-1}. Для цепочки

аа распознаватель Mq сделает последовательность тактов

[{аа$, 5Л) Ь ($. 5ЛЛ)1-($, АА)

Сравним эту последовательность с левым выводом цепочки аа в грамматике G:

S =Ф( aSA аА

Если L{Mq)=L(G), то распознаватель УИ распознает в точности язык L (G), т. е. он, так сказать, адекватен грамматике G и, если снабдить его выходом, станет анализатором для G, будет строить левые выводы всех цепочек из L{G). □

Определение. Псевдоразделенная грамматика G называется слаборазделенной, если L(G) = L{Mq) для соответствующего простого МП-распознавателя Мд.

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

SaSA\e А -Ь\е

слаборазделенная и LiG) \a"b\0kn}. □

Упр. 1. Для произвольной КС-грамматики G постройте эквивалентную ей грамматику G в слабой нормальной форме Грейбах.

Упр. 2. Для простого МП-распознавателя М» соответствующего псевдоразделенной грамматике G, постройте такой ДМП-автомат М, что L{M) = L{Mq)?p.

**Упр. 3. Докажите, что не существует алгоритма, распознающего по произвольной КС-трамматике, является ли она слабо-разделенной.

Определение. \-слаборазделенной грамматикой называется псевдоразделенная грамматика G(N, 2, Р, 5), для которой выполняется следующее условие: если Р содержит правила А-е и А-аа, то не существует такого BN (в том числе и В-А), что Р содержит правило В-а, S =*i wAyB6 и у=*е. Если В = А допускается, грамматика G называется 2-слабораэделенной.





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