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

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

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

В ВебТрансЛабе – шаблоны с названием …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 ₁ s ₂ ... s _k ),

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

­¯s _k... ¯s ₂ ¯s ₁¯M     ( если a пуста, то ­¯M )

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

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

N : t a               ( N : t s ₁ s ₂ ... s _k ),

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

­¯s _k... ¯s ₂ ¯s ₁®     ( если 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