Интерпретатор

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 23:12, 15 декабря 2017.

Интерпретатор — программа (разновидность транслятора), выполняющая интерпретацию.

Интерпретация — построчный анализ, обработка и выполнение исходного кода программы или запроса (в отличие от компиляции, где весь текст программы, перед запуском, анализируется и транслируется в машинный или байт-код, без её выполнения)[Источник 1]

История

Первым интерпретатором языка высокого уровня был Lisp. Lisp был впервые реализован в 1958 году Стивом Расселом на компьютере IBM 704. Рассел читать бумаги Джона Маккарти, и понял (к удивлению Маккарти), что lisp-функция оценки может быть реализован в машинный код. В результате получился рабочий интерпретатор Lisp, который мог бы использоваться для запуска программ Lisp, или, более правильно, "оценивать выражения Lisp". [Источник 2]

Типы интерпретаторов

Простой интерпретатор анализирует и тут же выполняет (собственно интерпретация) программу покомандно (или построчно), по мере поступления её исходного кода на вход интерпретатора. Достоинством такого подхода является мгновенная реакция. Недостаток — такой интерпретатор обнаруживает ошибки в тексте программы только при попытке выполнения команды (или строки) с ошибкой.

Интерпретатор компилирующего типа — это система из компилятора, переводящего исходный код программы в промежуточное представление, например, в байт-код или p-код, и собственно интерпретатора, который выполняет полученный промежуточный код (так называемая виртуальная машина). Достоинством таких систем является большее быстродействие выполнения программ (за счёт выноса анализа исходного кода в отдельный, разовый проход, и минимизации этого анализа в интерпретаторе). Недостатки — большее требование к ресурсам и требование на корректность исходного кода. Применяется в таких языках, как Java, PHP, Tcl, Perl, REXX (сохраняется результат парсинга исходного кода), а также в различных СУБД.

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

Некоторые интерпретаторы (например, для языков Лисп, Scheme, Python, Бейсик и других) могут работать в режиме диалога или так называемого цикла чтения-вычисления-печати (англ. read-eval-print loop, REPL). В таком режиме интерпретатор считывает законченную конструкцию языка (например, s-expression в языке Лисп), выполняет её, печатает результаты, после чего переходит к ожиданию ввода пользователем следующей конструкции.

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

Следует также отметить, что режимы интерпретации можно найти не только в программном, но и аппаратном обеспечении. Так, многие микропроцессоры интерпретируют машинный код с помощью встроенных микропрограмм, а процессоры семейства x86, начиная с Pentium (например, на архитектуре Intel P6), во время исполнения машинного кода предварительно транслируют его во внутренний формат (в последовательность микроопераций).

Алгоритм работы

  • прочитать инструкцию;
  • проанализировать инструкцию и определить соответствующие действия;
  • выполнить соответствующие действия;

Достоинства и недостатки интерпретаторов

Достоинства

  • Бо́льшая переносимость интерпретируемых программ — программа будет работать на любой платформе, на которой есть соответствующий интерпретатор.
  • Как правило, более совершенные и наглядные средства диагностики ошибок в исходных кодах.
  • Меньшие размеры кода по сравнению с машинным кодом, полученным после обычных компиляторов.

Недостатки

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

Изменения

Байткод переводчиков

Существует спектр возможностей интерпретации и компиляции, в зависимости от объема анализа, выполненного до выполнения программы. Например, Emacs Lisp компилируется в байт-код, который является сильно сжатым и оптимизированным представлением источника Lisp, но не машинный код (и поэтому не привязан к какому-либо конкретному оборудованию). Этот" скомпилированный " код затем интерпретируется интерпретатором байт-кода (сам написан на языке C). Скомпилированный код в этом случае представляет собой машинный код для виртуальной машины, который реализуется не в аппаратном обеспечении, а в интерпретаторе байт-кода. Такие компилирующие переводчики иногда называют компиляторами. В интерпретаторе байт-кода каждая инструкция начинается с байта, и поэтому интерпретаторы байт-кода имеют до 256 инструкций, хотя не все могут быть использованы. Некоторые байт-коды могут принимать несколько байт и могут быть произвольно сложными.

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

Переводчики с резьбовым кодом

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

Абстрактные синтаксические интерпретаторы

