Режим переполоха. Преобразование входного текста в постфиксную форму записи

Страницы работы

Содержание работы

Режим переполоха

Идея вытекает из рассмотрения процесса синтаксического анализа программы, содержащей, например, такую цепочку:

x = ( x + ) ) * ) ( ( + y ;

Множественные ошибки обнаруживаются при попытке разбора нетерминала Выражение в правиле, выглядящем приблизительно так:

ОператорПрисваивания : Выражение ;

Можно поступить так:

1.  В тот момент, когда будет обнаружена невозможность нейтрализации одиночной ошибки, приступить к поиску символа «;». Все остальные символы просто пропускать.

2.  При обнаружении символа «;» (в тот момент, когда этот символ стал текущим) модифицировать стек и состояние автомата так, как будто бы

a.  нисходящий автомат вернулся туда, откуда был выполнен переход для разбора нетерминала Выражение

b.  восходящий выполнил свертку основы для нетерминала Выражение и операцию перехода (Go) по этому нетерминалу.

3.  Вернуться к анализу текста.

Такая схема организации работы называется «режим переполоха».

В общем случае ситуация выглядит так:

Уровень восстанавливаемого дерева разбора можно представить себе так:

a g j b

Существует вывод N => g j

В момент включения режима переполоха нужно:

-  определить множество ожидаемых символов (либо предшественников цепочки b, либо последователей нетерминала N);

-  определить состояние автомата, в котором он должен оказаться в момент выхода из режима переполоха;

-  определить, каким должно быть содержимое стека автомата к этому моменту.


Нисходящий автомат с несколькими состояниями


N

M выб состояния

Флажки

Переход

a

s

r

e

0

( i c

1

2

1

u

Stop

2

( i c

11

3

+

1

13

4

 ) u

1

0

5

( i c

15

6

*

1

17

7

+ ) u

1

0

8

(

1

19

9

i

1

22

10

c

23

11

( i c

1

5

12

 + ) u

3

13

+

1

14

14

( i c

2

15

( i c

1

8

16

* + ) u

6

17

*

1

18

18

( i c

5

19

(

1

20

20

( i c

1

2

21

)

1

1

0

22

i

1

1

0

23

c

1

1

0

Такт

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

Вход

(

(

(

(

(

(

(

x

x

x

x

x

x

x

x

+

+

+

+

+

+

)

)

Сост.

0

2

11

5

15

8

19

20

2

11

5

15

8

9

22

16

6

7

12

3

13

14

Стек

1

1

12

12

16

16

16

21

21

12

12

16

16

16

12

12

12

21

21

21

21

1

1

12

12

12

16

16

21

21

12

12

12

21

21

21

16

16

16

16

1

1

1

12

12

16

16

21

21

21

16

16

16

12

12

12

12

1

1

12

12

16

16

16

12

12

12

1

1

1

1

1

1

12

12

12

1

1

1

1

1

1

Похожие материалы

Информация о работе