Мартыненко Б.К. Синтаксически управляемая обработка данных. Изд. 2-е, дополн
Подождите немного. Документ загружается.
191
В классе состояний 5:
В конструкции BoldTag после компоненты '.' ожидается Tag
В конструкции Lexeme
после компоненты SpecSymbol ожидается Comment
В классе состояний 7:
В конструкции Comment после компоненты '{' ожидается '}'
В классе состояний 8:
В конструкции BoldTag после компоненты Tag ожидается 'Blind'
В конструкции Lexeme после компоненты BoldTag ожидается Comment
В конструкции Tag после компоненты 'Digit' ожидается 'Letter', 'Digit'
В конструкции Tag после компоненты 'Letter' ожидается 'Letter', 'Digit'
В классе состояний 9:
В конструкции Lexeme после компоненты Comment ожидается Comment
В классе состояний 10:
В конструкции Lexeme после компоненты BoldTag ожидается Comment
Замечание 4. В спецификации трансляции GenerLex не были определены
синонимы для нетерминала и вспомогательных понятий. Поэтому в
приведенных диагностических сообщениях использованы рабочие термины
(акронимы). Разумеется, в окончательной версии этого процессора следовало
бы использовать русско-язычную терминологию. Здесь этого не сделано, чтобы
показать, что на ранней стадии разработки трансляции выбор окончательной
терминологии для диагностических сообщений временно можно отложить "на
потом".
7.5. ОДНОПРОСМОТРОВЫЙ АНАЛИЗ
ГЕНЕРАТОРОВ АЛГОЛА 68
Для иллюстрации многопроцессорной
123
техники трансляции здесь мы
рассмотрим ход анализа на лексическом и синтаксическом уровнях одного
локального генератора Алгола 68, а именно:
.loc .struct ([5].int x, .proc[ ] .real y).
Лексический анализ реализуется конечным процессором GenerLex, а
синтаксический — сплайновым процессором Gener. Собственно
сканированием входного текста занимается транслитератор, использующий
таблицу транслитерации, построенную по описанию микролексики в
спецификации трансляции GenerLex. Оба процессора однопросмотровые и
контекстно-чувствительные. Тот и другой используют оптимизированные
управляющие таблицы (см. табл.7.4 и 7.8).
Протокол однопросмотрового анализа генератора : .loc .struct ( [ 5 ] .int x,
.proc [ ] .real y). В представленном далее протоколе (табл. 7.10) левая колонка
показывает работу основного процессора Gener, а правая — процессора
123
Имеется в виду использование нескольких языковых процессоров.
192
GenerLex, используемого в качестве сканера. Номера строк протокола
представляют дискретное время. После литерного представления лексемы в
скобках указаны номер лексического класса и номер лексемы в этом классе
(для каждого процессора эта нумерация — своя).
Таблица 7.10
Уровень синтаксического
анализатора (Gener):
Уровень лексического
анализатора (GenerLex):
1 2
0 Состояние 1
1 Состояние: 1
2 Лексема: '.' (5,1)
3 ... принята в состоянии 1
4 Семантики: InitLex SetBlindVisible
5 Состояние: 5
6 Лексема: 'l' (4,12)
7 ... принята в состоянии 5
8 Семантики: InitTag
9 Состояние: 8
10 Лексема: 'o' (4,15)
11 ... принята в состоянии 8
12 Семантики: Append
13 Состояние: 8
14 Лексема: 'c' (4,3)
15 ... принята в состоянии 8
16 Семантики: Append
17 Состояние: 8
18 Лексема: ' ' (6,1)
19 Резольверы: Is KeyWord (true)
20 Резольверы: IsModeIndication (false)
21 ... принята в состоянии 8
22 Состояние: 10
23 Лексема: '.' (5,1)
24 Семантики: SetBlindInvisible
MakeLex
25 Лексема: '.loc' (1,0)
26 ... принята в состоянии 1
27 Семантики: Init SetActual
28 Состояние: 2
29 Состояние: 1
30 Лексема: '.' (5,1)
31 ... принята в состоянии 1
32 Семантики: InitLex SetBlindVisible
33 Состояние: 5
34 Лексема: 's' (4,19)
35 ... принята в состоянии 5
36 Семантики: InitTag
37 Состояние: 8
38 Лексема: 't' (4,20)
39 ... принята в состоянии 8
40 Семантики: Append
41 Состояние: 8
193
Продолжение табл. 7.10
1 2
42 Лексема: 'r' (4,18)
43 ... принята в состоянии 8
44 Семантики: Append
45 Состояние: 8
46 Лексема: 'u' (4,21)
47 ... принята в состоянии 8
48 Семантики: Append
49 Состояние: 8
50 Лексема: 'c' (4,3)
51 ... принята в состоянии 8
52 Семантики: Append
53 Состояние: 8
54 Лексема: 't' (4,20)
55 ... принята в состоянии 8
56 Семантики: Append
57 Состояние: 8
58 Лексема: '(' (9,1)
59 Резольверы : IsKeyWord(true)
60 Резольверы : IsModeIndication (false)
61 Семантики: SetBlindInvisible
MakeLex
62 Лексема: '.struct' (5,0)
63 ... принята в состоянии 2
64 Состояние: 5
65 Состояние: 1
66 Лексема: '(' (9,1)
67 ... принята в состоянии 1
68 Семантики: InitLex
SetLeftParenthesis
69 Состояние: 6
70 Лексема: '[' (7,1)
71 Семантики: MakeLex
72 Лексема: '(' (6,0)
73 ... принята в состоянии 5
74 Состояние: 10
75 Состояние: 1
76 Лексема: '[' (7,1)
77 ... принята в состоянии 1
78 Семантики: InitLex
SetLeftBracket
79 Состояние: 6
80 Лексема: '5' (1,6)
81 Семантики: MakeLex
82 Лексема: '[' (11,0)
83 ... принята в состоянии 10
84 Состояние: 7
85 Состояние: 1
86 Лексема: '5' (1,6)
87 ... принята в состоянии 1
194
Продолжение табл. 7.10
1 2
88 Семантики: InitLex InitInteger
Append
89 Состояние: 2
90 Лексема: ']' (8,1)
91 Семантики: MakeLex
92 Лексема: '5' (14,0)
93 Резольверы: IsActual (true)
94 ... принята в состоянии 7
95 Состояние: 13
96 Состояние: 1
97 Лексема: ']' (8,1)
98 ... принята в состоянии 1
99 Семантики: InitLex SetRightBracket
100 Состояние: 6
101 Лексема: '.' (5,1)
102 Семантики: MakeLex
103 Лексема: ']' (13,0)
104 ... принята в состоянии 13
105 Состояние: 12
106 Состояние: 1
107 Лексема: '.' (5,1)
108 ... принята в состоянии 1
109 Семантики: InitLex SetBlindVisible
110 Состояние: 5
111 Лексема: 'i' (4,9)
112 ... принята в состоянии 5
113 Семантики: InitTag
114 Состояние: 8
115 Лексема: 'n' (4,14)
116 ... принята в состоянии 8
117 Семантики: Append
118 Состояние: 8
119 Лексема: 't' (4,20)
120 ... принята в состоянии 8
121 Семантики: Append
122 Состояние: 8
123 Лексема: ' ' (6,1)
124 Резольверы: IsKeyWord (false)
125 Резольверы: IsModeIndication (true)
126 ... принята в состоянии 8
127 Семантики: SetModeIndication
128 Состояние: 10
129 Лексема: 'x' (4,24)
130 Семантики: SetBlindInvisible
MakeLex
131 Лексема: '.int' (3,0)
132 ... принята в состоянии 12
133 Состояние: 3
134 Состояние: 3
135 Состояние: 19
195
Продолжение табл. 7.10
1 2
136 Состояние: 1
137 Лексема: 'x' (4,24)
138 ... принята в состоянии 1
139 Семантики: InitLex InitTag
140 Состояние: 4
141 Лексема: ',' (11,1)
142 Семантики: MakeLex
143 Лексема: 'x' (8,0)
144 ... принята в состоянии 19
145 Состояние: 22
146 Состояние: 1
147 Лексема: ',' (11,1)
148 ... принята в состоянии 1
149 Семантики: InitLex SetComma
150 Состояние: 6
151 Лексема: '.' (5,1)
152 Семантики: MakeLex
153 Лексема: ',' (9,0)
154 ... принята в состоянии 22
155 Состояние: 23
156 Состояние: 1
157 Лексема: '.' (5,1)
158 ... принята в состоянии 1
159 Семантики: InitLex SetBlindVisible
160 Состояние: 5
161 Лексема: 'p' (4,16)
162 ... принята в состоянии 5
163 Семантики: InitTag
164 Состояние: 8
165 Лексема: 'r' (4,18)
166 ... принята в состоянии 8
167 Семантики: Append
168 Состояние: 8
169 Лексема: 'o' (4,15)
170 ... принята в состоянии 8
171 Семантики: Append
172 Состояние: 8
173 Лексема: 'c' (4,3)
174 ... принята в состоянии 8
175 Семантики: Append
176 Состояние: 8
177 Лексема: '[' (7,1)
178 Резольверы: IsKeyWord(true)
179 Резольверы: IsModeIndication (false)
180 Семантики: SetBlindInvisible
MakeLex
181 Лексема: '.proc' (15,0)
182 ... принята в состоянии 23
183 Семантики: SetFormal
184 Состояние: 8
196
Продолжение табл. 7.10
1 2
185 Состояние: 1
186 Лексема: '[' (7,1)
187 ... принята в состоянии 1
188 Семантики: InitLex SetLeftBracket
189 Состояние: 6
190 Лексема: ']' (8,1)
191 Семантики: MakeLex
192 Лексема: '[' (11,0)
193 ... принята в состоянии 8
194 Состояние: 7
195 Состояние: 1
196 Лексема: ']' (8,1)
197 ... принята в состоянии 1
198 Семантики: InitLex SetRightBracket
199 Состояние: 6
200 Лексема: '.' (5,1)
201 Семантики: MakeLex
202 Лексема: ']' (13,0)
203 Резольверы:IsNotActual(true)
204 ... принята в состоян 7
205 Состояние: 12
206 Состояние: 1
207 Лексема: '.' (5,1)
208 ... принята в состоянии 1
209 Семантики: InitLex SetBlindVisible
210 Состояние: 5
211 Лексема: 'r' (4,18)
212 ... принята в состоянии 5
213 Семантики: InitTag
214 Состояние: 8
215 Лексема: 'e' (4,5)
216 ... принята в состоянии 8
217 Семантики: Append
218 Состояние: 8
219 Лексема: 'a' (4,1)
220 ... принята в состоянии 8
221 Семантики: Append
222 Состояние: 8
223 Лексема: 'l' (4,12)
224 ... принята в состоянии 8
225 Семантики: Append
226 Состояние: 8
227 Лексема: ' ' (6,1)
228 Резольверы: IsKeyWord(false)
229 Резольверы: IsModeIndication (true)
230 ... принята в состоянии 8
231 Семантики: SetModeIndication
232 Состояние: 10
233 Лексема: 'y' (4,25)
197
Продолжение табл. 7.10
1 2
234 Семантики: SetBlindInvisible
MakeLex
235 Лексема: '.real' (3,0)
236 ... принята в состоянии 12
237 Состояние: 3
238 Состояние: 3
239 Состояние: 18
240 Семантики: Reset
241 Состояние: 19
242 Состояние: 1
243 Лексема: 'y' (4,25)
244 ... принята в состоянии 1
245 Семантики: InitLex InitTag
246 Состояние: 4
247 Лексема: ')' (10,1)
248 Семантики: MakeLex
249 Лексема: 'y' (8,0)
250 ... принята в состоянии 19
251 Состояние: 22
252 Состояние: 1
253 Лексема: ')' (10,1)
254 ... принята в состоянии 1
255 Семантики:InitLex
SetRightParenthesis
256 Состояние: 6
257 Лексема: 'Eof' (0,0)
258 Семантики: MakeLex
259 Лексема: ')' (7,0)
260 ... принята в состоянии 22
261 Состояние: 3
262 Состояние: 17
263 Семантики: Complete
264 Выполнение завершено
в конечном состоянии 17
Полезно пронаблюдать, что после того, как процессор Gener принимает
очередную лексему, вызывается сканер GenerLex, который, начав работу со
своего начального состояния 1, заканчивает ее вызовом семантики MakeLex,
которая и формирует ожидаемую основным процессором лексему. Можно
также заметить, что процессор GenerLex иногда завершает свою работу, приняв
входную лексему, а иногда не принимая ее — и тогда эта же входная лексема
повторно анализируется при следующем вызове сканера. Разное завершение
зависит от того, является ли текущая литера последней литерой формируемой
лексемы или она — первая литера следующей.
Бросающиеся в глаза подряд сменяющие друг друга состояния процессора
Gener без приема входной лексемы, например в моменты 133-134, 237-240, 261,
соответствуют ε-движениям.
198
7.6. ЧЕЛНОЧНЫЙ АНАЛИЗАТОР
ГЕНЕРАТОРОВ АЛГОЛА 68
Проиллюстрируем возможность использования челночных процессоров для
получения синтаксической структуры входных цепочек. Очевидно, что в этом
случае необходимо использовать неоптимизированный челночный процессор.
В дополнение к управляющей таблице прямого просмотра (см. табл.7.1–7.2)
потребуется расширенная таблица обратного, содержащая структурную
информацию о вспомогательных конструкциях.
Расширенная управляющая таблица обратного просмотра процессора
Gener отличается от обычной тем, что в ней присутствует графа Структурные
метки (см табл. 7.11). Во время интерпретации управляющего элемента
челночный процессор на обратном просмотре выдает содержимое этой графы
на выход в качестве структурных скобок. Эти скобки представляют границы
терминальных порождений вспомогательных понятий, входящих в состав
анализируемой цепочки.
Аналогичные структурные скобки служат для ограничения терминальных
порождений нетерминалов. Причем скобка, отмечающая конец конструкции
выдается обратным просмотром на выход в момент, когда он помещает символ
в магазин, а скобка, отмечающая ее начало — в момент выборки этого символа
из магазина. Имена соответствующих нетерминалов доступны обратному
просмотру через характеристики магазинных символов — возвратных
состояний и алфавит нетерминалов в составе управляющей граф-схемы.
Графы Резольверы и Семантика в табл. 7.11 не показаны, так как на
обратном просмотре в процессоре Gener контекстные символы не
используются.
Таблица 7.11
Вход
Мага-
зин
Структурные метки
Состоя-
ние
1 2
3
4
Состояние 1 = {11}
St20 3 конец - ACTUAL DECLARER 2
Состояние 2 = {106}
St4 4
St21
5
конец - DECLARATOR
конец - REFERENCE TO MODE DECLARATOR
конец - VIRTUAL DECLARER
2
St22
6
конец - DECLARATOR
конец - PROCEDURE DECLARATOR
конец - FORMAL DECLARER
2
St24 7
конец -
DECLARATOR
конец - ROWS OF MODE DECLARATOR
2
St30
конец -
DECLARATOR
конец - UNION OF MODE DECLARATOR
8
St32
конец -
DECLARATOR
конец - STRUCTURED WITH FIELDS DECLARATOR
9
199
Продолжение табл. 7.11
1 2 3 4
Состояние 3 = {8}
St2 начало - ACTUAL DECLARER 10
St3 начало - ACTUAL DECLARER 11
Состояние 4 = {14}
ε
Pop
Состояние 5 = {22}
St5 начало - VIRTUAL DECLARER 12
Состояние 6 = {87}
St9
начало - FORMAL DECLARER 13
St28
начало - FORMAL DECLARER 14
Состояние 7 = {70}
St14
конец - ROWER 15
Состояние 8 = {102}
St26 16 конец - FORMAL DECLARER 2
Состояние 9 = {41}
St27
конец - PORTRAYER 17
Состояния 10 = {4}, 11 = {6} (конечные)
St1
конец - PORTRAYER
Stop
Состояние 12 = {20}
ε
начало - REFERENCE TO MODE DECLARATOR
начало - DECLARATOR
Pop
Состояние 13 = {76}
ε
начало - PROCEDURE DECLARATOR
начало -
DECLARATOR
Pop
Состояние 14 = {85}
St25 18 конец - FORMAL DECLARER 2
Состояние 15 = {68}, 20 = {66}
St8
19
St12
20
St13
21
St15 конец - UNIT 22
St19 конец - UNIT 22
Состояние 16 = {97}
St17
начало - FORMAL DECLARER 23
St31
начало - FORMAL DECLARER 24
200
Продолжение табл. 7.11
1 2 3 4
Состояние 17 = {33}
St23 25
2
St33
26
Состояние 18 = {80}
St16 начало - FORMAL DECLARER 27
St29 начало - FORMAL DECLARER 28
Состояние 19 = {50}
ε
начало - ROWER
начало - ROWS OF MODE DECLARATOR
начало - DECLARATOR
Pop
St7
начало - ROWER 29
Состояние 21 = {64}
St8
19
St12
20
Состояние 22 = {59}
St8 начало - UNIT 19
St12 начало - UNIT 20
St18 начало - UNIT 30
Состояние 23 = {95}
St10
31
Состояние 24 = {100}
St26 16 конец - FORMAL DECLARER 2
Состояние 25 = {32}
St11 начало - PORTRAYER 32
St33
33
Состояние 26 = {35}
St27
17
Состояние 27 = {78}
St9
13
Состояние 28 = {83}
St25 18 конец - FORMAL DECLARER 2
Состояние 29 = {48}
ε
начало - ROWS OF MODE DECLARATOR
начало - DECLARATOR
Pop