Раздел 6.
АЛГОРИТМ РАЗБОРА ДЛЯ LR(0)-ГРАММАТИК И SLR(1)-ГРАММАТИК.
6.2. Построить управляющую таблицу и промоделировать работу SLR(1)-анализатора для КС-грамматики G = < T, N, S, R >.
6.2.4. T = { a, b, 1, 0 }, N = { S, A, B }, R = { S → aA, S → bB, A → 1A0, A → ε, B → 1B00, B → ε };
0)E → S
1)S → aA
2)S → bB
3)A → 1A0
4)A → ε
5)B → 1B00
6)B → ε
OBLOW:
T |
g(x) |
|||||||||||
S0 |
a1 |
A1 |
b2 |
B2 |
1 3 |
A3 |
0 3 |
1 5 |
B5 |
0 51 |
0 52 |
|
S0 |
|
|
|
|
|
|
|
|
|
|
|
|
a1 |
|
|
1 |
|
|
1 |
|
|
|
|
|
|
A1 |
|
|
|
|
|
|
|
|
|
|
|
|
b2 |
|
|
|
|
1 |
|
|
|
1 |
|
|
|
B2 |
|
|
|
|
|
|
|
|
|
|
|
|
1 3 |
|
|
|
|
|
1 |
1 |
|
|
|
|
|
A3 |
|
|
|
|
|
|
|
1 |
|
|
|
|
0 3 |
|
|
|
|
|
|
|
|
|
|
|
|
1 5 |
|
|
|
|
|
1 |
|
|
|
1 |
|
|
B5 |
|
|
|
|
|
|
|
|
|
|
1 |
|
0 51 |
|
|
|
|
|
|
|
|
|
|
|
1 |
0 52 |
|
|
|
|
|
|
|
|
|
|
|
|
┴ |
1 |
1 |
|
1 |
|
|
|
|
|
|
|
|
T |
g(x) |
||||||
a |
b |
1 |
0 |
S |
A |
B |
|
S0 |
|
|
|
|
|
|
|
a1 |
|
|
1 3 |
|
|
A1 |
|
A1 |
|
|
|
|
|
|
|
b2 |
|
|
1 5 |
|
|
|
B2 |
B2 |
|
|
|
|
|
|
|
1 3 |
|
|
1 3 |
|
|
A3 |
|
A3 |
|
|
|
0 3 |
|
|
|
0 3 |
|
|
|
|
|
|
|
1 5 |
|
|
1 5 |
|
|
|
B5 |
B5 |
|
|
|
0 51 |
|
|
|
0 51 |
|
|
|
0 52 |
|
|
|
0 52 |
|
|
|
|
|
|
|
┴ |
a1 |
b2 |
|
|
S0 |
|
|
T |
f(a) |
g(x) |
||||||||||
a |
b |
1 |
0 |
ε |
S |
A |
B |
a |
b |
1 |
0 |
|
S0 |
|
|
|
|
D |
|
|
|
|
|
|
|
a1 |
|
|
П |
C,4 |
C,4 |
|
A1 |
|
|
|
1 3 |
|
A1 |
|
|
|
|
C,1 |
|
|
|
|
|
|
|
b2 |
|
|
П |
C,6 |
C,6 |
|
|
B2 |
|
|
1 5 |
|
B2 |
|
|
|
|
C,2 |
|
|
|
|
|
|
|
1 3 |
|
|
П |
C,4 |
C,4 |
|
A3 |
|
|
|
|
|
A3 |
|
|
|
П |
|
|
|
|
|
|
|
0 3 |
0 3 |
|
|
|
C,3 |
C,3 |
|
|
|
|
|
|
|
1 5 |
|
|
П |
C,6 |
C,6 |
|
|
B5 |
|
|
|
|
B5 |
|
|
|
П |
|
|
|
|
|
|
|
0 51 |
0 51 |
|
|
|
П |
|
|
|
|
|
|
|
0 52 |
0 52 |
|
|
|
С,5 |
C,5 |
|
|
|
|
|
|
|
┴ |
П |
П |
|
|
|
S0 |
|
|
a1 |
b2 |
|
|
Проверка:
(
,
a1ε0, ε) → (
a1,1ε0,
ε) → (
a1
1 3,
ε0, ε) → (
a1
1 3 ε,
0, ε) → (
a1
1 3 A3
0
3
, 4) → (
a1
1 3 A3
0
3
, 4) → (
a1
A1
, 43) → (
S0
, 431) → Допуск