Ссылки, необходимые для реализации интерпретатора в C/С++

Я привязался к проекту, чтобы интегрировать интерпретатор в существующее приложение. Язык, который следует интерпретировать, является производным от Lisp, с встроенными приложениями. Индивидуальные "программы" будут запускаться в приложении в пакетном стиле.

Я удивлен, что за эти годы я написал несколько компиляторов и несколько переводчиков/парсеров на языке данных, но я никогда раньше не писал переводчика. Прототип довольно далеко, реализованный в качестве синтаксического дерева walker, в С++. Возможно, я могу повлиять на архитектуру за пределами прототипа, но не на язык реализации (С++). Итак, ограничения:

реализация будет в С++
синтаксический анализ, вероятно, будет обрабатываться грамматикой yacc/bison (теперь)
предложения по полным экологиям VM/Interpreter, такие как NekoVM и LLVM, вероятно, не подходят для этого проекта. Самостоятельный лучше, даже если это звучит как NIH.

То, что я действительно ищу, - это чтение материалов по основам внедрения переводчиков. Я просмотрел SO, и еще один сайт, известный как Lambda the Ultimate, хотя они более ориентированы на теорию языка программирования.

Некоторые из лакомых кусочков, которые я собрал до сих пор:

Lisp в малой части, Кристиан Квиннек. Человек, рекомендующий это, сказал, что "переходит от тривиального переводчика к более продвинутым методам и заканчивает представление компиляторов байт-кода и" Схемы для С ".
NekoVM. Как я уже упоминал выше, я сомневаюсь, что нам будет разрешено включать всю инфраструктуру VM для поддержки этого проекта.
Структура и интерпретация компьютерных программ. Первоначально я предположил, что это может быть излишним, но, проработав здоровый кусок, я согласен с @JBF. Очень информативный и расширяющий сознание.
В Lisp от Paul Graham. Я прочитал это, и хотя это информативное введение в принципы Lisp, недостаточно, чтобы начать создание интерпретатора.
Parrot Implementation. Это кажется забавным. Не уверен, что это предоставит мне основы.
Схема из Scratch. Peter Michaux атакует различные реализации Схемы, от быстрого и грязного интерпретатора Схемы, написанного на C (для использования в качестве начальной загрузки в более поздних проектах) для скомпилированного кода схемы. Очень интересно до сих пор.
Шаблоны языковой реализации: создайте свои собственные доменные и общие языки программирования, рекомендованные в потоке комментариев для Книги о создании интерпретируемых языков. Книга содержит две главы, посвященные практике создания интерпретаторов, поэтому я добавляю их в свою очередь чтения.
Новый (и еще старый, т.е. 1979): Написание интерактивных компиляторов и интерпретаторов П. Дж. Брауна. Это давно выходит из печати, но интересно представить схему различных задач, связанных с реализацией базового интерпретатора. Я видел смешанные обзоры для этого, но, поскольку он дешевый (у меня он по заказу, который используется около $3,50), я дам ему вращение.

Итак, как насчет этого? Есть ли хорошая книга, которая берет неофита за руку и показывает, как построить интерпретатор в C/С++ для Lisp -подобного языка? Есть ли у вас предпочтения для синтаксических пешеходов или интерпретаторов байт-кода?

Чтобы ответить @JBF:

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

На другие плакаты, я также проверю ваши цитаты. Спасибо, все!

Ответ 1

Короткий ответ:

Основным списком чтения для интерпретатора lisp является SICP. Я бы вообще не назвал это излишним, если вы считаете, что вы переоценены для первых частей книги, переходите к главе 4 и начинаете интерпретировать (хотя я чувствую, что это будет потерей, так как главы 1-3 действительно хороши!).

Добавьте lisp в Small Pieces (LISP с этого момента), главы 1-3. Особенно в главе 3, если вам нужно реализовать какие-либо нетривиальные формы управления.

Посмотрите это сообщение от Jens Axel Søgaard на минимальной схеме самообслуживания: http://www.scheme.dk/blog/2006/12/self-evaluating-evaluator.html.

Несколько более длинный ответ:

Трудно дать совет, не зная, что вам требуется от вашего переводчика.

действительно ли это должен быть интерпретатор, или вам действительно нужно выполнить код lisp?
нужно ли быстро?
Нужно ли соблюдение стандартов? Общие губы? R5RS? R6RS? Любые SFRI, которые вам нужны?

Если вам нужно что-нибудь более интересное, чем простой хордатор синтаксиса, я бы настоятельно рекомендовал встраивать подсистему быстрой схемы. На ум приходит схема гамбита: http://dynamo.iro.umontreal.ca/~gambit/wiki/index.php/Main_Page.

