Мартыненко Б.К. Синтаксически управляемая обработка данных. Изд. 2-е, дополн

Подождите немного. Документ загружается.

111

2) если существует такое подавляемое состояние q ∈Q

, сопряженное с

каждым из этих магазинных символов по некоторому составному резольверу r

∈ℜ

, для которого таблица возвратных состояний дает различающиеся

(согласно определению 4.2.1) возвратные состояния p

(q,X,r) и p

(q,Y,r).

Определение 4.2.5. Два магазинных символа X ∈Γ

и Y ∈Γ

—

эквивалентны, если они не различаются согласно определению 4.2.4.

Очевидно, что построение отношений эквивалентности на множестве со-

стояний и на множестве магазинных символов должно выполняться совместно.

Эквивалентность входных символов прямого просмотра устанавливается

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

вивалентных состояний и магазинных символов.

Определение 4.2.6. Два входных символа прямого просмотра

a ,b ∈Σ

счита-

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

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

ляющие элементы одинаковы, т.е. если для всех q ∈Q

выполняются равенства

(q,a)=

(q,b) и для всех r

∈

(q,a) (или, что то же самое, r ∈

(q,b)) имеют

место равенства

(q,a,r)=

(q,b,r). Здесь

— компоненты управляю-

щей таблицы прямого просмотра, в которых произведен переход к классам эк-

вивалентных состояний и магазинных символов.

Эквивалентность входных символов обратного просмотра, в качестве кото-

рых, как известно, используются состояния прямого просмотра, определяется

аналогично эквивалентности входных символов прямого просмотра.

4.3. СОКРАЩЕНИЕ ЧИСЛА ВХОДОВ В

ТАБЛИЦУ ВОЗВРАТНЫХ СОСТОЯНИЙ

Дополнительная оптимизация прямого просмотра возможна за счет

сокращения числа входов по магазинным символам в таблице возвратных

состояний. Именно, если после перехода в таблице возвратных состояний к

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

что для некоторого класса магазинных символов класс эквивалентности

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

состояний он соответствует, то такой класс магазинных символов исключается

из входа в таблицу возвратных состояний. Точнее, если при фиксированных

∈

ℜ

и X∈Γ

для всех q

∈

, для которых

(q,X,r) определено,

(q,X,r)

имеет одно и то же значение, равное, скажем, p ∈Q

, то магазинный символ X

во всех магазинных цепочках должен быть заменен на состояние p и исключен

из входов в таблицу возвратных состояний

. Во время процессирования

такой магазинный символ, будучи снят с вершины магазина, используется

непосредственно как возвратное состояние (без обращения к таблице воз-

вратных состояний).

112

4.4. ПОРЯДОК ОПТИМИЗАЦИОННЫХ ПРЕОБРАЗОВАНИЙ

Оптимизация управляющих таблиц челночного процессора производится в

следующем порядке:

1. Построить отношение эквивалентности R

на множестве состояний об-

ратного просмотра (безотносительно к прямому) и соответствующие

классы эквивалентности C

в этом отношении эквивалентности.

2. В управляющей таблице обратного просмотра перейти к классам эквива-

лентности состояний C

(сокращение числа входов по состояниям в

управляющую таблицу обратного просмотра).

3. Построить отношение эквивалентности R

на входных символах обрат-

ного просмотра, в качестве которых используются состояния прямого

просмотра (без учета их эквивалентности как состояний прямого про-

смотра) и соответствующие классы эквивалентности C

в этом

отношении эквивалентности.

4. Перейти в таблице обратного просмотра к классам эквивалентности C

(сокращение числа входов по входным символам обратного просмотра)

5. Построить отношения эквивалентности

на множестве состояний

на множестве магазинных символов R

прямого просмотра, а также

соответствующие им классы эквивалентности C

и C

6. В магазинных цепочках прямого просмотра заменить магазинные симво-

лы на классы эквивалентности из C

, которым они принадлежат.

7. В управляющей таблице прямого просмотра заменить переходные со-

стояния на классы эквивалентности из C

, которым они принадлежат

(сокращение числа входов по состояниям в управляющую таблицу пря-

мого просмотра).

8. В таблице возвратных состояний

перейти к классам эквивалентности

состояний из C

и магазинных символов из C

, построенных на шаге 5

(сокращение таблицы возвратных состояний по этим двум входам).

9. В магазинных цепочках прямого просмотра каждый класс из C

заменить

на класс возвратных состояний из C

, если последний не зависит от

классов подавляемых состояний, с которыми этот класс магазинных

символов сопряжен. Попросту говоря, если таблица

после ее

