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

UptoLike

ВУЗ: 

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

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

Рубрика: 

201
магазине — начальный нетерминал грамматики, и вся входная цепочка
просмотрена. Номера правил при командах свёртки (reduce) образуют
правосторонний анализ входной цепочки aabb.
Не все КС-грамматики поддаются правостороннему анализу посредством
детерминированного механизма типа “перенос—свёртка”.
Мы рассмотрим здесь класс КС-грамматик, которые позволяют однозначно
разрешать упомянутые проблемы путём заглядывания на k символов,
следующих за основой. Именно,
(1) производить сдвиг или свертку?
(2) если делать свертку, то по какому правилу?
(3) когда закончить процесс?
Этот класс грамматик, открытый Д.Кнутом, называется LR(k)-граммати-
ками. В этом названии L обозначает направление просмотра входной цепочки
слева направо при анализе, R что результатом анализа является инверти-
рованная последовательность номеров правил правосторонного вывода, k —
предельная длина цепочки, следующей за основой.
§ 3.2. LR(k)-Грамматики
В этом параграфе мы дадим строгое определение LR(k)-грамматик и
опишем характерные их свойства.
Определение 3.1. Пусть G = (V
N
, V
T
, P, S) — контекстно-свободная
грамматика. Пополненной грамматикой,
полученной из G, назовем грамматику
NT
(,, ,),GVVPS
′′
′′′
= где
NN NTT
{}; ; ; { }.VV SSVVVPPSS
′′
′′ ′ ′
=∪ ∉ = =∪→
Определение 3.2. Пусть
NT
(,, ,)GVVPS
′′
′
′′
= — пополненная грамматика для
контекстно-свободной грамматики G. Грамматика G является LR(k)-граммати-
кой, если для любых двух правосторонних выводов вида
1)
2)
в которых должно быть αAy = γBx.
Другими словами, α = γ, A = B, y = x.
Говоря неформально, если согласно первому выводу β — основа, сворачи-
ваемая в нетерминал A, то и во втором выводе β должна быть тоже основой,
сворачиваемой в нетерминал A.
Из этого определения следует, что если имеется правовыводимая цепочка
α
i
= αβw, где β — основа, полученная из A, и если αβ = X
1
X
2
…X
r
, то
1) зная первые символы X
1
X
2
…X
j
цепочки αβ и не более, чем k следующих
символов цепочки X
j + 1
X
j + 2
…X
r
w, мы можем быть уверены, что правый конец
основы не будет достигнут до тех пор, пока j ≠ r ;
2) зная цепочку αβ = X
1
X
2
…X
r
и не более k символов цепочки w, мы можем
быть уверены, что именно β является основой, сворачиваемой в нетерминал A;
3) если можно сигнализировать о выводимости исходной терми-
нальной цепочки из
S
′
и, следовательно, из S.
rm rm
*
,SBx y
′
⇒γ ⇒αβ
rm rm
*
,SAw w
′
⇒α ⇒αβ
1
,
i
S
−
′
α=
() (),
FIRST FIRST
GG
kk
wy=

Страницы