META II - это предметно-ориентированный язык программирования для написания компиляторов . Он был создан в 1963-1964 годах Дьюи Вэл Шорре из Калифорнийского университета в Лос-Анджелесе . META II использует то, что Шорре назвал синтаксическими уравнениями . Его действие просто объясняется как:
Каждое синтаксическое уравнение преобразуется в рекурсивную подпрограмму, которая проверяет входную строку на наличие определенной структуры фразы и удаляет ее, если она найдена. [1]
Программы Meta II компилируются в интерпретируемый язык байтового кода. Компиляторы VALGOL и SMALGOL, иллюстрирующие его возможности, были написаны на языке META II, [1] [2] VALGOL - это простой алгебраический язык, разработанный для иллюстрации META II. СМАЛГОЛ был довольно большим подмножеством АЛГОЛА 60 .
Обозначение
META II была впервые написана на META I [3], вручную скомпилированной версии META II. История неясна относительно того, была ли META I полной реализацией META II или необходимым подмножеством языка META II, необходимым для компиляции полного компилятора META II.
В документации META II описывается как похожий на BNF , который сегодня объясняется как производственная грамматика. META II - это аналитическая грамматика. В документе TREE-META эти языки были описаны как редуктивные грамматики.
Например, в BNF арифметическое выражение может быть определено как:
< выражение > : = < термин > | < expr > < addop > < term >
Правила BNF - это сегодня производственные правила, описывающие, как составные части могут быть собраны для формирования только допустимых языковых конструкций. Синтаксический анализатор делает обратное, разделяя языковые конструкции. META II - это язык программирования функционального парсера на основе стека, который включает директиву вывода. В META II порядок тестирования определяется уравнением. META II, как и другие языки программирования, переполняет свой стек при попытке левой рекурсии. META II использует оператор последовательности $ (ноль или более). Уравнение синтаксического анализа expr, записанное в META II, представляет собой условное выражение, вычисляемое слева направо:
выражение = термин $ ( '+' термин . OUT (' ДОБАВИТЬ ') / '-' термин . OUT (' SUB '));
Вышеупомянутое уравнение expr определяется выражением справа от '='. Вычисляя слева направо от '=', term - это первое, что необходимо проверить. Если термин возвращает отказ, выражение не работает. В случае успеха, термин был распознан, мы затем вводим неопределенный $ ноль или более цикл, где мы сначала проверяли на '+', если это не удается, выполняется попытка альтернативы '-' и, наконец, если '-' не был распознан, цикл завершается с expr возвращение успеха, узнав один термин. Если «+» или «-» были успешными, то будет вызываться термин. И в случае успеха цикл повторяется. Уравнение expr также может быть выражено с использованием вложенной группировки как:
выражение = термин $ (( '+' / '-' ) термин );
Элементы производства кода были опущены, чтобы упростить пример. Из-за ограниченного набора символов ранних компьютеров персонаж /
использовался как альтернативный, или, оператор. Оператор $
цикла используется для сопоставления нуля или большего количества чего-либо:
выражение = термин $ ( '+' термин . OUT (' ДОБАВИТЬ ') / '-' термин . OUT (' SUB ') );
Вышеупомянутое может быть выражено на английском языке: expr - это термин, за которым следует ноль или более (плюс термин или минус термин). Шорре описывает это как повышение эффективности, но, в отличие от наивного компилятора рекурсивного спуска, он также гарантирует правильность ассоциативности арифметических операций:
выражение = термин $ ( '+' термин . OUT (' ДОБАВИТЬ ') / '-' термин . OUT (' SUB ') ); термин = коэффициент $ ( '*' коэффициент . OUT (' MPY ') / '/' коэффициент . OUT (' DIV ') ); factor = ( . ID / . NUMBER / '(' expr ')') ( '^' factor . OUT (' EXP ') / . EMPTY ););
Имея возможность выразить последовательность с помощью цикла или правой («хвостовой») рекурсии, можно управлять порядком оценки.
Правила синтаксиса кажутся декларативными, но на самом деле они становятся императивными из-за их семантических спецификаций.
Операция
META II выводит ассемблерный код для стековой машины. Это похоже на использование калькулятора RPN .
выражение = термин $ ( '+' термин . OUT (' ДОБАВИТЬ ') / '-' термин . OUT (' SUB ')); термин = коэффициент $ ( '*' коэффициент . OUT (' MPY ') / '/' коэффициент . OUT (' DIV ')); фактор = (. ID . OUT (' LD ' *) / . NUM . OUT (' LDL ' *) / '(' expr ')') ( '^' factor . OUT (' XPN ' /. EMPTY );
В приведенных выше .ID и .NUM есть встроенные распознаватели токенов. * в продукте кода .OUT ссылается на последний распознанный токен. При распознавании числа с помощью .NUM .OUT ('LDL' *) выводит инструкцию load literal после числа. Выражение:
- (3 * а ^ 2 + 5) / б
сгенерирует:
LDL 3 LD a LDL 2 XPN MPY LDL 5 ADD LD b DIV
META II является в первую документированную версию metacompiler , [1] отмечает , как он компилируется в машинный код для одного из самых ранних экземпляров виртуальной машины .
Сама статья - замечательная жемчужина, которая включает в себя ряд отличных примеров, в том числе самонастройку Meta II (все это было сделано на 8K (шестибитном байте) 1401!) », - Алан Кей
Оригинал статьи не находится в свободном доступе, но был перепечатан в журнале доктора Добба (апрель 1980 г.). Переписанный исходный код в разное время предоставлялся (возможно, группой пользователей CP / M). Документ включал в себя листинг описания Meta II, который, в принципе, можно было обработать вручную, чтобы получить интерпретируемую программу в кодах операций виртуальной машины; если это сработало и дало идентичный результат, значит, реализация была правильной.
META II была в основном подтверждением концепции. База для работы.
META II представлен не как стандартный язык , а как отправная точка, на основе которой пользователь может разработать свой собственный « язык » META . [1]
Затем последовали многие «языки» МЕТА. Шорре перешел на работу в System Development Corporation, где он был участником проекта «Компилятор для написания и реализации компиляторов» (CWIC). Язык SYNTAX CWIC построен на META II, добавляя альтернативный оператор обратного поиска, операторы положительного и отрицательного просмотра вперед и запрограммированные уравнения токенов. .OUT
И .LABEL
операции удалены и стек трансформирующие операции :
и !
добавлен. Язык GENERATOR, основанный на LISP 2, обрабатывал деревья, полученные с помощью языка синтаксического анализа SYNTAX. Для генерации кода вызов функции генератора был помещен в уравнение SYNTAX. Эти языки были разработаны членами подгруппы LA ACM SIGPLAN по синтаксически управляемым компиляторам. Примечательно, как Шорре думал о языке META II:
Термин META «язык» с META заглавными буквами используется для обозначения любого компилятора писать язык так развиваться. [1]
Шорре объясняет META II как основу, на которой могут быть разработаны другие «языки» META.
Смотрите также
Заметки
- ^ Игнорирование META I, которое упоминается лишь вскользь в документе META II.
Рекомендации
- ^ a b c d META II ЯЗЫК ПИСЬМА СИНТАКС-ОРИЕНТИРОВАННОГО КОМПИЛЯТОРА (Dewey Val Schorre UCLA Computing Facility, 1964)
- ^ Дьюи, Вэл Шорре (1963). "Синтаксис - Направленный СМАЛГОЛ для 1401". ACM Natl. Конф., Денвер, Колорадо .
- ^ Дьюи, Вэл Шорре (1963). META II: синтаксически-ориентированный язык написания компиляторов (PDF) . UCLA: Вычислительный центр UCLA.