Разработка компиляторов - тест 15

Выбор инструкций - это:

В задачу выбора инструкций входит:

Для решения задачи построения генератора кода применяется теория:

Деревянные языки позволяют описать:

Выписыванием пометок вершин при простом обходе дерева слева-направо и сверху-вниз можно получить:

Через root(t) обозначается:

Для определения операции подстановки, в одном из двух деревьев выбирается лист, который затем:

Одним из способов задания деревянных языков являются:

Деревянная грамматика в нормальной форме - это четверка, содержащая:

В отличие от обычных контекстно-свободных грамматик, в деревянной грамматике в правой части правила находится:

В деревянном образце нетерминалами могут быть помечены:

Тривиальное дерево, состоящее из одной вершины, является:

Правила грамматики в нормальной форме содержат в правой части:

Образцом в данной последовательности троек:(p1,v1,R1),(p2,v2,R2),…,(pk,vk,Rk)будет:

Данная грамматика:G=(A, N, Expr, R)
A={‘+’, ‘-’, const, var}
N={Expr, Opnd}
R={
Opnd: const,				
Opnd: var,				
Expr: Opnd				
Expr: ‘+’ (Expr, Expr),			
Expr: ‘-’ (Expr)				
}порождает деревья выражений из:

Две грамматики назовем эквивалентными, если совпадают:

Любая деревянная грамматика может быть приведена к эквивалентной:

Для деревянной грамматики, у которой в правой части правил находятся образцы произвольного вида, существует:

Для представления множества выводов можно построить разметку C, которая вершине дерева v и нетерминалу K сопоставляет:

Чтобы проверить применимость правила для текущей вершины, проверяется соответствие этой вершины образцу в правой части правила - для этого используется функция:

После вывода нового нетерминала в разметке строится ее замыкание относительно цепных правил с помощью функции:

Пусть задана грамматика G=(A,N,S,R) и дерево t. Индукцией по числу шагов можно доказать, что приведенный алгоритм действительно:

Дерево t выводится в грамматике G=(A,N,S,R) тогда и только тогда, когда:

Деревянные грамматики лежат в основе:

BURS на сегодняшний день являются одним из наиболее распространенных способов описания:

BURS позволяет построить алгоритм выбора инструкций, который:

Деревянные грамматики представляются естественным выбором как механизм описания выбора команд, поскольку являются:

В системе восходящего переписывания деревьев язык интерпретируется как:

Поскольку системы команд предоставляют большое разнообразие способов вычислений, ожидается, что:

В грамматиках восходящего переписывания каждое правило описывает либо:

Поскольку BURS-грамматика однозначна, каждый нетерминал может быть выведен:

Стоимость вывода аддитивна относительно:

Построение замыкания по цепным правилам аналогично:

Извлечение оптимального вывода из разметки - это:

Действия на каком шаге позволяют от исходного размеченного дерева перейти к дереву, в котором вершины уже соответствуют машинным инструкциям, но их операнды еще известны не полностью:

Входной файл lburg поделен на следующие секции: