Система записи транслятора TREE-META (или Tree Meta , TREEMETA ) - это система компилятор-компилятор для контекстно-свободных языков, первоначально разработанная в 1960-х годах. Операторы синтаксического анализа метаязыка напоминают расширенную форму Бэкуса – Наура со встроенными директивами построения дерева. Правила разборки [1] включают в себя обширные конструкции сканирования дерева и генерации кода.
Автор (ы) оригинала | Дональд Эндрюс, Джефф Рулифсон |
---|---|
Первый выпуск | 1968? |
История
TREE-META сыграла важную роль в разработке онлайн -системы и была перенесена на многие системы, включая Univac 1108, GE 645, SDS-940, ICL 1906A, PERQ и UCSD p-System . [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]. %% * запускает неанализ дерева, начиная с последнего созданного%% tree, т.е. STORE [ID, AEXP], который выводится как результат, и%% удален из дерева. %AEXP = FACTOR $ ('+' FACTOR: ADD [2] / '-' FACTOR: SUB [2]);% Здесь у нас есть распознаватель для арифметических '+': ADD и '-': SUB%% построение дерева. [2] снова создает дерево ADD или SUB с двумя ветвями. %% Unparsing откладывается до тех пор, пока не будет проанализирован весь оператор. %% ADD [FACTOR, FACTOR] или SUB [FACTOR, FACTOR]%ФАКТОР = '-' ПРЕМЬЕР: МИНУСЫ [1] / ПРЕМЬЕР;PRIME = .ID / .NUM / '(' AEXP ')'? 3? ;%? 3? подсказка для сообщений об ошибках. % % ===================== НЕПРАВИЛЬНЫЕ ПРАВИЛА ВЫВОДА =====================%СОХРАНИТЬ [-, -] => ПОЛУЧИТЬ [* 2] 'СОХРАНИТЬ' * 1;% * 1 - левая ветвь дерева. * 2 - правильный%% GET [* 2] сгенерирует код для загрузки * 2. %% Будет выведена строка 'STORE'%%, за которым следует левая ветвь * 1 символ%% Неважно * 2, он будет загружен GET [* 2]. %ПОЛУЧИТЬ [.ID] => 'ЗАГРУЗИТЬ' * 1 / [.NUM] => 'ЗАГРУЗИТЬ' * 1 / [MINUSS [.NUM]] => 'ЗАГРУЗИТЬ' * 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] / ПОЛУЧИТЬ [* 1] 'СОХРАНИТЬ Т +' <ВЫХ [А]; A <-A + 1> / GET [* 2] 'ADD T +' ВЫХОД [A]>;% Шевроны <> указывают на арифметическую операцию, например на%% генерирует смещение A относительно базового адреса T.%SUB [-, -] => SIMP [* 2] GET [* 1] 'SUB' VAL [* 2] / SIMP [* 1] GET [* 2] 'NEGATE'% 'ADD' VAL [* 1] / ПОЛУЧИТЬ [* 2] 'STORE T +'A <-A + 1> / GET [* 1] 'SUB T +' ВЫХОД [A]>;% Символ процента в правиле неразборчивого анализа указывает на новую строку. %SIMP [.ID] => .EMPTY / [.NUM] => .EMPTY / [МИНУСЫ [.NUM]] => .EMPTY;VAL [.ID] => '' * 1 / [.NUM] => 'I' * 1 / [MINUSS [.NUM]] => 'N' * 1: * 1;МИНУСЫ [-] => ПОЛУЧИТЬ [* 1] 'ОТРИЦАТЕЛЬНЫЙ';.КОНЕЦ
Смотрите также
Рекомендации
- ^ Дональд И. Эндрюс, JF Rulifson (1967). Tree Meta (рабочий проект): мета-компилятор для SDS 940 , Стэнфордский исследовательский институт, Менло-Парк, Калифорния. Коллекция Энгельбарта, Архив Стэнфордского университета, M 638, Box 16, Folder 3.
- ^ Bowles, KL, 1978. (почти) машинно-независимая программная система для микро- и мини-компьютеров. SIGMINI Newsl., 4 (1), 3–7. [1] ‹См. ТПД› doi : 10.1145 / 1041256.1041257
- ^ Bowles, KL, 1978. (почти) машинно-независимая программная система для микро- и мини-компьютеров. Byte Magazine, май 1978 г., том 03, номер 05, стр. 46, стр. 170-173. archive.org сканирование
- ^ Хопгуд, FRA 1974, "ВАЛ-META Руководство", Atlas Computer Laboratory.
- К. Стивен Карр, Дэвид А. Лютер, Шериан Эрдманн, Система компилятора-компилятора TREE-META: система мета-компилятора для Univac 1108 и General Electric 645 , Технический отчет Университета Юты RADC-TR-69-83.
- [2] , а также [3] Технический отчет 1968 года Энглебарта, Инглиша и Рулифсона об использовании Tree Meta в так называемых языках специального назначения (SPL), которые мы теперь называем предметно-ориентированными языками (DSL), в NLS.
- Дональд И. Эндрюс, Дж. Ф. Рулифсон (1967). Tree Meta (рабочий проект): мета-компилятор для SDS 940 , Стэнфордский исследовательский институт, Менло-Парк, Калифорния. Коллекция Энгельбарта, Архив Стэнфордского университета, M 638, Box 16, Folder 3.
- ЭНДРЮС, LEHTMAN и WHP. «Tree Meta - метакомпилятор для Исследовательского центра Аугментации». Предварительный набросок, 25 марта 1971 г.
- Алан К. Кей, доктор философии по реактивным двигателям . дипломная работа 1969 года в Университете штата Юта. Отмечается, что Анри Гуро создал компилятор FLEX в TREE-META на SRI (Engelbart) SDS-940.
- Ежеквартальный отчет компьютерной лаборатории Атлас (21 ноября 1975 г.), FRA Hopgood документирует работу с использованием TREE-META для создания компилятора, генерирующего выходные данные ассемблера FR80.
- Ежеквартальный отчет компьютерной лаборатории Атласа (12 октября 1973 г.), документы CJ Pavelin (раздел 4.10) TREE-META переносится на 1906A .
- TREE-META: мета-компилятор для модели Interdata 4 от WM Newman. Колледж Королевы Марии, Лондон. Ноябрь 1972 г.
Внешние ссылки
- Руководство для ICL 1900 версии TREE-META от FRA Hopgood.
- Домашняя страница для сбора информации о TREE-META
- Проект документа TREE META, декабрь 1967 г., на сайте bitsavers.org
- Документ о выпуске TREE META, апрель 1968 г., на сайте bitsavers.org
- ИССЛЕДОВАНИЕ РАЗРАБОТКИ МЕТОДОВ УЛУЧШЕНИЯ ИНТЕЛЛЕКТУАЛЬНОСТИ, проведенное Д. К. Энгельбарт
- Реализация TREE-META на C (на основе версии TREE-META для ICL 1900) [ мертвая ссылка ]
- Возрождение компилятора-компилятора TREE-META.
- Страница Semantic Scholar для Дональда Эндрюса.