Компиляторы и интерпретаторы

      Писать  компилятор  приходится чаще,  чем обычно  думают. Практически всякая  большая   система  включает   в   себя   входной  язык   -   от примитивного до  весьма сложного.  Вспомним хотя  бы dBASE  - это  ведь не  язык  программирования,   а  система  баз   данных.  На  нее   даже программы  пишутся.  А  раз  нужен  входной  язык,  то  бывает  нужен и компилятор.  И   часто  нужен   быстро.  Конечно,   всякий   предпочтет компактный,  быстрый,  хорошо  оптимизирующий  компилятор, но далеко не всякому понравится такой компилятор писать.

Чтобы писать сложные, эффективные и быстрые  компиляторы, есть  много рецептов.  Но  здесь  речь  пойдет  не  о  них. Как написать компилятор просто  -  вот  в  чем  вопрос!  Ведь  такой  компилятор  и  короче,  и отлаживается  легче.  Здесь  не   будет  каких-то  хитрых   алгоритмов, позволяющих  достигать  чудес  эффективности  или  каких-  то особенных способов  организации  данных.  Увы,  с  этими способами одна проблема: заставить  их  работать  может  только  чудо.  А в этой статье - только практические рекомендации, а работают они надежно!

Модельный компиляторЛучший способ понять, как  писать компилятор - написать  его самому. Лучший способ  объяснить это  - предъявить  текст программы.  Вот мы  и предлагаем   статью-программу.   Впрочем,   ее   можно   читать   и  не заглядывая  в листинг,  но  при  этом  вы  много потеряете. Компилятор написан на  Паскале, выходной  язык -  Паскаль, входной  язык прост  до идиотизма. Читатели,  владеющие  с  языком  Паскаль, узнают и во входном языке знаковые конструкции. Наш  модельный компилятор состоит из четырех частей:  сканер,  блок  таблиц  имен, основная  часть  компилятора   и семантические  подпрограммы.  В  том  или  ином  виде  эти  части можно встретить  в любом  компиляторе.  Сканер  -  это  глаза   компилятора, который  обращается  к тексту  программы  только  через  него.  Сканер читает входной  файл  и   избавляет  остальные  части  копилятора   от необходимости  следить  за  каждым  входным  символом.  В  таблице имен хранится  информация   о   переменных   программы.   Обращение  к  ней осуществляется в основном через процедуры блок таблицы имен.

Сканер

Среди   всех   конструкций,   воспринимаемых   компилятором,    есть минимальные, и которые уже не исеет смысла делить на части.   Например: идентификатор,  число,   строка,  ключевое   слово.    Они   называются лексемами. Компилятору нет нужды разбираться в их структуре.   Кстати, в описании старого,  доброго Алгола-60 использовался  термин иероглифы, то есть нечто такое,  что можно  обозначить значком.   Но у компьютера всего-то 256 символов - и приходится писать, например, "procedure".   А посему  идея  следующая:   отдельная  процедура  считывает программу из файла,  выделяет   оттуда  лексемы   и  передает   их  основной   части компилятора. А той  до текста программы  уже нет никакого  дела.  Такаяподпрограмма называется сканером. 

В  языке  SIMPLE  существуют  пять  видов  лексем  (pис.2): ключевые слова,  идентификаторы,  числа,  спецсимволы   и  нечто  в   квадратных скобках.  По  поводу  первых  четырех  типов,  кажется,  все ясно - см. рисунок.  А  пятый,  последний  -  это  наша  хитрость. Дело в том, что компиляция  выражений  -  это  вопрос  особый,  и  ему  будет посвящена следующая статья.   Поэтому, пользуясь  тем, что  выходной язык  у  нас Паскаль, мы перекладываем эту задачу на плечи компилятора с Паскаля.  А чтобы  у  нас  не  возникало  проблем  -  информацию, которые мы просто переписываеми  в  выходной  файл,   не  разбираясь  в  его   внутренней структуре, заключаем в квадратные скобки.

      Посмотрим на текст программы (Пример 1. Сканер). Основная  процедура сканера -  Scan. Вызывая  ее, мы  получаем очередную  лексему. Мы можем даже считать  ее аналогом  процедуры ввода  - со  странного устройства, которое передает   внутрь  компьютера   лексемы.  Процедура   Scan  по первом символу  лексемы определяет,  что за  лексема нас  сейчас ждет, и  вызывает   "специализированную"  процедуру,   которая  только   этим типом  лексем  и  занимается.  Единственная  загвоздка здесь - ключевые слова  путаются  с  именами.  Поэтому  они  считываются  вместе,  а  уж потом одно отделяются от другого.

