Как сделать интерпретатор

Обновлено: 06.07.2024

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

Содержание

1. Введение

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

Например, определение выражения в вашем новом языке может выглядеть примерно следующим образом в терминах формальных грамматик:

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

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

2. Что такое шаблон дизайна переводчика

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

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

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

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

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

Поскольку каждый класс грамматики представляет другой класс, количество классов увеличивается с увеличением количества правил грамматики. Язык с обширными, сложными грамматическими правилами требует большого количества классов. Шаблон Interpreter работает лучше всего, когда грамматика проста. Наличие простой грамматики избавляет от необходимости иметь много классов, соответствующих сложному набору правил, которыми сложно управлять и поддерживать.

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

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

В калькуляторе используется простой синтаксис без понятия блока программного кода и области видимости. Т.е. все переменные являются глобальными, так же нет блоков, наподобие begin … end или < … >, которые присутствуют в языках высокого уровня Паскаль и C ++. Несмотря на свои скромные языковые конструкции, калькулятор может выполнять все те же действия, что и вышеизложенные языки, за исключением определения типов пользователя.

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

Алфавит встроенного калькулятора.

Алфавит встроенного калькулятора включает в себя следующие символы:

Все буквы латинского алфавита.

Цифры от 0 до 9

“ - обрамляет строковую константу

; - завершает оператор

: - начало имени метки

, - разделяет параметры, передаваемые функциям

+ - сложение

- - вычитание

* - умножение

( и ) - скобки в операторах или скобки вокруг параметров, передаваемых функции

А так же составные символы:

= = - сравнение

>= - больше или равно

- меньше или равно

<> - не равно

Словарь языка встроенного калькулятора.

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

Все слова подразделяются на:

ключевые слова,

стандартные идентификаторы,

идентификаторы пользователя.

Ключевые слова являются составной частью языка, имеют фиксированное написание и однозначно определенный смысл:

End – конец программы.

Not – отрицание.

Or – объединение.

Стандартные идентификаторы служат для обозначения заранее определенных конструкций:

True - истина

False - ложь

Pi - число пи = 3.1415926535897932385

Имена встроенных и внешних функций.

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

Идентификаторы имен переменных и процедур, определенных пользователем не должны начинаться с цифр.

Идентификаторы не должны начинаться с символов !, :, _ , т.к. мы будем использовать эти символы в служебных целях.

Пре компилятор воспринимает символы в строчном и прописном регистре в именах идентификаторов как прописные.

Между двумя идентификаторами должен быть хотя бы один разделитель.

Структура программы встроенного калькулятора.

Программа встроенного калькулятора состоит из операторов. Операторы могут быть как одиночными, так и составными. Программа обязательно должна заканчиваться словом end .

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

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

C = A + B ; // даст в результате 5.

C = A + B ; // даст в результате строку “Вася3”

C = A / B // вызовет исключительную ситуацию.

В программе Вы можете использовать комментарии. Комментарии начинаются с двойной наклонной черты - //. И заканчиваются концом строки, т.е. как короткие комментарии в С++.

Порядок выполнения операций естественный, принятый в математике, т.е. сначала операторы в скобках и функции, умножение и деление, сложение и вычитание, булевы операторы, например: 2+2*2 = = 6, а не 8. Вы можете использовать скобки, чтобы переопределить очередность выполнения операций, например: (2 + 2)*2 = = 8.

В качестве параметров функциям можно передавать другие функции и т.д., например: C = sin ( cos ( Z ));

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

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

Вот как выглядит типичная программа:

Если ошибка, то просто уходим из программы

OnExcept (":Exit");

Получаем код текущей таблицы. Здесь IdMain и IdType – встроенные переменные

ThisTable = tTableId(IdMain, IdType);

Получаем код записи, которую будем искать в справочнике при его открытии

FindValue = tGetValByFieldNum(ThisTable, 74);

Получаем код другой таблицы – таблицы справочника

Categors = tTableId(5, 3);

Подготавливаем справочник к открытию

SetOpenDoc(5, 3, "Категории социального положения");

Открываем справочник. OpenReference вернет true , если пользователь нажмет Ok

if (OpenReference(5, 3, FindValue), ":SetVal", ":Exit");

Устанавливаем код из справочника в текущую запись

