Языки и трансляции. Мартыненко Б.К. - 198 стр.

UptoLike

ВУЗ: 

СПбГУ | Санкт-Петербург

Составители: 

Рубрика: 

196
Алгоритм 2.9: построение магазинного процессора по непростой
семантически однозначной SDTS с входной грамматикой класса LL(k).
Вход: T = (N, Σ, ∆, R, S) — непростая семантически однозначная SDTS с
входной грамматикой G
i
класса LL(k).
Выход: магазинный процессор
P
, такой, что τ(
P
) = τ(T ).
Метод.
Магазинный процессор
P
в своем магазине будет повторять действия
LL(k)-анализатора
A, построенного по входной грамматике схемы T, используя
вместо выходной ленты устройство памяти прямого доступа, в котором он
строит дерево вывода результата трансляции в выходной грамматике схемы.
1. Первоначально
P
имеет запись (S, p
r
)
6
на вершине магазина, где p
r
—
указатель на корневой узел n
r
дерева результата. Этот же указатель
дублируются переменной Root.
2. Если A имеет терминал входной грамматики на вершине магазина и
текущий входной символ (первый символ аванцепочки) — такой же терминал,
то
A совершает pop-движение и процессор
P
делает то же самое.
3. Если A раскрывает нетерминал A (или замещает LL(k)-таблицу,
ассоциированную с A) посредством правила A → X
1
X
2
…X
m
с семантическим
элементом y
0
B
1
y
1
…B
m
y
m
и при этом рядом с этим нетерминалом на вершине
магазина процессора находится указатель на узел n, то процессор
P
делает
следующее:
a) создаёт узлы прямых потомков для n, помеченных слева направо
символами цепочки y
0
B
1
y
1
…B
m
y
m
;
б) на вершине магазина заменяет A (или соответствующую LL(k)-таблицу) и
указатель при нем на цепочку X
1
X
2
… X
m
с указателями при каждом
нетерминале, встречающемся в ней; указатель при X
j
, если это — нетерминал,
указывает на узел, созданный для B
i
, если X
j
и B
i
связаны в правиле схемы A →
X
1
X
2
…X
m
, y
0
B
1
y
1
…B
m
y
m
.
4. Если магазин процессора пуст к моменту достижения конца входной
цепочки, то он принимает ее. Выход есть дерево с корнем n
r
, построенное
процессором. Его расположение зафиксировано переменной Root.
Можно показать, что такой алгоритм реализует правильную трансляцию и
что на подходящей машине прямого доступа он может быть выполнен за
время, линейно зависящее от длины входа.
Теорема 2.12. Алгоритм 2.9 строит магазинный процессор, выдающий в
качестве выхода дерево, метки листьев которого, выписанные слева направо,
представляют результат трансляции входной цепочки.
6
В случае использования LL(k)-таблиц вместо начального нетерминала S будет
использоваться начальная LL(k)-таблица T
0
= T
S, {ε}
.

Страницы