Если это не вариант главы 5 в SICP и главы 5 - в lisp целевой компиляции для более быстрого выполнения.

Для более быстрой интерпретации я бы рассмотрел самые последние интерпретаторы/компиляторы JavaScript. Кажется, что мы много думаем о быстром выполнении JavaScript, и вы, вероятно, можете узнать у них. В V8 приводятся две важные статьи: http://code.google.com/apis/v8/design.html и squirrelfish цитирует пару: http://webkit.org/blog/189/announcing-squirrelfish/.

Существуют также канонические документы схемы: http://library.readscheme.org/page1.html для компилятора RABBIT.

Если я участвую в немного преждевременных спекуляциях, управление памятью может быть жесткой гайкой для взлома. Нильс Холм опубликовал книгу "Схема 9 из пустого пространства" http://www.t3x.org/s9fes/, которая включает в себя простую метку "стоп-мир" и сборщик мусора, Источник включен.

Джон Роуз (о новой славе JVM) написал статью об интеграции Схемы в C: http://library.readscheme.org/servlets/cite.ss?pattern=AcmDL-Ros-92.

Ответ 2

Да на SICP.

Я делал это задание несколько раз, и вот, что бы я сделал, если бы был вами:

Сначала создайте модель памяти. Вам понадобится система GC. Это WAAAAY проще сделать это сначала, чем закрепить его позже.

Создайте свои структуры данных. В моих реализациях у меня была базовая консоль с несколькими базовыми типами: atom, string, number, list, bool, primitive-function.

Создайте свою виртуальную машину и не забудьте очистить API. Моя последняя реализация имела это как API верхнего уровня (простить форматирование - SO pooching мой предварительный просмотр)

ConsBoxFactory &GetConsBoxFactory() { return mConsFactory; }
AtomFactory &GetAtomFactory() { return mAtomFactory; }
Environment &GetEnvironment() { return mEnvironment; }
t_ConsBox *Read(iostream &stm);
t_ConsBox *Eval(t_ConsBox *box);
void Print(basic_ostream<char> &stm, t_ConsBox *box);
void RunProgram(char *program);
void RunProgram(iostream &stm);

RunProgram не требуется - он реализован с точки зрения Read, Eval и Print. REPL - общий шаблон для переводчиков, особенно LISP.

A ConsBoxFactory доступен для создания новых ящиков cons и для их работы. AtomFactory используется так, чтобы эквивалентные символические атомы отображали ровно один объект. Среда используется для поддержания привязки символов к ящикам cons.

Большая часть вашей работы должна идти на эти три шага. Затем вы обнаружите, что код вашего клиента и код поддержки начинают очень похож на LISP:

t_ConsBox *ConsBoxFactory::Cadr(t_ConsBox *list)
{
    return Car(Cdr(list));
}

Вы можете написать парсер в yacc/lex, но зачем беспокоиться? LISP - невероятно простая грамматика и пара парсер-рекурсивный спуск пар, это около двух часов работы. Хуже всего писать предикаты для идентификации токенов (например, IsString, IsNumber, IsQuotedExpr и т.д.), А затем записывать подпрограммы для преобразования токенов в коробки cons.

Упростите писать клей в C-код и из него, а также легко отлаживать проблемы, если что-то не так.

Ответ 3

Переводчики Камина из книги программирования Сэмюэля Камина "Языки программирования", "Основанный на интерпретации" подход, переведенный на С++ Тимоти Баддом. Я не уверен, насколько полезен голый исходный код, поскольку он должен был идти с книгой, но это прекрасная книга, которая описывает основы реализации Lisp на языке более низкого уровня, включая сборку мусора и т.д. (Это не в центре внимания книги, которая является языком программирования вообще, но она покрыта.)

Lisp в Small Pieces идет более подробно, но это хорошо и плохо для вашего дела. Там много материала для компиляции и такого, что не будет иметь для вас отношения, а его более простые интерпретаторы находятся в Scheme, а не С++.

SICP - это хорошо, определенно. Не слишком много, но, конечно, письменные переводчики составляют лишь небольшую часть книги.

Предложение JScheme тоже является хорошим (и оно включает в себя некоторый код), но не поможет вам с такими вещами, как GC.

Я мог бы добавить это с дополнительными предложениями позже.

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

Ответ 4

Отъезд JScheme от Peter Norvig. Я нашел это удивительно простым для понимания и порта для С++. Ну, не знаю, как использовать схему в качестве языка сценариев, хотя преподавание ее jnrs громоздко и чувствует себя датированным (helloooo 1980-х).

Ответ 5

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