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

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

181

Сравнение размеров управляющих таблиц неоптимизированного (см.

табл. 7.3) и оптимизированного (см. табл. 7.5) вариантов процессора Gener

показывает, что оптимизация дает в этом случае 16%-ную экономию памяти.

Диагностики оптимизированного процессора Gener. Генератор

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

процессора Gener дает следующий набор диагностик:

В классе состояний 1:

В конструкции ГЕНЕРАТОР ожидается '.loc', '.heap'

В классе состояний 2:

В конструкции ГЕНЕРАТОР после компоненты '.heap'

ожидается ФАКТИЧЕСКИЙ ОПИСАТЕЛЬ

В конструкции ГЕНЕРАТОР после компоненты '.loc'

ожидается ФАКТИЧЕСКИЙ ОПИСАТЕЛЬ

В классе состояний 3: { Никаких диагностик}

В классе состояний 4:

В конструкции ОПРЕДЕЛИТЕЛЬ ИМЕНИ

после компоненты '.ref' ожидается ВИРТУАЛЬНЫЙ ОПИСАТЕЛЬ

В конструкции ОПРЕДЕЛИТЕЛЬ ПРОЦЕДУРЫ

после компоненты ')' ожидается ФОРМАЛЬНЫЙ ОПИСАТЕЛЬ

В классе состояний 5:

В конструкции ОПРЕДЕЛИТЕЛЬ СТРУКТУРЫ

после компоненты '.struct' ожидается '('

В классе состояний 6:

В конструкции ОПРЕДЕЛИТЕЛЬ МАССИВА

после компоненты '.flex' ожидается ИНДЕКСАТОР

В классе состояний 7:

В конструкции ИНДЕКСАТОР после компоненты ',' ожидается ОСНОВА, ':', ']'

В классе состояний 8:

В конструкции ОПРЕДЕЛИТЕЛЬ ПРОЦЕДУРЫ

после компоненты '.proc' ожидается '(', ФОРМАЛЬНЫЙ ОПИСАТЕЛЬ

В классе состояний 9:

В конструкции ОПРЕДЕЛИТЕЛЬ ОБЪЕДИНЕНИЯ

после компонеты '.union' ожидается '('

В классе состояний 10:

В конструкции ОПРЕДЕЛИТЕЛЬ СТРУКТУРЫ

после компоненты '(' ожидается СПЕЦИФИКАТОР ПОЛЕЙ

В классе состояний 11:

В конструкции ИНДЕКСАТОР после компоненты ':' ожидается ',', ']'

В конструкции ИНДЕКСАТОР после компоненты ОСНОВА ожидается ',', ']'

В классе состояний 12:

В конструкции ОПРЕДЕЛИТЕЛЬ МАССИВА

после компоненты ИНДЕКСАТОР ожидается ОПИСАТЕЛЬ

182

В классе состояний 13:

В конструкции ИНДЕКСАТОР после компоненты ОСНОВА ожидается ',', ']'

В конструкции ИНДЕКСАТОР после компоненты ОСНОВА ожидается ':'

В классе состояний 14:

В конструкции ОПРЕДЕЛИТЕЛЬ ПРОЦЕДУРЫ

после компоненты '(' ожидается ФОРМАЛЬНЫЙ ОПИСАТЕЛЬ

В конструкции ОПРЕДЕЛИТЕЛЬ ПРОЦЕДУРЫ

после компоненты ',' ожидается ФОРМАЛЬНЫЙ ОПИСАТЕЛЬ

В классе состояний 15:

В конструкции ОПРЕДЕЛИТЕЛЬ ОБЪЕДИНЕНИЯ

после компоненты '(' ожидается ФОРМАЛЬНЫЙ ОПИСАТЕЛЬ

конструкции ОПРЕДЕЛИТЕЛЬ ОБЪЕДИНЕНИЯ

после компоненты ',' ожидается ФОРМАЛЬНЫЙ ОПИСАТЕЛЬ

В классе состояний 16:

В конструкции ИНДЕКСАТОР после компоненты ':' ожидается ОСНОВА

В классах состояний 17 и 18: { Никаких диагностик }

