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

UptoLike

ВУЗ: 

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

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

Рубрика: 

194
9. δ([v$], ε, b’) = ([v$], ε, b), b∈∆, u∈Σ
*
k–1
— моделирование pass-движения при
короткой аванцепочке.
10. δ([$], ε, $) = ([ε], ε, ε) — моделирование перехода в принимающую кон-
фигурацию.
То, что построенный dpdt P действительно точно моделирует k-пред-
сказывающий алгоритм трансляции ℑ, нетрудно доказать индукцией по числу
движений типа 1 того и другого устройств.
2.11. Непростые LL(k)-трансляции
и магазинные процессоры
Пусть T = (N, Σ, ∆, R, S) — непростая семантически однозначная SDTS с
входной грамматикой G
i
класса LL(k). Для реализации такой трансляции можно
ввести ещё одну модификацию k-предсказывающего алгоритма анализа,
называемую магазинным процессором.
Магазинный процессор ведет анализ входной цепочки во входной
грамматике и генерирует дерево вывода выходной цепочки в выходной
грамматике. Другими словами, он моделирует вывод элемента трансляции,
используя магазин для манипуляции над синтаксическими цепочками трансля-
ционных форм, а семантические цепочки этих форм представляет в виде дерева
вывода в выходной грамматике, разрастающегося в ходе вывода. В тот момент,
когда в процессе анализа он воспроизводит шаг замены крайнего левого
нетерминала в синтаксической цепочке текущей трансляционной формы,
происходит пристраивание
вершин, помеченных символами соответствующей
семантической цепочки используемого правила схемы к вершине дерева
вывода, представляющей связанное вхождение одноименного нетерминала в
семантической цепочке трансляционной формы.
Чтобы следить за связями между нетерминалами синтаксической цепочки
текущей трансляционной формы с соответствующими вершинами дерева,
представляющего семантические цепочки, используются указатели, хранимые
в магазине анализатора при нетерминалах или LL(k)-таблицах, ассоциирован-
ных с ними.
Когда нетерминал (или LL(k)-таблица) на вершине магазина подменяется
цепочкой, представляющей синтаксический элемент правила схемы, указатель,
находящийся при нём (ней), указывает на вершину, к которой надлежит
пристроить новые вершины. Указатели же на эти вновь появившиеся вершины
помещаются в магазин при связанных вхождениях нетерминалов в синтакси-
ческом элементе правила, о котором шла речь.
Проще всего проиллюстрировать работу магазинного процессора
схематически (см. рис. 2.3).

Страницы