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

UptoLike

ВУЗ: 

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

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

Рубрика: 

221
Теперь вычисляем GOTO(
A
2
, X ), где X∈ {S, a, b}:
A
3
= GOTO(A
2
, S ) = {[S → SaS.b, ε|a], [S → S.aSb, a|b]};
GOTO(
A
2
, a)= GOTO(
V
G
1
(Sa), a)=∅;
GOTO(
A
2
, b)= GOTO(
V
G
1
(Sa), b)=∅.
Теперь вычисляем GOTO(
A
3
, X ), где X ∈ {S, a, b}:
GOTO (
A
3
, S )=∅;
A
4
= GOTO(A
3
, a)={[S → Sa.Sb, a | b], [S → .SaSb, a | b], [S → ., a | b]};
A
5
= GOTO(A
3
, b)={[S → SaSb., ε|a}.
Теперь вычисляем GOTO(
A
4
, X ), где X∈ {S, a, b}:
A
6
= GOTO(A
4
, S )={[S → SaS.b, a | b], [S → S.aSb, a | b]}.
GOTO(
A
4
, a) = GOTO(A
4
, b)=∅.
Теперь вычисляем GOTO(
A
5
, X ), где X∈ {S, a, b}:
GOTO(
A
5
, S ) = GOTO(A
5
, a) = GOTO(A
5
, b)=∅.
Теперь вычисляем GOTO (
A
6
, X ), где X∈ {S, a, b}:
GOTO(
A
6
, S )=∅;
GOTO(
A
6
, a)={[S → Sa.Sb, a | b], S → .SaSb, a |b], [S → ., a |b]} = A
4
;
A
7
= GOTO(A
6
, b)={[S → SaSb., a | b]}.
Таким образом {
A
0
, A
1
, A
2
, A
3
, A
4
, A
5
, A
6
, A
7
} — каноническая система
множеств LR(1)-ситуаций для грамматики G.
Табл. 3.4 представляет функцию
GOTO(A, X) для грамматики G. Заметим,
что с точностью до обозначений она совпадает с частью g(X ) табл. 3.3.
Таблица 3.4
X
A
S a b
A
0
A
1
A
1
A
2
A
2
A
3
A
3
A
4
A
5
A
4
A
6
A
5
A
6
A
4
A
7
A
7
Пустые клетки в ней соответствуют неопределённым значениям.
Заметим, что множество GOTO (
A, X ) всегда пусто, если в каждой LR(k)-
ситуации из
A точка расположена на конце правила. Примерами таких
множеств здесь служат
A
5
и A
7
.

Страницы