Д. Кнут - Искусство программирования том 1 (1119450), страница 54
Текст из файла (страница 54)
е. ваша программа должна получать на входе перфокарты типа (3), а на выходе выдавать перфокарты типа (2). На выходе должна быть настолько короткая строка символов, насколько это возможно, поэтому нуль перед буквой 3 в (2) на этот раз не должен быть перенесен нз (3).
1.4.3. Программы-интерпретаторы В этом разделе будет рассмотрен один из распространенных типов компьютерных программ — програлсмы-шГтперпретаторы (которые для краткости называют просто ипгперпретаторани). Интерпретатор — это компьютерная программа, которая выполняет команды другой программы, написанной на некотором машинно- ориентированном языке. Под машинно-ориентированным языком подразумевается такой способ представления команд, который предполагает использование в командах кодов операций, адресов и т.
д. (Это определение, как и большинство определений современных компьютерных терминов, не является точным, да оно и не должно быть таким; нельзя однозначно определить. какие программы являются интерпретаторами, а какие — нет.) Исторически первые интерпретаторы являлись оболочками машинно-ориентированных языков, специально предназначенными для упрощения процесса программирования. Такими языками было гораздо легче пользоваться, чем настоящими машинными языками. Возникновение символических языков программирования привело к тому, что отпала необходимость в программах-интерпретаторах такого типа, но это никоим образом не означает, что интерпретаторы начали постепенно исчезать. Наоборот, их продолжали применять и теперь применяют настолько широко, что эффективное использование программ-интерпретаторов можно считать одной из главных характеристик современного программирования.
Новые сферы применения интерпретаторов появились, в основном, по следующим причинам: а) на машинно-ориентированном языке можно представить сложную последовательность решений и действий в компактном и удобном виде; Ь) такое представление обеспечивает прекрасный способ передачи информации менСву проходами в многопроходном процессе. В подобных случаях разрабатываются машинно-ориентированные языки специального назначения для использования в конкретной программе и программы, написанные на этих языках, часто генерируются только компьютерами.
(Современные квалифицированные программисты являются также хорошими разработчиками машин, поскольку они не только создают программу-интерпретатор, но и определяют виртуальную машину, язык которой необходимо интерпретировать.) Принцип интерпретирования имеет еще одно дополнительное преимущество, которое состоит в относительной независимости от машины. Это означает, что прн переходе от одного компьютера к другому необходимо переписать только интерпретатор.
Более того, полезные средства отладки можно легко встроить в интерпрети- руюшую систему, Примеры интерпретаторов типа (а) приводятся ниже в нескольких разделах данного многотомника (например, рекурсивный интерпретатор — в главе 8 и машина для синтаксического анализа — в главе 10). Во многих ситуациях, как правило, приходится иметь дело с большим числом аналогичных задач, для которых не удается придумать описывающую их простую общую схему. Рассмотрим такой пример.
Предположим, необходимо написать алгебраический компилятор, с помощью которого можно генерировать эффективные команды машинного языка для сложения двух величин. Эти величины могут принадлежать одному из десяти классог ~константы, простые переменные, рабочие ячейки, ии- дексные переменные, содержимое аккумулятора или индексного регистра, числа с фиксированной или плавающей точкой и т. д.). Если подсчитать количество комбинаций всех пар, то подучится 100 различных случаев. И для того чтобы в каждом случае правильно выполнить операцию, понадобится длинная программа. Для решения данной задачи методом интерпретирования нужно изобрести специальный язык, "команды" которого помещались бы в одном байте.
Затем необходимо просто подготовить таблицу из 100 "программ" на этом языке, таких, чтобы каждая программа идеально помещалась в одном главе. Идея состоит в том, чтобы выбирать из таблицы соответствующий элемент-программу и выполнять ее. Это простой и эффективный метод. Пример интерпретатора типа (Ь) приведен в статье Д. Э. Кнута (В. Е. КппгЬ), "Сошрп!ег-Вгавп Р!овсЬаггв", САСМ 6 (1963), 555 — 563. В многопроходной программе предыдущие проходы должны передавать информацию последующим. Наиболее эффективным средством передачи этой информации следующему проходу является набор команд на машинно-ориентированном языке.
Тогда последующий проход — это ни что иное, как программа-интерпретатор специального назначения, а предыдущий проход — это "компилятор" специального назначения. Такую философию многопроходного процесса можно охарактеризовать следующим образом: мы, по возможности, рассказываем последующему проходу, что нужно делать, а не просто передаем ему набор фактов и просим понлгпь, что необходимо сделать. Другой пример интерпретатора типа (Ь) связан с компиляторами для специальных языков.
Если в язык включено много возможностей, которые достаточно просто можно реализовать только в виде подпрограмм, то полученные в результате объектные программы будут представлять собой очень длинные последовательности вызовов подпрограмм. Это может случиться, например, если язык предназначен, главным образом, для выполнения арифметических действий с высокой точностью. В подобном случае объектная программа будет значительно короче, если ее написать на интерпретируемом языке. Например, в книге В. Влпбе!1, 1.. 3. Впээе!1, АЕСОЬ 60 Ьпр!етепГаВоп ()Чек Ъ'огйк Асабеш!с Ргеэв, 1964) описывается компилятор, выполняющий трансляцию с языка АЬООЬ 60 на интерпретируемый язык, а также рассказывается об интерпретаторе для этого языка.
В работе Агс!шг Егапэ, 1г., "Ап АЬСОЬ 60 Сошр~!ег", Апп. Нею Аисо. Рго8гшпш!п8 4 (1964), 87 — 124, приводятся также примеры программ-интерпретаторов, которые используются во внутренней структуре компилятора. Повсеместное распространение микрокомпьютеров и интегральных микросхем специального назначения сделало этот метод интерпретирования еще более ценным. Написанная на Т)ЕХ программа, с помощью которой были созданы страницы этой книги, преобразовала файл, содержащий текст настоящего раздела, в интерпретируемый язык.
Этот язык, который называется форматом 0Ч1, был разработан Д. Р. Фучсом (В. В. РпсЬв) в 1979 году. (См. В. Е. КппгЬ, '.фХ: 2йе Ргойгат (Веаф !пб, Маввл Ацо!эоп-%еэ!еу, 1986), Рагс 31.] 0Ч1-файл, созданный ТЕХ, затем был обработан интерпретатором 4чйрв, который написал Т. Е Рокики (Т. 6. Вок!сЫ), и преобразован в файл команд на другом интерпретируемом языке под названием Роэг8сг!ргв (АбоЬе 8уагешв 1пс., РоэГБслрГ 7ап8иаде Вейегепсе Малиа1, 2пс! ей!!оп (Веасйпй, Маээл Ас!и!воп-'гЧев!еу, 1990)). Этот Ровг8сг!рс-файл был отослан в издательство, где его распечатали на фотонаборной машине, в которой для получения печатных пластин используется РовгБспрыинтерпретатор.
Такая трехпроходная операция является наглядной иллюстрацией интерпретаторов типа (Ъ); в сам ТЕХ также включен неболыирй интерпретатор типа (а), предназначенный для обработки так называемой лигатуры и выполнения кернинга для символов каждого шрифта, встречающегося в тексте [ЩХ: Тйе Ргоягат, З545). На программу, написанную на интерпретируемом языке, можно посмотреть и с другой точки зрения. Ее можно считать набором вызовов подпрограмм, следующих один за другим. Подобную программу можно легко развернуть в длинную последовательность вызовов подпрограмм, и наоборот: такую последовательность обычно можно свернуть в набор команд, который легко интерпретируется.
Итак, к преимуществам методов интерпретирования относятся компактность представления, машинная независимость и расширенные возможности диагностики Во многих случаях интерпретатор можно написать так, чтобы затраты времени на интерпретацию самого кода и на переход к нужной программе были незначительны. 1.4.3.1. Имитатор М1Х. Если язык, который должен обрабатываться интерпретатором, является машинным языком другого компьютера, то этот интерпретатор обычно называют имитатором (а иногда эмулятором). По мнению автора, на написание таких имитаторов потрачено слишком много времени работы программистов, а на нх использование — слишком много компьютерного времени.
Мотивы создания имитаторов очень просты Например, начальник компьютерного отдела покупает новую машину и хочет по-прежнему использовать на ней программы, написанные для старой машины (вместо того чтобы переписать их с учетом особенностей новой машины). Но обычно это стоит дороже и дает худшие результаты, чем в случае, когда временно нанимается группа программистов и перед ней ставится задача выполнить перепрограммирование. Например, однажды автор принимал участие в подобном проекте и в первоначальной программе, которая использовалась в течение нескольких лет, была обнаружена серьезная ошибка, Мало того что новая программа давала правильные результаты, она еще и работала в пять раз быстрее старой! (Не все имитаторы плохи. Например, для компьютерной фирмы-производителя обычно очень полезно сымитировать новую машину еще до того., как она будет запущена в производство, чтобы программное обеспечение для нее можно было разработать как можно скорее.
Но это очень узкая область применения имитаторов.) В качестве яркого примера неэффективного использования имитаторов компьютеров можно привести подлинную историю о машине А, имитирующей машину В, на которой работает программа, имитирующая машину С! Данный способ приводит к тому, что большой и дорогой компьютер дает худшие результаты по сравнению со своим более дешевым собратом. Ввиду всего вышесказанного возникает вопрос, почему же этот имитатор "поднял свою уродливую голову" в данной книге? На это есть две причины. а) Имитатор, который будет описан ниже, — это хороший пример типичной программы-интерпретатора. Здесь проиллюстрированы основные методы, использующиеся в интерпретаторах, и, кроме того, демонстрируется применение подпрограмм в достаточно длинной программе. Ь) Будет рассмотрен имитатор компьютера М1Х, написанный на языке М1Х (подумать только!).
Это облегчит написание имитаторов М1Х для большинства компью- герон, подобных И1Х; в коде нашей программы мы намеренно избегали широкого использования возможностей, присущих исключительно И1Х. Имитатор И1Х пригодится вам в качестре наглядного пособия к этой книге и, возможно, к другим. Компьютерные имитаторы, описываемые в настоящем разделе, следует отличать от имитаторов дискретных свсглем. Имитаторы дискретных систем — это важные программы, которые будут обсуждаться в разделе 2.2.5. А теперь вернемся к задаче написания имитатора И1Х.
Входными данными для нашей программы будут последовательность команд И1Х и данные, сохраненные в ячейках 0000-3499. Мы в точности сымитируем работу аппаратного обеспечения И1Х и сделаем вид, что И1Х сам интерпретирует эти команды. Таким образом мы попытаемся реализовать спецификации, которые были определены в разделе 1.3.1. В нашей программе, например, используется переменная АИЕС, с помощью которой сохраняется модуль значения, содержащегося в имитируемом регистре А; другая переменная, 51СИА, используется для хранения соответствующего знака. С помощью переменной СЕОСК ведется учет количества единиц имитируемого времени И1Х, затраченного на выполнение имитируемой программы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
