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

UptoLike

ВУЗ: 

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

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

Рубрика: 

205
фигураций, понимая
под конфигурацией тройку (α,w,y), где α∈ (V
N
∪ V
T
∪ T )
*
— магазинная цепочка; w∈ V
T
*
— непросмотренная часть входной цепочки; y
— выходная цепочка, состоящая из номеров правил грамматики G.
Начальная конфигурация есть (T
0
, x, ε). Далее алгоритм действует согласно
следующему описанию.
1: Сдвиг. Пусть текущая конфигурация есть (γT, w, π), где T∈ T —
некоторая LR(k)-таблица, T =(f, g) и пусть f(u) = shift для
FIRST ( ).
G
k
uw∈
1.1. Случай w ≠ ε:
,waw
′
=
где a ∈ V
T
,
*
T
.wV
′
∈
Ïðè ( ) :ga T
′
=
LR(k)-анализатор совершает переход
,,) , ,) , ,),Tw Taw TaT w
′
′′
(γ π = (γ π −− (γ π
воспроизводящий сдвиг.
При g(a) = error. Анализатор сигнализирует об ошибке и останавливается.
1.2. Случай w
= ε: u = ε и f(u) = f(ε) = error.
Так как сдвиг из пустой цепочки в магазин невозможен, анализатор
сигнализирует об ошибке и останавливается.
2: Cвёртка. Пусть текущая конфигурация есть (γTX
1
T
1
X
2
T
2
…X
m
T
m
, w, π),
где
T,T
1
,T
2
,…,T
m
∈ T — некоторые LR(k)-таблицы; T
m
= ( f
m
, g
m
), f
m
(u) = reduce i,
A → α — i-е правило из множества правил P, где α = X
1
X
2
…X
m
— основа,
FIRST ( ),
G
k
uw=
и пусть T = ( f, g).
2.1. Случай
() ,ga T
′
=
где T
′
∈
T — некоторая LR(k)-таблица.
Анализатор совершает переход
11 2
( ... ,,) ( ,, ) ( ,, ) ,
mm
TX T X X T w TA w i TAT w i−− −−
′
γπγπγπ
воспроизводящий свертку.
2.2. Случай g(A) = error.
Анализатор сигнализирует об ошибке и
останавливается.
3: Ошибка. Пусть текущая конфигурация есть (γT, w, π), где T ∈ T —
некоторая LR(k)-таблица;
FIRST ( ),
G
k
uw∈
T = ( f, g) и f(u) = error.
Анализатор сигнализирует об ошибке и останавливается.
4: Приём. Пусть текущая конфигурация есть (T
0
ST, ε, π
R
), T = ( f, g), f (ε) =
accept.
Анализатор сигнализирует о приёме цепочки x и останавливается.
Выходная цепочка π
R
представляет правосторонний анализ цепочки x.
Пример 3.6. Обратимся ещё раз к грамматике из примера 3.1. Как мы
увидим далее, она — LR(1)-грамматика. Она имеет два правила:
1) S → SaSb, 2) S → ε.
Управляющая таблица LR(1)-анализатора, построенная для неё, имеет вид,
представленный табл. 3.3, где пустые клетки соответствуют значениям error.
Свертка в A

Страницы