Файл: Отчеты оформляются в виде файлов формата Microsoft Word (файлы других форматов не принимаются), размер шрифта 1214.docx

Построенный фрагмент таблицы конфигураций после выполнения этого шага для нулевого состояния выглядит так, как показано в табл. 5.3.

Таблица 5.3.

Состояние	Образовано		База		Конфигурация		Символ		Отм.
	Из	Через
0				Да		Z : ▼ S ►		S
						S : ▼ S + T		S
						S : ▼ T		T
						T : ▼ T * V		T
						T : ▼ V		V
						V : ▼ ( S )		(
						V : ▼ i		i
						V : ▼ c		c

Шаг 2. Образование новой базы. Просматривается колонка Отм. с целью найти такую строку таблицы, которая еще не помечена и в колонке Символ содержит какой-либо символ грамматики, отличный от псевдотерминала ► (конец файла). Если таких строк нет, то этап построения таблицы конфигураций завершается.

Если такая строка найдена, то зафиксируем номер состояния (далее оно называется исходным), найдем и отметим те строки таблицы, которые принадлежат данному состоянию и содержат тот же самый символ в соответствующей колонке. Выберем конфигурации из соответствующей колонки этих строк и перенесем в каждой из них маркер через один символ. Тем самым будет образовано новое базовое подмножество конфигураций.

---

Шаг 3. Проверка наличия состояния с таким набором базовых конфигураций, который совпадает с вновь образованной базой. Просматривается таблица конфигураций и база каждого уже существующего состояния (в том числе исходного) сравнивается с новой базой, сформированной на предыдущем шаге. Возможны два случая.

Шаг 3.1. Состояние, имеющее в точности такую же базу, уже существует (подчеркнем, что для этого новая и уже существующая база должны совпадать полностью). В этом случае добавим в колонки Из и Через этого состояния номер исходного состояния и символ, через который был перенесен маркер для образования базы. Эти данные пригодятся на втором этапе при преобразовании таблицы конфигураций в управляющую таблицу. Возвращаемся к шагу 2.

Шаг 3.2. Не найдено состояния, имеющего в точности такую же базу, что и проверяемая (вновь образованная). В этом случае создается новое состояние.
В таблицу добавляется столько строк, сколько конфигураций содержится в проверяемой базе. Клетки во вновь добавленных строках заполняются в соответствии с назначением колонок. После завершения формирования нового состояния осуществляется возврат к шагу 1.

Описание процедуры завершено. Результат ее применения к грамматике G_a1 приведен в табл. 5.4. Заметим, что в колонке Отм. указан порядковый номер применения второго шага процедуры. Шаги с первого по девятый приводили к образованию таких подмножеств базовых конфигураций, которых к моменту выполнения каждого шага еще не было в таблице. Поэтому были сформированы состояния с номерами 1–9.

На десятом применении второго шага в результате переноса маркера через символ T были получены конфигурации S: T▼ и T: T▼ * V , в точности совпадающие с базой состояния номер 2. Согласно третьему шагу процедуры новое состояние не создано, в колонке Из состояния 2 отмечено, что его база получена из конфигураций как состояния 0, так и состояния 4. Начиная с одиннадцатого новые состояния были созданы только на 15, 20 и 24 применении второго шага процедуры. Все остальные шаги приводили к образованию уже существующих базовых подмножеств конфигураций.

Таблица 5.4.

Состояние

Образовано

База

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

Символ

Отм.

Из

Через

0

Да

Z : ▼ S ►

S

1

S : ▼ S + T

S

1

S : ▼ T

T

2

T : ▼ T * V

T

2

T : ▼ V

V

3

V : ▼ ( S )

(

4

V : ▼ i

i

5

V : ▼ c

c

6

1

0

S

Да

Z : S ▼►

S

Да

S : S ▼ + T

+

7

2

0, 4

T

Да

S : T ▼

T

Да

T : T▼ * V

*

8

3

0, 4, 7

V

Да

T : V▼

4

0, 4, 7, 8

(

Да

V : (▼ S )

S

9

S : ▼ S + T

S

9

S : ▼ T

T

10

T : ▼ T * V

T

10

T : ▼ V

V

11

V : ▼ ( S )

(

12

V : ▼ i

i

13

V : ▼ c

c

14

5

0, 4, 7, 8

i

Да

V : i ▼

6

0, 4, 7, 8

i

Да

V : c▼

7

1, 9

+

Да

S : S + ▼ T

T

15

T : ▼ T * V

T

15

T : ▼ V

V

16

Из

Через

V : ▼ ( S )

(

17

V : ▼ i

i

18

V : ▼ c

c

19

8

2, 10

*

Да

T : T * ▼ V

V

20

V : ▼ ( S )

(

21

V : ▼ i

i

22

V : ▼ c

c

23

9

4

S

Да

V : ( S ▼ )

)

24

S

Да

S : S ▼+ T

+

25

10

7

T

Да

S : S + T ▼

T

Да

T : T▼* V

*

26

11

8

V

Да

T : T * V▼

12

9

)

Да

V : ( S ) ▼

---

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

В результате построения таблицы конфигураций (табл. 5.4.) было выяснено, что автомат, реализующий восходящее восстановление дерева грамматического разбора предложений языка, порождаемого грамматикой G_a1, должен иметь ровно 13 состояний (с номерами 0…12). Общее количество символов (как терминальных, так и нетерминальных) вместе с псевдотерминалом ► равно 10.

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

Шаг 1. Строится пустая заготовка управляющей таблицы автомата, содержащая 13 строк и 10 столбцов (не считая заголовочных). Строки и столбцы нумеруются начиная с нуля. Нетерминальные символы грамматики в произвольном порядке помещаются в заголовки столбцов начиная с нулевого. Затем в произвольном порядке формируются заголовки столбцов, соответствующих терминальным символам. Последняя колонка ставится в соответствие псевдотерминальному символу конца входной цепочки ►.

Шаг 2. Занесение знаков операций Stop, Shift и Go. Знак операции Stop заносится в клетку строки состояния 1, колонка которой озаглавлена псевдотерминалом ►. Это соответствует моменту окончания восстановления дерева разбора согласно конфигурации Z : S ▼►.

Просматриваются колонки Из и Через таблицы конфигураций (табл. ?). Для каждой непустой пары значений из этих колонок формируется знак операции Shift, если символ в колонке Через является терминальным, и знак операции Go – в противном случае. Номер состояния, взятый из первой колонки текущей строки таблицы конфигураций, является параметром знака операции. Построенный таким образом знак операции заносится в клетку управляющей таблицы, находящуюся на пересечении строки с номером, взятым из колонки Из, и столбца, озаглавленного символом из колонки Через.

Например, при просмотре первой строки таблицы конфигураций, соответствующей состоянию номер 1, будет образован один знак операции G1, который должен быть занесен в клетку строки номер 0 того столбца управляющей таблицы, который помечен символом S. При обработке первой строки состояния 3 таблицы конфигураций будут образованы три одинаковых знака операции

---

S3, которые должны быть помещены в клетки столбца, помеченного нетерминалом V, находящиеся на его пересечении со строками 0, 4 и 7.

Шаг 3. Занесение знаков операций Reduce. Просматривается содержимое колонки Конфигурация в поисках такой конфигурации, в которой маркер находится после последнего символа правой части правила. Формируется знак операции Rk,n, где k – количество символов в правой части правила; n – номер столбца управляющей таблицы, помеченного нетерминалом из левой части этого правила.

Выполняется попытка занесения сформированного знака операции во все клетки той строки управляющей таблицы, которая имеет номер, взятый из первой колонки таблицы конфигураций. Знак операции свертки не заносится в клетки, столбцы которых помечены нетерминалами. Если клетка уже содержит знак операции Shift или Reduce, то фиксируется конфликт типа сдвиг/свертка или свертка/свертка соответственно. Вопрос о том, что делать при возникновении конфликтов, будет рассматриваться ниже.

Применение этой процедуры к ранее построенной нами таблице конфигураций (см. табл. 5.4.) позволит получить такую управляющую таблицу автомата (табл. 5.5.).

Таблица 5.5.

0

1

2

3

4

5

6

7

8

9

S

T

V

+

*

(

)

i

c

►

0

G1

G2

G3

S4

S5

S6

1

S7

Stop

2

R1,0

S8

R1,0

R1,0

R1,0

R1,0

R1,0

3

R1,1

R1,1

R1,1

R1,1

R1,1

R1,1

R1,1

4

G9

G2

G3

S4

S5

S6

5

R1,2

R1,2

R1,2

R1,2

R1,2

R1,2

R1,2

6

R1,2

R1,2

R1,2

R1,2

R1,2

R1,2

R1,2

7

G10

G3

S4

S5

S6

8

G11

S4

S5

S6

9

S7

S12

10

R3,0

S8

R3,0

R3,0

R3,0

R3,0

R3,0

11

R3,1

R3,1

R3,1

R3,1

R3,1

R3,1

R3,1

12

R3,2

R3,2

R3,2

R3,2

R3,2

R3,2

R3,2

---

В качестве примера выполнения шага 3 рассмотрим состояние номер 2, в наборе конфигураций которого имеется конфигурация S : T▼. Формируется знак операции R1,0, поскольку правая часть правила содержит один символ T, а нетерминалу S из левой части поставлен в соответствие столбец управляющей таблицы с номером 0. При занесении этого знака в строку номер 2 управляющей таблицы будет обнаружен конфликт типа сдвиг/свертка в клетке столбца, помеченного терминалом *. Возникновение конфликта легко объясняется наличием в наборе конфигураций состояния номер 2 конфигурации
T : T▼ * V.

В табл. 5.5. серым фоном отмечены две клетки, в которых при занесении знаков операций были зафиксированы конфликты типа сдвиг/свертка.

Возникновение конфликтов, казалось бы, свидетельствует о недетерминированности конечного автомата, т. е. о невозможности восстановления дерева разбора некоторых входных цепочек без возвратов к пересмотру ранее принятых решений. Знаки операций сдвига и свертки не могут быть помещены в одну клетку управляющей таблицы в силу противоположности смысла действий, выполняемых этими операциями. То же самое относится и к потенциально возможным конфликтам типа свертка/свертка.

В одной клетке управляющей таблицы может находиться только один знак операции. Поэтому необходимо выяснить, может ли каждый конфликт быть разрешен в пользу одного из знаков операций. Только тогда можно считать завершенным процесс преобразования грамматики в восходящий синтаксический акцептор. Для разрешения конфликтов, очевидно, необходимо исследовать свойства исходной грамматики и порождаемого ею языка.

Однако в действительности для многих грамматик, в том числе для рассматриваемой грамматики G_a1, возникновение конфликтов обусловлено не их свойствами и даже не свойствами порождаемого языка, а всего только несовершенством способа занесения знаков операций свертки в управляющую таблицу, сформулированного в шаге 3 процедуры.

8. 
   Предотвращение конфликтов путем использования множеств последователей нетерминальных символов
   

Недетерминированность автомата, обнаруженная при попытке занесения знака операции свертки R1,0 (или R3,0) в клетку состояния номер 2 (или 10), находящуюся на пересечении со столбцом, помеченным терминалом * и содержащую знак операции S8, следует понимать, как возможность реализации более чем одной истории работы, начиная с момента выполнения одной из этих двух конфликтующих операций.

---