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

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

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

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

Шаг 1. Строится заготовка управляющей таблицы (13 строк – от 0 до 12; 10 колонок – 3 нетерминала, 6 терминалов и „), в клетку строки 1 колонки „ заносится знак операции Stop.

Шаг 2. По первым трем колонкам таблицы конфигураций (Состояние, Из, Через) формируются знаки операций Go (если в колонке «Через» нетерминал) и Shift (если в этой колонке терминал) – в клетку строки, номер которой взят из колонки «Из», находящуюся на пересечении с колонкой, озаглавленной символом из колонки «Через» пишется G или S с номером, взятым из колонки «Состояние», в скобках.

Шаг 3. Во все клетки строк, состояниям которых соответствуют конфигурации вида M : b ▼, а колонки озаглавлены терминалами (в том числе „) пишется знак операции R[educe] с двумя параметрами в скобках:

–  первый параметр – это длина правой части правила (количество состояний, сбрасываемых со стека);

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

В результате получится такая УТ:

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)

R(1,0)

R(1,0)

R(1,0)

3

R(1,1)

R(1,1)

R(1,1)

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)

R(1,2)

R(1,2)

R(1,2)

6

R(1,2)

R(1,2)

R(1,2)

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)

R(3,0)

R(3,0)

R(3,0)

11

R(3,1)

R(3,1)

R(3,1)

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)

R(3,2)

R(3,2)

R(3,2)


Разрешение конфликтов путем использования
множеств последователей нетерминальных символов

Текущий уровень дерева разбора выглядит так:                                                                                                           Выполнение операции свертки приведет к:

для конфликта в состоянии 2:         … T * …                                                                        … S *

для конфликта в состоянии 10:       … S+ T * …                                                                        … S *

Однако, терминал * НЕ принадлежит множеству последователей нетерминала S.

Разрешать этот конфликт в пользу знака операции свертки, формирующего нетерминал S при наличии на входе терминала * нельзя. Этот конфликт должен быть разрешен в пользу знака операции сдвига.

Более того, знак ЛЮБОЙ операцию свертки имеет смысл заносить только в те клетки, колонки которых помечены терминалами из множества последователей нетерминала, образующегося в результате свертки. Теперь управляющая таблица будет выглядеть так:

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

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