МЕТА II - META II

МЕТА II это специфичный для домена язык программирования для записи компиляторы. Он был создан в 1963-1964 годах Дьюи Вэл Шорре в UCLA. 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 - это аналитическая грамматика. в ДЕРЕВО-МЕТА В документе эти языки были описаны как редуктивные грамматики.

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

<expr> := <срок> | <expr> <аддоп> <срок>

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

expr = срок       $( '+' срок .ИЗ('ДОБАВИТЬ')        / '-' срок .ИЗ('SUB'));

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

expr = срок $(('+' / '-') срок);

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

expr = срок $(  '+' срок .ИЗ('ДОБАВИТЬ')              / '-' срок .ИЗ('SUB')              );

Вышеупомянутое может быть выражено на английском языке: expr - это термин, за которым следует ноль или более (плюс термин или минус термин). Шорре описывает это как повышение эффективности, но в отличие от наивного рекурсивный спуск компилятор, он также гарантирует, что ассоциативность арифметических операций правильно:

expr = срок $('+' срок .ИЗ('ДОБАВИТЬ')              / '-' срок .ИЗ('SUB')             );срок = фактор $( '*' фактор .ИЗ('MPY')               / '/' фактор .ИЗ('DIV')               );фактор = ( .Я БЫ         / .НОМЕР         / '(' expr ')')         ( '^' фактор .ИЗ('EXP')         / .ПУСТОЙ);

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

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

Операция

META II выводит ассемблерный код для стековой машины. Оценка этого подобна использованию РПН калькулятор. 

expr = срок       $('+' срок .ИЗ('ДОБАВИТЬ')        /'-' срок .ИЗ('SUB'));срок = фактор       $('*' фактор .ИЗ('MPY')       / '/' фактор .ИЗ('DIV'));фактор = (.Я БЫ .ИЗ('LD ' *)          / .NUM .ИЗ('ЛПНП ' *)         / '(' expr ')')          ( '^' фактор .ИЗ('XPN'/.ПУСТОЙ);

В приведенных выше .ID и .NUM есть встроенные распознаватели токенов. * в продукте .OUT кода ссылается на последний распознанный токен. При распознавании числа с помощью .NUM .OUT ('LDL' *) выводит инструкцию load literal после числа. Выражение:

(3 * а ^ 2 + 5) / б

сгенерирует:

      ЛПНП 3      LD  а      ЛПНП 2      XPN      MPY      ЛПНП 5      ДОБАВИТЬ      LD  б      DIV

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

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

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

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

МЕТА II не представлен как стандартный язык, но как отправная точка, из которой пользователь может разрабатывать свои собственные МЕТА "язык".[1]

Затем последовали многие «языки» МЕТА. Шорре пошел работать на Корпорация системного развития где он был участником проекта «Компилятор для написания и реализации компиляторов» (CWIC). Язык SYNTAX CWIC построен на META II, добавляя альтернативный оператор обратного поиска, операторы положительного и отрицательного просмотра вперед и запрограммированные уравнения токенов. В .ИЗ и .МЕТКА операции удалены и операции преобразования стека : <узел> и ! <число> добавлен. Язык ГЕНЕРАТОРА на основе LISP 2 обработал деревья, созданные языком синтаксического анализа SYNTAX. Для генерации кода вызов функции генератора был помещен в уравнение SYNTAX. Эти языки были разработаны членами подгруппы L.A. ACM SIGPLAN по синтаксически управляемым компиляторам. Примечательно, как Шорре думал о языке META II:

Период, термин МЕТА "язык" с МЕТА заглавными буквами используется для обозначения любого компилятора, пишущего язык так развивалось.[1]

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

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

Примечания

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

Рекомендации

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

внешняя ссылка