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

UptoLike

ВУЗ: 

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

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

Рубрика: 

220
Согласно определению, учитывая вышеприведённый вывод, заключаем,
что LR(k)-ситуация [A →β
1
.β
2
, u] ∈
V
G
k
(γ) допустима для активного префикса γ.
Утверждение II доказано.
Из рассуждений I и II следует справедливость теоремы.
Алгоритм 3.3: построение системы множеств допустимых LR(k)-
ситуаций для данной КС-грамматики.
Вход:
G =(V
N
, V
T
, P, S) — контекстно-свободная грамматика.
Выход:
S
=
{A | A =
V
G
k
(γ), где γ — активный префикс G}.
Метод.
1. Построить множество A
0
=
V
G
k
(ε) и поместить его в S как непомеченное
множество.
2. Пусть A ∈ S и A — не помечено. Пометить его и построить множество
′
A = GOTO(A, X ) для всех X ∈ V
N
∪V
T
. Если
′
A ≠∅ и
′
A ∉ S, то включить
′
A
в S как непомеченное множество.
3. Повторять шаг 2 до тех пор, пока все множества LR(k)-ситуаций в S не
будут помечены. Момент, когда в
S все множества окажутся помеченными,
обязательно наступит, так как число правил грамматики G конечно, число
позиций в них конечно, число терминальных цепочек, длина которых не
превосходит k, конечно и, соответственно, число LR(k)-ситуаций, допустимых
для грамматики G, тоже конечно.
4. Полученное множество S является искомым.
Определение 3.10. Если G — контекстно-свободная грамматика, то систему
множеств допустимых LR(k)-ситуаций для пополненной грамматики
G
′
будем
называть
канонической системой множеств LR(k)-ситуаций для грамматики G.
Замечание 3.4. Множество
GOTO( , )S
′
A
никогда не потребуется вычислять, так
как оно всегда пусто
7
.
Пример 3.10. Рассмотрим ещё раз пополненную грамматику из примера
3.1, содержащую следующие правила: 0)
S
′
→ S, 1) S → SaSb, 2) S →ε, и
проиллюстрируем на ней алгоритм 3.3.
Как положено, начинаем с построения:
A
0
=
V
G
1
(ε) = {[
S
′
→ .S, ε], [S → .SaSb, ε | a], [S → ., ε | a]} (см. пример 3.9).
Затем строим GOTO(
A
0
, X ), где X ∈{S, a, b}:
A
1
= GOTO(A
0
, S )=
V
G
1
(S ) = {[
S
′
→ S., ε], [S → S.aSb, ε|a]}(см.пример 3.9);
GOTO(
A
0
, a) = GOTO(A
0
, b)=∅.
Теперь вычисляем GOTO(
A
1
, X ), где X ∈ {S, a, b}:
GOTO(
A
1
, S )=∅;
A
2
= GOTO(A
1
, a) = GOTO(
V
G
1
(S ), a) =V
G
1
(Sa) =
=
{[S → Sa.Sb, ε | a], [S → .SaSb, a | b], [S → ., a | b]} (см. пример 3.9);
GOTO(
A
1
, b) = GOTO(
V
G
1
(S ), b)=∅.
7
Так как S
’
не встречается в правых частях правил.

Страницы