МЕТА II

META II — это предметно-ориентированный язык программирования для написания компиляторов . Он был создан в 1963–1964 годах Дьюи Валом Шорре в Калифорнийском университете в Лос-Анджелесе . META II использует то, что Шорре называл синтаксическими уравнениями . Его работа объясняется просто:

Каждое синтаксическое уравнение преобразуется в рекурсивную подпрограмму, которая проверяет входную строку на наличие определенной фразовой структуры и удаляет ее, если она найдена. [1]

Программы Meta II компилируются в интерпретируемый язык байт-кода. Компиляторы VALGOL и SMALGOL, иллюстрирующие его возможности, были написаны на языке META II, [1] [2] VALGOL — это простой алгебраический язык, разработанный для иллюстрации META II. SMALGOL был довольно большим подмножеством ALGOL 60 .

Обозначение

META II была впервые написана в META I, [3] вручную скомпилированной версии META II. История неясна, была ли META I полной реализацией META II или необходимым подмножеством языка META II, необходимым для компиляции полного компилятора META II.

В своей документации META II описывается как напоминающая BNF , которая сегодня объясняется как производственная грамматика. META II — это аналитическая грамматика. В документе TREE-META эти языки были описаны как редуктивные грамматики.

Например, в БНФ арифметическое выражение может быть определено как:

< выражение >  := < термин > | < выражение >  < добавление >  < термин >

Правила BNF сегодня являются правилами производства, описывающими, как составные части могут быть собраны для формирования только допустимых языковых конструкций. Парсер делает противоположное, разбирая языковые конструкции. META II — это язык программирования функциональных парсеров на основе стека , который включает директиву вывода. В META II порядок тестирования задается уравнением. META II, как и другие языки программирования, переполнит свой стек, пытаясь выполнить левую рекурсию. META II использует оператор последовательности $ (ноль или более). Уравнение парсинга expr, записанное в META II, представляет собой условное выражение, вычисляемое слева направо: 

expr =  term  $ (  '+'  term . OUT (' ADD ')  /  '-'  term . OUT (' SUB '));

Выше уравнение expr определяется выражением справа от '='. Оценивая слева направо от '=', term - это первое, что должно быть проверено. Если term возвращает failure, expr терпит неудачу. Если успешно, то term был распознан, то мы входим в неопределенный цикл $ zero или more, где мы сначала проверяем на '+', если это не удается, то пробуем альтернативу '-' и, наконец, если '-' не были распознаны, то цикл завершается с expr, возвращающим success, распознав один term. Если '+' или '-' были успешными, то term будет вызван. И если успешно, то цикл будет повторен. Уравнение expr также можно выразить с помощью вложенной группировки как:

выражение =  термин $ (( '+'  /  '-' )  термин );

Элементы кода производства были опущены для упрощения примера. Из-за ограниченного набора символов ранних компьютеров символ /использовался как альтернативный оператор или. $Оператор цикла , используется для сопоставления нуля или более чего-либо:

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)/б

будет генерировать:

 ЛПНП 3 ЛПНП 2 XPN MPY ЛПНП 5 ДОБАВИТЬ ЛПНП b ДЕЛИТЬ​​

META II — первая документированная версия метакомпилятора [ примечание 1], поскольку он компилирует в машинный код для одного из самых ранних экземпляров виртуальной машины .

Сама статья — это замечательная жемчужина, которая включает в себя ряд превосходных примеров, включая самостоятельную загрузку Meta II (все это было сделано на 8K (шестибитном байте) 1401!)» — Алан Кей

Оригинальная статья не находится в свободном доступе, но была перепечатана в журнале доктора Добба (апрель 1980 г.). Транскрибированный исходный код в разное время был доступен (возможно, группой пользователей CP/M). Статья включала листинг описания Meta II, его в принципе можно было обработать вручную, чтобы получить интерпретируемую программу в кодах операций виртуальной машины; если она запускалась и выдавала идентичный вывод, то реализация была правильной.

META II была по сути доказательством концепции. Базой, с которой можно было работать.

META II не представлен как стандартный язык , а как отправная точка, от которой пользователь может разработать свой собственный « язык » META . [1]

Затем последовало множество «языков» META. Шорре устроился на работу в System Development Corporation , где был членом проекта Compiler for Writing and Implementing Compilers (CWIC). Язык SYNTAX CWIC был построен на META II, добавив альтернативный оператор возврата, положительные и отрицательные операторы опережения и запрограммированные уравнения токенов. Операции .OUTи .LABELбыли удалены, а операции преобразования стека :<node>и !<number> добавлены. Язык GENERATOR, основанный на LISP 2, обрабатывал деревья, созданные языком синтаксического анализа SYNTAX. Для генерации кода вызов функции генератора был помещен в уравнение SYNTAX. Эти языки были разработаны членами подгруппы LA ACM SIGPLAN по компиляторам, направленным на синтаксис. Примечательно, как Шорре думал о языке META II:

Термин «язык» META с заглавными буквами META используется для обозначения любого языка программирования, разработанного таким образом. [1]

Шорре описывает META II как основу, на основе которой могут быть разработаны другие «языки» META.

Смотрите также

Примечания

  1. ^ Игнорируем META I, который лишь вскользь упоминается в документе META II.

Ссылки

  1. ^ abcd META II СИНТАКСИСНО-ОРИЕНТИРОВАННЫЙ ЯЗЫК ДЛЯ НАПИСАНИЯ КОМПИЛЯТОРА (Dewey Val Schorre UCLA Computing Facility 1964)
  2. ^ Дьюи, Вэл Шорре (1963). «Синтаксис — направленный SMALGOL для 1401». ACM Natl. Conf., Денвер, Колорадо .
  3. ^ Дьюи, Вэл Шорре (1963). META II: язык написания компиляторов, ориентированный на синтаксис (PDF) . UCLA: Вычислительный комплекс UCLA.
  • ACM - Статья о META II
  • Учебник: Метакомпиляторы Часть 1
  • Meta II Мета Компилятор
Взято с "https://en.wikipedia.org/w/index.php?title=META_II&oldid=1270492111"