Преобразование таблицы конфигураций в управляющую таблицу, страница 2

0

1

2

3

4

5

6

7

8

9

S

T

F

+

*

(

)

i

c

„

0

G(1)

G(2)

G(3)

S(4)

S(5)

S(6)

1

S(7)

Stop

2

R(1,0)

S(8)

R(1,0)

R(1,0)

3

R(1,1)

R(1,1)

R(1,1)

R(1,1)

4

G(9)

G(2)

G(3)

S(4)

S(5)

S(6)

5

R(1,2)

R(1,2)

R(1,2)

R(1,2)

6

R(1,2)

R(1,2)

R(1,2)

R(1,2)

7

G(10)

G(3)

S(4)

S(5)

S(6)

8

G(11)

S(4)

S(5)

S(6)

9

S(7)

S(12)

10

R(3,0)

S(8)

R(3,0)

R(3,0)

11

R(3,1)

R(3,1)

R(3,1)

R(3,1)

12

R(3,2)

R(3,2)

R(3,2)

R(3,2)

Грамматика Ga1 называется SLR(1) – грамматикой.

LR(0)- и SLR(1)- грамматики и автоматы

Существуют LR(0) – грамматики:

ГрамматикаG a0

0

Z : S „

1

S : T

2

S : S + T

3

T : ( S )

4

T : i

5

T  : c

При построении УТ восходящего синтаксического акцептора по этой грамматике конфликтов не возникнет вообще, поэтому не понадобится ни один символ (0 символов) для их разрешения.

К классу SLR(1)-грамматик относятся такие грамматики, для которых все конфликты при построении управляющей таблицы удается предупредить (иногда говорят – разрешить) путем использования множеств последователей нетерминалов, образующихся в результате свертки.


LR(1)-грамматики и автоматы

ГрамматикаG LALR

0

Z : L „

1

L : E = R

2

L : R

3

R : E

4

E : * R

5

E : ident

Таблица конфигураций:

Состояние

Образовано

База

Конфигурация

Символ

Отм.

Из

Через

0

Да

Z : ▼ L „

L

1

L : ▼ E = R

E

2

L : ▼ R

R

3

E : ▼ * R

*

4

E : ▼ i

i

5

R : ▼ E

E

2

1

0

L

Да

Z : L ▼ „

„

2

0

E

Да

L : E= R

=

6

Да

R : E

3

0

R

Да

L : R

4

0, 4, 6

*

Да

E : * R

R

7

R : ▼ E

E

8

E : ▼ * R

*

9

E : ▼ i

i

10

5

0, 4, 6

i

Да

R : i

6

2

=

Да

L : E =R

R

11

R : ▼ E

E

12

E : ▼ * R

*

13

E : ▼ i

i

14

7

4

R

Да

E : * R

8

4, 6

E

Да

R : E

9

6

R

Да

L : E = R