Компиляторы компиляторов с модульным описанием языка?

Question

[palexisru]

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


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

Модульное описание синтаксиса pl2-rainbow.livejournal.com/1090.html


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


В 1999 делал описание языка, которое проходило на TP YACC (Albert Graef), но описание приходилось делать в 15 файлах четырех категорий, которые сливались с помощью copy перед подачей на вход yacc.

Каскадные национальные языки программирования pl2-rainbow.livejournal.com/301.html


Идея: возможность последовательного перевода с языка народности на русский, затем на английский, затем трансляция в байт код (или машинный)

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

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


Тема национальных языков поднималась в статье habrahabr.ru/post/176243/


Предполагаемые области видимости и группы операторов для порожденного языка:
functional — Функциональное — для разделов, использующих функциональное программирование.
aspect — Аспектное — для интерфесов и аспектов. Для методов могут указываться необходимые свойства и дополнения, используемые перед
predicate — Логичное — соответствует Булевым переменным, доказательству теорем, Аристотелевкой логике, работе с запросами SQL, LINQ или простейшим операциям Prolog.
controller — Управляющее — соответствует контроллеру (Controller) модели MVC
publish — Изменяемое — соответствует представлению (View) для модели MVC
public — Соединяющее — соответствует модели базы данных (Model) модели MVC
protected — Защищенное — внутренние элементы класса
private — Внутреннее — скрытые элементы класса
local — Блоковые — переменные методов и блоков

(из habrahabr.ru/post/176249/ — Абстрактность и модель взаимодействия открытых систем)


Спасибо.

Answer 1

[Sergei Borisov]

Если я правильно понял о чем Вы говорите, то может Вам поможет пре-процессинг до lex/yacc. Скажем m4.

Comments

[palexisru]

Конечно, разработка Кернигана и Ричи — тоже приятная штука (спасибо, впервые узнал о таком препроцессоре), но я имел ввиду что-нибудь типа lex/yacc нового объектно-ориентированного поколения.

Хотелось бы уточнить, является ли fsyacc последним писком, или существуют похожие разработки?
Самое интересное, трудно ищется в интернете описание форматов входных файлов для fslex/fsyacc

Спасибо.

[palexisru]

Стоило задать вопрос на Хабрахабре, и yandex выдал
и fsharppowerpack.codeplex.com/SourceControl/changeset/view/71313
и javacc.java.net/

Ранее поисковик куда-то это прятал :-)

Спасибо, но и ради m4 вопрос задать стоило.

[Sergei Borisov]

Учтите что javacc это генератор LL парсеров в отличие от семейства yacc которые дают парсер, основанный на LR, точнее LALR(1). Вообще, мне кажется Вы еще не определились с таргетным языком. Все таки F# или Java?

[Sergei Borisov]

На всякий случай, LL по сравнению с LR это не хорошо и не плохо. Это просто по другому :) Просто надо учитывать, что в общем случае не каждую КС грамматику можно привести к LL. Хотя, большинство имеющих смысл таки да.

[palexisru]

Ответ разместил ниже — еще не до конца освоился, где куда отвечать :-)

Answer 2

[palexisru]

Спасибо за уточнение.
У меня «в желании» самораскручивающийся компилятор с переведенным на него же компилятором компиляторов.

