Нисходящий автомат с одним состоянием, управляемый входным символом и символом, находящимся на верхушке стека

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

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

Нисходящий автомат с одним состоянием,

управляемый входным символом и символом, находящимся на верхушке стека

В ВебТрансЛабе – шаблоны с названием …SyntAsOneSA…

Обозначения операций:

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

0

Z : Su

1

S : U R

2

R : + S

3

R : e

4

U : V W

5

W : * U

6

W : e

7

V : ( S )

8

V : i <идентификатор>

9

V : c <константа>

¯X             – занесение символа X в стек

­                – снятие одного символа с верхушки стека

®                 – чтение следующего символа из входной цепочки

Stop          – останов по окончанию разбора правильного предложения

<пусто>    – останов по обнаружению ошибки.

S

u

Начальное состояние стека:

Построение автомата (преобразование грамматики в автомат):

Шаг 1:

i

c

+

*

(

)

u

S

U

R

W

V

u

Stop


Шаг 2:

Для каждой строки:

1. Если строка озаглавлена нетерминалом, то перебираются все правила для него.

1.1. Если правило имеет вид

N : M a             ( N : M s 1 s 2 ... s k ),

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

­¯s k... ¯s 2 ¯s 1¯M     ( если a пуста, то ­¯M )

Если среди s i есть терминалы, то к таблице добавляются строки, озаглавленные этими терминалами (если их еще нет).

1.2. Если правило имеет вид

N : t a               ( N : t s 1 s 2 ... s k ),

то в клетку, столбец которой озаглавлен терминалом t (единственный символ, составляющий множество выбора этого правила), заносится

­¯s k... ¯s 2 ¯s 1®     ( если a пуста, то ­® )

Если среди s i есть терминалы, то к таблице добавляются строки, озаглавленные этими терминалами (если их еще нет).

1.3. Если правило имеет вид

N : e

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

­

2. Если строка озаглавлена терминалом, то в клетку, находящуюся на пересечении с одноименным столбцом, заносится

­®

i

c

+

*

(

)

u

S

­¯ R ¯ U

­¯ R ¯ U

­¯ R ¯ U

U

­¯ W ¯ V

­¯ W ¯ V

­¯ W ¯ V

R

­¯ S ®

­

­

W

­

­¯ U ®

­

­

V

­®

­®

­¯ ) ¯ S ®

u

Stop

)

­®

( x + y ) * z u

Такт

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

19

20

Вход

(

(

(

x

x

x

+

+

y

y

y

)

)

)

*

z

z

u

u

u

Стек

S

U

V

S

U

V

W

R

S

U

V

W

R

)

W

U

V

W

R

u

u

R

W

)

R

W

R

)

)

R

W

R

)

W

R

R

W

R

u

u

R

W

)

R

)

W

W

)

R

)

W

R

u

u

R

u

u

R

W

)

W

R

R

W

)

W

R

u

u

u

R

W

R

u

u

R

W

R

u

u

R

u

u

R

u

u

u

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

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