tSetValByFieldNum (ThisTable, 74, tGetValByName(Categors, "ID_NUM"));

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

Проектирование калькулятора.

Калькулятор должен иметь как минимум следующие блоки:

  1. Компилятор, точнее что-то вроде анализатора текста ( парсер ), разбивающего текст на лексемы, и создающего нужные объекты для дальнейшего выполнения программы.
  2. Два стека – вычислительный и стек вызова подпрограмм. Я на всякий случай разделил их для простоты.
  3. Сам вычислитель, способный правильно выполнять программу, согласно правилам математики, вызывать функции и т.д.
  4. Контейнер переменных.
  5. Контейнер встроенных функций.
  6. Контейнер внешних функций, способный перед выполнением программы регистрировать внешние функции.
  7. Ну, и собственно, компонент – контейнер для всех этих объектов, который может согласовать их работу, который можно поставить на форму.

Тексты – разбор полетов.


Калькулятор.

function GetCompProgramm: TStringList;

function GetProgramm: TStringList;

function GetVariable(const AName: string): Variant;

procedure SetVariable(const AName: string; const AVal: Variant);

function GetIsDebug: boolean;

procedure SetIsDebug(const Value: boolean);

procedure DoCheckName(const VarName: string; var TypeName: TEnumToken;

var InternalName: string);

constructor Create(AOwner: TComponent); override;

destructor Destroy; override;

function Run: Variant;

property Programm: TStringList read GetProgramm;

property CompilerProgramm: TStringList read GetCompProgramm;

property Variable[const AName: string]: Variant read GetVariable write SetVariable;

property Variables: TunVariables read FVariables;

property Functions: TunFunctions read FFunctions;

property Externals: TunExternals read FExternals;

Fcompiler – это наш компилятор, упомянутый как пункт 1. Fstack и FsubStack – два стека для вычислений и подпрограмм, соответственно. Fvariables – контейнер с переменными. Ffunctions – контейнер с встроенными функциями. Fexternals – контейнер внешних функций. И, наконец, Fstalker – сам вычислитель.

Посмотрим, что собственно, происходит, когда нам нужно что-то посчитать. Например, нужно посчитать видимость пункта меню для пользователя:

Присваиваем калькулятору программу.

Устанавливаем значения неких переменных в программе

Запускаем программу на выполнение.

Получаем результат, посчитанный калькулятором.

Здесь isOk – видимость пункта меню.

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

Репозиторий с проектом находится тут, там же есть возможность в браузере посмотреть историю ревизий (английский в логах весьма примитивен,комментарии и рекомендации можете писать в личку),а также скачать самый последний архив репозитория в формате .tar.gz
Если кто-то пользуется Subversion,скачать исходники можно так:

,то получаем "a", равное первому элементу в выражении,то есть 3.В чём логическая ошибка данной программы?С этими каскадными вызовами она слегка запутана.Уверен,что кто-то уже делал это задание.

Теперь всё пашет,всем спасибо,вопрос можно считать закрытым,но есть вопрос поважнее: В функциях prim и term возвращается int при ошибке,но ведь они имеют тип double,как вообще это работает?Происходит неявное преобразование типа,так?Мне интересно,почему Страуструп прибег к такому способу,это распространённая практика?

Пишем свой интерпретатор языка BASIC
Добрый день. Я смотрю, тут на форуме была тема коллективного написания интерпретатора BASIC на.

Пишем свой чекер
Я хочу написать свой чекер, но не знаю с чего начать? Кто знает основные принцип работы чекеров.

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

Пишем свой класс, спецификатор доступа protected
Всем привет! Из книги Р. Лафоре относительно спецификатора доступа protected: Далее пишется.

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

Странный какой-то дебаггер. Если условие (1) выполнилось, происходит не переход к switch, а выход из функции get_token() с возвратом значения END.

> но мотаю на ус всё сказанное и написанное)

Ну вот это самое главное. Остальное со временем придёт

Наверное в страуструпе есть и дальнейшее развитие этой задачи. Со своей стороны могу дыть 3 предложения по дальнейшему апгрейду

По возрастающей сложности (как мне кажется)