При этом основным видом является императивный язык (близкий к C# и Java), но в таком же синтаксисе предполагается функциональная часть. Захват/освобождение памяти — неявные, без указателей. Если LL позволит обработку преффиксного декремента/инкремента, то и его хватит.

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

Так же учил сына учить стихи: Последняя строчка. Предпоследняя и последняя.Предпрепоследняя, предпоследняя и последняя…

Посмотрел на список алгоритмов, используемый в компиляторах и в функциональном программировани (Филд, П. Харрисон Функциональное программирование: Пер. с англ. — М.: Мир, 1993) — они подозрительно совпадают. Возможно, я не прав, но проверить на соответствие стоит.

F# в чистом виде трогать не хочется, разве что понадобится для промежуточных версий.

Возмножно, получится компилятор компиляторов сделать с помощью только самого языка программирования (с другим по сравнению lex+yacc) разделением, без выделения BNF в отдельные файлы (чем можно обеспечить и модульность описания)

Понимаю, что звучит хуже самоката, но основная идея — проверить описательную полноту туннельного моделирования в применении к языкам программирования. Возможно, удастся выбрать подмножество оберточных классов, достаточное для учебных языков, которое будет одинаково плохо работать и на .NET, и на JVM.
Из опыта:
1991г. — разработка на C утилиты, которая выбирала из bat команды управления меню, и строила меню на экране с возвратом выбора через errorlevel
1992 г. — разработка файла описания поля ввода на Clipper — с генерацией промежуточного файла — для ускорения считывания в память
1992г. — изготовление на C из калькулятора Страуструпа генератора расчетных работ (без массивов) с XBase-подобным языком. Метод рекурсивного спуска.
1993г. — библиотеки на C для использования в Clipper

Далее — в основном не законченные разработки в направлении системы:
библиотека наследования классов в Clipper 5
мастера для Delphi
сквозная система на метаописании БД для Clipper, FoxPro 2, Delphi, PHP
описание для транслятора COBOL-подобного языка с хранением таблиц описания BNF, ключевых слов и переменных в файлах DBase

Для меня таблицы переходов конечных автоматов — так и просятся в реляционные БД. Но на СУБД завязываться не хочу — видимо буду делать с файлами данных или XML, или HTML. Зато, если заработает — какой простор для оптимизации!

Спасибо. С уважением, Алексей.

Comments

[Sergei Borisov]

Ух! чувствую, Вы очень увлечены своей идеей, но я до конца не понял, что же Вы хотите сделать. Ок, прокомментирую, то что понял :)))

Префиксные и постфиксные инкременты/декременты я в свое время реализовывал на рекурсивном спуске, значит они точно могут быть разобраны при помощи LL, но может не хватить LL(1), потребуется LL(k) для k>1. Наверное, хватит k=2. Поскольку JavaCC умеет генерировать LL(*) парсер, то есть с переменным k, то это не проблема.

Достоинство JavaCC — на выходе генератора получается довольно человеко-читаемый рекурсивный спуск, особенно при k=1, в отличие от yacc с их человеко-невоспринимаемыми таблицами. Но вот с модульностью, о чем был Ваш начальный вопрос все так же плохо. В JavaCC вся грамматика (лексика и синтаксис) языка должна быть описана одним файлом.

Как я понял Ваш самокат Вам нужно:
1. сперва сделать парсер языка, при помощи какого-то CC
2. затем на нем написать CC с Вашим языком, в качестве таргетного
И между 1 и 2 еще и компилятор или интерпретатор. Насколько мне известно Java примерно так и создавалась при помощи JavaCC.

При этом в качестве бонуса Вы хотите, чтобы в п.1 можно было генерировать как на Java машину, так и на .NET. Вот для решения этого бонуса, я думаю Вам лучше посмотреть на antlr. Он тоже LL(*), но в качестве таргета умеет и Java и C# и C++. Я с ним близко не знаком, но судя по репозиторию проект жив.

[Sergei Borisov]

Хотя нет. обманул. Сейчас только Java поддерживается в antlr

[palexisru]

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

Просто появилась концепция, которую смог описать словами :-)

Плюс создал сообщество pl2-rainbow.livejournal.com Сейчас могу пробовать развивать идеи только на выходных и в отпусках.

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

Появилась еще одна мысль на будущее: Механизм доказательства теорем Пролог (логичные переменные и методы — сеансовый уровень языка) попробовать применить к описаниям грамматик. Но это — уже лет через 10-20 :-)

Еще раз спасибо за подтверждение наличия белых пятен в инструментах.