Литература по созданию языков программирования

[rockclimber]

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

[iifat]

Хм. Мне казалось, что гугл по строке «создание компилятора» должен давать уйму литературы, не? Да и громадный пласт знаний и методов по этой теме для создания действительно простенького языка, в общем-то, и ни к чему. Хотя, конечно, чтиво весьма интересное.

[bin]

Техника:
А.В. Костельцев, Построение интерпретаторов и компиляторов, СПб: Наука и техника, 2001.
Теория:
Языки программирования Ада, Си, Паскаль. Сравнение и оценка. М.: Радио и связь, 1989.
В.Ш. Кауфман, Языки программирования. Концепции и принципы, М.: Радио и связь, 1993.
3я очередь:
С.Янг, Алгоритмические языки реального времени, Конструирование и разработка, М.:Мир, 1985.

[Pphantom]

rockclimber в сообщении #934909 писал(а):

На наводящие и уточняющие вопросы отвечу с удовольствием.

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

[Pavia]

rockclimber

rockclimber в сообщении #934909 писал(а):

Насколько я понимаю, на данный момент мне предстоит создать некий простенький DSL. Посоветуйте литературу, которая может помочь. На наводящие и уточняющие вопросы отвечу с удовольствием.

А есть смысл создавать новый, когда можно взять готовый? К примеру Lua или Python.
Или модифицировать существующий.

Теория по созданию компиляторов настолько обширна, что не помещается в одной книге. И практика ещё больше.
При этом ничего не мешает создавать компилятор с минимальным числом знаний. Главное упорство. Просто выберете свое направление и свою дорогу и идите в нужную сторону. Путь тернистый, но дорогу осилит идущий.

Пожалуй посоветую классику:
1) Альфред Ахо,Рави Сети,Джеффри Ульман. Компиляторы. 2-е издание, Вильемс 2003
Но по каждой теме главе надо смотреть и искать и читать дополнительный материал.
2) Т. Пратт, М. Зелковиц Языки программирования разработка и реализация. 4-е издание, Питер 2002

И да посмотрите как делаются успешные компиляторы.

[Pphantom]

Pavia в сообщении #935035 писал(а):

А есть смысл создавать новый, когда можно взять готовый? К примеру Lua или Python.

Да, это может быть хорошим решением (но надо все-таки увидеть условия).

Pavia в сообщении #935035 писал(а):

Теория по созданию компиляторов настолько обширна, что не помещается в одной книге. И практика ещё больше.

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

[bin]

rockclimber в сообщении #934909 писал(а):

Насколько я понимаю, на данный момент мне предстоит создать некий простенький DSL.

Если я правильно понял, речь о компиляторе или интерпретаторе пока не идет. Прежде нужно создать язык. Например, составить описание с помощью БНФ. Попытавшись обойти подводные камни, выявленные ранее в других языках. Конечно же, по возможности стоит взять уже существующий язык и расширить его в нужную сторону, упростив в ненужную, а потом найти открытый код транслятора и модифицировать его. Если простенький, то м.б. в качестве прототипа подойдет "игрушечный" язык, нпр., PL/0, Pascal-S Вирта, или small-C.

[Xaositect]

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

[rockclimber]

iifat в сообщении #934959 писал(а):

Хм. Мне казалось, что гугл по строке «создание компилятора» должен давать уйму литературы, не?

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

Pphantom в сообщении #934967 писал(а):

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

Ситуация такая. Около года назад мне в голову пришла идея сделать фреймворк для модульного тестирования кода на PL/SQL (это процедурное расширение SQL, используемое в СУБД Oracle, если кто не в курсе). В силу специфики языка тесты на PL/SQL пишут редко, а существующие фреймворки (их вроде около 10, если считать всех, кто сам так себя называет, и всего два, если считать тех, кого обычно советуют на форумах) меня не впечатлили (почему не впечатлили, это отдельная длинная история). По этой причине не получится, скорее всего, использовать Lua и Python (я не слышал, чтобы их можно было исполнять в оракле, беглый поиск ничего не дал).
Свой фреймворк я написал в итоге и даже немного успел поэксплуатировать на роботе, но слегка забросил позже (в силу ряда причин). Сейчас ситуация изменилась, у меня есть время и пара знакомых, которым интересно как минимум посмотреть на результат ( а как максимум, и попользоваться).
Это была присказка. Один из знакомых, посмотрев на подготовленный специально для него пример, сказал: "Тут придется постоянно писать много однотипного кода, почему бы его не генерировать автоматически?" Я сделал простенький генератор, а потом начал думать над тем, как лучше совместить генерацию одних кусков кода и ручное написание других. Попросил совета у второго знакомого и получил совет использовать DSL (в качестве примера мне была дана вот эта ссылка). Когда я создавал топик, мне казалось, что тут все ясно, что делать. Поэтому советов особо не спрашивал, а спросил литературу. Однако, чем больше времени я об этом думаю, тем больше понимаю, что пока не все так ясно, как хотелось бы, поэтому реализацию автоматизации немного отложу. Сейчас начал читать "классику"

Pavia в сообщении #935035 писал(а):

Пожалуй посоветую классику:
1) Альфред Ахо,Рави Сети,Джеффри Ульман. Компиляторы. 2-е издание, Вильемс 2003

Пока почитаю, возможно, в процессе чтения меня посетит вдохновение.

[iifat]

Очень зависит от сложности и необходимой гибкости.
Ну, например: если бы это был Цэ, хватило бы вам возможностей его макрогенератора? Или можно упростить — например, нужны ли вам определение собственных макрокоманд/переменных? Или наоборот — к примеру, хочется вызывать макро не $f(a,b)$, а, скажем,

Используется синтаксис Visual Basic

let a=b