1. Работать со входным файлом (т.е. фактически получается некий простенький интерпретатор). Выдавать пользовательские ошибки с прявязкой к исходнику: т.е. печатать имя файла, номер строки, номер позиции в строке (последнее некритично), суть ошибки. Использование неинициализированной переменной считать ошибкой. При этом добавить конструкцию "print ". На вход программы подаём имя файла с текстом программы, которую будем интерпретировать

2. Заменить плавающий типа (double) на целочисленный и добавить операции битовой арифметики: & | ~ >. Приоритет операций такой же, как и в си (можешь посмотреть в том страуструпе).

3. Сделать типизацию. Т.е. понимать как плавающие типы, так и целые. При первой записи в перменную, её тип вычисляется по типу выражения, стоящей в правой части присваивания. Т.е. для "a = 5" переменная a заводится как целочисленная, для "a = 5.0" - как плавающая. Все дальнейшие присваивания в переменную делаются с учётом типа. Т.е. если изначально переменная была как целочисленная, то операция "a = 23.2" означает запись целого значения 23 (потому как a целое).

При вычислении двухоперандногй операции выражения, второй операнд должен приводиться к типу первого операнда. Т.е. "12 + 34.5" должно вычисляться как (пишу в терминах си) "12 + (int)34.5", а "12.1 + 7" должно вычисляться как "12.1 + (float)7". При попытке построения битовых операций над плавающим типом выдавать ошибку (ибо считаем, что битовые типы разрешены только для целых чисел)

Может быть эти задания тебе покажутся сложными, но всё же рекомендую сделать все три. Потому что это тебе сильно поможет в освоении проектирования программ. Если от этого не устанешь, а меня не заломает - попробуем дальше это дело наворотить. Таким образом, писать программу следует с учётом того, что её функциональность будет расширяться - это ещё добавит экспы в части проектирования. Да и на своих же ошибках, возможно, начнёшь лучше понимать, как НЕ надо делать


Photo by David Schultz on Unsplash

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

Интерпретатор или компилятор?