преобразования на шаге 8 для некоторого класса магазинных символов

[X] для всех резольверных входов дает один и тот же класс возвратных

состояний [q] по всем классам подавляемых состояний, с которыми этот

класс магазинных символов [X] сопряжен, то во всех магазинных

цепочках управляющих элементов магазинный класс [X] должен быть

заменен на класс состояний [q].

Соответственно обратный просмотр, получив из входного потока номер класса состояний

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

обратного просмотра через лексический переходник обратного просмотра, дающий номер

соответствующего входа по классам входных символов обратного просмотра. Способ

построения такого переходника обратного просмотра описывается в разд. 4.5.

С учетом их эквивалентности как входных символов обратного просмотра.

113

10. Построить отношения эквивалентности R

на множестве входных

символов прямого просмотра и соответствующие классы

эквивалентности C

в этом отношении.

11. Перейти в управляющей таблице прямого просмотра к классам

эквивалентности входных символов из C

(сокращение числа входов по

входным символам в управляющей таблице прямого просмотра)

4.5. ПОСТРОЕНИЕ ЛЕКСИЧЕСКИХ ПЕРЕХОДНИКОВ

ПРЯМОГО И ОБРАТНОГО ПРОСМОТРОВ

Лексический переходник прямого просмотра — это таблица, которая по

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

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

прямого просмотра.

Для построения такого переходника достаточно сначала построить список

номеров 1,2,...,

n, где n — число первоначальных лексических классов, а затем

каждый элемент этого списка заменить на номер соответствующего класса

эквивалентности из C

, которому принадлежит этот элемент. Точнее, если

некоторый входной символ сканер относит к первоначальному лексическому

классу номер i, то этот номер i в упомянутой последовательности заменяется на

номер k, где k — номер класса эквивалентности, к которому этот символ

отнесен оптимизатором таблиц.

Лексический переходник прямого просмотра строится оптимизатором

таблиц автоматически.

Лексический переходник обратного просмотра — это таблица, которая по

номеру класса эквивалентных состояний прямого просмотра определяет номер

входа по входным символам в управляющую таблицу обратного просмотра.

Способ построения лексического переходника обратного просмотра так же

прост. Составляется последовательность номеров: 1,2,...,m, где m — число

классов эквивалентности состояний прямого просмотра. В этой последователь-

ности номер i заменяется на k, если любое из состояний, входящих в класс эк-

вивалентных состояний прямого просмотра номер i, содержится в классе экви-

валентных входных символов обратного просмотра номер k. Лексический пе-

реходник обратного просмотра строится оптимизатором таблиц автоматически.

Соответственно прямой просмотр использует лексический переходник, который

определяет номер входа для каждого входного символа. Способ построения такого

переходника описывается в разд. 4.5.

114

4.6. ИЛЛЮСТРАЦИЯ

МЕТОДА ОПТИМИЗАЦИИ ПРОЦЕССОРА

Оптимизация калькулятора. Рассмотрим метод оптимизации процессо-

ров на примере калькулятора арифметических выражений, обсуждавшегося в

гл.1. В результате его применения к сплайновому процессору, моделирующему

калькулятор, получаем следующие классы эквивалентности состояний, мага-

зинных и входных символов прямого просмотра

1. Классы эквивалентности состояний

1: { 1 } 6: { 7 } 11: { 1 7 }

2: { 2 } 7: { 1 2 } 12: { 1 8 }

3: { 3 4 5 8 9 10 11 } 8: { 1 3 } 13: { 1 9 }

4: { 5 } 9: { 14 15 }

5: { 6 } 10: { 1 6 }

2. Классы эквивалентности магазинных символов

1: {1}

2: {2}

3. Классы эквивалентности входных символов

1: {d} 4: {+ –} 7: {)}

2: {.} 5: {

/} 8: {EOF}