Обратим  внимание  на  вспомогательные  процедуры  GetCh  и UngetCh. Процедура GetCh заменяет сиволы перевода строки и табуляции на  пробелы и пропускает  лишние пробелы  (так получается,  что несколько  пробелов подряд эквивалентны  одному). Процедура  UngetCh используется,  если мы погорячились"  и  считали  "лишний"  символ.   Тогда  с  помощью  этой процедуры можно  сказать: "Возьми  обратно!" Процедура  GetCh выдаст  в следующий раз тот же символ.

Таблица имен

Когда  человек  пишет  свою  программу  или разбирается в чужой, ему нужно держать в голове кое-какую информацию. Но машина железная, у  нее головы нет.  Поэтому необходима  структура данных,  которая про  каждуюпеременную   хранила   бы   определенную   информацию.   Эта  структура называется таблицей имен. Без нее не обходится ни один компилятор.   Таблица  имен  действительно  похожа  на  таблицу.  Она  состоит  из "строк"  - ячеек  таблицы  имен,  которые могут содержать инфорацию об одной  простой  переменной,  например,  переменной целого типа. (Обычно эти ячейки  называют  записями  таблицы  имен,  но  здесь  сознательно используется другой термин, чтобы не было путаницы с языком SIMPLE).    Посмотрим на  рис.3. Там  изображена структура  нашей таблицей имен. Проще всего,  когда переменная  - целого  типа. Для  нее нужно  хранить всего ничего - имя и  тип (integer). В реальных, больших  компиляторах, впрочем, есть  еще кое-что  - ее  адрес, например.  Но мы,  слава Богу, компилируем в Паскаль!

С записями  будет посложнее.  Даже в  голове у  нас они  хранятся не целиком,  а  как  нечто,  сложенное  из кусочков. А к чему должно быть ближе то, что хранится в  таблице имен? Наверное, к тому, что хранится в голове,  а не на бумаге.

• Но в одну ячейку таблицы имен может поместиться информация  максимум об  одной  переменной. Поэтому сейчас наша  задача  - "раскидать" по  
  ячейкам информацию о структуре записи.  Это  можно  сделать разными способами. Здесь выбран следующий. На  любую переменную - i,j,u и  т.д. - заводим одну запись таблицы имен.   Если эта переменная - запись,  то в поле Fields пишется ссылка  на описание структуры ее полей. 
• В данном случае ссылка - просто номер ячейки таблицы имен, содержащей  заголовок этого  описания.
• Описание  структуры  записи  представляет  собой  заголовок и еще несколько - по одной на  каждое поле - ячеек. Каждая из  этих ячеек (в  том  числе  и  заголовок)  содержит  в  поле  Ref  номер ячейки для следующего поля записи. Ячейка для последнего поля содержит в  поле Ref ноль.  Это означает  "Дальше полей  нет!".   Если  же   поле  записи   снова  запись,    то соответствующая  этому  полю  ячейка  содержит  в поле Fields ссылку на описание структуры полей.
• Первые  MaxKey  записей  таблицы  имен  на  самом  деле  не имена, а ключевые слова. Имена и  ключевые слова вообще очень  легко перепутать. Поэтому если имя будет  найдено в таблице имен,  но в записи с  номером не большим, чем MaxKey, то это на самом деле не имя, а ключевое  слово. Можно, конечно,  завести для  ключевых слов  отдельный список,  но так, как сделано здесь, проще.

