ДЕРЕВО-МЕТА

ДЕРЕВО-МЕТА
Оригинальный автор(ы)	Дональд Эндрюс, Джефф Рулифсон
Первоначальный выпуск	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 года.

Внешние ссылки

[SDS940-1] Дональд И. Эндрюс, Дж. Ф. Рулифсон (1967). Мета дерева (рабочий проект): метакомпилятор для SDS 940 , Стэнфордский исследовательский институт, Менло-Парк, Калифорния. Коллекция Энгельбарта, Архив Стэнфордского университета, M 638, ящик 16, папка 3.

[Bowles-2] Боулз, К.Л., 1978. (Почти) машинно-независимая система программного обеспечения для микро- и мини-компьютеров. SIGMINI Newsl., 4 (1), 3–7. дои : 10.1145/1041256.1041257

[Bowles2-3] Боулз, КЛ (май 1978 г.). «UCSD Pascal: (почти) машинно-независимая система программного обеспечения для микро- и мини-компьютеров» . Байт . Том. 3, нет. 5. стр. 46, 170–173 – в Интернет-архиве. {{cite magazine}}: CS1 maint: дата и год ( ссылка )

[Hopgood-4] Хопгуд, FRA 1974, «Руководство TREE-META», Компьютерная лаборатория Атласа.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]