Интерпретаторы, компиляторы и виртуальные машины
Какой путь проходит программа от исходного кода до исполнения? Если язык достаточно прост, как в printf или в наших простейших регулярных выражениях, то исполняться может сам исходный код. Это несложно; таким образом можно запускать программу сразу же по написании.
Нужно искать компромисс между временем на подготовку к запуску и скоростью исполнения. Если язык не слишком прост, то для исполнения желательно преобразовать исходный код в некое приемлемое и эффективное внутреннее представление. На это начальное преобразование исходного кода тратится определенное время, но оно вполне окупается более быстрым исполнением. Программы, в которых преобразование и исполнение объединены в один процесс, читающий исходный текст, преобразующий его и его исполняющий, называются интерпретаторами (interpreter). Awk и Perl, как и большая часть других языков скриптов и языков специального назначения, являются именно интерпретаторами.
Третья возможность — генерировать инструкции для конкретного типа компьютера, на котором должна исполняться программа; этим занимаются компиляторы. Такой подход требует наибольших затрат времени на подготовку, однако в результате ведет и к наиболее быстрому последующему исполнению.
Существуют и другие комбинации. Одна из них — мы рассмотрим ее подробно в данном разделе — это компиляция программы в инструкции для воображаемого компьютера (виртуальной машины — virtual machine), который можно имитировать на любом реальном компьютере. Виртуальная машина сочетает в себе многие преимущества обычной интерпретации и компиляции.
Если язык прост, то какой-то особо большой обработки для определения структуры программы и преобразования ее во внутреннюю форму не требуется. Однако при наличии в языке каких-то сложных элементов — определений, вложенных структур, рекурсивно определяемых выражений, операторов с различным приоритетом и т. п. — провести синтаксический разбор исходного текста для определения структуры становится труднее.
Синтаксические анализаторы часто создаются с помощью специальных автоматических генераторов, называемых также компиляторами компиляторов (compiler-compiler), таких как уасс или bison. Подобные программы переводят описание языка, называемое его грамматикой, как правило, в программу на С или C++, которая, будучи однажды скомпилирована, переводит выражения языка во внутреннее представление. Конечно же, генерация синтаксического анализатора непосредственно из грамматики языка является еще одной впечатляющей демонстрацией мощи хорошей нотации.
Представление, создаваемое анализатором, — это обычно дерево, в котором внутренние вершины содержат операции, а листья — операнды. Выражение
а = max(b, с/2);
эжет быть преобразовано в такое синтаксическое дерево:
Многие из алгоритмов работы с деревьями, описанных в главе 2, вполне]
огут быть применимы для создания и обработки синтаксических деревьев.
После того как дерево построено, обрабатывать его можно множе- j гвом способов. Наиболее прямолинейный метод, применяемый, кста-1 я, в Awk, — это прямой обход дерева с попутным вычислением узлов. | 'прощенная версия алгоритма такого вычисления для языка, основанного на целочисленных выражениях, может включать в себя восходя-] щи обход типа такого:
Первые несколько выражений case вычисляют простые выражения вроде констант
или значений; следующие вычисляют арифметические выражения, а дальше может
идти обработка специальных случаев, условных выражений и циклов. Для реализации
управляющих структур нашему дереву потребуется не показанная здесь дополнительная
информация, которая представляет собой поток управления.
Подобно тому, как мы делали в pack и unpack, здесь можно заменить явный переключатель таблицей указателей на функции. Отдельные операции при этом будут выглядеть практически так же, как и в варианте с переключателем:
Таблица указателей сопоставляет операции и функции, выполняющие операции:
Вычисление использует операции для индексирования в таблице указа-1бй
на функции для вызова этих функций; в этой версии другие функ-и вызываются
рекурсивно.
Обе наши версии eval применяют рекурсию. Существуют способы уст-нить ее
— в частности, весьма хитрый способ, называемый шитым кодом ireaded code),
который практически не использует стек вызовов. Самым ящным способом избавления
от рекурсии будет сохранение функций в 1ссиве, с последующим выполнением
этих функций в записанном поряд-:. Таким образом, этот массив становится
просто последовательностью гструкций, исполняемых некоторой специальной
машиной.
Для представления частично вычисленных значений из нашего выра-ения мы, так же как и раньше, будем использовать стек, так что, не-ютря на изменение формы функций, преобразования отследить будет трудно. Фактически мы изобретаем некую стековую машину, в которой инструкции представлены небольшими функциями, а операнды хранятся в отдельном стеке операндов. Естественно, это не настоящая машина, но мы можем писать программу так, как будто подобная машина все же существует: в конце концов, мы можем без труда реализовать ее в виде интерпретатора.
При обходе дерева вместо подсчета его значения мы будем генерировать массив функций, исполняющих программу. Массив будет также содержать значения данных, используемых командами, такие как константы и переменные (символы), так что тип элементов массива должен быть объединением:
Ниже приведен блок кода, генерирующий указатели на функции и помещающий
их в специальный массив code. Возвращаемым значением функции generate
является не значение выражения — оно будет подсчитано только после выполнения
сгенерированного кода, — а индекс следующей операции в массиве code, которая
должна быть сгенерирована:
Для выражения а - max( b , с/2 ) сгенерированный код будет выглядеть так:
Функции-операции управляют стеком, извлекая из него операнды и за-ружая
результаты.
Код интерпретатора организован в виде цикла, в котором командный :четчик рс обходит массив указателей на фрикции:
Этот цикл моделирует в программном виде на изобретенной нами стековой
машине то, что происходит на самом деле в настоящем компьютере:
Обратите внимание на то, что проверка делимого на ноль осуществляется
в divop, а не в generate.
Условное исполнение, ветвление и циклы модифицируют счетчик программы внутри функции-операции, осуществляя тем самым доступ к массиву функций с какой-то новой точки. Например, операция goto всегда переустанавливает значение переменной рс, а операция условного ветвления — только в том случае, если условие есть истина.
Массив code является, естественно, внутренним для интерпретатора, однако представим себе, что нам захотелось сохранить сгенерированную программу в файл. Если бы мы записывали адреса функций, то результат получился бы абсолютно непереносимым, да и вообще ненадежным. Однако мы могли бы записывать константы, представляющие функции, например 1000 для addop, 1001 для pushop и т. д., и переводить их обратно в указатели на функции при чтении программы для интерпретации.
Если внимательно посмотреть на файл, который создает эта процеду-, можно понять, что он выглядит как поток команд виртуальной машины. Эти команды реализуют базовые операции нашего рабочего языка, рункция generate — это компилятор, транслирующий язык на вирту-. ьную машину. Виртуальные машины — стародавняя идея, обретшая госледнее время новую популярность благодаря Java и виртуальной шгане Java (Java Virtual Machine, JVM); виртуальные машины предо-авляют простой способ создавать переносимые и эффективные реали-, ции программ, написанных на языках высокого уровня.