? Для первого случая не нужна никакая теория. Поставьте чётко задачу и можно делать. Для последнего — зависит таки от того, чего вы конкретно хотите.

[iifat]

Кстати, вспомнил вот: «Конструирование компиляторов для цифровых вычислительных машин» Д. Грис. Старая, но, помнится, вполне интересная книга. Потоньше Ахо, Ульмана , но всё нужное есть.

[alex_4x]

Добрый день!
Забрел сюда в поисках книжки Колокольцева Построение трансляторов и компиляторов.
Нашел её в одном месте, но там не могу скачать, только с экрана читать получается.
https://reslib.org/reader/web/viewer.ht ... #locale=ru

У меня вопрос, а есть опыт в написании трансляторов у вас и возможность направить на путь правильный ?
Все вроде не сложно LR и LL разбор так просто на словах выглядит, вроде рекурсия сплошная и всё, но у меня что то не получается структуру придумать для задания правил.
Поясню.
Вот есть например определение функции:
FUNC (param1,param2,param3,.....,paramN) [external]
FUNC -обязательное слово и при объявлении должно быть обязательно
Скобки открытие и закрытие - тоже должны быть обязательно
а слово external - может быть или не быть
При этом то же самое может быть записано так:

FUNC //Коментарий
( param1 //это тоже коментарий
//коментарий, ага...
,param2 //и это коментарий
,param3, //и это коментарий
paramn) //и тут коментарий
external //ага, это тоже коментарий

Как составить таблицу правил разбора, ведь таблица должна быть "универсальной" чтобы любые нотации записи работали. Как хранить сами определения этих "возможных" сочетаний?
Если кто может свой опыт изложить - буду очень признателен

[rockclimber]

alex_4x в сообщении #1056484 писал(а):

Поясню.
Вот есть например определение функции:
FUNC (param1,param2,param3,.....,paramN) [external]
FUNC -обязательное слово и при объявлении должно быть обязательно
Скобки открытие и закрытие - тоже должны быть обязательно
а слово external - может быть или не быть
При этом то же самое может быть записано так:

FUNC //Коментарий
( param1 //это тоже коментарий
//коментарий, ага...
,param2 //и это коментарий
,param3, //и это коментарий
paramn) //и тут коментарий
external //ага, это тоже коментарий

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

Тут в топике рекомендовали книгу

Pavia в сообщении #935035 писал(а):

1) Альфред Ахо,Рави Сети,Джеффри Ульман. Компиляторы. 2-е издание, Вильемс 2003

Могу порекомендовать еще раз, там есть именно то, что вам нужно.

[arseniiv]

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

-- Пт сен 25, 2015 14:42:38 --

Плюс ещё немного телепатии: при этом ещё стоит ориентироваться во всяких полезных штуках, сокращающих разработку парсера (не обязательно синтаксического анализатора, это я уже в общем): например, часто может хватить производительности parser combinator’ов, если они есть в языке (в некоторых есть возможность их удобно и выразить, и эффективно реализовать); другие вещи принимают на вход грамматику (и/или описания токенов) и выдают код или какое-то представление, которое использует уже скомпилированный модуль. И тому подобные. Не всё нужно писать руками (хотя пробовать стоит).

[Pavia]

Опыта хоть отбавляй. Большинство теорий по компиляторам написано довольно сухим языком из-за чего детали ускользают.
Книга дракона конечно хорошая. Но нельзя ограничиваться только ей. Существует много книг по компиляторам.

Для ответа на ваши вопросы вам понадобиться:
Опалева Э.А., Самойленко В.П. -Языки программирования и методы трансляции-БХВ (2005)

Вот наводящие вопросы:

alex_4x в сообщении #1056484 писал(а):

Все вроде не сложно LR и LL разбор так просто на словах выглядит,

Разборщики LR, LL работают с контекстно-свободным (КС) или контекстно-зависимым (КЗ) языкам?

alex_4x в сообщении #1056484 писал(а):

FUNC -обязательное слово и при объявлении должно быть обязательно
Скобки открытие и закрытие - тоже должны быть обязательно
а слово external - может быть или не быть

Есть БНФ и РБНФ запись. Что вы знаете о символах '|' и '$\epsilon$' ?

rockclimber в сообщении #1056498 писал(а):

При этом то же самое может быть записано так:

FUNC //Коментарий
( param1 //это тоже коментарий
//коментарий, ага...
,param2 //и это коментарий
,param3, //и это коментарий
paramn) //и тут коментарий
external //ага, это тоже коментарий

Не должно. Делайте проще. Отсеивайте комментарии на стадии разбора лексем.

alex_4x в сообщении #1056484 писал(а):

Как хранить сами определения этих "возможных" сочетаний?

Почему в кавычках? Как работает НКА знаете? Вот так и хранить как в нём. А что-бы работало быстро надо переводить в ДКА.
Советую ознакомиться тут:
http://swtch.com/~rsc/regexp/regexp1.html
http://swtch.com/~rsc/regexp/

alex_4x в сообщении #1056484 писал(а):

Как составить таблицу правил разбора, ведь таблица должна быть "универсальной" чтобы любые нотации записи работали.

Что-бы сделать универсальным к БНФ и ЕБНФ надо добавить ряд дополнений. Прочитать про описания языков можно тут:
https://www.opennet.ru/docs/RUS/bison_yacc/
У Колокольцева показаны не все возможности и особенности работы с Bison'ом и YACC. Так что настоятельно советую изучить всю справку по ним.

А ещё можно забыть про все вопросы КЗ и составить грамматику так что-бы в нём не было таких зависимостей. Что сделал Вирт создавая свои языки ПЛ/0, Паскаль, Модуль. Читать "Вирт Н.-Алгоритмы + структуры данных = программы" (У него несколько книг с одним названием, но с примерами на разных языках.)