Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 83
Текст из файла (страница 83)
Здесь А распознает левые участки снизу вверх. Заметим, что А — либо 5, либо левый уча. сток некоторого правила, так что в какой-то момент разбора А будет целью. (б) Если а не начинается нетермнналом, то Т(А, а) = (и[А, В], 1) для всех А ар( н а Е Н1(5Т,(ауб), таких, что 5 =Фи сиА6 и А =о'Ву.
(2) Т ([А, А], а) = (е, е) для всех А Е 'Р1 и а Е НГКЗТ,(6), таких, что 5=>мсВА6. (3) Т(а, а) =выброс для всех аЕХ. (4) Т($, е) =допуск. (5) В остальных случаях Т(Х, а) =ошибка. 404 Пример 5.20. Рассмотрим грамматику 6 с правилами (1) 5 — 5+ А (2) 5 — Л (3) Л- АВВ (4) А- В (5)  — <5> (6)  — а 6 является 1.С(1)-грамматикой, причем это фактически грамматика 6„, слегка измененная.
Таблица, управляющая разбором Во левому участку для гралсматики 6, приведена на рис. 5.8, Анаааанняан« Ваяв«асуеиасван шмван ( З Ф м е 18, Я )Н,'4) (в,в) (л,м] (л, ) гВА В) а Рис, В.З. Таблица, уиравлякяцая разбором ео левому у.астку для грамматики б. Анализатор„управляемый этой таблицей, для входной цепочки (а«а> проделает такую последовательность тактов: ((а «-а>, 55, е) ) — <а и а>, <5> [5, В] 5, 5) ',-- (а «.а>, 5> [5, В] $, 5) ) — (а в >, а [5 „В]> [5, В] $, 56) ) — («. а>, [5, В]> [5, В] $, 56) ) — (и а>, [5, А]> [5, В] $, 564) ) — (ма>, «В[5, А]>[5, В]$', 5643) 405 упглжнения « — (е, [5, В]$, 564362) «-(в, [Я, Л]5, 5643624) « — (в, Я, З]$, 56436242) «- ( , 56436242) в, 3 407 гл.
ю однопооходныи синтлксичвскин лиллиз ввз возвглтов )-(а>, В[Я, А]>[В, В]$, 5643) « — (а>, а[В, В][Я, А]>[В, В]$, 56436) « — (>, [В, В] [3, А]) [В, В] 5, 56436) ) — (>, [В, А]> [Я, В]$, 56436) «-(>, [В, З]>[5, В]8, 564362) «-(», [З, В]5, 564362) Читатель может легко проверить, что 56436242 — действи. тельно разбор по левому участку цепочки (аяа).
() *5.1.27. Покажите„что грамматика с правилами 3 — А)В Л- аАЬ)0  — аВЬЬ ) 1 не является ЕС(й)-грамматикой ни для какого й. "5.1.28. Покажите, что грамматика Е=Е+Т(Т Т Тир(!Р Р Р)Р!. Р— (Е) /а является 1С(!)-грамматикой. 5,1.29. Постройте анализатор по левому участку для грамматики из упр. 5.1.28. *"5.1.30. Дайте алгоритм, проверяющий, является ли произвольная грамматика ЕС(1).грамматикой.
""5.1.31. Покажите, что каждая 11.(я)-грамматика является ЕС(й)-грамматикой. 5.1.32. Приведите пример ЕС(1)-грамматики, которая не является 1Л.-грамматикой. **5.1.33. Покажите, что если к грамматике 6 применяется алгоритм 2.14 для преобразования ее к нормальной форме Грей бах, то в результате получится грамматика, которая будет 1.1(й). грамматикой тогда и только тогда, когда 6 — ЕС(й)-грамматика. Следовательно, класс ЕС-языков совпадает с классом !.).-язы' ков. *5,1,34.
Дайте алгоритм построения анализатора по левому частку для произвольной 1.С(й).грамматики. )у роблеса для исследования 5,1.35. Найдите преобразования, позволяющие превращать не 1Л (й)-грамматики в эквивалентные 1.1.(1)-грамматики, упражнения на програллирование 5,1,36. Напишите программу, которая в качестве входа воспринимает произвольную КС-грамматику 6 и строит для нее таблицу, управляющую 1-предсказывающим анализатором, если 6 — ЕЕ(!) грамматика 5,1.37.
Напишите программу, которая по входу, состоящему пз управляющей таблицы и цепочки, делает с помощью данной таблицы разбор данной входной цепочки. 5.1.38. Преобразуйте одну из грамматик„о исанных в приложении, в эквивалентную 1Л.(1)-грамматику. Затем постройте для этой грамматики ЕЕ(!)-анализатор. 5.1.39. Напишите программу, проверяющую, является ли данная грамматика ЕЕ(1)-грамматикой. Пусть М вЂ” управляющая таблипа для 1.).(!)-грамматики 6. Допустим, что мы анализируем входную цепочку и анализатор достиг конфигурации (ах, Ха, и). Если М(Х, а) — ошибка, то нам хотелось бы объявить о том, что в данной позиции входной цепочки встретилась ошибка, и перейти к процедуре исправления ошибок, изменяющей содержимое магазина н входной ленты так, чтобы можно было нормально продолжать разбор.
Среди стратегий исправления ошибок возможны такие: (1) Устранить а н попытаться продолжать разбор. (2) Заменить а таким символом Ь, что М(Х, Ь)~ошибка, и продолжать разбор. (3) Вставить перед символом а во входной цепочке такой символ Ь, что М(Х, Ь)~ошибка, и продолжать разбор. Этим приемом надо пользоваться осторожно, так как легко впасть в бесконечный цикл. (4) Читать далее входную цепочку, пока не обнаружится некоторый выделенный входной символ Ь. Выбрасывать из магазина символы до тех пор, пока не обнаружится такой символ Х, что Х=>'Ь6 для некоторой цепочки р. Затем продолжить норМальный разбор. Можно также для каждой пары (Х, а), для которой (Х, а) =ошибка, перечислить несколько возможных приемов "справления ошибки, начиная с наиболее обещающих из них.
В~олпе возможно, что в некоторых ситуациях наиболее разум- ГЛ. В ОДНОПРОХОДНЫЙ СИНТАКСИЧЕСКИЙ АНАЛИЗ ВЕЗ ВОЗВРАТОВ ный образ действий заключается во вставке символа, тогда как в других случаях более вероятно, что к успеху приведет устранение или изменение символа. 5.1,40.
Разработайте алгоритм исправления ошибок для ].[.(1)-анализатора, построенного в упр. 5.1.38. Замечания по литературе ь1(й)-грамматики были впервые определены Льюисом и Стирнзом [1968(, В ранней версии их работы зги грамматики иззыаалнсь ТР(й)-грамматикамн (по верным буквам слов !ор.багги — сверху вниз). Простые ьЦ1)-грамматики впервые исследованы Корсньяком н Хопкрофтом [1966], которые называли их о-грамматиками т). Теория ].[.[А)-грамматик была в значительной степсни развита Розенкрзн. цем и Стирнзом [1970), в их статье можно найти решения уцр.
6.1,21 — 5.1.21, !.!.[А]-грамматики и другие варианты грамматик, ориентированных па детерминированный нисходящий разбор, рассмзтривались Кнутом [1967], КуркнСуопно [1969], Вудом [1969а, 1970[ и Чудиком [!968] '). Льюис, Стирнз и Розенкранц построили компиляторы для Алгола и Фортрана, в которых иа этапе синтаксического анализа используется ].1[1)-анализатор. Подробности о компиляторе для Алгола можно найти в статье Льюиса и Розенкранца [1971], в ней также содержится 11[!)-грамматика длн Алгола 60. ].С[1)-грамматики были впервые определены Розенкранцем и Льюисом [1970], в их статье можно найти ключ к упр.
5.1.27 — б. !.84. ДОПОЛНЕНИЕ О МЕТОДАХ РАЗВОРА „ПО ТЕКУЩЕМУ СИМВОЛУ" В. Н. Агафонов В равд. 2.5.3 был описан педетермннированный предсказывающий алгоритм разбора для пронзвольных КС-грамматик. Введение понятия ].1(!)-грамматики — это один из возможных способов наложить на грамматику такие условия, чтобы шаг предсказания очередного, правила вывода можно было сделать детерминированным, используя для этого только текущий вход- т) А также независимо от этих авторов Фуксманом [1968], иазвавщщ! эти грамматики ргизделенными — Прин.
лерга. ') Классы грамматик, ориентированные на безвозвратный нисходящей анализ и обобщающие класс 1.ь(й)-грамматик, изучаются в работак Яжабехз и Кравчика [1976], Ни»хольта [1976[, Непомнящей [!976], Анисимова ]1974а, б), Никитченко и Шкильняк [197Б] и Шевченко [1974]. В последний четырех работах проблема разбора рассматривается в рамках некоторой общей схемы управления анализом, предложенной Редько ]1970]. Особого внимания заслуживают методы разбора „по текущему символу", к которым относится алгоритм анализа для ь1(1)-грамматик.
По-видимому, первый метод такого рода разработан Конвэем [!9»З!. Затем (кроме работ Кореньяна и Хопкрофта [1966], Льюиса и Стнрнза ]19»8]) следует упомянуть работы Фостера [!968. 1970], Вуда (!969], Вельбицкого и !Оп!сикс 11970], Вельбицкого 1!973(, Фукс мзпа [(1976] н (Основы разработки трансляторов, !974]), камора [!972], Ато н др. [1975], Кауфмана 1!976] (см. дополнение переводчика к этому разделу)— Прим.
перев. ДОПОЛНЕНИЕ символ. Рассмотрим несколько иной подход, который явяется естественным обобщением алгоритма разбора, соответствующего разделенной (т. е, простой 1.[ (1)-) грамматике. Для разделенной грамматики шаг предсказания максимально прост: если а — текущни входной символ, А — верхний символ магазина и в грамматике есть правило А-- ая, то в магазине надо зацепить А на сс и сдвинуть входную головку. Иден обобщения такова. К Л-правилам разделенной грамматики разрешается добавить е-правило А е, а на шаге предсказания для текущих символов а и А разрешается применить правило А — не (т.
е. удалить А нз магазина), если в грамматике нет правила вида А — ая. Классы грамматик, для которых работает такой метод разбора, изучались в работах Фуксмана ([Основы разработки трансляторов, ]974[ и [1976]), Комора []972(, Кауфмана (1976~, Ахо и др. (1975!. Определение. КС-грамматика 6 = (]А], Х, Р, 5) называется грамматикой в слабой нормальной форме Грейбах, если каждое правило из Р имеет вид А — ая, где яЕХ, яЕ ]ч]*, или А — е. Если к тому же у нее правые части правил вида А — ая и Л вЂ” Ь(! начинаются разными символами, т. е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
