Интерпретаторы, компиляторы и виртуальные машины Какой путь проходит программа от исходного кода до исполнения? Если язык достаточно прост, как в 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); виртуальные машины предо-авляют простой способ создавать переносимые и эффективные реали-, ции программ, написанных на языках высокого уровня.