- •Формальные грамматики и языки.
- •Задача разбора
- •Классификация грамматик по Холмскому.
- •Диаграмма состояний
- •Отношения предшествования
- •Распознаватель
- •Матрица предшествования
- •Некоторые приемы приведения к грамматикам простого предшествования.
- •Представление автоматов.
- •Концевые маркеры и выходы из распознавания.
- •Эквивалентность состояний.
- •Проверка эквивалентности двух состояний.
- •Недостижимые состояния.
- •Алгоритм составления списка достижимых состояний.
- •Приведённые автоматы.
- •Получение минимального автомата.
- •Недетерминированные автоматы.
- •Эквивалентность недетерминированных и детерминированных конечных распознавателей (нкр и дкр).
- •Задание:
- •Транслятор.
- •Введение таблицы символов.
- •Включение неявной информации.
- •Обнаружение ошибок.
- •Макрообработка и операции, выполняемые во время компиляции.
- •Синтез объектной программы.
- •Оптимизация.
- •Генерация кода.
- •Редактирование связей и загрузки.
- •Задача идентификации. Реализация ка при работе трансляторов.
- •Хранение информации о лексемах.
- •Механизм запоминания.
- •Метод хеширования.
- •Нисходящий разбор с возвратами.
- •Начальная установка.
- •Новый человек.
- •Неудача
- •Класс грамматик, допускающих нисходящий распознаватель.
- •Статистические управляемые схемы перевода и атрибутные грамматики.
- •Контекстные условия
Введение таблицы символов.
Одной из центральных структур данных каждого транслятора является таблица символов – она обычно состоит из элементов, соответствующих всем различным идентификатором, встречающихся в исходной программе.
Лексический анализатор создаёт начальные элементы по мере того ,как он сканирует исходную программу, но затем вся ответственность возлагается на семантический анализатор. Элементы таблицы содержат идентификаторы и их атрибуты: его тип (простая переменная, имя массива, имя подпрограммы, формальные параметры и т.п.) тип значений, отношение к той или иной среде ссылок, а также любую другую информацию, которую можно извлечь в программе из деклараций.
Семантический анализатор вносит эту информацию в таблицу символов. Синтезирующая часть транслятора используем эту информацию для построения эффективного выполняемого хода. Таблица символов в трансляторах для компилируемых языков упраздняется в конце трансляции. Её можно сохранить, например, в языках позволяющих создавать новые идентификаторы во время выполнения программы.
Включение неявной информации.
Зачастую, информация заданная неявно в исходной программе, должна стать явной в объектной программе низкого уровня. Большая часть этой неявной информации выступает под общим названием соглашений по умолчанием.
Обнаружение ошибок.
Синтаксические и семантические анализаторы должны уметь обращаться не только с идеальными, но и с неправильно составленными программами. Семантический анализатор обязан не только заявлять ошибки, когда она ему встречаются, и давать соответствующие сообщения о ошибке, но обязан в таких случаях определить, каким образом можно продолжить синтаксический анализ оставшегося куска программы. При этом может потребоваться больше усилий, чем весь анализ.
Макрообработка и операции, выполняемые во время компиляции.
Не во всех языках предусмотрены средства «макро» и возможность выполнения операций во время компиляции. Однако если такие средства имеются, то их обработка ведётся при семантическом анализе.
Макро – в своей простейшей форме – это кусок текста программы, который определён сам по себе и в программу вставляется во время трансляции, как только встретится соответствующий макровызов.
Макро очень напоминает подпрограмму, с тем лишь отличием, что подпрограмму транслируют отдельно и вызывают во время выполнения, а макро просто подставляют вместо макровызова во время трансляции.
В тех языках, где макро допускаются, семантический анализатор должен идентифицировать в исходной программе макровызовы и сделать соответствующие подстановки тела макро вместо его вызова.
Часто в этом случае необходимо прерывать работу лексического и синтаксического анализаторов и переключить их на анализ цепочки, представляющей тело макро, прежде чем будет возобновлён анализ остатка исходной цепочки. Возможна и такая ситуация, что тело макро – уже частично транслировано , так что семантический анализатор может обрабатывать его непосредственно, вставляя соответствующий объектный код и создавая соответствующие элементы таблицы, а потом вернуться к анализу исходной программы.
Операция, относящая ко времени компиляции, которая выполнятся во время трансляции и управляет трансляцией исходной программы, позволяют транслировать куски программ только при выполнении некоторых условий или позволяет несколько раз транслировать группы инструкций, как если бы транслятор работал в цикле. Семантический анализатор должен идентифицировать и выполнять эти операции, относящиеся ко времени компиляции, и только потом продолжать трансляцию.
