Стр. 75 - Информационные структуры и их преобразование

Содержание 73
ИНФОРМАЦИОННЫЕ СТРУКТУРЫ И ИХ ПРЕОБРАЗОВАНИЕ
{ }
S,P,,NG
0 0 ∆ называется выходной.
СУ-перевод можно трактовать как метод преобразования деревьев
вывода входной грамматики G1 в деревья вывода выходной грамматики G0.
Перевод цепочки х можно получить, построив дерево вывода, затем
преобразовать это дерево в системе правил выходной грамматики и в
качестве выходной цепочки взять крону выходного дерева.
Алгоритм работы синтаксически управляемого перевода
Вход: СУ – схема с входной грамматикой Gi {N, Σ, Pi, S}и дерево
вывода D.
Выход: Дерево D’ в грамматике G0 {N, ∆, P0, S}.
Шаг 1: Применять шаг 2 начиная с корня D.
Шаг 2: Пусть этот шаг (2) применяется к вершине n, внутренней в
дереве D, и пусть n1, nk – прямые потомки. Пусть А:=α - правило из Pi,
соответствующее вершине n.
Цепочка α образуется конкатенацией меток n1…nk .
Выбрать из R правило А:= α, β и переставить вершины согласно
соответствию, установленному этими правилами.
Применять шаг 2 к вершинам, не являющимся листьями.
Рассмотрим следующий пример, поясняющий алгоритм синтаксически
управляемого перевода:
T= {(S,A), (0,1), (a,b), R, S};






=
=
=
=
=
ASa ,SA0:A
b,1:A
b,1:S
SAa ,AS0:S
R
СУ – схема, у которой в правилах соответствия нетерминалов,
однозначное называется простой.
D:D’: S
0 A S1
0 S A1
0 A S1
S
S A a
A S a
S A a
b
b
b b