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

UptoLike

ВУЗ: 

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

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

Рубрика: 

234
§ 3.9. Простые непостфиксные
синтаксически управляемые LR-трансляции
Предположим, что имеется простая, но не постфиксная SDTS, входная
грамматика которой есть LR(k)-грамматика. Как реализовать такой перевод?
Один из возможных методов состоит в использовании многопросмотровой
схемы перевода на базе нескольких dpdt.
Пусть T = (N, Σ, ∆, R, S) — простая семантически однозначная
SDTS с
входной LR(k)-грамматикой G. Для реализации трансляции, задаваемой схемой
T, можно построить четырехуровневую схему перевода (рис. 3.3).
Первый уровень занимает dpdt P
1
. Его входом служит входная цепочка w$,
а выходом π
R
— правосторонний анализ цепочки w.
На втором уровне dpdt P
2
обращает цепочку π
R
. Для этого ему достаточно
поместить всю цепочку π
R
в магазин типа last-in-first-out и прочитать её из
магазина, выдавая на выход. Получается цепочка π — последовательность
номеров правил правостороннего вывода входной цепочки w. На следующем
этапе она используется для порождения соответствующей инвертированной
выходной цепочки правосторонним выводом в выходной грамматике схемы T.
Входом для третьего уровня служит цепочка π. Выход — перевод,
определяемый простой SDTS
(,,, ,),TN RS
′
′′
=
Σ∆
где
R
′
содержит правило вида
A → iB
m
B
m –1
...B
1
, y
m
B
m
y
m –1
B
m –1
...y
1
B
1
y
0
тогда и только тогда, когда A → x
0
B
1
x
1
...B
m
x
m
, y
0
B
1
y
1
...B
m
y
m
— правило из R, а
правило A → x
0
B
1
x
1
...B
m
x
m
есть правило номер i входной LR(k)-грамматики.
Нетрудно доказать, что (, ) ( )
R
yT
′
π∈τтогда и только тогда, когда
Схема
T
′
— это простая SDTS, основанная на LL(1)-грамматике, и,
следовательно, её можно реализовать посредством dpdt P
3
.
На четвертом уровне dpdt P
4
просто обращает цепочку y
R
— выход P
3
,
записывая его в магазин типа first-in-last-out, а затем выдавая цепочку y из
магазина на свой выход.
Число основных операций, выполняемых на каждом уровне, пропор-
ционально длине цепочки w. Таким образом, можно сформулировать
следующий результат:
Теорема 3.9. Трансляция, задаваемая простой семантически однозначной
схемой синтаксически управляемой трансляции с входной LR(k)-грамматикой,
может быть реализована за время, пропорциональное длине входной цепочки.
Доказательство представляет собой формализацию вышеизложенного.
P
4
y
R
y
π
R
π
P
2
P
1
w$
π
R
P
3
π
y
R
(,) (,).
rm
SS wy
π
⇒
Рис. 3.3.

Страницы