Теория и практика разработки компиляторов

Задача разбора для контекстно свободной грамматики как задача, противоположная выводу в грамматике. Общий алгоритм разбора для КС-грамматик, работающий за время O(n^3). Практические методы разбора: 1) алгоритм нисходящего, или рекурсивного, или LL(1)-разбора; 2) алгоритм восходящего, или LR(1) разбора, или разбора с помощью конечного автомата со стеком (с магазинной памятью).
Два этапа разбора: 1) сканер, разбивающий входной поток символов на лексемы, который традиционно реализуется с помощью конечного автомата; 2) парсер, на вход которого подается поток лексем, выполняющий синтаксический разбор и при необходимости перевод на другой язык, вычисление значения формулы, а также другие задачи, связанные с синтаксическим разбором.
Построение сканера с помощью утилиты lex операционной системы Unix или ее свободной версии flex. Входной язык для утилиты flex. Примеры программ, написанных с использованием flex: выделение имен и числовых констант из входного потока, удаление комментариев из программы на C/C++, раскрашивание в разные цвета ключевых слов, констант и других лексем в тексте программы на C++.
Нисходящий, или рекурсивный, или LL(1)-разбор. Примеры КС-грамматик, допускающих и не допускающих LL(1)-разбор. Критерий того, что КС-грамматика допускает LL(1)-разбор. Способ преобразование грамматики, не допускающей LL(1)-разбор, к форме, которая его допускает: удаление непосредственной рекурсии. Пример такого преобразования для грамматики арифметически формул.
Проект "Калькулятор формул", парсер в котором реализован с помощью
LL(1)-разбора, в котором формула преобразуется в обратную польскую запись, позволяющую вычислить ее значение с помощью стекового вычислителя. Использование этого парсера для реализации на Qt программы, рисующей график функции, заданной в виде формулы в текстовом окне.
Идея восходящего, или LR-разбора. Понятие LR-процесса как процесса, противоположного правому выводу предложения языка в КС-грамматике. Действия сдвиг и свертка, неопределенности.
Понятия LR(0)-ситуации и LR(0)-состояния разбора. Алгоритм построения множества LR(0)-состояний разбора. Конфликты типа сдвиг-свертка (shift-reduce) и свертка-свертка. Определение грамматики, допускающей LR(0)-разбор. Примеры грамматик, допускающих и не допускающих LR(0)-разбор. Таблицы разбора, алгоритм работы LR-парсера, семантический стек.
Определения LR(1)-ситуации и LR(1)-состояния разбора. Примеры разрешения конфликтов LR(0)-разбора путем использования алгоритма LR(1)-разбора, учитывающего первый непрочитанный символ аванцепочки. Определение LR(1)-грамматики и детерминированного языка. Алгоритм работы LR(1)-парсера. Использование сематнического стека для решения различных задач, связанных с синтаксическим разбором.
Утилита yacc и ее свободная версия bison, предназначенная для написания парсеров. Связь с утилитой lex (и ее свободной версией flex), предназначенной для написания сканеров. Синтаксис входного языка для утилиты bison. Пример реализации калькулятора формул с помощью утилит flex и bison, испольующих лексический разбор с помошью конечного автомата и восходящий LR(1)-разбор с помощью конечного автомата со стековой памятью. Применение калькулятора формул для реализации на Qt графической программы, рисующей график функции, заданной в виде формулы в текстовом окне.
Модельный язык Delta, компилятор которого реализован с помощью утилит flex и bison. Синтаксис языка: динамическая типизация, напоминающая язык Python, синтаксис ближе к языку C++. Примеры программ на Delta. Промежуточный код для языка Delta как язык команд для стекового вычислителя.
Генерация промежуточного кода по дереву, представляющему выражение. Принципиальная разница между арифметическими и логическими выражениями. Условные переходы в промежуточном языке. Рекурсивный алгоритм генерации промежуточного кода для логических выражений. Пример генерации кода для логических выражений языка C.
Сканер языка Delta, реализованный с помощью flex. Реализация парсера языка Delta с использованием утилиты bison, а также различных классов на языке C++. Генерация промежуточного кода для арифметических и логических выражений через построение на первом этапе дерева выражения и затем генерацию кода по дереву.
Реализация интерпретатора промежуточного кода языка Delta, аналогия с интерпретатором промежуточного кода языка Python.
Задачи, связанные с развитием языка Delta (добавления новых операций, циклов "для каждого", задания списков в стиле языка Haskell, добавление классов и др.).