3: {E} 6: {(}

Замена состояний, магазинных и входных символов на соответствующие

классы эквивалентности, которым они принадлежат, с учетом того, что воз-

вратные состояния не зависят от подавляемых, дает оптимизированную управ-

ляющую таблицу калькулятора — см. табл.4.1. Она также состоит из малень-

ких табличек, в заголовке каждой из них указан состав класса эквивалентных

состояний, к которому она относится.

Таблица 4.1

Вход Семантика

Мага-

зин

Состо-

яние

1 2 3 4

Класс состояний 1={1}

[ d ] Reset;InitInt;SetDig -10 2

[ + ] Reset;PushMonOp -10 3

[ ( ] Reset;PushOpenPar -10 4

Обратный просмотр в калькуляторе не используется.

115

Продолжение табл. 4.1

1 2 3 4

Класс состояний 2={2}

AppDig; SetIntPart; PushOpd

Sup

[ d ] AppDig;SetDig 2

[.] AppDig;SetIntPart 5

[ E ] AppDig;SetIntPart 6

[ + ] AppDig; SetIntPart; PushOpd; PushDyadicOp 3

[

] AppDig; SetIntPart; PushOpd; PushDyadicOp 3

Класс состояний 3={3 4 8 9 10 11}

[ d ] InitInt;SetDig 2

[ + ] PushMonOp 3

[ ( ] PushOpenPar 4

Класс состояний 4={5}

[ d ] InitInt;SetDig -11 2

[ + ] PushMonOp -11 3

[ ( ] PushOpenPar -11 4

Класс состояний 5={6}

[ d ] InitInt;SetDig 7

Класс состояний 6={7}

[ d ] SetSign;InitInt;SetDig 8

[ + ] SetSign 9

Класс состояний 7={12}

AppDig;SetFrPart;AppFrPart;PushOpd

Sup

[ d ] AppDig;SetDig 7

[ E ] AppDig;SetFrPart;AppFrPart 6

[ + ] AppDig;SetFrPart;AppFrPart;PushOpd;PushDyadicOp 3

[

] AppDig;SetFrPart;AppFrPart;PushOpd;PushDyadicOp 3

Класс состояний 8={13}

AppDig;SetExp;AppExpPart;PushOpd

Sup

[ d ] AppDig;SetDig 8

[ + ] AppDig;SetExp;AppExpPart;PushOpd;PushDyadicOp 3

[

] AppDig;SetExp;AppExpPart;PushOpd;PushDyadicOp 3

Класс состояний 9={14 15}

[ d ] InitInt;SetDig 8

Класс состояний 10 ={16}

[EOF]

Complete

116

Окончание табл. 4.1

1 2 3 4

Класс состояний 11 ={17}

) UnloadAndDiscardOpenPar 13

Класс состояний 12 ={18} (конечный)

Stop

Класс состояний 13 ={19}

Sup

[ + ] PushDyadicOp 3

[

] PushDyadycOp 2

В графе Вход перечислены допустимые классы эквивалентности входных

символов. Каждый такой класс представлен первым своим элементом, заклю-

ченным в прямоугольные скобки.

Графа Семантика, как обычно, содержит цепочки семантических символов,

которые следует интерпретировать в данном состоянии управления.

Графа Магазин задает магазинные цепочки, в которых отрицательными

номерами представлены магазинные символы — возвратные состояния.

Графа Состояние задает переходный класс состояний или содержит символ

Sup — указание на ε-движение при котором, как известно, используется верх-

ний символ магазина: если он представлен положительным числом, то проис-

ходит обычное использование оптимизированной таблицы возвратных состо-

яний; если он представлен отрицательным номером, то это номер возвратного

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

состояния управления.

Далее мы приведем размеры компонент управляющей таблицы калькуля-

тора до (табл.4.2) и после (табл.4.3) оптимизации.

Размеры компонент в этих таблицах даны в элементах и в байтах. Напри-

мер, компонента "Характеристики состояний : Descr" состоит из 19 элементов

— дескрипторов, занимающих в памяти 76 байтов, а компонента "Характери-

стики состояний : Pool" состоит из 19 элементов — номеров вершин управляю-

щей граф-схемы, занимающих в памяти 38 байтов.

Следует заметить, что приведенные оценки несколько расходятся с реаль-

ными цифрами, так как объекты, используемые для представления соответ-

ствующих компонент таблиц, содержат дополнительные поля данных, не

показанные в этих таблицах.

117

Замечание 1. Более точные цифры, относящиеся к длине двоичных

файлов, содержащих соответствующие варианты управляющих таблиц

калькулятора, равны соответственно 1079 и 845 байтов, а показатель

оптимизации составляет 78%.

Замечание 2. В результате оптимизации исключена таблица возвратных

состояний. Этого, впрочем, и следовало ожидать, так как оригинальная таблица

возвратных состояний калькулятора (см. табл. 1.2) демонстрирует независи-

мость возвратных состояний от подавляемых. Возвратные состояния в оптими-

зированной управляющей таблице появляются лишь как элементы магазинных

цепочек, представленные отрицательными номерами

Таблица 4.2

Размер компоненты

КОМПОНЕНТА

в элементах в байтах

Характеристики состояний: Descr 19 76

Pool 19 38

Лексический вход: Descr 19 76

Pool 46 276

Резольверный вход 0 0

Пул управляющих элементов 46 276

Семантические цепочки: Descr 20 80

Pool 39 78

Резольверные цепочки: Descr 0 0

Pool 0 0

Магазинные цепочки: Descr 2 8

Pool 2 4

Магазинные символы: Descr 2 8

Pool 2 4

Конечные состояния 1 2

Таблица возвр. состояний: Descr 1 4

Pool 2 8

Всего: 938

Для отличия их от обычных магазинных символов, которые представляются

положительными номерами.

118

Таблица 4.3

Размер компоненты

КОМПОНЕНТА

в элементах в байтах

Характеристики состояний: Descr 13 52

Pool 19 38

Лексический вход: Descr 13 52

Pool 34 204

Резольверный вход 0 0

Пул управляющих элементов 29 174

Семантические цепочки: Descr 20 80

Pool 39 78

Резольверные цепочки: Descr 0 0

Pool 0 0

Магазинные цепочки: Descr 2 8

Pool 2 4

Магазинные символы: Descr 2 8

Pool 2 4

Конечные состояния 1 2

Таблица возвр. состояний: Descr 0 0

Pool 0 0

Всего: 704

В заключение этого раздела приведем оптимизированные управляющие

таблицы для рекурсивного варианта

вычисления n! (табл.4.4) и функции

Аккермана (табл.4.5). В обоих случаях в результате оптимизации таблицы

возвратных состояний исключаются.

Таблица 4.4

Условие Действия Магазин Состояние

1 2 3 4

Класс состояний 1 = {1}

Start 2

Класс состояний 2 = {2}

Valid Open_F_in_S 3

Default

Alarm 4

Класс состояний 3 = {3}

Large Open_F_in_F -7 5

Small SetOne -7 6

В примере 1.4 итеративного варианта вычисления факториала (см. разд.1.6) приведена

уже оптимизированная управляющая таблица.

119

Таблица 4.4 (продложение)

1 2 3 4

Класс состояний 4 = {4 11} (конечное)

Stop

Класс состояний 5 = {5}

Large Open_F_in_F -8 5

Small SetOne -8 6

Класс состояний 6 = {6 10}

Sup

Класс состояний 7= {7}

Close_F_in_S 9

Класс состояний 8 = {8}

Close_F_in_F 6

Класс состояний 9 = {9}

Finish 4

Таблица 4.5

Условие Действие Магазин Состояние

1 2 3 4

Класс состояний 1 = {1}

Start 2

Класс состояний 2 = {2}

Valid Open_A_in_Main 4

Default

Класс состояний 3 = {3}

Finish 5

Класс состояний 4 = {4}

Condition1 SetResult -9 6

Condition2 Open1_A_in_A -9 7

Condition3 Open2_A_in_A -9 8

Класс состояний 5 = {5 12 } (конечный)

Stop

Класс состояний 6 = {6 13 17}

Sup

120

Таблица 4.5 (продложение)

1 2 3 4

Класс состояний 7= {7 15}

Condition1 SetResult -10 6

Condition2 Open1_A_in_A -10 7

Condition3 Open2_A_in_A -10 8

Класс состояний 8 = {8}

Condition1 SetResult -11 6

Condition2 Open1_A_in_A -11 7

Condition3 Open2_A_in_A -11 8

Класс состояний 9 = {9}

Close_A_in_Main 5

Класс состояний 10 = {10 16}

Close_A_in_A 6

Класс состояний 11 = {11}

Close_A_in_A 12

Класс состояний 12 = {14}

Open3_A_in_A 7

4.7. УЧЕТ ДИАГНОСТИЧЕСКИХ СООБЩЕНИЙ

ПРИ ОПТИМИЗАЦИИ

Оптимизация управления несколько ухудшает точность диагностики

ошибок. Это связано с тем, что используемое отношение эквивалентности на

множестве состояний не принимает в расчет еще один возможный

различительный признак — диагностики. При такой оптимизации ничего не

остается, как объединять диагностики, относящиеся ко всем состояниям одного

класса, из-за чего и ухудшается точность характеризации ошибок.

Альтернативное определение отношения эквивалентности состояний,

учитывающее диагностики как еще один различительный признак, не было

использовано, так как платой за точность диагностики ошибок было бы

увеличение объема управляющих таблиц. Из двух возможностей — точные

диагностики при больших управляющих таблицах или чуть менее точные

диагностики при меньших по объему таблицах — была выбрана вторая.

Заметим, что учет диагностик при определении эквивалентности состояний

потребовал бы частичного изменения технологической последовательности:

оптимизации управляющих таблиц должна была бы выполняться после

генерации диагностических сообщений.