- •Упрощенная модель компилятора. Проходы компилятора.
- •3. Проходы компиляторов
- •Задача идентификации. Транслитерация.
- •Методы лексического анализа.
- •Использование автомата для решения задачи идентификации слов (различные классы лексем).
- •Контекстно-свободные грамматики. Основные определения.
- •Задание кс грамматики. Способы задания грамматик: синтаксические диаграммы, форма Бекуса-Наура.
- •Лишние нетерминалы.
- •Выводы. Деревья синтаксического разбора.
- •Праволинейная грамматика.
- •Атрибутные грамматики. Наследуемые и синтезируемые атрибуты.
- •1 Синтезируемые атрибуты
- •2 Наследуемые атрибуты
- •Использование автоматов с магазинной памятью для нисходящего разбора.
- •Общие правила построения нисходящего распознающего автомата.
- •Распознающий автомат для s - грамматик.
- •Ll(1) - грамматики. Множество выбора.
- •Метод рекурсивного спуска.
- •Обработка ошибок при нисходящем разборе.Обнаружение и нейтрализация ошибок.
- •Восходящие методы синтаксического разбора. Метод перенос-свертка.
- •Задачи семантического анализа. Семантические соглашения.
Восходящие методы синтаксического разбора. Метод перенос-свертка.
Условия реализации метода:
Магазинные символы МП-автомата – терминалы и нетерминалы КС – грамматики, дополненные маркером дна
Входные символы автомата - терминальные символы, дополненные маркером конца цепочки -| .
Управление автоматом задается управляющей таблицей. Элементами таблицы являются операции ПЕРЕНОС , ОТВЕРГНУТЬ или вызывают процедуру ОПОЗНАТЬ для каждой комбинации магазинного символа и входного символа.
Каждая процедура ОПОЗНАТЬ просматривает несколько верхних символов магазина и либо выбирает одну из операций СВЕРТКА (i) - для i-го правила грамматики, либо выполняет операцию ДОПУСТИТЬ, либо операцию отвергнуть.
Управляющая таблица задает выбор процедуры ОПОЗНАТЬ когда наверху магазина находится основа, в остальных случаях выбирается операция ПЕРЕНОС.
Метод распознает LR грамматики не содержащие аннулирующие правила <A>→ .
Принцип переноса:
Управляющая таблица строится по следующему правилу . Операция ПЕРЕНОС для магазинного символа <В> и терминала a вносится в таблицу когда выполняется одно из условий:
1) имеется правило <A>→ =<B> , - цепочка из терминальных и нетерминальных символов , a FIRST () ;
2) если вместо <В> стоит маркер дна магазина и a FIRST (S), где S – стартовый нетерминал грамматики.
Принцип свертывания:
В управляющей таблице ячейка на пересечении магазинного символа <В> и терминала a обеспечивает вызов процедуры ОПОЗНАТЬ в следующих случаях:
для правила <A>→ <B> терминал a NEXT (<A>)
если <B> является стартовым нетерминал грамматики a = -|
Эти правила задают построение двух таблиц, таблицы переносов и таблицы свертываний.
Задачи семантического анализа. Семантические соглашения.
Статическая проверка (Static Checking)
Выполняется на этапе компиляции.
Типы проверок:
Проверка типов: проверяется совместимость типов при выполнении операций и других действий. Самое сложное
Эквивалентность по типу
A: array[1..10] of integer
B: array[1..10] of integer
A и B эквивалентны. Но могут быть более сложные ситуации с собственными типами.
Эквивалентность по структуре
В FORTRAN можно присваивать массивы: A:=B
Типы:
Базовые (integer, real, char, Boolean)
Выражение типа (пользовательские) – на основе базовых типов конструируются более сложные типы
Массив – конечное множество однотипных элементов – array[T,I]
Декартово произведение – многомерный массив TxT.
Например, H: array[1..n] of array[1..k] of integer
Запись – конструкция, предполагающая объединение типов разного вида
record((num x integer)(lex x array[T,I]))
Указатель – указатель на некоторую переменную, в которой хранится тип
pointer(T)
Функция – позволяет от одних типов переходить к другим – F: T1xT2 T3
Например, Sin(x): real real
Проверка управления: передача управления за пределы языковых конструкций (условие, цикл, конкатенация) должна производиться в место, которое является корректным с точки зрения языка. Например, в Си: break.
Проверка единственности. Например, в case несколько пунктов с пересекающимися множествами
Проверка имен. Например, проверка меток: каждая метка должна встретиться минимум 2 раза
Динамическая проверка (Dynamic Checking)
Выполняется на этапе выполнения.
