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