А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 72
Текст из файла (страница 72)
збй Глава 4. Синтаксический анализ Восстановление на уровне фразы реализуется путем проверки каждой ошибочной записи в таблице 1 К-анализа и принятия решения (на основе знания особенностей языка) о том, какая наиболее вероятная ошибка программиста могла привести к данной ситуации. После этого можно построить подходящую процедуру восстановления после ошибки; возможно, при этом придется изменить вершину стека и!или первые символы входного потока способом, соответствующим данной записи ошибки. При разработке специализированных подпрограмм обработки ошибок для ).йсинтаксического анализатора можно заполнить каждую пустую запись таблицы действия указателем на подпрограмму, которая будет выполнять действия, выбранные для данного конкретного случая разработчиком компилятора.
Эти действия могут включать вставку символов в стек или входной поток (или и туда, н туда) и удаление их оттуда или изменение и перестановку входных символов. Выбор должен делаться таким образом, чтобы исключить возможность зацикливания 1.канализатора.
Безопасная стратегия должна гарантированно удалять или псреносить при каждом цикле по крайней мере один символ из входного потока нли при достижении его конца гарантированно уменьшать стек на каждой итерации. Снятия со стека состояния над нетерминалом следует избегать, поскольку такое изменение удаляет из стека успешно разобранную конструкцию. Пример 4.51.
Обратимся еще раз к грамматике выражений Е- Е+Е)Е~Е((Е) ~Ы На рис. 4.53 показана таблица ).Гх-анализа для этой грамматики, представляющая собой дополненную программами обработки ошибок таблицу нз рис. 4.49. Для каждого состояния, вызывающего свертку при том или ином входном символе, все записи ошибок заменены записями некоторых сверток. Такая замена приводит к отложенному обнаружению ошибок после выполнения одной или нескольких лишних сверток; ошибка в любом случае будет найдена до выполнения первого переноса.
Оставшиеся пустыми ячейки заполнены указателями на подпрограммы обработки ошибок. Далее приведены описания подпрограмм обработки ошибок. е1: Эта подпрограмма вызывается из состояний О, 2, 4 и 5; все они ожидают начало операнда — Ы или левую скобку. Вместо этого обнаруживается оператор + илн * либо окончание входного потока. Поместить в стек состояние 3 (переход из состояний О, 2, 4 и 5 прн входном символе Ы). Вывести сообщение "Отсутствует операнд". 361 4.8. Использование неоднозначных грамматик Рнс.
4.53. Таблица 1.К-анализа с программами обработки ошибок е2: Эта подпрограмма вызывается из состояний О, 1, 2, 4 и 5 при обнаружении правой скобки. Удалить правую скобку из входного потока. Вывести сообщение "Несбалансированная правая скобка". ез: Эта подпрограмма вызывается из состояний ! и 6, когда ожидается оператор, а обнаруживается Ы или правая скобка. Поместить в стек состояние 4 (соответствующее символу +). Вывести сообщение "Отсутствует оператор". е4: Эта подпрограмма вызывается из состояния 6 при обнаружении конца входного потока Поместить в стек состояние 9 (для правой скобки). Вынести сообщение "Отсутствует правая скобка". Для ошибочной входной строки Ы+) последовательность конфигураций синтаксического анализатора показана на рис.
4.54. а 4.8.4 Упражнения к разделу 4.8 ! Упражнение 4.8.1. Ниже приведена неоднозначная грамматика для выражений с и бинарными инфикснымн операторами и и, различными уровнями приоритетов: 362 Глава 4. Синтаксический анализ Рвс.
4.54. Анализ и восстановление после ошибок в ЬК-анализаторе а) Что собой представляют Я.К-множества пунктов для этой грамматики как функция от п? б) Как бы вы разрешили конфликты Я.В.-пунктов, если все операторы лево- ассоциативны, а приоритет оператора 01 выше приоритета оператора Ог, который, в свою очередь, выше приоритета 0з, и т.д.? в) Приведите таблицу Я.К-анализа, получающуюся в результате решения ча- сти б данного упражнения.
г) Повторите части а и в для однозначной грамматики, которая определяет то же множество выражений и показана на рис. 4.55. д) Подсчитайте и сравните количества множеств пунктов и размеры таблиц для однозначной и неоднозначной грамматик. Что говорит это сравнение об использовании неоднозначных грамматик выражений? Е1 — Е1 0 Ег ! Ег Ег — Ег 0п з Ез !Ез Еп — ~ Еп дз Еп-ьз ~ Епьз Е„ьз — (Ег) ! Ы Рис.
4.55. Однозначная грамматика для п операторов 363 4.9. Генераторы синтаксических анализаторов ! Упражнение 4.8.2. На рис. 4.56 представлена грамматика для ряда инструкций, похожая на грамматику из упражнения 4.4.12. Здесь, как и ранее, е и а — терминалы, обозначающие соответственно условные выражения и "иные инструкции". а) Постройте таблицу !.К-анализа для данной грамматики с разрешением конфликтов обычным для "висящего е1зе** способом.
б) Реализуйте исправление ошибок путем заполнения пустых записей таблицы синтаксического анализа дополнительными свертками или подходящими подпрограммами восстановления после ошибок. в) Покажите, как будет вести себя ваш синтаксический анализатор для следующих входных строк; 1) !!' е тйеп в; 1Г е гйеп в епп й) зкЫ!е е по Ьеп!п а; !Г е бйеп а; епп' зплг — 1Г е бйеп яплг !Г е Гйеп зплг е!ве или н Ы!е е по зплг Ьед!п!Ыг епй — Йкг; залп хллг Рис. 4.56. Грамматика для инструкций некоторых видов 4.9 Генераторы синтаксических анализаторов В зтом разделе будет рассмотрен генератор синтаксических анализаторов, используемый для облегчения построения начальной фазы компилятора. Мы обратимся к генератору ЬА!.В.-анализаторов уасс, поскольку он реализует многие концепции из числа рассмотренных в двух предыдущих разделах и широко распространен.
Название Хасс означает "Уе! апогйег согпр11ег-сошр11ег" (еще один компилятор компиляторов), что отражает популярность генераторов синтаксических анализаторов в начале 1970-х годов, когда С. Джонсоном (Я.С. Зойпзоп) была создана первая версия хасс. Этот генератор доступен в качестве команды в !)Ы!Х и использовался при разработке многих промышленных компиляторов. 364 Глава 4. Синтаксический анализ 4.9.1 Генератор синтаксических анализаторов Тасс Создание транслятора с использованием Хасс схематично показано на рис.
4.57. Вначале создается файл, скажем, Ьгапв1аее. у, содержащий Хасс- спецификацию разрабатываемого транслятора. Команда (ЛкПХ уасс Ьгапв1асе.у преобразует файл Ьгапв1асе . у в программу у. ЬаЪ. с на языке С с использованием ЕАЕК-метода, описанного в алгоритме 4.63. Программа у. ЬаЬ. с является синтаксическим ЕА( й-анализатором, написанным на языке С и объединенным с другими подпрограммами на языке С, которые могут быть подготовлены пользователем. Таблица ЕА(.а-анализа уплотнена с помощью технологии, описанной в разделе 4.7. Путем компиляции у.
ЬаЬ . с вместе с библиотекой 1у, содержащей программу ЕК-анализа, с использованием команды сс у.саЬ.с -1у мы получим требуемую объектную программу а. оцт., которая выполняет транс- ляцию, определенную исходной программой Хасс(~. Если необходимы другие процедуры, они могут быть скомпилированы или загружены вместе с у. ЬаЬ. с точно так же, как и с любой другой программой на языке С.
Спецификация уаее ехаяе(аке.у у.еаЬ.с у.еаЬ.с а.еце Вход Выход Рис. 4.57. Создание транслятора с помощью Хасс Исходная Хасс-программа состоит из трех частей: Объявления ЪЪ Правила трансляции ЪЪ С-подпрограммы поддержки и Имя библиотеки (указанное параметром -1у) системно зависимо (т.е. может быть разным в разных системах) 365 4.9. Генераторы синтаксических анализаторов Пример 4.52. Чтобы проиллюстрировать подготовку Хасс-программы, построим простой калькулятор, ко~орый считывает арифметические выражения, вычисляет их и выводит соответствующие числовые значения. Построение калькулятора начнем со следующей грамматики для арифметических выражений: Š— Е+Т)Т Т вЂ” Т*Е)ŠŠ— (Е) ! 618й Токен й18й представляет отдельную цифру от 0 до 9.
Хасс-калькулятор на основе этой грамматики показан на рис. 4.58. Б Часть объявлений В Хасс-программе имеется два необязательных раздела объявлений. В первом размещаются обычные объявления С, ограниченные Ъ ( и Ъ ) . Здесь мы помещаем объявления временных переменных, используемых правилами трансляции или процедурами второй и третьей частей. На рис. 4.58 этот раздел содержит только директиву йфпс1ибе <стуре.
Ь> Она заставляет препроцессор С включить стандартный заголовочный файл <ссуре. Ь>, содержащий описание предиката 1вЖдфс. В части объявлений находятся также объявления токенов грамматики. На рис. 4.58 инструкция Ъсохеп Р161Т объявляет токен Р161Т. Токены, объявленные в этом разделе, могут использоваться во второй и третьей частях спецификации Хасс. Если для создания лексического анализатора, передающего токены Хасс, использовался Рех, эти объявления токенов делаются доступными и для этого лексического анализатора, как говорилось в разделе 3.5.2. Часть правил трансляции В этой части спецификации Хасс после первой пары %% мы размещаем правила трансляции.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
