- •Цели лексического анализа:
- •Основные функции лексического анализатора:
- •Общие принципы построения лексических анализаторов
- •Конечные автоматы
- •Преобразования нка
- •Задачи синтаксич анализа:
- •Роль синтаксического анализатора
- •Контекстно-свободные грамматики
- •Стековая реализация пс-анализа
- •Грамматики предшествования
- •Алгоритм синтаксического анализа простого предшествования
- •Алгоритм синтаксического анализа приоритета операторов
- •Нерекурсивный предиктивный анализ
- •Множества first и follow
- •Внутреннее представление программы
- •Способы внутреннего представления программ.
- •Триады – многоадресный код с неявно именуемым результатом.
- •Алгоритм преобразования дерева вывода в дерево операций:
- •Ассемблерный код и машинные команды
- •Синтаксически управляемые определения
- •Вид синтаксически управляемого определения
- •Восходящее выполнение s-атрибутных определений
- •Синтезируемые атрибуты в стеке синтаксического анализатора
- •Наследование атрибутов в стеке синтаксического анализатора
- •Замена наследуемых атрибутов синтезируемыми
Внутреннее представление программы
Результатом работы распознавателя КС-грамматики - входного языка является последовательность правил грамматики, примененных для построения входной цепочки. По найденной последовательности, зная тип распознавателя, можно построить цепочку вывода или дерево вывода. В этом случае дерево вывода выступает в качестве дерева синтаксического разбора и представляет собой результат работы синтаксического анализатора в компиляторе.
Однако ни цепочка вывода, ни дерево синтаксического разбора не являются целью работы компилятора.
Для полного представления о типе и структуре найденной и разобранной синтаксической конструкции входного языка в принципе достаточно знать последовательность номеров правил грамматики, примененных для ее построения. Однако форма представления этой информации может быть различной как в зависимости от реализации самого компилятора, так и от фазы компиляции. Эта форма называется внутренним представлением программы (иногда используется также термины «промежуточное представление» или «промежуточная программа»).
Способы внутреннего представления программ.
Все внутренние представления программы обычно содержат в себе две принципиально различные вещи – операторы и операнды. Различия между формами внутреннего представления заключаются в том, как операторы и операнды соединяются между собой.
Обратная (постфиксная) польская запись – это постфиксная запись операций. В этой записи знаки операций записываются непосредственно за операндами. Постфиксная запись выражения Е может быть определена следующим образом.
Если Е является переменной или константой, то постфиксная запись Е представляет собой Е.
Если Е – выражение вида Е1 op Е2 , где op – произвольный бинарный оператор, то постфиксная запись Е представляет собой Е1’ Е2’ op, где Е1’ и Е2’ - постфиксные записи для Е1 и Е2 соответственно.
Если Е – выражение вида (Е1), то постфиксная запись для Е1 представляет собой также и постфиксную запись для Е.
Скобки в постфиксной записи не используются.
Например, постфиксная запись для выражения (8-3)+5 представляет 83-5+.
Все операции выполняются в том порядке, в котором записаны -> удобно для реализации на ЭВМ. Нет скобок и не нужно вычислять приоритет операций. Очень эффективна при использовании стека.
Главный недостаток: используется стек -> для работы доступна только верхушка стека -> почти не поддается оптимизации.
Тетрады - многоадресный код с явно именуемым результатом (операция, два операнда и результат операции)
<операция1>(<операнд1>,<операнд2>,<результат>)
ПРИМЕР: A:=B*C+D-B*10
* (B, C, T1) 2. + (T1, D, T2) 3. * (B, 10, T3) 4. – (T2, T3, T4) 5. := (T4, 0, A)
Преимущества тетрад:
Тетрады представляют собой линейную последовательность.
Тетрады представляют машинно-независимую форму внутреннего представления программы
Недостатки: требуют большие памяти для своего представления, чем триады, они также не отражают явно взаимосвязь операций между собой.