Мартыненко Б.К. Синтаксически управляемая обработка данных. Изд. 2-е, дополн
Подождите немного. Документ загружается.
171
56 } UNIT
57 T ‘:’
58 { UNIT
59 T ‘integer’
60 } UNIT
61
→
65
62 FR IsNotActual
63
−<
65
64 T ‘:’
65
−<
68
66 T ‘,’
67
→
51
68 T ‘]’
69 } ROWER
70 N DECLARER
71 } ROWS OF MODE
DECLARATOR
72
→
105
73
−<
92
74 { PROCEDURE
DECLARATOR
75 FS SetFormal
76 T ‘.proc’
77
−<
86
78 T ‘(’
79 { FORMAL DECLARER
80 N DECLARER
81 } FORMAL DECLARER
82
−<
85
83 T ‘,’
84
→
79
85 T ‘)’
86 { FORMAL DECLARER
87 N DECLARER
88 } FORMAL DECLARER
89 FS Reset
90 }
PROCEDURE
DECLARATOR
91
→
105
92 { UNION OF MODE
DECLARATOR
93 FS SetFormal
94 T ‘.union’
95 T ‘(’
96 { FORMAL DECLARER
97 N DECLARER
98 } FORMAL DECLARER
99
−<
102
100 T ‘,’
101
→
96
102 T ‘)’
103 FS Reset
104 } UNION OF MODE
DECLARATOR
105 } DECLARATOR
106 end DECLARER
Словарь терминалов:
1
.loc
5 .struct 9 , 13 ]
2
.heap
6 ( 10 .flex 14 integer
3
ModeIndication
7 ) 11 [ 15 .proc
4
.ref
8 tag 12 : 16 .union
Словарь нетерминалов:
Acronym: Synonym:
1 DECLARER ( ОПИСАТЕЛЬ)
2 GENERATOR ( ГЕНЕРАТОР )
172
Словарь вспомогательных понятий:
Acronym: Synonym:
1 ACTUAL DECLARER ( ФАКТИЧЕСКИЙ_ОПИСАТЕЛЬ)
2 DECLARATOR ( ОПРЕДЕЛИТЕЛЬ)
3 FORMAL DECLARER ( ФОРМАЛЬНЫЙ_ОПИСАТЕЛЬ)
4 PORTRAYER ( СПЕЦИФИКАТОР_ПОЛЕЙ)
5 PROCEDURE DECLARATOR ( ОПРЕДЕЛИТЕЛЬ_ПРОЦЕДУРЫ)
6 REFERENCE TO MODE DECLARATOR ( ОПРЕДЕЛИТЕЛЬ_ИМЕНИ)
7 ROWER ( ИНДЕКСАТОР)
8 ROWS OF MODE DECLARATOR ( ОПРЕДЕЛИТЕЛЬ_МАССИВА)
9 STRUCTURED WITH FIELDS DECLARATOR (ОПРЕДЕЛИТЕЛЬ_СТРУКТУРЫ)
10 UNION OF MODE DECLARATOR ( ОПРЕДЕЛИТЕЛЬ_ОБЪЕДИНЕНИЯ)
11 UNIT ( ОСНОВА)
12 VIRTUAL DECLARER ( ВИРТУАЛЬНЫЙ_ОПИСАТЕЛЬ)
Словари контекстных символов:
Forward Pass Semantics: Forward Pass Resolvers:
1 Complete 4 SetActual 1 IsActual
2 Init 5 SetFormal 2 IsNotActual
3 Reset 6 SetVirtual 3 IsVIRACT
Управляющая таблица прямого просмотра Gener. Сначала приведем
таблицу управляющих элементов
118
(табл. 7.1), а затем таблицу возвратных
состояний анализатора генераторов Алгола 68 (табл. 7.2).
Таблица 7.1
Вход Резольвер Семантика Магазин Состояние
1 2 3 4 5
Состояние 1={0}
.loc Init;SetActual 2
.heap Init;SetActual 3
Состояния 2={4}, 3={6}
ModeIndication 1 4
.ref SetVirtual 1 5
.struct 1 6
.flex IsVIRACT 1 7
[ 1 8
.proc SetFormal 1 9
.union SetFormal 1 10
118
Совмещенную с таблицей резольверов в форме дополнительной графы Резольвер в
составе таблицы управляющих элементов.
173
Продолжение табл. 7.1
Состояния 4={14}, 24={70}, 32={41}
ε
Sup
Состояние 5={20}
ModeIndication 2 4
.ref SetVirtual 2 5
.struct 2 6
.flex IsVIRACT 2 7
[ 2 8
.proc SetFormal 2 9
.union SetFormal 2 10
Состояние 6={29}
.struct 11
Состояние 7={48}
[ 8
Состояния 8={50}, 12={66}
, IsNotActual 12
: IsNotActual 13
] IsNotActual 14
integer IsActual 15
Состояние 9={76}
ModeIndication 3 4
.ref SetVirtual 3 5
.struct 3 6
( 16
.flex IsVIRACT 3 7
[ 3 8
.proc SetFormal 3 9
.union SetFormal 3 10
Состояние 10={29}
( 17
Состояние 11={30}
ModeIndication 4 4
.ref SetVirtual 4 5
.struct 4 6
.flex IsVIRACT 4 7
[ 4 8
.proc SetFormal 4 9
.union SetFormal 4 10
174
Продолжение табл. 7.1
Состояния 13 = {64}, 19 = {59}
, 12
] 14
Состояние 14 = {68}
ModeIndication 5 4
.ref SetVirtual 5 5
.struct 5 6
.flex IsVIRACT 5 7
[ 5 8
.proc SetFormal 5 9
.union SetFormal 5 10
Состояние 15 = {55 59}
, 12
: 18
] 14
Состояния 16 = {78}, 29 = {83}
ModeIndication 6 4
.ref SetVirtual 6 5
.struct 6 6
.flex IsVIRACT 6 7
[ 6 8
.proc SetFormal 6 9
.union SetFormal 6 10
Состояния 17 = {95}, 31 = {100}
ModeIndication 7 4
.ref SetVirtual 7 5
.struct 7 6
.flex IsVIRACT 7 7
[ 7 8
.proc SetFormal 7 9
.union SetFormal 7 10
Состояние 18 = {57}
integer Complete 19
Состояние 20 = {8} (конечное)
ε
Complete
Stop
175
Продолжение табл. 7.1
Состояния 21 = {22}, 22 = {87}, 30 = {102}
ε
Reset
Sup
Состояние 23 = {32}
tag 27
Состояние 25 = {80}
) 28
, 29
Состояние 26 = {80}
) 30
, 31
Состояние 27 = {33}
) 32
, 33
Состояние 28 = {85}
ModeIndication 3 4
.ref SetVirtual 3 5
.struct 3 6
.flex IsVIRACT 3 7
[ 3 8
.proc SetFormal 3 9
.union SetFormal 3 10
Состояние 33 = {35 38}
ModeIndication 4 4
.ref SetVirtual 4 5
.struct 4 6
tag 27
.flex IsVIRACT 4 7
[ 4 8
.proc SetFormal 4 9
.union SetFormal 4 10
Таблица 7.2
Подавляемые состояния: 4, 21, 22, 24, 30, 32
Магазинный символ Возвратное состояние
1 20
2 21
3 22
4 23
5 24
6 25
7 26
176
Замечание 1. Одинаковые таблички, относящиеся к различным состояниям,
ради краткости сведены под общие заголовки, содержащие характеристики
соответствующих состояний. Характеристика состояния — некоторое
множество вершин управляющей граф-схемы. Вершины заданы номерами
представляющих их записей управляющей граф-схемы.
Замечание 2. Таблица возвратных состояний (табл. 7.2) фактически состоит
из шести совершено одинаковых подтаблиц для подавляемых состояний 4, 21,
22, 24, 30 и 32
119
. Это означает, что возвратные состояния не зависят от
подавляемых. Они однозначно определяются магазинными символами. Как
следствие этого обстоятельства, после оптимизации процессора Gener таблица
возвратных состояний исчезает, а в управляющих элементах магазинные
символы замещаются соответствующими возвратными состояниями,
представленными их номерами со знаком минус — см. далее табл. 7.4. Размеры
компонент управляющей таблицы Gener приведены в табл. 7.3. Большинство из
них представляются динамическими массивами, состоящими из дескрипторов
(Descr) и собственно элементов, размещаемых в пулах (Pool).
Суммарный объем (в байтах) всех компонент таблицы позволит в дальней-
шем судить о степени экономии памяти за счет оптимизации управляющих
таблиц обсуждаемых процессоров.
119
В них графа Резольверы опущена, поскольку в данном примере возвратные состояния не
зависят от состояния операционной среды.
Таблица 7.3
Компонента Элементов Байт
Характеристики cостояний:
Descr
33
132
Pool 34 68
Лексический вход: Descr 33 132
Pool 90 540
Резольверный вход 11 44
Пул управляющих элементов 71 426
Семантические цепочки: Descr 5 20
Pool 6 12
Резольверные цепочки: Descr 3 12
Pool 3 6
Магазинные цепочки: Descr 7 28
Pool 7 14
Магазинные символы: Descr 7 28
Pool 7 14
Конечные состояния 1 2
Табл. возвр. состояний: Descr 1 4
Pool 7 28
1510
177
Оптимизация управляющей таблицы прямого просмотра процессора Gener
производится путем замены состояний, входных и магазинных символов (в
табл. 7.1, 7.2) соответствующими классами эквивалентности, которые указаны
ниже,
— для состояний:
1: {1} 7: {8 12} 13: {15} 19: {23}
2: {2 3} 8: {9} 14: {16 29} 20: {25}
3: {4 24 32} 9: {10} 15: {17 31} 21: {26}
4: {5 28} 10: {11} 16: {18} 22: {27}
5: {6} 11: {13 19} 17: {20} 23: {33}
6: {7} 12: {14} 18: {21 22 30}
— для входных символов:
1: { .loc .heap } 6: { ) } 11: { : }
2: { ModeIndication } 7: { tag } 12: { ] }
3: { .ref } 8: { , } 13: { integer }
4: { .struct } 9: { .flex } 14: { .proc }
5: { ( } 10: { [ } 15: { .union }
и для магазинных символов:
1: {1} 3: {4} 5: {6}
2: {2 3} 4: {5} 6: {7}
В результате оптимизации процессора Gener получается управляющая
таблица, которая состоит только из таблицы управляющих элементов
120
(табл. 7.4). Таблица возвратных состояний, как уже отмечалось, в результате
оптимизации исключена.
Таблица 7.4
Вход Резольвер Семантика
Мага-
зин
Состо-
яние
1 2 3 4 5
Класс состояний 1 = {1}
[.loc] Init;SetActua
l
2
Класс состояний 2 = {2 3}
[ModeIndication] –17 3
[.ref] SetVirtual –17 4
[.struct] –17 5
[.flex] IsVIRACT –17 6
[[] –17 7
[.proc] SetFormal –17 8
[.union] SetFormal –17 9
120
Совмещенной с таблицей резольверов.
178
Продолжение табл. 7.4
Класс состояний 3 = {4 24 32}
ε
Sup
Класс состояний 4 = {5 28}
[ModeIndication] –18 3
[.ref] SetVirtual –18 4
[.struct] –18 5
[.flex] IsVIRACT –18 6
[[] –18 7
[.proc] SetFormal –18 8
[.union] SetFormal –18 9
Класс состояний 5 = {6}
[(] 10
Класс состояний 6 = {7}
[]] 7
Класс состояний 7 = {8 12}
[,] IsNotActual 7
[:] IsNotActual 11
[]] IsNotActual 12
[integer] IsActual 13
Класс состояний 8 = {9}
[ModeIndication] –18 3
[.ref] SetVirtual –18 4
[.struct] –18 5
[(] 14
[.flex] IsVIRACT –18 6
[[] –18 7
[.proc] SetFormal –18 8
[.union] SetFormal –18 9
Класс состояний 9 = {10}
[(] 15
Класс состояний 10 = {11}
[ModeIndication] –19 3
[.ref] SetVirtual –19 4
[.struct] –19 5
[.flex] IsVIRACT –19 6
[[] –19 7
[.proc] SetFormal –19 8
[.union] SetFormal –19 9
179
Продолжение табл. 7.4
Класс состояний 11 = {13 19}
[,] 7
[]] 12
Класс состояний 12={14}
[ModeIndication] –3 3
[.ref] SetVirtual –3 4
[.struct] –3 5
[.flex] IsVIRACT –3 6
[[] –3 7
[.proc] SetFormal –3 8
[.union] SetFormal –3 9
[]] 7
Класс состояний 13 = {15}
[,] 7
[:] 16
[]] 12
Класс состояний 14 = {16 29}
[ModeIndication] –20 3
[.ref] SetVirtual –20 4
[.struct] –20 5
[.flex] IsVIRACT –20 6
[[] –20 7
[.proc] SetFormal –20 8
[.union] SetFormal –20 9
Класс состояний 15 = {17 31}
[ModeIndication] –21 3
[.ref] SetVirtual –21 4
[.struct] –21 5
[.flex] IsVIRACT –21 6
[[] –21 7
[.proc] SetFormal –21 8
[.union] SetFormal –21 9
Класс состояний 16 = {18}
[integer] Complete 11
Класс состояний 17 = {20} (конечных)
ε
Complete
Stop
Класс состояний 18 = {21 22 30}
ε
Reset
Sup
Класс состояний 19={23}
[tag] 22
Класс состояний 20={25}
[)] 4
[,] 14
180
Продолжение табл. 7.4
Класс состояний 21={26}
[)] 18
[,] 15
Класс состояний 22 = {27}
[)] 3
[,] 23
Класс состояний 23 = {33}
[ModeIndication] –19 3
[.ref] SetVirtual –19 4
[.struct] –19 5
[tag] 22
[.flex] IsVIRACT –19 6
[[] –19 7
[.proc] SetFormal –19 8
[.union] SetFormal –19 9
В этой таблице отрицательные номера в графе Магазин представляют воз-
вратные состояния
121
.
Количественные характеристики компонент оптимизированной управляю-
щей таблицы процессора Gener приведены в табл. 7.5.
Таблица 7.5
Компонента Элементов Байт
Классы состояний: Descr 23 92
Pool 33 66
Лексический вход: Descr 33 92
Pool 82 492
Резольверный вход 10 40
Пул управляющих элементов 59 354
Семантические цепочки: Descr 5 20
Pool 6 12
Резольверные цепочки: Descr 3 12
Pool 3 6
Магазинные цепочки: Descr 6 24
Pool 6 12
Классы магазинных символов:
Descr
6
24
Pool 7 14
Классы конечных состояний 1 2
Табл. возвр. состояний: Descr 0 0
Pool 0 0
1262
121
В общем случае в результате оптимизации не все магазинные символы замещаются
возвратными состояниями. Знак минус как раз и служит для их отличия от "обычных"
магазинных символов.