ДЕРЕВО-МЕТА
| Оригинальный автор(ы) | Дональд Эндрюс, Джефф Рулифсон |
|---|---|
| Первоначальный выпуск | 1968? |
Система письма переводчика TREE-META (или Tree Meta , TREEMETA ) — это система компилятора-компилятора для контекстно-свободных языков, первоначально разработанная в 1960-х годах. Операторы синтаксического анализа метаязыка напоминают расширенную форму Бэкуса-Наура со встроенными директивами построения дерева. Разбор [1] правила включают обширные конструкции сканирования деревьев и генерации кода.
История [ править ]
TREE-META сыграла важную роль в разработке NLS (on-Line System) и была портирована на многие системы, включая 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).
% Это комментарий в стиле ALGOL, разделенный знаком %.
% ====================== INPUT PARSE RULES ======================= %
.META PROG
% A program defining driving rule is required. %
% This PROG rule is the driver of the complete program. %
PROG = $STMT ;
% $ is the zero or more operator. %
% PROG (the program) is defined as zero or more STMT (statements). %
STMT = .ID ':=' AEXP :STORE[2]*;
% Parse an assignment statement from the source to the tree. %
% ':=' is a string constant, :STORE creates a STORE node, %
% [2] defines this as having two branches i.e. STORE[ID,AEXP]. %
% * triggers a unparse of the tree, Starting with the last created %
% tree i.e. the STORE[ID,AEXP] which is emitted as output and %
% removed from the tree. %
AEXP = FACTOR $('+' FACTOR :ADD[2] / '-' FACTOR :SUB[2]);
% Here we have the recognizer for arithmetic '+' :ADD and '-' :SUB %
% tree building. Again the [2] creates a 2-branch ADD or SUB tree. %
% Unparsing is deferred until an entire statement has been parsed. %
% ADD[FACTOR,FACTOR] or SUB[FACTOR,FACTOR] %
FACTOR = '-' PRIME :MINUSS[1] / PRIME ;
PRIME = .ID / .NUM / '(' AEXP ')' ?3? ;
% ?3? is a hint for error messages. %
% ===================== OUTPUT UNPARSE RULES ===================== %
STORE[-,-] => GET[*2] 'STORE ' *1 ;
% *1 is the left tree branch. *2 is the right %
% GET[*2] will generate code to load *2. %
% The 'STORE' string will be output %
% followed by left branch *1 a symbol %
% Whatever *2, it will be loaded by GET[*2]. %
GET[.ID] => 'LOAD ' *1 /
[.NUM] => ' LOADI ' *1 /
[MINUSS[.NUM]] => 'LOADN ' *1:*1 /
[-] => *1 ;
% Here an .ID or a .NUM will simply be loaded. A MINUSS node %
% containing a .NUM will have this used, the notation *1:*1 means %
% the first branch (a .NUM) of the first branch (MINUSS). %
% Anything else will be passed on for node recognition %
% The unparse rules deconstruct a tree outputing code. %
ADD[-,-] => SIMP[*2] GET[*1] 'ADD' VAL[*2] /
SIMP[*1] GET[*2] 'ADD' VAL[*1] /
GET[*1] 'STORE T+' < OUT[A] ; A<-A+1 > /
GET[*2] 'ADD T+' < A<-A-1 ; OUT[A] > ;
% Chevrons < > indicate an arithmetic operation, for example to %
% generate an offset A relative to a base address T. %
SUB[-,-] => SIMP[*2] GET[*1] 'SUB' VAL[*2] /
SIMP[*1] GET[*2] 'NEGATE' % 'ADD' VAL[*1] /
GET[*2] 'STORE T+' < OUT[A] ; A<-A+1 > /
GET[*1] 'SUB T+' < A<-A-1 ; OUT[A] > ;
% A percent character in an unparse rule indicates a newline. %
SIMP[.ID] => .EMPTY /
[.NUM] => .EMPTY /
[MINUSS[.NUM]] => .EMPTY;
VAL[.ID] => ' ' *1 /
[.NUM] => 'I ' *1 /
[MINUSS[.NUM]] => 'N ' *1:*1 ;
MINUSS[-] => GET[*1] 'NEGATE' ;
.END
См. также [ править ]
Ссылки [ править ]
- ^ Дональд И. Эндрюс, Дж. Ф. Рулифсон (1967). Мета дерева (рабочий проект): метакомпилятор для SDS 940 , Стэнфордский исследовательский институт, Менло-Парк, Калифорния. Коллекция Энгельбарта, Архив Стэнфордского университета, M 638, ящик 16, папка 3.
- ^ Боулз, К.Л., 1978. (Почти) машинно-независимая система программного обеспечения для микро- и мини-компьютеров. SIGMINI Newsl., 4 (1), 3–7. дои : 10.1145/1041256.1041257
- ^ Боулз, КЛ (май 1978 г.). «UCSD Pascal: (почти) машинно-независимая система программного обеспечения для микро- и мини-компьютеров» . Байт . Том. 3, нет. 5. стр. 46, 170–173 – в Интернет-архиве.
{{cite magazine}}: CS1 maint: дата и год ( ссылка ) - ^ Хопгуд, FRA 1974, «Руководство TREE-META», Компьютерная лаборатория Атласа.
- К. Стивен Карр, Дэвид А. Лютер, Шериан Эрдманн, Система компилятора-компилятора TREE-META: система метакомпилятора для Univac 1108 и General Electric 645 [ мертвая ссылка ] , Технический отчет Университета Юты RADC-TR-69-83.
- [1] [ мертвая ссылка ] , а также [2] Технический отчет Энглбарта, Инглиша и Рулифсона за 1968 год об использовании Tree Meta в так называемых языках специального назначения (SPL), которые мы теперь называем предметно-специфичными языками (DSL) в NLS.
- Дональд И. Эндрюс, Дж. Ф. Рулифсон (1967). Мета дерева (рабочий проект): метакомпилятор для SDS 940 , Стэнфордский исследовательский институт, Менло-Парк, Калифорния. Коллекция Энгельбарта, Архив Стэнфордского университета, M 638, ящик 16, папка 3.
- ЭНДРЮС, ЛЕКТМАН и 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 Model 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.