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

UptoLike

ВУЗ: 

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

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

Рубрика: 

195
На рис. 2.3,a представлена начальная конфигурация магазинного
процессора. В магазине кроме маркера “дна” магазина находится только
начальная LL(k)-таблица T
0
с указателем p
0
на корень строящегося дерева
вывода в выходной грамматике результата трансляции входной цепочки. Этот
указатель запоминается также в отдельной переменной (Root), чтобы через
него получить доступ к дереву после его построения.
На рис. 2.3,б представлена промежуточная конфигурация магазинного
процессора, когда часть дерева вывода построена. Среди его листьев находится
вершина, помеченная нетерминалом A. В рассматриваемый момент на вершине
магазина находится LL(k)-таблица T
A,L
с указателем p на вершину дерева
вывода, к которой будет пристроено поддерево, представляющее семантиче-
ский элемент правила A → α
1
Bβ
1
, α
2
Bβ
2
, используемого на этом шаге
моделирования вывода. В правиле явно выделена пара связанных вхождений
одного нетерминала (B). Рис. 2.3, в иллюстрирует результат этого шага:
в магазине вместо таблицы T
A,L
помещен образ синтаксической цепочки α
1
Bβ
1
,
а к узлу A пристроен древовидный образ семантической цепочки α
2
Bβ
2
.
Показана связь одного символа T
B ,Y
— образа нетерминала B в синтаксической
цепочке, заместившей в магазине T
A,L
, с узлом B из множества вновь
образованных узлов, составляющих образ семантической цепочки α
2
Bβ
2
.
Указатель q определяет ту вершину, к которой будет “подвешиваться”
древовидный образ семантической цепочки некоторого правила схемы, когда
магазинный символ T
B ,Y
будет замещаться синтаксической цепочкой этого же
правила.
Опишем теперь неформально алгоритм построения магазинного процессора
по
данной схеме, обладающей указанными свойствами.
Рис. 2.3.
$
T
0
, p
0
М
а
г
а
з
и
н
S
Root
а
$
T
A
,
L
, p
М
а
г
а
з
и
н
Root
б
γ
A →
α
1
B
β
1
, α
2
B
β
2
S
в
α
2
β
2
A
$
T
B
,
Y
, q
М
а
г
а
з
и
н
γ
β
S
α
B
А

Страницы