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

UptoLike

ВУЗ: 

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

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

Рубрика: 

200
Итак, один шаг работы анализатора типа “снизу—вверх” состоит в
последовательном сдвиге символов из входной цепочки в магазин до тех пор,
пока не достигается правая граница основы, а затем у него должна быть
возможность однозначно определить, где в магазине находится левая граница
основы и по какому правилу (к какому нетерминалу) свернуть её. Таким
образом, он воспроизводит предыдущую сентенциальную форму правосторон-
него вывода анализируемой цепочки. Если задача решается детерминирован-
ным анализатором, то свойства КС-грамматики, в которой производится
анализ, должны гарантировать упомянутую однозначность,
Процесс заканчивается, когда в магазине остаётся один символ S, а входная
цепочка прочитана вся.
Замечание 3.1. Если S
αAw, то основа β не может быть в пределах α.
Действительно, если бы
α = α
1
βα
2
, то предыдущая сентенциальная форма имела бы
вид
α
1
Bα
2
Aw и из неё текущая получалась бы заменой нетерминала B на β. Но символ
B не является крайним правым нетерминалом, что противоречило бы предположению
о том, что мы имеем дело с правосторонним выводом. Однако, основа могла бы быть в
пределах цепочки
w или даже цепочки Aw.
Пример 3.1. Пусть G = (V
N
, V
T
, P, S) — контекстно-свободная грамматика,
в которой V
N
= {S}, V
T
= {a, b}, P = {(1) S → SaSb, (2) S →ε}.
Рассмотрим правосторонний вывод в этой грамматике:
(1) (1) () () ()
222
rm rm rm rm rm
.S SaSb SaSaSbb SaSabb Saabb aabb⇒⇒ ⇒ ⇒ ⇒
Здесь π
R
= 22211 — правосторонний анализ цепочки x = aabb.
Последовательность конфигураций восходящего анализатора во время
разбора этой цепочки показана в табл. 3.2.
Таблица 3.2
№ Магазин Вход Действие
1 $ aabb reduce 2
2 $S aabb shift
3 $Sa abb reduce 2
4 $SaS abb shift
5 $SaSa bb reduce 2
6 $SaSaS bb shift
7 $SaSaSb b reduce 1
8 $SaS b shift
9 $SaSb reduce 1
10 $S
“Дно” магазина отмечено маркером $. Исходная конфигурация
характеризуется тем, что магазин пуст (маркер “дна” не считается),
непросмотренная часть входа — вся цепочка
aabb. Первое действие — свёртка
пустой основы на вершине магазина по правилу 2. Это приводит к
конфигурации, показанной в строке 2. Следующее действие по команде shift —
сдвиг: текущий символ a перемещается с входа на вершину магазина.
Положение вершины магазина тоже изменяется, как и текущий входной
символ. Эта конфигурация представлена в строке 3. Дальнейшие действия
“сдвиг—свёртка” в конце концов приводят к заключительной конфигурации: в
rm
*
⇒

Страницы