Составители:
198
Рис. 3.1.
Глава 3
LR(k)-ГРАММАТИКИ И ТРАНСЛЯИИ
§ 3.1. Синтаксический анализ
типа “снизу—вверх”
В предыдущей главе был рассмотрен класс LL(k)-грамматик, наибольший
подкласс КС-грамматик, естественным образом детерминированно анализируемых
в технике “сверху—вниз”, которая предполагает последовательное построение
сентенциальных форм левостороннего вывода, начиная с начальной формы S,
причём S — начальный нетерминал грамматики, и заканчивая конечной
формой — анализируемой терминальной цепочкой. Один шаг этого процесса
состоит в определении того правила, правая часть которого должна
использоваться для замены крайнего левого нетерминала в текущей
сентенциальной форме, чтобы получить следующую сентенциальную форму.
Именно, если wAα — текущая сентенциальная форма, где w — закрытая часть,
Aα — открытая часть и x — анализируемая цепочка, то правило определяется
по нетерминалу A, множеству допустимых локальных правых контекстов
()
FIRST
G
k
L
α
=
и аванцепочке
(),
FIRST
G
k
y
u ∈
причём
x = wy. Адекватный тип
анализатора — k-предсказывающий алгоритм анализа, выполняя эти шаги,
воспроизводит открытые части сентенциальных форм в своём магазине.
В альтернативной терминологии такого рода анализатор выстраивает
дерево вывода анализируемой цепочки, начиная с корня и на каждом шаге при-
страивая очередное поддерево к крайнему левому нетерминальному листу
строящегося дерева (рис. 3.1).
В противоположность этому подходу техника анализа “снизу—вверх”
основана на воспроизведении сентенциальных форм правостороннего вывода,
начиная с последней — анализируемой цепочки и заканчивая первой —
начальным нетерминалом грамматики. Именно, пусть
12
() () () ()
0
1
rm rm rm rm
... ...
i
n
pppp
n
Sx=α ⇒α ⇒ ⇒ ⇒α =
— правосторонний вывод терминальной
цепочки x в некоторой КС-грамматике.
Индекс p
i
(i = 1, 2,…, n) над стрелкой
означает, что на данном шаге нетерминал текущей сентенциальной формы α
i –1
w
α
z
β
S
A
B
A → zB
β
Страницы
- « первая
- ‹ предыдущая
- …
- 198
- 199
- 200
- 201
- 202
- …
- следующая ›
- последняя »
