А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 59
Текст из файла (страница 59)
Уь) ( Выводим продукцию Х вЂ” УгУз... Уь, Снимаем символ со стека; Помешаем в стек Уь, Уь ы ..,, У~', У! помещается на вершину стека; Устанавливаем Х равным символу на вершине стека; Рнс. 4.20. Алгоритм предикгивного синтаксическою анализа Пример 4.21. Рассмотрим грамматику (4.14); ее таблица синтаксического анализа уже была приведена на рнс. 4.17. Для входной строки И+ и)*И нерекурсивный 294 Глава 4. Синтаксический анализ предиктивный синтаксический анализатор алгоритма 4.20 делает последователь- ность шагов, представленную на рис.
4.21. Эти шаги соответствуют левому по- рождению Е ~ Т Е' ~ Е Т' Е' ~ Ы Т' Е' ~ Ы Е' ~ Ы + Т Е' =~ ьч 1т ьп ьп 1т Ьч Полностью оно показано на рис. 4.12. Соотввтствив Ствк Входнля стгокА Двйствив Вывод Š— Т Е' Вывод Т вЂ” Е Т' Вывод Š— Ы Соответствие Ы Ы Вывод Т' — е Вывод Е'- + ТЕ' Рис. 4.21. Шаги, выполняемые предихтивным синтаксическим анализатором лля входной строки н$ + Ы я Ы Обратите внимание, что сентенциальные формы в этом порождении представляют собой части входного потока, которые уже были проверены на соответствие (приведены в столбце "Соответствие" ) и за которыми следует содержимое стека Часть потока, проверенная на соответствие, показана исключительно для того, чтобы подчеркнуть указанную связь.
По той же причине вершина стека располагается слева; при рассмотрении восходящего синтаксического анализа более естественно располагать вершину стека справа. Указатель входного потока указывает на крайний слева символ строки в столбце "Входная строка". О Ы Ы+ И+ Ы+ Ы+Ы ы+ы Ы+ Ыя н$+ Ы* И+И*И И+И*И И+И*И ЕЬ Т Е'Ь Г Т' Е'3 н$ Т' Е'3 Т' Е'3 Е'Ь + Т Е'3 Т Е'Ь Е Т' Е'Ь Ы Т' Е'3 Т' Е'3 * ЕТ'Е'Ь Г Т' Е'3 Ы Т' Е'3 Т' Е'3 Е'Ь 3 Ы+н$ВЫЬ Ы+Ы*ЫЬ И+И*ИЗ Ы+Ы*ЫЬ +н$ * н$3 +ы*ыЬ +н$ * нИ И*ИЗ Ы*ЫЬ Ы я ЫЬ *нИ ьы3 ЫЬ нИ 3 Ь Ь Соответствие ч- Вывод Т вЂ” Г Т' Вывод Е- Ы Соответствие Ы Вывод Т' — * Е Т' Соответствие * В ДЕ Ы Соответствие н$ ВыВОд Т' — ~ е ВыВОд Е' — ~ е 295 4.4. Нисходящий синтаксический анализ 4.4.5 Восстановление после ошибок в предиктивном синтаксическом анализе Данное рассмотрение восстановления после ошибок ссылается на стек предиктивного синтаксического анализатора, управляемого таблицей анализа, поскольку он явно указывает терминалы и нетерминалы, соответствие которым синтаксический анализатор намеревается найти в оставшейся части входного потока.
Эти методы могут использоваться и при синтаксическом анализе методом рекурсивного спуска. Ошибка в процессе предиктивного синтаксического анализа обнаруживается в тот момент, когда терминал на вершине стека не соответствует очередному входному символу или когда на вершине стека находится нетерминал А, очередной входной символ — а, а ячейка таблицы синтаксического анализа М [А, а) содержит еггог (т.е. данная запись таблицы пуста).
Режим паники Восстановление после ошибки "в режиме паники" основано на пропуске символов из входного потока до тех пор, пока не будет обнаружен токен из предопределенного множества синхронизирующих токенов. Эффективность этого метода зависит от выбора синхронизирующего множества. Эти множества должны выбираться так, чтобы синтаксический анализатор быстро восстанавливался после часто встречающихся на практике ошибок. Вот некоторые эвристические правила.
1. В качестве первого приближения можно поместить в синхронизирующее множество для нетерминала А все символы из множества Е0110%1А). Если пропустить все токены до элемента из Г01 Е0%(А) и снять А со стека, вероятно, удастся продолжить синтаксический анализ. 2. В качестве синхронизирующего множества для А недостаточно использовать РОЙ 0%(А). Например, если инструкция завершается точкой с запятой, как в языке программирования С, то ключевое слово, с которого начинается инструкция, может не оказаться в множестве ГОЕЕ0% нетерминалов, представляющих выражения. Отсутствующая точка с запятой после присвоения может, таким образом, привести к пропуску ключевого слова, с которого начинается новая инструкция.
Зачастую в языке имеется иерархическая структура конструкций; например, выражения появляются в инструкциях, которые находятся в блоках, и т.д. В таком случае к синхронизирующему множеству конструкции нижнего уровня можно добавить символы, с которых начинаются конструкции более высокого уровня. Например, можно добавить ключевые слова, с которых начинаются инструкции, в синхронизирующие множества нетерминалов, порождающих выражения.
29б Глава 4. Синтаксический анализ 3. Если добавить символы из РИБТ (А) в синхронизирующее множество для нетерминала А, станет возможным продолжение анализа в соответствии с А, когда во входном потоке появится символ из множества ЯКУТ (А). 4. Если нетерминал может порождать пустую строку, то в качестве продукции по умолчанию может использоваться продукция, порождающая е. Это может отсрочить обнаружение ошибки, зато не может вызвать ее пропуск и сокращает число нетерминалов, которые должны быть рассмотрены в процессе восстановления после ошибки.
5. Если терминал на вершине стека не может быть сопоставлен с входным символом, то простейший метод состоит в снятии терминала со стека, генерации сообщения о вставке терминала в программу и продолжении синтаксического анализа. По сути, при этом подходе синхронизирующее множество токена состоит из всех остальных токенов. Пример 4.22. Использование символов из множеств ЕОЕЕ0% и НКЯТ в качестве синхронизирующих достаточно неплохо работает при синтаксическом анализе грамматики (4.!4). Таблица синтаксического анализа для этой грамматики, приведенная на рис. 4.17, повторена на рис.
4.22, но здесь значение зулсл в ячейках таблицы указывает синхронизирующие токены, полученные из множества Е01.- Е0% соответствующего нетерминала. Множества ГОП.0% для нетерминалов получены из примера 4.16. Рис. 4.22. Синхронизируюшие токены, добавленные к таблице синтаксического анализа из рис. 4.17 Рис. 4.22 используется следующим образом. Если синтаксический анализатор просматривает ячейку М [А, а] и обнаруживает, что она пуста, то входной символ а пропускается. Если в этой ячейке находится запись зупсл, то нетерминал снимается с вершины стека в попытке продолжить синтаксический анализ.
Если токен на вершине стека не соответствует входному символу, то, как упоминалось выше, мы снимаем его со стека. 297 4.4. Нисходящий синтаксический анализ В случае ошибочного ввода )Ы *+Ы синтаксический анализатор и механизм восстановления после ошибок, представленные на рис. 4.22, ведут себя так, как показано на рис. 4.23. о СТЕК ВХОДНАЯ СТРОКА ПРИМЕЧАНИЕ Ошибка, пропускаем ) Ы Е Р$КЬТ (Е) Ошибка, М ]Г, +] =.вулси Е снимается со стека Е Т' Е'3 Ы Т' Е'Ь Т' ЕЪ 3 Е'$ Рнс. 4.23. Шаги синтаксического анализа н восстановления после ошибок, выполняемые преднхтивным анализатором В приведенном обсуждении метода восстановления после ошибки "в режиме паники" мы не касались важного вопроса — сообщений об ошибках.
Разработчик компилятора должен обеспечить вывод информативных сообщений об обнаруженных ошибках, которые не только описывают ошибку, но и указывают, где именно она обнаружена. Восстановление на уровне фразы Восстановление на уровне фразы реализуется заполнением пустых ячеек в таблице предиктивного синтаксического анализа указателями на подпрограммы обработки ошибок. Эти подпрограммы могут изменять, вставлять или удалять символы входного потока и выводить соответствующие сообщения об ошибках. Кроме того, онн могут снимать элементы со стека. При таком способе восстановления ЕЗ ЕЗ Т Е'3 Е Т' Е'3 Ы Т' Е'3 Т' Е'3 * Е Т' Е'3 Г Т' Е'$ Т' Е'$ Е'3 +ТЕ'$ Т Е'3 )Ы *+ИЗ И *+ЫЗ н$ *+ИЗ и *+ИЗ н$ *+ИЗ *+ ЫЗ х+ н$3 +ИЬ +ЫЗ +ИЬ +ЫЗ ЫЗ 298 Глава 4.
Синтаксический анализ по ряду причин возникают вопросы, следует ли разрешить изменение символов в стеке и размещение в стеке новых символов. Во-первых, после этого шаги, выполняемые синтаксическим анализатором, могут не соответствовать порождению ни одного слова языка вообще.
Во-вторых, следует гарантировать невозможность бесконечного цикла. Проверка того, что каждое действие по восстановлению после ошибки в конечном счете приводит к потреблению очередного входного символа (или к снятию элементов со стека, если достигнут конец входного потока),— хороший способ защиты от зацикливания. 4.4.б Упражнения к разделу 4.4 Упражнение 4.4.1. Разработайте для каждой из приведенных грамматик предиктивный синтаксический анализатор и покажите, какой вид имеют таблицы синтаксического анализа. Перед разработкой синтаксического анализатора при необходимости можно выполнить левую факторизацию и/или устранение левой рекурсии.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
