Некоторые идеи опережают свою эпоху на многие десятилетия. Автор данной заметки к оным безусловно относит систему META II, представленную еще в 1964 году. Среди прочих эта работа впечатлила Дональда Кнута, послужив одним из источников вдохновения в его работе над атрибутными грамматиками.
Автор всего на 6 страницах очень легкого текста статьи[1] описывает виртуальную машину для разбора входной строки и предметно-ориентированный язык, основанный на расширенной версии БНФ (форме Бэкуса-Науэра). В качестве иллюстрации возможностей META II показывается, как предметно-ориентированный язык системы позволяет транслировать выражения на упрощенном варианте Алгола (VALGOL) в инструкции абстрактной стековой машины; естественно, что и языки алгебраических выражений[3] тоже легко разбираются META II.
Но самый интересный аспект META II это возможность
метакомпиляции: опорный предметно-ориентированный язык можно выразить в терминах самого себя, что позволяет пошагово расширять исходные виртуальную машину и сам язык (см. инструкцию в [3]). Предполагалось, что пользователи реализуют исходную виртуальную машину (всего 19 инструкций), после чего, запустив на ней код для языка META II, будут дальше раскручивать компилятор до нужного состояния. Более того, первая версия META II тоже была написана на метаязыке-предшественнике (META), после чего повторно реализована уже на самом META II. Кульминацией публичных исследований автора стал язык TREE-META[2], применявший те же идеи к преобразованию дерева абстрактного синтаксиса.
Помимо теоретических работ Кнута META II стала предтечей более современного формализма - PEG, который набирает все большую популярность в прикладных разработках[4]. Схожие идеи легли в основу систем OMeta[5] и Ohm[6]. О META II тепло отзывались Алан Кэй, Джо Армстронг и другие известные ислледователи языков программирования. В Интернете можно найти множество реализаций виртуальной машины META II, среди которых и версия для Python 3[7] от автора заметки.
Литература:
1.
http://www.chilton-computing.org.uk/acl/literature/reports/p025.htm - исходная публикация
2.
https://en.wikipedia.org/wiki/TREE-META - кульминация развития исходной системы авторами
3.
http://www.bayfronttechnologies.com/mc_tutorial.html - подробная интерактивная демонстрация возможностей метакомпилирующих систем, отталкивающееся от META II
4.
https://www.python.org/dev/peps/pep-0617/ - реализация разбора в Python 3
5.
https://en.wikipedia.org/wiki/OMeta - современное развитие идей META II
6.
https://ohmlang.github.io/ - еще более современная система
7.
https://github.com/vkazanov/pymetaii - реализация META II на Python 3 от автора данной заметки
8.
https://github.com/stevenbagley/metaii - реализация на Common Lisp
9.
https://github.com/EyeBool/Meta-II-Compiler - реализация на C++
10.
https://github.com/siraben/meta-II - реализация на Scheme
#classic #parsing #metaii #peg