ДЕРЕВО-МЕТА - TREE-META

ДЕРЕВО-МЕТА
Оригинальный автор (ы)Дональд Эндрюс, Джефф Рулифсон
изначальный выпуск1968?

В ДЕРЕВО-МЕТА (или же Дерево Мета, TREEMETA) Система письма переводчика - это компилятор-компилятор система для контекстно-свободные языки первоначально разработан в 1960-х годах. Операторы синтаксического анализа метаязыка напоминают дополненная форма Бэкуса-Наура со встроенными директивами построения дерева. Разбор[1] правила включают расширенное сканирование дерева и конструкции генерации кода.

История

TREE-META сыграла важную роль в развитии Он-лайн система и был перенесен на многие системы, включая Univac 1108, GE 645, SDS-940, ICL 1906A, PERQ и UCSD p-система[2][3].

Пример

Это полный пример программы TREE-META, извлеченной (и непроверенной) из более полного (объявления, условия и блоки) примера в Приложении 6 к руководству ICL 1900 TREE-META.[4] В этом документе также есть определение TREE-META в TREE-META в Приложении 3. Эта программа не только распознает, но и выводит язык ассемблера для входа. Он демонстрирует одну из ключевых функций TREE-META - сопоставление с образцом дерева. Он используется как на LHS (например, GET и VAL), так и на RHS (ADD и SUB).

% Это комментарий в стиле АЛГОЛА, разделенный%

% ====================== ПРАВИЛА ВВОДА PARSE =======================% .META PROG% Требуется программа, определяющая правила вождения. %% Это правило PROG является драйвером всей программы. % PROG = $ STMT;% $ - это оператор нуля или более. %% PROG (программа) определяется как ноль или более STMT (операторов). % STMT = .ID ': =' AEXP: STORE [2] *;% Анализировать оператор присваивания из источника в дерево. %% ': =' - строковая константа,: STORE создает узел STORE, %% [2] определяет его как имеющий две ветви, то есть STORE [ID, AEXP]. %% * запускает неанализ дерева, начиная с последнего созданного дерева %%, то есть STORE [ID, AEXP], который выводится как результат, а %% удаляется из дерева. % AEXP = FACTOR $ ('+' FACTOR: ADD [2] / '-' FACTOR: SUB [2]);% Здесь у нас есть распознаватель для арифметических '+': ADD и '-': SUB %% построение дерева . [2] снова создает дерево ADD или SUB с двумя ветвями. %% Распознавание откладывается до тех пор, пока не будет проанализирован весь оператор. %% ADD [FACTOR, FACTOR] или SUB [FACTOR, FACTOR]% FACTOR = '-' PRIME: MINUSS [1] / PRIME; PRIME = .ID / .NUM / '(' AEXP ')'? 3? ;%? 3? подсказка для сообщений об ошибках. %% ===================== НЕПРАВИЛЬНЫЕ ПРАВИЛА ВЫВОДА =====================% STORE [ -, -] => GET [* 2] 'STORE' * 1;% * 1 - левая ветвь дерева. * 2 - правый %% GET [* 2] сгенерирует код для загрузки * 2. %% Будет выведена строка 'STORE' %%, за которой следует левая ветвь * 1 символ %% Независимо от * 2, она будет загружена GET [* 2]. % GET [.ID] => 'LOAD' * 1 / [.NUM] => 'LOADI' * 1 / [MINUSS [.NUM]] => 'LOADN' * 1: * 1 / [-] => * 1;% Здесь просто загружается .ID или .NUM. Узел MINUSS %%, содержащий .NUM, будет использовать это, обозначение * 1: * 1 означает %% первую ветвь (.NUM) первой ветви (MINUSS). %% Все остальное будет передано для распознавания узла %% Неанализируемые правила деконструируют дерево, выводя код. % ADD [-, -] => SIMP [* 2] GET [* 1] 'ADD' VAL [* 2] / SIMP [* 1] GET [* 2] 'ADD' VAL [* 1] / GET [* 1] 'СОХРАНИТЬ T +' <ВЫХ [A]; A <-A + 1> / GET [* 2] 'ADD T +' ;% Chevron <> обозначают арифметическую операцию, например, %% сгенерировать смещение A относительно базового адреса T.% SUB [-, -] => SIMP [* 2] GET [* 1] 'SUB' VAL [* 2] / SIMP [* 1] GET [* 2] 'NEGATE'% 'ADD' VAL [* 1] / GET [* 2] 'STORE T +'  / GET [* 1] 'SUB T +' ;% Символ процента в правиле неразборчивого анализа указывает на новую строку. % SIMP [.ID] => .EMPTY / [.NUM] => .EMPTY / [MINUSS [.NUM]] => .EMPTY; VAL [.ID] => '' * 1 / [.NUM] => 'I' * 1 / [MINUSS [.NUM]] => 'N' * 1: * 1; MINUSS [-] => GET [* 1] 'NEGATE'; .END

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

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

  1. ^ Дональд И. Эндрюс, Дж. Ф. Рулифсон (1967). Tree Meta (рабочий проект): мета-компилятор для SDS 940, Стэнфордский исследовательский институт, Менло-Парк, Калифорния. Коллекция Энгельбарта, Архив Стэнфордского университета, M 638, Box 16, Folder 3.
  2. ^ Боулз, К. Л., 1978. (Почти) машинно-независимая программная система для микро- и мини-компьютеров. SIGMINI Newsl., 4 (1), 3–7. [1] Дои:10.1145/1041256.1041257
  3. ^ Боулз, К. Л., 1978. (Почти) машинно-независимая программная система для микро- и мини-компьютеров. Byte Magazine, май 1978 г., том 03, номер 05, стр. 46, стр. 170-173. archive.org сканирование
  4. ^ Хопгуд, Ф. Р. А. 1974, "Руководство по TREE-META", Компьютерная лаборатория Атласа.

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