Глава 2
Простой однопроходный компилятор
Данная глава является вводной к главам 3-8 и представляет ряд базовых технологий компиляции, проиллюстрированных разработкой рабочей программы на С, которая транслирует инфиксные выражения в постфиксную форму. Здесь основное внимание уделяется предварительной стадии компиляции, т.е. лексическому анализу, разбору и генерации промежуточного кода. Главы 9, "Генерация кода", и 10, "Оптимизация кода" посвящены вопросам генерации и оптимизации кода.
2.1. Обзор
Язык программирования может быть определен с помощью описания того, как должна выглядеть программа (синтаксис языка) и что она означает (семантика языка). Для определения синтаксиса языка рекомендуем широко применяемую запись, называемую контекстно-свободной грамматикой, или BNF (Backus-Naur Form, форма Бэкуса-Наура). На сегодня описание семантики языка — гораздо более сложная задача, чем описание синтаксиса; для ее решения необходимо использовать неформальные описания и примеры.
Кроме определения синтаксиса языка, контекстно-свободная грамматика используется при трансляции программ. Грамматически управляемая технология компиляции, известная также как синтаксически управляемая трансляция (syntax-directed translation), очень полезна при разработке предварительной стадии компилятора и будет широко использоваться в данной главе.
В процессе обсуждения синтаксически управляемой трансляции мы построим компилятор, переводящий инфиксные выражения в постфиксные, в которых операторы появляются после своих операндов. Например, постфиксная форма выражения 9 - 5 + 2 выглядит как 9 5-2+. Постфиксная запись может быть преобразована непосредственно в компьютерный код, который выполняет все необходимые вычисления с использованием стека. Давайте начнем с построения простой программы для трансляции в постфиксную форму выражений из цифр, разделенных знаками "плюс" и "минус". После того как станет понятна основная идея, мы расширим программу для обработки более общих конструкций языка программирования. Каждый из наших трансляторов будет представлять собой расширение предыдущего.
В нашем компиляторе лексический анализатор конвертирует поток входных символов в поток токенов, которые представляют собой входной поток для следующей фазы, как показано на рис. 2.1. В данном случае "синтаксически управляемый транслятор" представляет собой комбинацию синтаксического анализатора и генератора промежуточного кода. Одна из причин, по которой мы первоначально ограничиваемся только выражениями, состоящими из цифр и операторов, — простота лексического анализатора (каждый входной символ представляет собой отдельный токен). Позже мы расширим наш язык, включив в него такие лексические конструкции, как числа, идентификаторы и ключевые слова. Для такого расширенного языка мы построим лексический анализатор, который будет накапливать последовательные символы из входного потока и преобразовывать их в токены. Детально построение такого лексического анализатора будет рассмотрено в главе 3, "Лексический анализ".
Рис. 2.1. Структура предварительной стадии компилятора