В спектре между интерпретацией и компиляцией другой подход заключается в преобразовании исходного кода в оптимизированное абстрактное дерево синтаксиса (AST), а затем выполнении программы, следующей за этой древовидной структурой, или использовании его для генерации собственного кода просто в срок. При таком подходе каждое предложение должно быть проанализировано только один раз. Как преимущество над байт-код, АСТ сохраняет глобальную структуру программы и отношения между утверждениями (которые теряются в представлении байт-код), а при сжатии обеспечивает более компактное представление. Таким образом, использование AST было предложено в качестве лучшего промежуточного формата для компиляторов just-in-time, чем байткод. Кроме того, это позволяет системе выполнять лучший анализ во время выполнения.

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

Сборник «точно в срок»

Дальнейшим размыванием различия между интерпретаторами, интерпретаторами байт-кода и компиляцией является компиляция just-in-time (JIT), метод, в котором промежуточное представление компилируется в машинный код машинного кода во время выполнения. Это повышает эффективность выполнения собственного кода за счет времени запуска и увеличения использования памяти при первой компиляции байт-кода или AST. Адаптивная оптимизация-это дополнительный метод, при котором интерпретатор профилирует запущенную программу и компилирует ее наиболее часто выполняемые части в машинный код. Оба метода несколько десятилетий, появляются в языках, таких как Smalltalk в 1980-х.

Просто в момент компиляции завоевала всеобщее внимание среди разработчиков языков в последние годы, с Java, на .Framework, у большинства современных реализациях JavaScript, MATLAB, которые сейчас в том числе JITs.

Self-переводчик

Само-переводчика интерпретатора языка программирования, написанный на языке программирования, который может интерпретировать себя; пример-базовый интерпретатор написан на Basic. Собственн-переводчики, связанные с самообслуживанием таких компиляторов.

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

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

Важную дизайна аспект в реализации собственной переводчика является ли особенностью интерпретируемый язык реализуется с той же функцией, принимающей в переводчик язык. Пример является ли закрытие в lisp-подобного языка реализуется с помощью замыканий в языке переводчика или реализован "вручную" с помощью структуры данных, явно сохраняя окружающую среду. Чем больше функций реализовано той же функцией на языке хоста, тем меньше контроля программист имеет; разное поведение для борьбы с переполнением числа не может быть реализовано, если арифметические операции делегированы соответствующим операциям на языке хоста.

Некоторые языки имеют элегантный само-переводчик, таких как Лисп или Пролог.[править] много исследований по собственной переводчиков (в частности, отражательная переводчиков) был проведен в схеме язык программирования, диалект Лиспа. В целом, однако, любой Тьюринг-полный язык позволяет писать собственные переводчика. Lisp-это такой язык, потому что программы Lisp являются списками символов и другими списками. XSLT-это такой язык, потому что язык XSLT программы пишутся в XML. Суб-домен Мета-программирование-это написание проблемно-ориентированные языки (DSL-языки).

Клайв Гиффорд представил[править] измерение качества собственн-переводчик (в eigenratio), предел соотношения между компьютерами время, потраченное на работу стека N собственн-переводчики и времени, потраченных на проведение стек из N − 1 самовыдвижение-переводчиков при N стремящемся к бесконечности. Это значение не зависит от программы.

Книга Структура и интерпретация компьютерных программ представлены примеры Мета-круговой перевод схема и его диалектах. Другие примеры языков с собственной переводчика вперед и Паскаль.

Микрокод

Микрокод - это очень часто используемый метод, который накладывает интерпретатор между аппаратным и архитектурным уровнем компьютера »[13]. Таким образом, микрокод является слоем аппаратных инструкций, которые реализуют инструкции машинного кода более высокого уровня или секвенсирование внутреннего состояния во многих элементах цифровой обработки. Микрокод используется в центральных процессорах общего назначения, а также в более специализированных процессорах, таких как микроконтроллеры, цифровые сигнальные процессоры, контроллеры каналов, контроллеры дисков, контроллеры сетевых интерфейсов, сетевые процессоры, графические процессоры и другие аппаратные средства.

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

Более обширное микрокодирование позволяет малым и простым микроархитексам эмулировать более мощные архитектуры с более широкой длиной слова, большим количеством исполнительных блоков и т. Д., Что является относительно простым способом обеспечения совместимости программного обеспечения между различными продуктами семейства процессоров.

