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

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 17:31, 18 января 2018.
How-php-works.png

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

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

История

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

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

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

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

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

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

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

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

Компиляторы против интерпретаторов [2]

2008 10 11 22 26 635205627.jpg

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

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

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

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

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

Цикл разработки

Во время цикла разработки программного обеспечения программисты вносят частые изменения в исходный код. При использовании компилятора, каждый раз, когда изменение было внесено в исходный код, они должны ожидать компилятор, чтобы перевести измененные исходные файлы и соединить все файлы двоичного кода, прежде чем программа может быть исполнена. Чем больше программа, тем дольше ожидание. В отличие от этого, программист, использующий интерпретатор, делает ждет намного меньше, поскольку интерпретатор обычно просто должен перевести код, работающий на промежуточном представлении (или не перевести его вообще), таким образом требуется намного меньшего количества времени, прежде чем изменения смогут быть протестированы. Эффекты заметны после сохранения исходного кода и перезагрузки программы. Скомпилированный код обычно с меньшей готовностью отлажен для редактирования, компиляции и соединения - последовательные процессы, которые должны быть проведены в надлежащей последовательности с надлежащим набором команд. Поэтому у многих компиляторов также есть исполнительное средство, известное как Make-файл и программа. Make-файл перечисляет командные строки компилятора и компоновщика и файлы исходного кода программы, но мог бы использовать простой ввод меню командной строки (например, "Make 3"), который выбирает третью группу (набор) инструкций, и тогда дает команды компилятору и компоновщику, которые подают указанные файлы исходного кода. [3]

Распределение

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

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

Факт, который интерпретировал код, может легко быть считан и скопирован людьми, может представить интерес с точки зрения авторского права. Однако существуют различные системы шифрования. Доставка промежуточного кода, такого как байт-код, имеет подобный эффект к шифрованию, но байт-код может декодироваться при помощи декомпилятора или дизассемблера. Эффективность Основной недостаток интерпретаторов - то, что интерпретируемая программа обычно работает медленнее, чем если бы она была скомпилирована. Различие в скоростях могло быть крошечным или большим; часто на порядок, иногда больше. Обычно для запуска программы под интерпретатором требуется больше времени, чем для запуска скомпилированного кода, но для его интерпретации может потребоваться меньше времени, чем общее время, необходимое для его компиляции и запуска. Это особенно важно при анализе прототипа и тестировании кода, когда цикл "редактирования-интерпретации-отладки", может часто быть намного короче цикла редактирования-компиляции-отладки.

Интерпретация кода медленнее, чем выполнение скомпилированного кода, потому что интерпретатор должен проанализировать каждый оператор в программе каждый раз, когда это выполняется, и затем выполнить желаемое действие, тогда как скомпилированный код просто выполняет действие в фиксированном контексте, определенном компиляцией. Этот анализ во время выполнения известен как "интерпретирующие издержки". Доступ к переменным также медленнее в интерпретаторе, потому что отображение идентификаторов в места хранения должно выполняться повторно во время выполнения, а не во время компиляции. [5]

Есть различные компромиссы между скоростью разработки при использовании интерпретатора и скоростью выполнения при использовании компилятора. Некоторые системы (такие как Lisp) позволяют интерпретируемому и скомпилированному коду вызывать друг друга и совместно использовать переменные. Это означает, что, как только подпрограмма была протестирована и отлажена под интерпретатором, она может быть скомпилирована и таким образом извлечь выгоду из более быстрого выполнения, в то время как другие подпрограммы разрабатываются. Много интерпретаторов не выполняют исходный код как есть но преобразуют его в некоторую более компактную внутреннюю форму. Многие интерпретаторы BASIC заменяют ключевые слова единственными маркерами байта, которые могут использоваться, чтобы найти инструкцию в таблице переходов. Несколько интерпретаторов, таких как интерпретатор PBASIC, достигают еще более высоких уровней уплотнения программы при помощи бит-ориентированной, а не байтовой структуры памяти программы, где маркеры команд занимают, возможно, 5 битов, номинально "16-разрядные" константы сохранены в неравномерном коде, требующем 3, 6, 10, или 18 битов, и операнды адреса включают "разрядное смещение". Многие BASIC интерпретаторов могут сохранить и считать назад свое собственное маркируемое внутреннее представление.

Регрессия

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

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

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

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

Достоинства

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

Недостатки

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

Изменения

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

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

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

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

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

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

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

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

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

Дальнейшим размыванием различия между интерпретаторами, интерпретаторами байт-кода и компиляцией является компиляция 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 стремящемся к бесконечности. Это значение не зависит от программы.

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

Микрокод

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

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

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

Приложения [12]

  • Интерпретаторы часто используются для выполнения языков команд, и языки клея, так как каждый оператор, выполняемый на языке команд, обычно является вызовом сложной подпрограммы, такой как редактор или компилятор.
  • Самомодифицирующийся код может быть легко реализован на интерпретируемом языке. Это относится к истокам интерпретации в 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. Дата обновления: 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. Habrahabr // Интерпретатор. Дата обновления: 28.05.2011. URL: https://habrahabr.ru/post/116301/0 (дата обращения: 15.12.2017)

Примечание

  1. "Why was the first compiler written before the first interpreter?". Ars Technica. Retrieved 9 November 2014. 
  2. Short animation, explaining the key conceptual difference between interpreters and compilers
  3. Terence Parr, Johannes Luber, The Difference Between Compilers and Interpreters
  4. Theodore H. Romer, Dennis Lee, Geoffrey M. Voelker, Alec Wolman, Wayne A. Wong, Jean-Loup Baer, Brian N. Bershad, and Henry M. Levy, The Structure and Performance of Interpreters]
  5. Heyne, R. (1984). "Basic-Compreter für U880" [BASIC compreter for U880 (Z80)]. Шаблон:Ill (in German) 1984 (3): 150–152. 
  6. Kühnel, Claus (1987) [1986]. "4. Kleincomputer - Eigenschaften und Möglichkeiten" [4. Microcomputer - Properties and possibilities]. In Erlekampf, Rainer; Mönk, Hans-Joachim. Mikroelektronik in der Amateurpraxis [Micro-electronics for the practical amateur] (in German) (3 ed.). Berlin: Шаблон:Ill, Leipzig. p. 222. ISBN 3-327-00357-2. 7469332. 
  7. A Tree-Based Alternative to Java Byte-Codes, Thomas Kistler, Michael Franz
  8. Surfin' Safari - Blog Archive » Announcing SquirrelFish. Webkit.org (2008-06-02). Retrieved on 2013-08-10.
  9. L. Deutsch, A. Schiffman, Efficient implementation of the Smalltalk-80 system, Proceedings of 11th POPL symposium, 1984.
  10. Kent, Allen; Williams, James G. (April 5, 1993). Encyclopedia of Computer Science and Technology: Volume 28 - Supplement 13. New York: Marcel Dekker, Inc. ISBN 0-8247-2281-7. Retrieved Jan 17, 2016. 
  11. IBM Card Interpreters, page at Columbia University
  12. Theoretical Foundations For Practical 'Totally Functional Programming', (Chapter 7 especially) Doctoral dissertation tackling the problem of formalising what is an interpreter