В классе состояний 19:

В конструкции СПЕЦИФИКАТОР ПОЛЕЙ

после компоненты ОПИСАТЕЛЬ ожидается 'tag'

В классе состояний 20:

В конструкции ОПРЕДЕЛИТЕЛЬ ПРОЦЕДУРЫ

после компоненты ФОРМАЛЬНЫЙ ОПИСАТЕЛЬ ожидается ',', ')'

В классе состояний 21:

В конструкции ОПРЕДЕЛИТЕЛЬ ОБЪЕДИНЕНИЯ

после компоненты ФОРМАЛЬНЫЙ ОПИСАТЕЛЬ ожидается ',', ')'

В классе состояний 22:

В конструкции ОПРЕДЕЛИТЕЛЬ СТРУКТУРЫ

после компоненты СПЕЦИФИКАТОР ПОЛЕЙ ожидается ')'

В конструкции СПЕЦИФИКАТОР ПОЛЕЙ после компоненты 'tag'ожидается ','

В классе состояний 23:

В конструкции СПЕЦИФИКАТОР ПОЛЕЙ после компоненты ',' ожидается 'tag'

В конструкции СПЕЦИФИКАТОР ПОЛЕЙ

после компоненты ',' ожидается ОПИСАТЕЛЬ

Замечание. Как видим, к одному классу эквивалентных состояний может

относиться несколько вариантов диагностических сообщений. Это связано с

возможностью трактовки ошибки с точки зрения нескольких конструкций раз-

ного уровня вложенности или неоднозначностью распознавания конструкций

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

3, 17 и 18, не существует никакой информации для формирования диагностик.

Как исключение, диагностические сообщения, относящиеся к начальному

классу состояний (первому), не содержат в своей рамке части "после

…". Это и

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

цепочки.

183

7.4. ЛЕКСИКА ГЕНЕРАТОРОВ

Продолжим обсуждение процессора GenerLex, используемого в качестве

сканера для анализатора генераторов Алгола 68. Начнем с граф-схемы,

построенной по грамматике GenerLex (см. разд. 7.1).

Управляющая граф-схема GenerLex:

0 begin Lexeme

−<

3 { Comment

4 FS SetComment

5 T '{'

6 FS Restore

7 T '}'

8 } Comment

→

10 T Blind

→

12 FS InitLex

−<

14 { Integer

15 FS InitInteger

16 FS Append

17 T 'Digit'

−<

19 } Integer

→

−<

22 { Tag

23 FS InitTag

24 T 'Letter'

−<

26 FS Append

−<

28 T 'Letter'

→

30 T 'Digit'

→

32 } Tag

→

−<

35 { BoldTag

36 FS SetBlindVisible

37 T '.'

38 { Tag

39 FS InitTag

40 T 'Letter'

−<

42 FS Append

−<

44 T 'Letter'

→

46 T 'Digit'

→

48 } Tag

−<

50 FR IsKeyWord

→

52 FR IsModeIndication

53 FR SetModeIndication

−<

55 T 'Blind'

56 FS SetBlindInvisible

57 } BoldTag

184

→

59 { SpecSymbol

−<

61 FS SetLeftBracket

62 T '['

→

−<

65 FS SetRightBracket

66 T ']'

→

−<

69 FS SetLeftParenthesis

70 T '('

→

−<

73 FS SetRightParenthesi

74 T ')'

→

−<

77 FS SetComma

78 T ','

→

80 FS SetColon

81 T ':'

82 } SpecSymbol

83 FS MakeLex

−<

85 { Comment

86 FS SetComment

87 T '{'

88 FS Restore

89 T '}'

90 } Comment

→

92 end Lexeme

Словарь терминалов:

1 'Digit' 4 'Letter' 7 '[' 10 ')'

2 '[' 5 '.' 8 ']' 11 ','

3 '}' 6 'Blind' 9 '(' 12 ':'

Словарь нетерминалов:

Acronym: Synonym:

1 Lexeme ( Lexeme)

Словарь вспомогательных понятий:

Acronym: Synonym:

1 Bold Tag ( Bold Tag)

2 Comment (Comment)

3 Integer ( Integer)