Приложения

  • Интерпретаторы часто используются для выполнения языков команд, и языки клея, так как каждый оператор, выполняемый на языке команд, обычно является вызовом сложной подпрограммы, такой как редактор или компилятор.
  • Самомодифицирующийся код может быть легко реализован на интерпретируемом языке. Это относится к истокам интерпретации в Lisp и исследований искусственного интеллекта.
  • Виртуализация. Машинный код, предназначенный для аппаратной архитектуры можно запустить с помощью виртуальной машины. Это часто используется, когда предполагаемая архитектура недоступна или используется для выполнения нескольких копий.
  • Песочница: в то время как некоторые типы песочницы полагаются на защиту операционной системы, интерпретатор или виртуальная машина часто используется. Фактическая аппаратная архитектура и первоначально предназначенная аппаратная архитектура могут быть одинаковыми или не совпадать. Это может показаться бессмысленным, за исключением того, что песочницы не вынуждены фактически выполнять все инструкции, которые они обрабатывают. В частности, он может отказаться выполнить код, который нарушает какие-либо ограничения, связанные с безопасностью его эксплуатации в соответствии.
  • Эмуляторы для запуска компьютерного программного обеспечения, написанного для устаревшего и недоступного оборудования на более современном оборудовании

Типы языка

Первый наш файл, yobaType.ml, который описывает все возможные виды инструкций, устроен максимально просто: [Источник 3]

type action =
        DoNothing
      | AddFunction of string * action list
      | CallFunction of string
      | Stats
      | Create of string
      | Conditional of int * string * action * action
      | Decrement of int * string
      | Increment of int * string;;

Каждая конструкция языка будет приводиться к одному из этих типов. DoNothing — это просто оператор NOP, он не делает ровным счётом ничего. Create создаёт переменную (у нас они всегда целочисленны), Decrement и Increment соответственно уменьшают и увеличивают заданную переменную на какое-то число. Кроме этого есть Stats для вывода статистики по всем созданным переменным и Conditional — наша реализация if, которая умеет проверять, есть ли в заданной переменной требуемая величина (или большая). В самом конце я добавил AddFunction и CallFunction — возможность создавать и вызывать собственные функции, которые на самом деле очень даже процедуры.

Грамматика языка

Любая конструкция, кроме запроса статистики (это у нас как бы служебная команда) и создания функции начинается и заканчивается ключевыми словами. Благодаря этому мы можем смело расставлять как угодно переносы строк и отступы. Кроме этого (мы же работаем с русским языком) я специально создал по паре инструкций для случаев, когда надо передавать и переменную, и значение. Позже увидите, зачем это было нужно. Итак, наш файл yobaParser.mly:

%{
        open YobaType
%}

%token <string> ID
%token <int> INT

%token RULEZ
%token GIVE TAKE
%token WASSUP DAMN
%token CONTAINS THEN ELSE
%token FUCKOFF
%token STATS
%token MEMORIZE IS
%token CALL

%start main
%type <YobaType.action> main

%%

main:
        expr                                          { $1 }
expr:
        fullcommand                                   { $1 }
      | MEMORIZE ID IS fullcommandlist DAMN           { AddFunction($2, $4) }
fullcommandlist:
        fullcommand                                   { $1 :: [] }
      | fullcommand fullcommandlist                   { $1 :: $2 }
fullcommand:
        WASSUP command DAMN                           { $2 }
      | STATS                                         { Stats }
command:
        FUCKOFF                                       { DoNothing }
      | GIVE ID INT                                   { Increment($3, $2) }
      | GIVE INT ID                                   { Increment($2, $3) }
      | TAKE ID INT                                   { Decrement($3, $2) }
      | TAKE INT ID                                   { Decrement($2, $3) }
      | RULEZ ID                                      { Create($2) }
      | CALL ID                                       { CallFunction($2) }
      | CONTAINS ID INT THEN command ELSE command     { Conditional($3, $2, $5, $7) }
      | CONTAINS INT ID THEN command ELSE command     { Conditional($2, $3, $5, $7) }
%%

