Интерпретаторы, компиляторы и виртуальные машины
Какой путь проходит программа от исходного кода до исполнения? Если язык достаточно прост, как в printf или в наших простейших регулярных выражениях, то исполняться может сам исходный код. Это несложно; таким образом можно запускать программу сразу же по написании.
Нужно искать компромисс между временем на подготовку к запуску и скоростью исполнения. Если язык не слишком прост, то для исполнения желательно преобразовать исходный код в некое приемлемое и эффективное внутреннее представление. На это начальное преобразование исходного кода тратится определенное время, но оно вполне окупается более быстрым исполнением. Программы, в которых преобразование и исполнение объединены в один процесс, читающий исходный текст, преобразующий его и его исполняющий, называются интерпретаторами (interpreter). Awk и Perl, как и большая часть других языков скриптов и языков специального назначения, являются именно интерпретаторами.
Третья возможность – генерировать инструкции для конкретного типа компьютера, на котором должна исполняться программа; этим занимаются компиляторы. Такой подход требует наибольших затрат времени на подготовку, однако в результате ведет и к наиболее быстрому последующему исполнению.
Существуют и другие комбинации. Одна из них – мы рассмотрим ее подробно в данном разделе – это компиляция программы в инструкции для воображаемого компьютера (виртуальной машины – virtual machine), который можно имитировать на любом реальном компьютере. Виртуальная машина сочетает в себе многие преимущества обычной интерпретации и компиляции.
Если язык прост, то какой-то особо большой обработки для определения структуры программы и преобразования ее во внутреннюю форму не требуется. Однако при наличии в языке каких-то сложных элементов – определений, вложенных структур, рекурсивно определяемых выражений, операторов с различным приоритетом и т. п. – провести синтаксический разбор исходного текста для определения структуры становится труднее.
Синтаксические анализаторы часто создаются с помощью специальных автоматических генераторов, называемых также компиляторами компиляторов (compiler-compiler), таких как уасс или bison. Подобные программы переводят описание языка, называемое его грамматикой, как правило, в программу на С или C++, которая, будучи однажды скомпилирована, переводит выражения языка во внутреннее представление. Конечно же, генерация синтаксического анализатора непосредственно из грамматики языка является еще одной впечатляющей демонстрацией мощи хорошей нотации.
Представление, создаваемое анализатором, – это обычно дерево, в котором внутренние вершины содержат операции, а листья – операнды. Выражение:
а = max(b, с/2);
Может быть преобразовано в такое синтаксическое дерево:
Многие из алгоритмов работы с деревьями, описанных в главе 2, вполне могут быть применимы для создания и обработки синтаксических деревьев.