4 Spec Symbol ( Spec Symbol)

5 Tag ( Tag)

185

Словари контекстных символов:

Forward pass semantics: Forward pass resolvers:

1 Append 9 SetColon 1 IsKeyWord

2 InitInteger 10 SetComma 2 IsModeIndication

3 InitLex 11 SetComment

4 InitTag 12 SetLeftBracket

5 MakeLex 13 SetLeftParenthesis

6 Restore 14 SetModeIndication

7 SetBlindInvisible 15 SetRightBracket

8 SetBlindVisible 16 SetRightParenthesis

Управляющая таблица прямого просмотра GenerLex состоит из одной

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

122

(табл.7.6), поскольку соответствую-

щий процессор — конечный. По этой же причине в ней отсутствует графа

Магазин.

Таблица 7.6

Вход Резольвер Семантика

Состоя-

ние

1 2 3 4

Состояние 1={0}, 6={10}, 14={7}

Digit InitLex; InitInteger; Append 2

{ SetComment 3

Letter InitLex; InitTag 4

. InitLex; SetBlindVisible 5

Blind 6

[ InitLex; SetLeftBracket 7

] InitLex; SetRightBracket 8

( InitLex; SetLeftParenthesis 9

) InitLex; SetRightParenthesis 10

, InitLex; SetComma 11

: InitLex; SetColon 12

Состояния 2={17} (конечное)

MakeLex

Stop

Digit Append 2

{ MakeLex; SetComment 13

122

Cовмещенной с таблицей резольверов в форме дополнительной графы Резольвер в ее

составе.

186

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

1 2 3 4

Состояния 3={5}

} Restore 14

Состояния 4={24}, 15={30}, 16={28} (конечные)

MakeLex

Stop

Digit Append 15

{ MakeLex; SetComment 13

Letter Append 16

Состояния 5={37}

Letter InitTag 17

Состояния 7={62},8={66},9={70},10={74},11={78},12={81} (конечные)

MakeLex

Stop

{ MakeLex; SetComment 13

Состояния 13={87}

} Restore 18

Состояния 17={40}, 19={46}, 20={44} (конечные)

IsKeyWord SetBlindInvisible; MakeLex

Stop

IsModeIndication SetModeIndication;

SetBlindInvisible; MakeLex

Stop

Digit Append 19

{ IsKeyWord

SetBlindInvisible; MakeLex;

SetComment

IsModeIndication

SetModeIndication; SetBlindInvisible;

MakeLex; SetComment

Letter Append 20

Blind IsKeyWord 21

IsModeIndication SetModeIndication 21

Состояние 18 ={ 89 } (конечное)

{ SetComment 13

Состояние 21 ={ 55 } (конечное)

SetBlindInvisible; MakeLex

Stop

{

SetBlindInvisible; MakeLex;

SetComment

Напомним, что ε-вход используется лишь в том случае, когда текущий

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

данному состоянию.

187

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

то ее следует интерпретировать как тождественно истинный предикат. В

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

каждой резольверной цепочке. Если ни одна из конъюнкций не есть true, то

имеет место контекстная ошибка. Если две или более конъюнкций (не считая

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

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

последнюю очередь.

Символ Stop в графе Состояние означает завершение работы процессора-

сканера.

Размеры компонент управляющей таблицы GenerLex представлены в

табл. 7.7. Поскольку этот процессор — конечный, то ее компоненты,

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

размер. По той же причине никакой таблицы возвратных состояний не

существует.

Таблица 7.7

Компонента Элементов Байт

Характеристики состояний: Descr 21 84

Pool 21 42

Лексический вход: Descr 21 84

Pool 32 192

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

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

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

Pool 36 72

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

Pool 3 6

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

Pool 0 0

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

Pool 0 0

Конечные состояния 15 30

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

Pool 0 0

794

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

получается из его первоначальной управляющей таблицы (см. табл. 7.6) путем

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

оптимизации были использованы следующие классы эквивалентности

состояний:

188

1: {1 6 14} 4: {4 15 16} 7: {13} 10: {21}

2: {2} 5: {5} 8: {7 19 20}

3: {3} 6: {7 8 9 10 11 12} 9: {18}

и входных символов:

1: {'Digit' } 4: {'Letter'} 7: {'['} 10: {')'}

2: {'{'} 5: {'.'} 8: {']'} 11: {','}

3: {'}'} 6: {'Blind'} 9: {'('} 12: {':'}

Здесь классы пронумерованы, а их члены заключены в фигурные скобки.

Управляющая таблица оптимизированного сканера генераторов состоит из

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

форме дополнительной графы Резольвер в ее составе (см. табл. 7.8).

Таблица 7.8

Вход Резольвер Семантика

Состоя-

ние

1 2 3 4

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

[Digit] InitLex; InitInteger; Append 2

[{] SetComment 3

[Letter] InitLex; InitTag 4

[.] InitLex; SetBlindVisible 5

[Blind] 1

[[] InitLex; SetLeftBracket 6

[]] InitLex; SetRightBracket 6

[(] InitLex; SetLeftParenthesis 6

[)] InitLex; SetRightParenthesis 6

[,] InitLex; SetComma 6

[:] InitLex; SetColon 6

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

MakeLex

Stop

[Digit] Append 2

[{] MakeLex; SetComment 7

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

[}] Restore 1

Класс состояний 4={4 15 16} (конечных)

MakeLex

Stop

[Digit] Append 4

[{] MakeLex; SetComment 7

[Letter] Append 4

189

Продолжение таблицы 7.8

1 2 3 4

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

[Letter] InitTag 8

Класс состояний 6={7 8 9 10 11 12 } (конечных)

MakeLex

Stop

[{] MakeLex; SetComment 7

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

[}] Restore 9

Класс состояний 8={17 19 20 } (конечных)

IsKeyWord SetBlindInvisible; MakeLex

Stop

IsModeIndication SetModeIndication;

SetBlindInvisible; MakeLex

Stop

[Digit] Append 8

[{] IsKeyWord SetBlindInvisible; MakeLex;

SetComment

IsModeIndication SetModeIndication;

SetBlindInvisible; MakeLex;

SetComment

[Letter] Append 8

[Blind] IsKeyWord 10

IsModeIndication SetModeIndication 10

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

Stop

[{] SetComment 7

Класс состояний 10 = { 21 } (конечных)

SetBlindInvisible; MakeLex

Stop

[{] SetBlindInvisible; MakeLex;

SetComment

Как видим, вместо 21 состояния в исходном процессоре GenerLex

оптимизированный процессор имеет всего 10 классов эквивалентных

состояний — входов в управляющую таблицу.

Что касается классов эквивалентности входных символов — лексических

классов (Digit, Letter, Blind), то они были предусмотрены заранее без

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

спецификации процессора. Поэтому-то никакого полезного эффекта от

оптимизации лексических входов мы не наблюдаем.

190

Размеры компонент оптимизированной таблицы GenerLex — см.

табл. 7.9.

Таблица 7.9

Компонента Элементов Байт

Классы состояний: Descr 10 40

Pool 21 42

Лексический вход: Descr 10 40

Pool 32 192

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

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

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

Pool 36 72

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

Pool 2 4

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

Pool 0 0

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

Descr

0 0

Pool 0 0

Классы конечных состояний 6 12

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

Pool 0 0

676

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

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

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

составляет 15% — почти столько же, сколько дала оптимизация главного

процессора Gener (16%).

Диагностические сообщения оптимизированного процессора GenerLex

представлены в следующем перечне:

В классе состояний 1:

В конструкции Lexeme

ожидается Comment, 'Blind', Integer, Tag, BoldTag, SpecSymbol

В классе состояний 2:

В конструкции Integer после компоненты 'Digit' ожидается 'Digit'

В конструкции Lexeme после компоненты Integer ожидается Comment

В классе состояний 3:

В конструкции Comment после компоненты '{' ожидается '}'

В классе состояний 4:

В конструкции Lexeme после компоненты Tag ожидается Comment

В конструкции Tag после компоненты 'Digit' ожидается 'Letter', 'Digit'

В конструкции Tag после компоненты 'Letter' ожидается 'Letter', 'Digit'