А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 51
Текст из файла (страница 51)
Синтаксический анализ семантические ошибки, такие как несоответствие типов. Однако в общем случае точное определение семантических и логических ошибок во время компиляции является крайне трудной задачей. Обработчик ошибок синтаксического анализатора имеет очень просто формулируемые, но очень сложно реализуемые цели: ° он должен ясно и точно сообщать о наличии ошибок; ° он должен обеспечивать быстрое восстановление после ошибки, чтобы продолжить поиск других ошибок; ° он не должен существенно замедлять обработку корректной программы. К счастью, обычные ошибки достаточно просты, и для их обработки часто достаточно относительно простых механизмов обработки ошибок. Каким образом обработчик ошибок должен сообщить об обнаруженных неприятностях? Самое меньшее, что он должен сделать, — указать место в исходной программе, где выявлена ошибка, поскольку, скорее всего, реальная ошибка находится несколькими токенами ранее.
Распространенная стратегия заключается в том, чтобы вывести проблемную строку с указателем позиции, в которой обнаружена ошибка. 4.1.4 Стратегии восстановления после ошибок После того как ошибка обнаружена, каким образом должно выполниться восстановление синтаксического анализатора? Хотя универсальной стратегии не существует, все же несколько методов применяются чаще других. Простейший подход состоит в том, что синтаксический анализатор завершает работу при первой же обнаруженной ошибке, выводя о ней информативное сообщение.
Если же синтаксический анализатор может восстановить некоторым образом свое состояние до такого, когда работа может быть продолжена, то имеется определенная надежда на то, что будут обнаружены и другие ошибки, а также что информация о них окажется достаточно корректной. Если же восстановление не совсем корректное и количество обнаруженных ошибок растет, как снежный ком, то будет лучше, если юмпилятор после некоторого предельного количества ошибок прекратит вывод раздражающих сообщений об этих "фальшивых" ошибках.
Этот раздел посвящен следующим стратегиям восстановления: режим паники, уровень фразы, продукции ошибок и глобальная юррекция. Восстановление в режиме паники В этом случае при обнаружении ошибки синтаксический анализатор пропускает входные символы по одному, пока не будет найден один из специально 4.!. Введение 257 определенного множества синхронизирующих токенов. Обычно такими токенами являются разделители, такие как; или ), роль которых в исходной программе совершенно очевидна и недвусмысленна.
Разработчик компилятора, естественно, должен выбирать синхронизирующие токены, исходя из особенностей исходного языка. Хотя в ходе такой коррекции часто значительное количество символов пропускается без проверки на наличие дополнительных ошибок, ее преимуществом является простота; кроме того, в отличие от некоторых методов, рассматриваемых ниже, она гарантирует отсутствие зацикливания. Восстановление на уровне фразы При обнаружении ошибки синтаксический анализатор может выполнить локальную коррекцию оставшегося входного потока, т.е. он может заменить префикс остальной части потока некоторой строкой, которая позволит синтаксическому анализатору продолжить работу.
Типичная локальная коррекция может состоять в замене запятой точкой с запятой, удалении лишней точки с запятой или вставке недостающей. Выбор способа локальной коррекции — прерогатива разработчика компилятора. Естественно, следует быть предельно осторожным при выборе способа коррекции, чтобы он не привел, например, к бесконечному циклу (что возможно при вставке некоторого символа перед текущим сканируемым). Замена на уровне фразы используется в некоторых компиляторах с восстановлением после ошибки и может скорректировать любую входную строку. Главным недостатком этого метода являются сложности, с которыми приходится сталкиваться в ситуациях, когда реальная ошибка произошла до точки ее обнаружения.
Продукции ошибок Знание наиболее распространенных ошибок позволяет расширить грамматику языка продукциями, порождающими ошибочные конструкции. Синтаксический анализатор, построенный на основе такой расширенной продукциями ошибок грамматики языка, обнаруживает ошибку при использовании "ошибочной" продукции. Таким образом, он может сгенерировать корректное диагностическое сообщение для распознанной во входном потоке ошибки. Глобальная коррекция В идеальном случае при обработке некорректной входной строки компилятор должен вносить минимально возможное количество изменений. Существует ряд алгоритмов, которые позволяют выбрать минимальную последовательность вносимых изменений для проведения коррекции.
По заданной некорректной строке я и грамматике С такие алгоритмы находят дерево разбора для строки у, такой, что количество вставок, удалений и изменений токенов, требуемых для преобразования х в у, минимально возможное. К сожалению эти методы в общем случае слишком дорогостоящи для применения в компиляторах в силу высоких требо- 258 Глава 4. Синтаксический анализ ваний к памяти и времени работы, а потому представляют в настоящее время, в основном, теоретический интерес. Следует заметить, что ближайшая к исходной исправленная программа может оказаться вовсе не тем, что хотел получить программист.
Тем не менее понятие минимальной коррекции дает нам критерий оценки качества различных технологий восстановления после ошибок и используется для поиска оптимальной замены строки при восстановлении на уровне фразы. 4.2 Контекстно-свободные грамматики Грамматики были введены в разделе 2.2 для систематического описания конструкций языка программирования наподобие выражений или инструкций. Используя синтаксическую переменную з1тг для обозначения инструкций и переменную ехрг для обозначения выражений, продукция зплг — И (ехрг) згтт еие згтг (4.4) определяет структуру условной инструкции данного вида. Другие продукции затем точно определяют, что могут представлять собой ехрг и згтп В этом разделе рассматривается определение контекстно-свободных грамматик и вводится терминология, используемая при рассмотрении синтаксического анализа.
В частности, понятие порождения очень полезно при рассмотрении порядка применения продукций в процессе разбора. 4.2.1 Формальное определение контекстно-свободной грамматики Из раздела 2.2 мы знаем, что контекстно-свободная грамматика (далее для краткости — просто грамматика) состоит из терминалов, нетерминалов, стартового символа и продукций. 1. Терминалы прелставляют собой базовые символы, из которых формируются строки. Термин "имя токена" является синонимом слова "терминал", и мы часто будем использовать слово "токен" для обозначения терминала там, где очевидно, что мы говорим об имени токена.
Мы считаем также, что терминалы являются первыми компонентами токенов, возвращаемых лексическим анализатором, когда мы говорим о грамматиках языков программирования. В (4.4) терминалами являются ключевые слова И и е1ве, а также символы ( и ). 2. Нетерминалы представляют собой синтаксические переменные, которые обозначают множества строк. В (4.4) зттг и ехрг являются нетерминалами. 259 4.2.
Контекстно-свободные грамматики Эти множества строк, обозначаемые нетерминалами, помогают определить язык, порождаемый грамматикой. Нетерминалы также налагают на язык иерархическую структуру, облегчающую синтаксический анализ и транс- ляцию. 3. Один из нетерминалов грамматики считается стартовым символам, и множество строк, которые он обозначает, является языком, определяемым грамматикой. По соглашению продукции стартового символа указываются первыми. 4. Продукции грамматики определяют способ, которым терминалы и нетерминалы могут объединяться для создания строк.
Каждая продукции состоит из следующих частей. а) Нетерминал, именуемый заголовком или левой частью продукции; эта продукция определяет некоторые из строк, обозначаемые заголовком. б) Символ — . Иногда вместо стрелки используется:: =. в) Тело, или правая часть, состоящая из нуля или некоторого количества терминалов и нетерминалов.
Эти компоненты тела описывают один из способов, которым могут быть построены строки нетерминала в заголовке. Пример 4.1. Грамматика на рис. 4.2 определяет простые арифметические выра- жения. В этой грамматике терминальными символами являются Ы+ — */ ( ) Нетерминальными символами являются ехр«еЫоп, ге«т и/асго«, причем ехр«езлоп — стартовый символ грамматики. и ехр«езз/оп — ехр«езз(оп + гепп ехр«еззюп — ехр«еззюп — !е«т ехр«езяоп — гепп ~е«т — ( ехр«еззюп ) — Ы Рнс. 4.2. Грамматика для простых арифметических выражений /асго« /асго« вЂ” ~ гели * ~асго« гепп //асю« /асго« 2бй Глава 4. Синтаксический анализ 4.2.2 Соглашения об обозначениях Для того чтобы избежать постоянного упоминания "это — терминалы", "это— нетерминалы" и т.п., будем использовать следующие соглашения по обозначениям при записи грамматик в оставшейся части книги.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