3) Компиляторы и интерпретаторы

      С помощью языка программирования создаётся не готовая программа, а только её текст, описывающий ранее  разработанный алгоритм. Чтобы получить работающую программу, надо этот текст либо автоматически перевести в машинный код (для этого служат программы компиляторы) и затем использовать отдельно от исходного текста, либо сразу выполнять команды языка, указанные в тексте программы (этим занимаются программы-интерпретаторы).

      Интерпретатор берёт очередной оператор языка  из текста программы, анализирует его  структуру и затем сразу исполняет (обычно после анализа оператор транслируется  в некоторое промежуточное представление  или даже машинный код для более эффективного дальнейшего исполнения). Только после того как текущий оператор успешно выполнен, интерпретатор перейдёт к следующему. При этом если один и тот же оператор будет выполняться в программе многократно, интерпретатор будет выполнять его так как, как будто встретил впервые. Вследствие этого программы,в которых требуется осуществить большой объём вычислений, будут выполняться медленно. Кроме того, для выполнения программы на другом компьютере там тоже должен стоять интерпретатор – ведь без него текст является просто набором символов.

      По-другому  можно сказать, что интерпретатор  моделирует некоторую вычислительную виртуальную машину, для которой  базовыми инструкциями служат не элементарные команды процессора, а операторы  языка программирования.

      Компиляторы полностью обрабатывают весь текст  программы (он иногда называется исходный код) Они просматривают его в поиске синтаксических ошибок (иногда несколько раз), производят определенный смысловой анализ, а затем автоматически переводят (транслируют) на машинный язык - генерируют машинный код. Нередко при этом выполняется оптимизация с помощью набора методов позволяющих повысить быстродействие программы (например, с помощью инструкций, ориентированных на конкретный процессор, путём исключения ненужных команд, промежуточных вычислений и т.д.). В результате законченная программа получается законченной и эффективной, работает

      В сотни раз быстрее программы, выполняемой с помощьюинтерпретатора, может быть перенесена на другие компьютеры с процессором, поддерживающим соответствующий машинный код.  

      Недостаток  компилятора – трудоёмкость трансляции языков программирования, ориентированных на обработку данных сложных структур, часто заранее неизвестной или динамически меняющейся во время работы программы. Тогда в машинный код приходиться вставлять множество  дополнительных проверок, анализировать  наличие ресурсов операционной  системы, динамически их захватывать и освобождать, формировать  и обрабатывать в памяти компьютера  сложные объекты, что на уровне жестко заданных машинных инструкций  осуществить довольно трудно, а для задачи почти невозможно.

      С помощью интерпретатора, наоборот, допустимо в любой момент остановить программу, исследовать содержимое памяти, организовать диалог с пользователем, выполнить сколь угодно сложные преобразования и при этом постоянно контролировать состояние окружающей программно - аппаратной среды, благодаря чему достигается высокая надёжность работы. Интерпретатор при выполнении  каждого оператора проверяет множество характеристик операционной системы и при необходимости максимально подробно информирует разработчика  о возникающих  проблемах. Кроме того, интерпретатор очень удобен  для использования в качестве инструмента  изучения  программирования, так как позволяет понять принципы работы любого отдельного оператора языка.

      В реальных системах программирования перемешаны технологии и компиляции и интерпретации. В процессе отладки программа  может выполняться по шагам, а  результирующий код не обязательно  будет машинным – он даже может быть исходным кодом, написанном  на другом языке программирования (это существенно упрощает процесс трансляции, но требует компилятора для конкретного языка), или промежуточным машинно-независимым кодом  абстрактного процессора, который в различных машинных архитектурах  станет выполнять  с помощью интерпретатора или компилировать в соответствующий машинный код.

4) Командный интерпретатор

      Операционная  система должна предоставлять удобный  интерфейс пользователю, работающему  за компьютером. В настоящее время получило распространение два вида интерфейсов: графический и алфавитно-цифровой или текстовый. ОС Linux дает возможность использовать интерфейсы любого из этих видов.

      Задачи  администрирования системы обычно решаются в текстовом режиме. Основным посредником между пользователем и системой в текстовом режиме является командный интерпретатор. Вкратце его роль можно охарактеризовать так: интерпретатор должен постоянно ожидать ввода команд пользователя и при их получении выполнять соответствующие действия, как правило, выражающиеся в вызове других программ.

      В действительности роль интерпретатора гораздо шире, он обладает значительным набором самых разнообразных  возможностей, призванных сделать взаимодействие пользователя с компьютером предельно эффективным.

      ОС Linux использует несколько различных  видов интерпретаторов. Наиболее распространенными  среди них являются:

• sh. Bourne Shell. Прообраз командных интерпретаторов сегодняшнего дня. В современных Linux-системах sh представляет собой символическую ссылку на файл bash;
• bash. Bourne-Again SHell. Основной командный интерпретатор ОС Linux. Представляет собой развитие ash и sh. Поддерживает богатый язык написания скриптов, удобный интерфейс для редактирования командной строки, автопродолжение команд и множество других полезных возможностей;
• tcsh. C Shell. Расширенная версия интерпретатора C Shell, использующегося в BSD-системах. Поддерживает функцию автозавершения текста и расширенные возможности редактирования;
• zsh. Очень развитый командный интерпретатор, объединяющий в себе возможности csh, bash с дополнительными, такими как: улучшенная поддержка автопродолжения, более развитые возможности редактирования, расширенные файловые шаблоны и ряд других;
• nash. Not A SHell. Предельно облегченная оболочка, предназначенная для интерпретации сценариев в linuxrc файлах, при загрузке с виртуального диска initrd. Не позволяет работать пользователю в интерактивном режиме.