Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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 ')  ); фактор =  (  . ID  /  . НОМЕР  /  '('  выражение ')') (  коэффициент '^'  . OUT (' EXP ') / . EMPTY );

Имея возможность выразить последовательность с помощью цикла или правой («хвостовой») рекурсии, можно управлять порядком оценки.

Правила синтаксиса кажутся декларативными, но на самом деле их семантические спецификации делают их императивными.

Операция [ править ]

META II выводит ассемблерный код для стековой машины. Это похоже на использование калькулятора RPN . 

выражение =  термин  $ ( '+'  термин . OUT (' ДОБАВИТЬ ')  / '-'  термин . OUT (' SUB ')); термин =  коэффициент  $ ( '*'  коэффициент . OUT (' MPY ')  /  '/'  коэффициент . OUT (' DIV ')); фактор =  (. ID . OUT (' LD '  *)  /  . NUM . OUT(' LDL '  *)  /  '('  expr ')')  (  '^'  множитель . 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операции удалены и стек трансформирующие операции :<node>и !<number> добавлен. Язык ГЕНЕРАТОРА на основе LISP 2обработал деревья, созданные языком синтаксического анализа SYNTAX. Для генерации кода вызов функции генератора был помещен в уравнение SYNTAX. Эти языки были разработаны членами подгруппы LA ACM SIGPLAN по синтаксически управляемым компиляторам. Примечательно, как Шорре думал о языке META II:

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

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

См. Также [ править ]

Заметки [ править ]

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

Ссылки [ править ]

  1. ^ a b c d META II ЯЗЫК ПИСЬМА СИНТАКС-ОРИЕНТИРОВАННОГО КОМПИЛЯТОРА (Dewey Val Schorre UCLA Computing Facility, 1964)
  2. ^ Дьюи, Вэл Шорре (1963). "Синтаксис - Направленный СМАЛГОЛ для 1401". ACM Natl. Конф., Денвер, Колорадо .
  3. ^ Дьюи, Вэл Шорре (1963). META II: синтаксически-ориентированный язык написания компиляторов (PDF) . UCLA: Вычислительный центр UCLA.

Внешние ссылки [ править ]

  • ACM - Бумага о META II
  • Учебник: метакомпиляторы, часть 1
  • Мета-компилятор Meta II