Первым делом мы вставляем заголовок — открытие модуля YobaType, который содержит наш тип action, описанный в самом начале. Для чисел и строк, не являющихся ключевыми словами языка (переменных) мы объявляем два специальных типа, которым указываем, что именно они в себе содержат. Для каждого из ключевых слов с помощью директивы %token мы создаём тоже свой тип, который будет идентифицировать это слово в грамматике. Можно было бы указать их все хоть в одну строчку, просто такая запись группирует всё по видам инструкций. Имейте в виду, что все созданные нами токены — это именно подстановочные типы, по которым парсер грамматики определяет, что ему делать. Обозвать их можно как угодно, то, как они будут выглядеть в самом языке, мы опишем позже. Указываем, что входной точкой для грамматики является main, и что возвращать он всегда должен объект типа action — инструкцию для интерпретатора. Наконец, после двух знаков %% мы описываем саму грамматику:

  • Инструкция состоит либо из команды (fullcommand), либо из создания функции.
  • Функция, в свою очередь, состоит из списка команд (fullcommandlist).
  • Команда бывает либо служебной (STATS), либо обычной (command), в таком случае она должна быть обёрнута в ключевые слова.
  • С обычной командой всё просто, даже расписывать не буду.

В фигурных скобках мы указываем, что делать при совпадении строки с данным вариантом, при этом $N обозначает N-ный член конструкции. Например, если мы встречаем «CALL ID» (ID — это строка, не забываем), то мы создаём инструкцию CallFunction, которой в качестве параметра передаём $2 (как раз ID) — имя вызываемой функции.

Лексер — превращаем язык в ключевые слова

Мы дошли одновременно до практически самой простой и самой муторной части. Простая она, потому что всего лишь описывает превращение слов языка в наши токены. А муторная, потому что лексеры (а может, только окамловский лексер) плохо рассчитаны на работу с русским языком, поэтому работать с русскими символами можно только как со строками. Так как я хотел сделать ключевые слова языка регистро-независимыми, это добавило кучу геморроя — вместо простого написания «дай» надо было расписывать вариант написания каждой буквы. В общем, смотрите сами, файл yobaLexer.mll:

{
        open YobaParser
        exception Eof
}
rule token = parse
        ("и"|"И") ("д"|"Д") ("и"|"И") (' ')+
        ("н"|"Н") ("а"|"А") ("х"|"Х") ("у"|"У") ("й"|"Й") { FUCKOFF }
      | ("б"|"Б") ("а"|"А") ("л"|"Л") ("а"|"А")
        ("н"|"Н") ("с"|"С") (' ')+
        ("н"|"Н") ("а"|"А") ("х"|"Х")                     { STATS }
      | [' ' '\t' '\n' '\r']                              { token lexbuf }
      | ['0'-'9']+                                        { INT(int_of_string(Lexing.lexeme lexbuf)) }
      | ("д"|"Д") ("а"|"А") ("й"|"Й")                     { GIVE }
      | ("н"|"Н") ("а"|"А")                               { TAKE }
      | ("ч"|"Ч") ("о"|"О")                               { WASSUP }
      | ("й"|"Й") ("о"|"О") ("б"|"Б") ("а"|"А")           { DAMN }
      | ("л"|"Л") ("ю"|"Ю") ("б"|"Б") ("л"|"Л") ("ю"|"Ю") { RULEZ }
      | ("е"|"Е") ("с"|"С") ("т"|"Т") ("ь"|"Ь")           { CONTAINS }
      | ("т"|"Т") ("а"|"А") ("д"|"Д") ("а"|"А")           { THEN }
      | ("и"|"И") ("л"|"Л") ("и"|"И")                     { ELSE }
      | ("у"|"У") ("с"|"С") ("е"|"Е") ("к"|"К") ("и"|"И") { MEMORIZE }
      | ("э"|"Э") ("т"|"Т") ("о"|"О")                     { IS }
      | ("х"|"Х") ("у"|"У") ("й"|"Й") ("н"|"Н") ("и"|"И") { CALL }
      |
      ("а"|"б"|"в"|"г"|"д"|"е"|"ё"|"ж"
       |"з"|"и"|"й"|"к"|"л"|"м"|"н"|"о"
       |"п"|"р"|"с"|"т"|"у"|"ф"|"х"|"ц"
       |"ч"|"ш"|"щ"|"ъ"|"ы"|"ь"|"э"|"ю"|"я")+             { ID(Lexing.lexeme lexbuf) }
      | eof                                               { raise Eof }

