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

UptoLike

ВУЗ: 

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

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

Рубрика: 

199
замещается правой частью правила номер p
i
. Индекс rm (right-most) под
стрелкой означает, что замещается крайний
правый нетерминал.
Последовательность номеров правил π
R
= p
n
…p
2
p
1
называется правосто-
ронним анализом цепочки x.
Задача анализатора типа “снизу—вверх”, называемого также восходящим
анализатором, состоит в том, чтобы найти правосторонний анализ данной
входной цепочки x в данной КС-грамматике G. Как было сказано, исходная
сентенциальная
форма, с которой анализатор начинает работу, есть α
n
= x. Далее
он должен строить последующие сентенциальные формы и заканчивать свою
работу тогда, когда будет построена последняя сентенциальная форма α
0
= S.
Рассмотрим один шаг работы такого анализатора. Пусть α
i
= αAw —
текущая сентенциальная форма правостороннего вывода. Эта форма
получается из предыдущей: α
i –1
= γBz ⇒ γβAyz = αAw = α
i
посредством правила
вида B → βAy, где α = γβ, w = yz. Как всюду в этом пособии мы обозначаем
прописными буквами латинского алфавита нетерминалы, строчными латин-
скими буквами из конца алфавита — терминальные цепочки, а греческими
буквами — цепочки над терминальными и нетерминальными символами.
Размещение сентенциальной формы в восходящем анализаторе показано в
табл. 3.1. Восходящий анализатор располагает текущую сентенциальную
форму α
i
в магазине и на входной ленте таким образом, что в магазине
располагается открытая её часть, а закрытая представлена ещё не прочитанной
частью входной цепочки, которая начинается с текущего входного символа и
простирается до конца этой цепочки.
Таблица 3.1
№ Магазин Вход
1
α
i
= αA
w
2
γβA
yz
3
γβAy
z
4
α
i –1
= γB
z
В строке 1 табл. 3.1 представлено расположение текущей сентенциальной
формы α
i
, в строке 2 — то же самое, но более детально. Предполагается, что
вершина магазина расположена справа, а текущий входной символ — слева.
Анализатор посимвольно сдвигает часть входной цепочки в магазин пока не
достигнет правой границы цепочки, составляющей правую часть правила, при
помощи которого данная сентенциальная форма α
i
была получена из
предыдущей α
i –1
. В строке 3 представлено размещение сентенциальной формы
после сдвига в магазин части входа — цепочки y. Далее анализатор
сворачивает часть цепочки, примыкающую к вершине магазина и
совпадающую с правой частью упомянутого правила, в нетерминал левой
части этого правила. В строке 4 приведен результат свертки цепочки βAy,
располагавшейся на предыдущем шаге в верхней части магазина, в
нетерминальный символ B посредством правила B →βAy. Цепочка,
подлежащая свертке, называется основой. В таблице 3.1 она подчеркнута в
строке 3.

Страницы