Некоторые идеи опережают свою эпоху на десятилетия. Автор данной заметки к оным безусловно относит систему 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