Для начала нужно выбрать, что вы хотите написать: интерпретатор или компилятор (или оба). Какую роль они играют?

  • Компьютер (машина) — это интерпретатор машинного кода (а это тоже язык, пусть и не человекочитаемый).
  • Компилятор переводит исходный код на другой язык, например:
    • на высокоуровневый язык программирования (транспиляция),
    • на машинный код для виртуальной машины (байткод), например JVM,
    • на низкоуровневый язык, например язык ассемблера, который затем будет переведен (другой программой) на машинный код.

    Любопытно, что вы можете написать для своего языка программирования и интерпретатор, и компилятор. Примеры — Lisp (CommonLisp), Scheme (Chez Scheme).

    Также можно написать интерпретатор или компилятор для языка программирования на этом же языке. Для этого вам придется сначала написать первый интерпретатор или компилятор на другом языке, а затем, в новых версиях, вы сможете пользоваться уже новым языком (т. н. раскрутка).

      — реализация Lisp на 82 языках — реализация Scheme на Haskell — подмножество Haskell 2010, реализованное на Haskell.

    Управление памятью

    Следующее, что нужно определить, это как ваш язык программирования будет управлять памятью:

    • вообще не будет (как, например, какой-нибудь декларативный язык)
    • вам это безразлично. Выделяем память и позволяем операционной системе очищать ее после закрытия приложения.
    • статическое управление памятью, как в C
      • частный случай — Rust borrow checker
      • частный случай — Zig
      • частный случай — ссылочные возможности Pony

      Система типов

      Далее надо разобраться, как в вашем языке будет обстоять дело с типами:

      • отсутствие типизации (когда у вас есть только один тип), пример — lambda calculus или calculator;
      • динамическая типизация, пример — Lisp;
      • статическая типизация, пример — Haskell;
      • структурная типизация, пример — TypeScript.

      Можно выбрать и кое-что позаковыристее. Например, типизацию Мартина-Лёфа (ML), зависимые типы (Idris), линейные типы и т. п.


      Photo by Alexandru Acea on Unsplash

      Парадигмы

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

      Например, вы допускаете использование функций первого класса, строгие вычисления (с вызовом по соиспользованию), динамические типы, макросы — и получаете Lisp.

      • Если вы используете гигиенические макросы и продолжения, вы получаете Scheme (приблизительно).
      • используя неизменяемые типы данных, вы получаете Clojure (тоже приблизительно).

      Или вы можете разрешить использование функций первого класса, ленивые вычисления, статические типы — и получить на выходе ML.

      Дополнительные особенности

      Поверх всего этого вы можете добавить дополнительные особенности, например:

      • систему модулей
      • оптимизацию хвостовой рекурсии
      • сопоставление с образцом, как в функциональных языках программирования, и т. п.

      Генераторы парсеров

      Одним из факторов успеха MAL является то, что ему не нужен генератор парсера: парсер Lisp относительно легко имплементировать. Это делает его очень портируемым (реализован более чем на 80 языках). То же касается lis.py — у него есть еще более простой токенизатор.

      Большинство руководств, не связанных с Lisp, предполагают необходимость какого-то специфичного генератора парсеров, что делает их менее портируемыми.

      Список туториалов

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

      Вот заинтересовался (только для своего развития) попробовать написать тормоза ^W интерпретатор, язык c++, с чего начать? В гугле только 2 статьи каких то унылых (там какое то уныние через switch сделано). Какие книги? Можно на английском.



      в первую очередь кури РБНФ и далее по списку



      Это какая книга?


      >интерпритатор, язык c++, с чего начать?

      С чего-нибудь попроще. BASIC например.


      Нашел, спасибо за подсказку.

      С чего-нибудь попроще. BASIC например.


      Не, я синтаксиса базика не знаю, я лучше свой придумаю.


      >>С чего-нибудь попроще. BASIC например.

      вы так говорите как будто хотите использовать сотни if strcmp(some_token, current_token) == 0 а не описывать синтаксис в РБНФ и генерить парсер.


      Да. Ахо, Сети, Ульман в авторах.


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


      В смысле? Я же не интерпритатор C++ писать собираюсь О_о.

      >Не, я синтаксиса базика не знаю, я лучше свой придумаю.

      Всё уже придумано 40 лет назад.


      >>Генератор парсеров сделает убогий год, это пруть для лентяев.

      ага. еще скажи что flex, bison, yacc нинужны а то авторы компиляторов об это не знают или они лентяи.

      Тут кто-то писал что c++ дико сложный для компиляции.

      А понял, тогда boost.spirit

      Это одна из тех книг, которую все активно советуют, но никто из советчиков её как правило не читал.

      Начать можно со стандартного упражнения: написание метациклического интерпретатора, на тех языках, которые это позволяют (лисп, пролог).

      Синтаксический анализ это, конечно, интересно, но и завязнуть в нем можно надолго.


      >вы так говорите как будто хотите использовать сотни if strcmp(some_token, current_token) == 0 а не описывать синтаксис в РБНФ и генерить парсер.

      Ты говоришь так, будто ТС это хочет для работы, а не для учёбы.

      ага. еще скажи что flex, bison, yacc нинужны а то авторы компиляторов об это не знают или они лентяи.

      Да, скажу именно так. Имею опыт работы с этими тулзами и, мягко говоря, не в востороге от их кодогенерации. Все серьёзные проекты имеют свои, руками написанные, парсеры. А кодогенераторы в основном встречаю только в по, где парсеры используются эпизодически.

      Судя по твоим вопросам по руби лучше не надо, документацию ты читать не умеешь и не хочешь.


      Книга очень годная, но сложная - наскоком не возьмешь. Если не осилил, просто пройди мимо.

      Если не понял, о чем я, просто не комментируй.

      > Да, скажу именно так. Имею опыт работы с этими тулзами и, мягко говоря, не в востороге от их кодогенерации. Все серьёзные проекты имеют свои, руками написанные, парсеры. А кодогенераторы в основном встречаю только в по, где парсеры используются эпизодически.

      gcc довольно долго использовали два парсера - один из них был написан на связке lex + yacc и служил для парсинга объявлений.

      И о какой кодогенерации может идти речь, если вы говорите про lex/yacc. Это table driven вещи, там генерятся таблицы, все темплейты кода уже давно написанны и не генерятся. Вы явно не знаете, о чём говорите.


      Еще вот эта книжка довольно хорошая, правда там все примеры на Java и ANTLR.


      Могу еще предложить написать виртуальную машину для Lua, для её байт-кода есть подробное описание. Плюс в том, что не придется писать компилятор, что довольно скучно.


      Читайте также: