- •1. Начальные сведения о компиляции
- •1.1 Общие сведения о языке программирования и структуре транслятора.
- •1.2 Модель анализа-синтеза компиляции
- •1.3 Понятие прохода. Однопроходные и многопроходные компиляторы
- •1.4 Фазы компилятора
- •1.5 Управление таблицей символов
- •1.6 Обнаружение ошибок и сообщение о них
- •1.7 Фазы анализа
- •2. Лексический анализ
- •2.1 Назначение лексического анализатора
- •2.2 Атрибуты лексем
- •2.3 Общие принципы построения лексических анализаторов
- •2.4 Определение границ лексем
- •2.5 Выполнение действий, связанных с лексемами
- •2.6 Практическая реализация лексических анализаторов
- •2.7 Лексические ошибки
- •2.8 Способы построения лексических анализаторов
- •3. Определение лексем
- •3.1 Строки и языки
- •3.2 Операции над языками
- •3.3 Регулярные выражения
- •3.4 Регулярные определения
- •3.5 Распознавание лексем и регулярные выражения
- •3.6 Диаграммы переходов
- •Конечные автоматы
- •3.7.1 Недетерминированные конечные автоматы
- •3.7.2 Детерминированный конечный автомат
- •Преобразования нка
- •Построение конечного автомата по регулярной грамматике
- •4. Формальные языки и грамматики
- •4.1 Цепочки символов. Операции над цепочками символов
- •4.2 Понятие языка. Формальное определение языка
- •4.3 Способы задания языков
- •4.4 Синтаксис и семантика языка
- •4.5 Особенности языков программирования
- •4.6 Понятие о грамматике языка
- •4.7 Формальное определение грамматики. Форма Бэкуса-Наура
- •4.8 Принцип рекурсии в правилах грамматики
- •Другие способы задания грамматик
- •4.10 Запись правил грамматик с использованием метасимволов
- •4.11 Запись правил грамматик в графическом виде
- •4.12 Классификация языков и грамматик
- •4.12.1 Классификация грамматик по Хомскому
- •4.12.2 Классификация языков
- •4.12.3 Примеры классификации языков и грамматик
- •4.13 Цепочки вывода. Сентенциальная форма. Вывод. Цепочки вывода
- •4.14 Сентенциальная форма грамматики. Язык, заданный грамматикой
- •4.15 Левосторонний и правосторонний выводы
- •4.16 Дерево вывода. Методы построения дерева вывода
- •5. Синтаксический анализ
- •5.1 Основные принципы работы синтаксического анализатора
- •5.2 Роль синтаксического анализатора
- •5.3 Обработка синтаксических ошибок
- •5.4 Контекстно-свободные грамматики
- •5.5 Порождение
- •Деревья разбора и приведения.
- •Неоднозначность грамматик. Устранение неоднозначности
- •5.8 Устранение левой рекурсии
- •Левая факторизация
- •Эквивалентные преобразования кс-грамматик
- •6. Нисходящий анализ
- •6.1 Анализ методом рекурсивного спуска
- •6.2 Предиктивные анализаторы
- •6.3 Нерекурсивный предиктивный анализ
- •6.4 Множества first и follow
- •6.5 Построение таблиц предиктивного анализа
- •6.6 Ll(1)-грамматики
- •7. Восходящий синтаксический анализ
- •7.1 Понятие основы
- •7.2 Стековая реализация пс-анализа
- •Стек Вход
- •Стек Вход
- •7.3 Конфликты в процессе пс-анализа
- •7.4 Синтаксический анализ приоритета операторов
- •7.4.1 Грамматики простого предшествования
- •7.4.2 Грамматики операторного предшествования
- •7.4.3 Использование отношений приоритетов операторов
- •7.4.4 Нахождение отношений приоритетов операторов
- •7.4.5 Обработка ошибок переноса/свертки
- •7.4.6 Алгоритм синтаксического анализа простого предшествования
- •7.4.7 Алгоритм синтаксического анализа приоритета операторов
- •7.5.1 Алгоритм lr-анализа
- •7.5.2 Построение таблиц slr-анализа
- •7.5.3 Операция замыкания
- •7.5.4 Операция goto
- •7.5.5 Построение множеств пунктов
- •7.5.6 Построение таблицы разбора slr-анализа
- •8. Генерация кода. Методы Генерации кода.
- •8.1 Общие принципы генерации кода.
- •8.2 Внутреннее представление программы
- •8.3 Способы внутреннего представления программ.
- •8.4 Синтаксические деревья
- •8.4.1 Дерево разбора. Преобразование дерева разбора в дерево операций
- •Трехадресный код. Типы трехадресных инструкций
- •8.6 Тетрады - многоадресный код с явно именуемым результатом
- •8.8 Косвенные триады
- •8.9 Сравнение представлений: использование косвенного обращения
- •8.10 Ассемблерный код и машинные команды
- •8.11 Обратная польская запись операций
- •8.11.1 Вычисление выражений с помощью обратной польской записи
- •9. Синтаксически управляемая трансляция
- •9.1 Синтаксически управляемые определения
- •9.2 Вид синтаксически управляемого определения
- •9.3 Синтезируемые атрибуты
- •9.4 Наследуемые атрибуты
- •9.5 Графы зависимости
- •9.6 Порядок выполнения
- •9.7 Восходящее выполнение s-атрибутных определений
- •9.7.1 Синтезируемые атрибуты в стеке синтаксического анализатора
- •9.9 Схемы трансляции
- •9.9.1 Восходящее вычисление наследуемых атрибутов.
- •9.9.2 Наследование атрибутов в стеке синтаксического анализатора
- •9.9.3 Замена наследуемых атрибутов синтезируемыми
- •9.9.4 Память для значений атрибутов во время компиляции
- •9.9.5 Назначение памяти атрибутам во время компиляции
- •9.9.6 Устранение копий
6. Нисходящий анализ
Нисходящий разбор можно рассматривать, как попытку найти левое порождение входной строки. Так же его можно рассматривать и как попытку построить дерево разбора для входной строки, начиная с корня и создавая вершины в прямом порядке.
6.1 Анализ методом рекурсивного спуска
Рассмотрим нисходящий анализ в общем виде, а именно — анализ методом рекурсивного спуска, который может использовать откаты, т.е. производить повторное сканирование входного потока. Однако такие синтаксические анализаторы с откатом встречаются редко. При анализе языков программирования технология отката не очень эффективна, и предпочтительными являются табличные методы.
Рассмотрим пример, в котором откат необходим.
Пример 15
Рассмотрим грамматику
S → cAd
A → ab|a
и входную строку w = cad.
При нисходящем построении дерева разбора для этой строки вначале создаем дерево, состоящее из одного узла, помеченного как S. Указатель входа указывает на с, первый символ строки w. Теперь воспользуемся первой продукцией для S, чтобы получить дерево, показанное на рис. 27а.
Рис. 27. Шаги нисходящего разбора
Крайний слева лист, с, соответствует первому символу строки w, так что переместим указатель входа к а, второму символу строки w, и рассмотрим следующий лист дерева, помеченный А. Теперь можно воспользоваться для А первой альтернативой и получить дерево, изображенное на рис. 27б. Здесь обнаружено соответствие считанного символа листу дерева, и осуществляется переход к следующему символу — d. Однако d не соответствуют листу дерева b, значит, надо вернуться к А с тем, чтобы выбрать новую альтернативу для работы.
Возвращаясь к А, необходимо вернуть указатель входа в позицию 2, в которой он был когда впервые выбирали продукцию для разложения А. Это означает, что процедура для А должна хранить указатель входа в локальной переменной. При рассмотрении второй альтернативы для А получаем дерево, показанное на рис. 21в. Лист а соответствует второму символу w, а лист d - третьему. Поскольку в этот момент построено дерево разбора для w, прекращаем работу и сообщаем об успешном завершении разбора.
Леворекурсивная грамматика может вызвать зацикливание синтаксического анализатора, работающего методом рекурсивного спуска, даже с откатами (при разборе А может потребоваться вновь проанализировать А, находясь в той же входной позиции, что автоматически приводит к бесконечной рекурсии).
6.2 Предиктивные анализаторы
Во многих случаях аккуратная разработка грамматики, устранение из нее левой рекурсии и ее левая факторизация позволяют получить грамматику, которая может быть проанализирована синтаксическим анализатором, работающим методом рекурсивно спуска и не требующим отката. Для построения предиктивного синтаксического анализатора необходимо знать, какая из альтернатив A → α1|α2|…|αn данного анализируемого нетерминала A, порождает строку, начинающуюся с полученного входного символа а. То есть правильная альтернатива должна точно определяться по первому, порождаемому ею символу. Обычно в языках программирования управляющие конструкции отвечают этому правилу. Например, если есть продукции
stmt → if expr then stmt else stmt |while expr do stmt | begin stmt_list end
то ключевые слова if, while и begin однозначно определяют возможную альтернативу для рассматриваемой инструкции stmt.