Интерпретатор

Осталась последняя часть — сам интерпретатор, который обрабатывает наши конструкции языка.

open YobaType
 
let identifiers = Hashtbl.create 10;;
let funcs = Hashtbl.create 10;;
 
let print_stats () =
        let print_item id amount =
                Printf.printf ">> Йо! У тебя есть %s: %d" id amount;
                print_newline ();
                flush stdout in
        Hashtbl.iter print_item identifiers;;
 
let arithm id op value () =
        try
                Hashtbl.replace identifiers id (op (Hashtbl.find identifiers id) value);
                Printf.printf ">> Гавно вопрос\n"; flush stdout
        with Not_found -> Printf.printf ">> Х@#на, ты %s не любишь\n" id; flush stdout;;
 
let rec cond amount id act1 act2 () =
        try
                if Hashtbl.find identifiers id >= amount then process_action act1 () else process_action act2 ()
        with Not_found ->
                Printf.printf ">> Човаще?!\n";
                flush stdout
and process_action = function
        | Create(id) -> (function () -> Hashtbl.add identifiers id 0)
        | Decrement(amount, id) -> arithm id (-) amount
        | Increment(amount, id) -> arithm id (+) amount
        | Conditional(amount, id, act1, act2) -> cond amount id act1 act2
        | DoNothing -> (function () -> ())
        | Stats -> print_stats
        | AddFunction(id, funclist) -> (function () -> Hashtbl.add funcs id funclist)
        | CallFunction(id) -> callfun id
and callfun id () =
        let f: YobaType.action list = Hashtbl.find funcs id in
        List.iter (function x -> process_action x ()) f
;;
 
while true do
        try
                let lexbuf = Lexing.from_channel stdin in
                process_action (YobaParser.main YobaLexer.token lexbuf) ()
        with
                YobaLexer.Eof ->
                        print_stats ();
                        exit 0
              | Parsing.Parse_error ->
                        Printf.printf ">> Ни@#я не понял б@#!\n";
                        flush stdout
              | Failure(_) ->
                        Printf.printf ">> Ни@#я не понял б@#!\n";
                        flush stdout
done

Первым делом мы создадим две хэштаблицы — для переменных и для функций. Начальный размер 10 взят от фонаря, у нас же тренировочный язык, зачем нам сразу много функций. Затем объявим две небольших функции: одна — для вывода статистики, вторая — для инкремента/декремента переменных.

Дальше идёт группа из сразу трёх функций: cond обрабатывает условные конструкции (наш if), callfun отвечает за вызов функций, а process_action отвечает за обработку пришедшей на вход инструкции как таковой. Надеюсь, почему все три функции зависят друг от друга, объяснять не надо.

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

Наконец, последняяя часть кода до посинения в цикле читает и обрабатывает результат работы парсера.

Добавим к этому Makefile:

all:
   ocamlc -c yobaType.ml
   ocamllex yobaLexer.mll
   ocamlyacc yobaParser.mly
   ocamlc -c yobaParser.mli
   ocamlc -c yobaLexer.ml
   ocamlc -c yobaParser.ml
   ocamlc -c yoba.ml
   ocamlc -o yoba yobaLexer.cmo yobaParser.cmo yoba.cmo

clean:
   rm -f *.cmo *.cmi *.mli yoba yobaLexer.ml yobaParser.ml

Источники

  1. .Wikipedia Interpreter // Wiki. Дата обновления: 15.11.2017. URL: https://en.wikipedia.org/wiki/Interpreter_(computing) (дата обращения: 15.12.2017)
  2. .Википедия Интерпретатор // Википедия. Дата обновления: 13.11.2017. URL: https://ru.wikipedia.org/wiki/%D0%98%D0%BD%D1%82%D0%B5%D1%80%D0%BF%D1%80%D0%B5%D1%82%D0%B0%D1%82%D0%BE%D1%80 (дата обращения: 15.12.2017)
  3. .Хабр Интерпретатор // Хабрахабр. Дата обновления: 28.05.2011. URL: https://habrahabr.ru/post/116301/0 (дата обращения: 15.12.2017)