Алгоритм восходящего восстановления дерева разбора. Понятие конфигурации. Связь между конфигурациями, состояниями и операциями восходящего акцептора, страница 4

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


После завершения процедуры по грамматике Ga2 будет построена такая таблица:


Состояние

Образовано

База

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

С

Отм.

Из

Через

0

Да

Z : ▼ S „

S

1

S : ▼ S + T

S

1

S : ▼ T

T

2

T : ▼ T * F

T

2

T : ▼ F

F

3

F : ▼ ( S )

(

4

F : ▼ i

i

5

F : ▼ c

c

6

1

0

S

Да

Z : S ▼„

„

S

Да

S : S ▼+ T

+

7

2

0, 4

T

Да

S : T ▼

T

Да

T : T ▼ * F

*

8

3

0, 4, 7

F

Да

T : F ▼

4

0, 4, 7, 8

(

Да

F : (▼ S )

S

9

S : ▼ S + T

S

9

S : ▼ T

T

10

T : ▼ T * F

T

10

T : ▼ F

F

11

F : ▼ ( S )

(

12

F : ▼ i

i

13

F : ▼ c

c

14

5

0, 4, 7, 8

i

Да

F : i ▼

6

0, 4, 7, 8

i

Да

F : c ▼

7

1, 9

+

Да

S : S + ▼ T

T

15

T : ▼ T * F

T

15

T : ▼ F

F

16

F : ▼ ( S )

(

17

F : ▼ i

i

18

F : ▼ c

c

19

8

2, 10

*

Да

T : T * ▼ F

F

20

F : ▼ ( S )

(

21

F : ▼ i

i

22

F : ▼ c

c

23

9

4

S

Да

F : ( S ▼ )

)

24

S

Да

S : S ▼+ T

+

25

10

7

T

Да

S : S + T ▼

T

Да

T : T* F

*

26

11

8

F

Да

T : T * F ▼

12

9

)

Да

F : ( S ) ▼