Рекурсивный спуск используется не только у Вирта, но и в большинстве современных компиляторов. В том числе в Clang и в Rust. И одна из важнейших причин использования этого подхода — хорошая обработка ошибок.
По поводу восстановления после ошибок. Цитирую Compiler Construction Вирта, раздел «7.3. Coping with syntactic errors».
1. As many errors as possible must be detected in a single scan through the text.
2. As few additional assumptions as possible about the language are to be made.
3. Error handling features should not slow down the parser appreciably.
4. The parser program should not grow in size significantly
Технология Core в NI Reaktor это как раз пример вполне профессионального подхода к созданию DSL. Внутри это потоковый DSP-язык с JIT-компилятором. Тут уже другой момент — высокий порог вхождения. Но для музыкантов это не должно быть чем-то новым. Вспомним высокий порог вхождения в скрипку, ф-но или даже в минимуг.
Но вопрос интересный. Какой язык предоставить музыканту, знакомому с модульным синтезом, но не с программированием? У меня подозрение, что граф. программирование в духе Reaktor или Max/MSP здесь будет предпочтительнее какого-нибудь JavaScript.
К сожалению, по тематике DSL существует не так много источников на русском языке. Но в мировом масштабе о DSL существует целый ряд монографий. На что важно обратить внимание: использование металингвистической абстракции является эффективным способом борьбы со сложностью программных проектов, а встроенный в приложение язык — это эффективный способ обеспечения расширяемости приложения.
Можно согласиться с следующим положением: невежество, дилетантизм в области простроения языков наносит вред проекту. В качестве встраиваемого языка лучше сначала рассмотреть готовое решение: Lua, Scheme, Python и так далее.
Здесь вспоминаются русскоязычные движки для текстовых игр. Существовал целый ряд проектов, авторы которых, судя по всему, получали удовольствие от начального создания собственных ЯП, а затем, по прошествии времени, уже с тоской и нежеланием поддерживали и расширяли свои языки. И вот в какой-то момент такие самоделки-долгострои сходу опередил по уровню реализации проект, где в качестве встроенного фигурировал обычный язык Lua.
При этом определенные предметные области вполне заслуживают создания DSL. Особенно, если нотация получается декларативной, не тьюринг-полной. Раз уж исходно был взят музыкальный контекст, то здесь можно вспомнить язык LilyPond. Он, с одной стороны, является декларативным («с4 e g e c»), а с другой — расширяется с помощью Scheme.
Здесь любопытно, что та же Lua — это как раз пример DSL (миниязык для встроенных применений), который кто-то за нас уже написал. В своей работе, вы, возможно, используете и иные «чужие DSL»: make, TeX, graphviz и так далее.
Кроме того, собственный DSL может быть разумным решением, если того требуют определенные условия функционирования встроенного языка. В своей заметке автор пишет по поводу Reaper: «в итоге там, где можно, продублировала свой ЯП JSFX(ReaScript) в виде API для C++, lua и Python». Тут явная путаница. В Reaper используется тот же Python для задач автоматизации редактирования на уровне piano roll. А вот собственный DSL JSFX, который напоминает Си, был создан для задач обработки аудио и MIDI в реальном времени. Язык, к сожалению, тоже отдает дилетантизмом, но, с другой стороны, а где было взять готовый небольшой встраиваемый DSP-язык для работы в реальном времени?
Подводя итог. Разработка DSL — задача, которая требует определенного опыта и знаний. Причем, подобные знания, во многом, за пределами типичных университетских курсов по теории компиляторов.
Меня удивляет, почему так мало внимания (в данной заметке вообще не уделяется) такой замечательной штуке, как doctest. Это одна из тех вещей, которую из Питона (или, возможно, из Лиспа) позаимствовали многие современные языки.
Я выше уже написал по поводу lex/yacc/bison. Обратите внимание, что в современных «промышленных» компиляторах (clang, gcc и проч.) такого рода инструментарий не используется. А используется там традиционный подход на основе рекурсивного спуска.
Обратите внимание, что моя заметка, по большому счету, именно о backend. Как раз по той причине, что статей на эту тему «значительно меньше».
Лексический/синтаксический анализ вы можете найти в любом учебнике. Это самая формализованная, проверенная часть компилятора. Тем не менее, действительно, полезно еще раз обратить внимание на это, что кроме lex/yacc существуют более удобные, современные средства: PEG, комбинаторы. Вот пример игрушечного компилятора, который сделан с помощью моей библиотеки raddsl: github.com/true-grue/PigletC
Продолжение будет, определенно. Идея была в том, чтобы публиковать отдельные фрагменты «руководства» (назовем это так) на хабре, получая обратную связь. Но теперь я для себя выяснил, что разумнее будет написать здесь, спустя время, уже о выходе полного и окончательного результата :)
Я думаю, не стоит даже упоминать том, что создавать компиляторы — дело непростое. За 15 минут вас никто не сможет научить это делать. Тут у нас, скорее, ситуация в духе знаменитой заметки Teach Yourself Programming in Ten Years П. Норвига. Поэтому специалисты по компиляторам и ценятся так высоко, правильно?
Есть и еще один момент. Компиляторы это чрезвычайно широкая область. В большинстве случаев ее и не нужно досконально изучать. Необходимо определить свою нишу. Например, в последнее время очень популярна тема создания собственных DSL, в том числе и на основе source-to-source подхода. Еще один популярный аспект — создание компилятора с порождением целевого кода для LLVM или подобного готового backend'а. Здесь надо понимать, хотя бы, что такое SSA. Теперь давайте вернемся к моей 15-минутной заметке. А ведь тут уже изложены на простых примерах как source-to-source-подход, так и SSA.
Я и сам немного подустал от многочисленных легковесных введений в компиляторостроение. Но мне захотелось попробовать свои силы: как много я смогу доходчиво рассказать в пределах условных 15 минут. Мне показалось, что можно разработать цикл 15-минутных историй по разным моментам, связанным с данной тематикой. И эти истории помогут читателям с разбором серьезных материалов. О них — ниже.
Итак, вы хотите серьезного подхода. Тогда добро пожаловать на вики-страничку.
Конечно же является. Вот определения из двух известных учебников:
«A compiler is a tool that translates software written in one language into
another language». (K. Cooper. L Torczon. Engineering a Compiler)
«Compilers are software systems that translate programs written in higher-level languages into equivalent programs in object code or machine language for execution on a computer». (Steven Muchnick. Advanced Compiler Design and Implementation).
Собственно, Вы сами ответили уже на свой вопрос. Зачем «целая куча терминов для одного и того же»? «Транспилятор» это тот же транслятор. Ведь ничего же нового нет в такого рода трансляции. Вот здесь имеется любопытная дискуссия на тему: news.ycombinator.com/item?id=15154994
Без звуковой карты некоторые MOD'ы звучали даже лучше %)
Речь, разумеется, о PC Speaker. Я всего Purple Motion в свое время прослушал именно через бипер.
В 1996 году купил USR Sportster 33.6. Появился редкий и дорогой почасовой интернет, разнообразные FTN-сети (EagleNet, BasicNet, само Fido, разумеется), UUPC, терминалки… BBS! А вы помните многоканальную DialogueScience BBS, все эти interrupt-lists, тексты, заархивированные с .ha и тд, и тп.? :)
Кстати, пользуясь случаем, хочу передать разработчикам «Касперского» большое спасибо за утилиту avputil. Очень она мне в свое время помогла в исследовании разнообразного кода.
Большое спасибо за популяризацию техник создания интерпретаторов/языковых ВМ!
«Писать программы для виртуальной машины прямо в C — моветон, но и создавать язык программирования — долго, поэтому мы с поросёнком решили ограничиться свинским языком ассемблера»
А вот эта фраза меня раззадорила. Дело в том, что у меня как раз, совершенно случайно, завалялся набор инструментов для быстрого создания компиляторов. В результате полдня ушло вот на такой миниатюрный компилятор PigletC, написанный с нуля: github.com/true-grue/PigletC
Пример.
int r;
int n;
void main() {
n = 5;
r = 1;
while (n > 1) {
r = r * n;
n = n - 1;
}
print(r);
}
Результат компиляции.
PUSHI 1
PUSHI 5
STORE
PUSHI 0
PUSHI 1
STORE
L0:
PUSHI 1
LOAD
PUSHI 1
GREATER
JUMP_IF_FALSE L1
PUSHI 0
PUSHI 0
LOAD
PUSHI 1
LOAD
MUL
STORE
PUSHI 1
PUSHI 1
LOAD
PUSHI 1
SUB
STORE
JUMP L0
L1:
PUSHI 0
LOAD
PRINT
DONE
Запускаем.
pigletvm-exec asm fact.c.pvm fact.c.b
pigletvm-exec run fact.c.b
120
Result value: 0
PROFILE: switch code finished took 0ms
120
Result value: 0
PROFILE: switch code (no range check) finished took 1ms
120
Result value: 0
PROFILE: threaded code finished took 0ms
120
Result value: 0
PROFILE: trace code finished took 1ms
Надеюсь, PigletVM и PigletC сумеют кого-то заинтересовать тематикой создания инструментального ПО.
Опять же, это вотчина Форта. Есть форт-процессоры с двумя аппаратными стеками (возвратов и вычислений). Для каждого типа данных можно заводить свой стек. Собственно, даже на x86 есть еще и FPU-стек.
Спасибо за ссылку, не встречал этого текста. По беглому просмотру делаю следующий вывод. Это не эквивалент, то есть не нечто равноценное оригинальному SICP. Больше похоже на дословный перевод стихотворения без соблюдения рифм и подбора метафор. Кроме того, здесь далеко не весь материал SICP, самые интересные темы отсутствуют.
Выбор именно Scheme для оригинального SICP являлся определяющим с точки зрения методики преподавания: это «пластилиновый» язык, голое синтаксическое дерево. С одной стороны, конкретный синтаксис не затеняет детали реализаций алгоритмов, а с другой — Scheme дает гибкость в исследовании самых разных стилей программирования.
Повторюсь, учебника для Питона, который учит решать задачи в хорошем питоновском стиле я пока не встретил. В этом отношении мне понравился подход П. Норвига: norvig.com/python-lisp.html
Обратите внимание на пример с генератором случайных фраз. Норвиг сначала приводит реализацию на Питоне такой, какой бы написал ее Лисп-программист. Затем он показывает более изящный вариант — более идиоматический, характерный для Питона.
По поводу восстановления после ошибок. Цитирую Compiler Construction Вирта, раздел «7.3. Coping with syntactic errors».
Но вопрос интересный. Какой язык предоставить музыканту, знакомому с модульным синтезом, но не с программированием? У меня подозрение, что граф. программирование в духе Reaktor или Max/MSP здесь будет предпочтительнее какого-нибудь JavaScript.
Можно согласиться с следующим положением: невежество, дилетантизм в области простроения языков наносит вред проекту. В качестве встраиваемого языка лучше сначала рассмотреть готовое решение: Lua, Scheme, Python и так далее.
Здесь вспоминаются русскоязычные движки для текстовых игр. Существовал целый ряд проектов, авторы которых, судя по всему, получали удовольствие от начального создания собственных ЯП, а затем, по прошествии времени, уже с тоской и нежеланием поддерживали и расширяли свои языки. И вот в какой-то момент такие самоделки-долгострои сходу опередил по уровню реализации проект, где в качестве встроенного фигурировал обычный язык Lua.
При этом определенные предметные области вполне заслуживают создания DSL. Особенно, если нотация получается декларативной, не тьюринг-полной. Раз уж исходно был взят музыкальный контекст, то здесь можно вспомнить язык LilyPond. Он, с одной стороны, является декларативным («с4 e g e c»), а с другой — расширяется с помощью Scheme.
Здесь любопытно, что та же Lua — это как раз пример DSL (миниязык для встроенных применений), который кто-то за нас уже написал. В своей работе, вы, возможно, используете и иные «чужие DSL»: make, TeX, graphviz и так далее.
Кроме того, собственный DSL может быть разумным решением, если того требуют определенные условия функционирования встроенного языка. В своей заметке автор пишет по поводу Reaper: «в итоге там, где можно, продублировала свой ЯП JSFX(ReaScript) в виде API для C++, lua и Python». Тут явная путаница. В Reaper используется тот же Python для задач автоматизации редактирования на уровне piano roll. А вот собственный DSL JSFX, который напоминает Си, был создан для задач обработки аудио и MIDI в реальном времени. Язык, к сожалению, тоже отдает дилетантизмом, но, с другой стороны, а где было взять готовый небольшой встраиваемый DSP-язык для работы в реальном времени?
Подводя итог. Разработка DSL — задача, которая требует определенного опыта и знаний. Причем, подобные знания, во многом, за пределами типичных университетских курсов по теории компиляторов.
Среди современных генераторов парсеров, удобных для начинающих, я бы выделил, например, Ohm: nextjournal.com/dubroy/ohm-parsing-made-easy
Лексический/синтаксический анализ вы можете найти в любом учебнике. Это самая формализованная, проверенная часть компилятора. Тем не менее, действительно, полезно еще раз обратить внимание на это, что кроме lex/yacc существуют более удобные, современные средства: PEG, комбинаторы. Вот пример игрушечного компилятора, который сделан с помощью моей библиотеки raddsl: github.com/true-grue/PigletC
Есть и еще один момент. Компиляторы это чрезвычайно широкая область. В большинстве случаев ее и не нужно досконально изучать. Необходимо определить свою нишу. Например, в последнее время очень популярна тема создания собственных DSL, в том числе и на основе source-to-source подхода. Еще один популярный аспект — создание компилятора с порождением целевого кода для LLVM или подобного готового backend'а. Здесь надо понимать, хотя бы, что такое SSA. Теперь давайте вернемся к моей 15-минутной заметке. А ведь тут уже изложены на простых примерах как source-to-source-подход, так и SSA.
Я и сам немного подустал от многочисленных легковесных введений в компиляторостроение. Но мне захотелось попробовать свои силы: как много я смогу доходчиво рассказать в пределах условных 15 минут. Мне показалось, что можно разработать цикл 15-минутных историй по разным моментам, связанным с данной тематикой. И эти истории помогут читателям с разбором серьезных материалов. О них — ниже.
Итак, вы хотите серьезного подхода. Тогда добро пожаловать на вики-страничку.
«A compiler is a tool that translates software written in one language into
another language». (K. Cooper. L Torczon. Engineering a Compiler)
«Compilers are software systems that translate programs written in higher-level languages into equivalent programs in object code or machine language for execution on a computer». (Steven Muchnick. Advanced Compiler Design and Implementation).
Речь, разумеется, о PC Speaker. Я всего Purple Motion в свое время прослушал именно через бипер.
Кстати, пользуясь случаем, хочу передать разработчикам «Касперского» большое спасибо за утилиту avputil. Очень она мне в свое время помогла в исследовании разнообразного кода.
P.S. 2:5020/1537.1 :)
Обратите внимание на раздел «Модели процессора на основе интерпретации».
А вот эта фраза меня раззадорила. Дело в том, что у меня как раз, совершенно случайно, завалялся набор инструментов для быстрого создания компиляторов. В результате полдня ушло вот на такой миниатюрный компилятор PigletC, написанный с нуля: github.com/true-grue/PigletC
Пример.
Результат компиляции.
PUSHI 1
PUSHI 5
STORE
PUSHI 0
PUSHI 1
STORE
L0:
PUSHI 1
LOAD
PUSHI 1
GREATER
JUMP_IF_FALSE L1
PUSHI 0
PUSHI 0
LOAD
PUSHI 1
LOAD
MUL
STORE
PUSHI 1
PUSHI 1
LOAD
PUSHI 1
SUB
STORE
JUMP L0
L1:
PUSHI 0
LOAD
PRINT
DONE
Запускаем.
pigletvm-exec asm fact.c.pvm fact.c.b
pigletvm-exec run fact.c.b
120
Result value: 0
PROFILE: switch code finished took 0ms
120
Result value: 0
PROFILE: switch code (no range check) finished took 1ms
120
Result value: 0
PROFILE: threaded code finished took 0ms
120
Result value: 0
PROFILE: trace code finished took 1ms
Надеюсь, PigletVM и PigletC сумеют кого-то заинтересовать тематикой создания инструментального ПО.
Выбор именно Scheme для оригинального SICP являлся определяющим с точки зрения методики преподавания: это «пластилиновый» язык, голое синтаксическое дерево. С одной стороны, конкретный синтаксис не затеняет детали реализаций алгоритмов, а с другой — Scheme дает гибкость в исследовании самых разных стилей программирования.
Повторюсь, учебника для Питона, который учит решать задачи в хорошем питоновском стиле я пока не встретил. В этом отношении мне понравился подход П. Норвига: norvig.com/python-lisp.html
Обратите внимание на пример с генератором случайных фраз. Норвиг сначала приводит реализацию на Питоне такой, какой бы написал ее Лисп-программист. Затем он показывает более изящный вариант — более идиоматический, характерный для Питона.