|
1 /**************************************************************************** |
|
2 ** |
|
3 ** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies). |
|
4 ** All rights reserved. |
|
5 ** Contact: Nokia Corporation (qt-info@nokia.com) |
|
6 ** |
|
7 ** This file is part of the utils of the Qt Toolkit. |
|
8 ** |
|
9 ** $QT_BEGIN_LICENSE:LGPL$ |
|
10 ** No Commercial Usage |
|
11 ** This file contains pre-release code and may not be distributed. |
|
12 ** You may use this file in accordance with the terms and conditions |
|
13 ** contained in the Technology Preview License Agreement accompanying |
|
14 ** this package. |
|
15 ** |
|
16 ** GNU Lesser General Public License Usage |
|
17 ** Alternatively, this file may be used under the terms of the GNU Lesser |
|
18 ** General Public License version 2.1 as published by the Free Software |
|
19 ** Foundation and appearing in the file LICENSE.LGPL included in the |
|
20 ** packaging of this file. Please review the following information to |
|
21 ** ensure the GNU Lesser General Public License version 2.1 requirements |
|
22 ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. |
|
23 ** |
|
24 ** In addition, as a special exception, Nokia gives you certain additional |
|
25 ** rights. These rights are described in the Nokia Qt LGPL Exception |
|
26 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package. |
|
27 ** |
|
28 ** If you have questions regarding the use of this file, please contact |
|
29 ** Nokia at qt-info@nokia.com. |
|
30 ** |
|
31 ** |
|
32 ** |
|
33 ** |
|
34 ** |
|
35 ** |
|
36 ** |
|
37 ** |
|
38 ** $QT_END_LICENSE$ |
|
39 ** |
|
40 ****************************************************************************/ |
|
41 |
|
42 #include "recognizer.h" |
|
43 #include <cstdlib> |
|
44 #include <cstring> |
|
45 #include <cctype> |
|
46 |
|
47 Recognizer::Recognizer (Grammar *grammar, bool no_lines): |
|
48 tos(0), |
|
49 stack_size(0), |
|
50 state_stack(0), |
|
51 _M_line(1), |
|
52 _M_action_line(0), |
|
53 _M_grammar(grammar), |
|
54 _M_no_lines(no_lines) |
|
55 { |
|
56 } |
|
57 |
|
58 Recognizer::~Recognizer() |
|
59 { |
|
60 if (stack_size) |
|
61 ::qFree(state_stack); |
|
62 } |
|
63 |
|
64 inline void Recognizer::reallocateStack() |
|
65 { |
|
66 if (! stack_size) |
|
67 stack_size = 128; |
|
68 else |
|
69 stack_size <<= 1; |
|
70 |
|
71 sym_stack.resize (stack_size); |
|
72 |
|
73 if (! state_stack) |
|
74 state_stack = reinterpret_cast<int*> (::qMalloc(stack_size * sizeof(int))); |
|
75 else |
|
76 state_stack = reinterpret_cast<int*> (::qRealloc(state_stack, stack_size * sizeof(int))); |
|
77 } |
|
78 |
|
79 int Recognizer::nextToken() |
|
80 { |
|
81 QString text; |
|
82 |
|
83 Lagain: |
|
84 while (ch.isSpace ()) |
|
85 inp (); |
|
86 |
|
87 if (ch.isNull ()) |
|
88 return EOF_SYMBOL; |
|
89 |
|
90 int token = ch.unicode (); |
|
91 |
|
92 if (token == '"') |
|
93 { |
|
94 inp(); // skip " |
|
95 text.clear (); |
|
96 while (! ch.isNull () && ch != QLatin1Char ('"')) |
|
97 { |
|
98 if (ch == QLatin1Char ('\\')) |
|
99 { |
|
100 text += ch; |
|
101 inp(); |
|
102 } |
|
103 text += ch; |
|
104 inp (); |
|
105 } |
|
106 |
|
107 if (ch == QLatin1Char ('"')) |
|
108 inp (); |
|
109 else |
|
110 qerr << _M_input_file << ":" << _M_line << ": Warning. Expected `\"'" << endl; |
|
111 |
|
112 _M_current_value = text; |
|
113 return (token = STRING_LITERAL); |
|
114 } |
|
115 |
|
116 else if (ch.isLetterOrNumber () || ch == QLatin1Char ('_')) |
|
117 { |
|
118 text.clear (); |
|
119 do { text += ch; inp (); } |
|
120 while (ch.isLetterOrNumber () || ch == QLatin1Char ('_') || ch == QLatin1Char ('.')); |
|
121 _M_current_value = text; |
|
122 return (token = ID); |
|
123 } |
|
124 |
|
125 else if (token == '%') |
|
126 { |
|
127 text.clear (); |
|
128 |
|
129 do { inp (); } |
|
130 while (ch.isSpace ()); |
|
131 |
|
132 do { text += ch; inp (); } |
|
133 while (ch.isLetterOrNumber () || ch == QLatin1Char ('_') || ch == QLatin1Char ('-')); |
|
134 |
|
135 if (text == QLatin1String("token_prefix")) |
|
136 return (token = TOKEN_PREFIX); |
|
137 else if (text == QLatin1String("merged_output")) |
|
138 return (token = MERGED_OUTPUT); |
|
139 else if (text == QLatin1String("token")) |
|
140 return (token = TOKEN); |
|
141 else if (text == QLatin1String("start")) |
|
142 return (token = START); |
|
143 else if (text == QLatin1String("parser")) |
|
144 return (token = PARSER); |
|
145 else if (text == QLatin1String("decl")) |
|
146 return (token = DECL_FILE); |
|
147 else if (text == QLatin1String("impl")) |
|
148 return (token = IMPL_FILE); |
|
149 else if (text == QLatin1String("expect")) |
|
150 return (token = EXPECT); |
|
151 else if (text == QLatin1String("expect-rr")) |
|
152 return (token = EXPECT_RR); |
|
153 else if (text == QLatin1String("left")) |
|
154 return (token = LEFT); |
|
155 else if (text == QLatin1String("right")) |
|
156 return (token = RIGHT); |
|
157 else if (text == QLatin1String("nonassoc")) |
|
158 return (token = NONASSOC); |
|
159 else if (text == QLatin1String("prec")) |
|
160 return (token = PREC); |
|
161 else |
|
162 { |
|
163 qerr << _M_input_file << ":" << _M_line << ": Unknown keyword `" << text << "'" << endl; |
|
164 exit (EXIT_FAILURE); |
|
165 return (token = ERROR); |
|
166 } |
|
167 } |
|
168 |
|
169 inp (); |
|
170 |
|
171 if (token == '-' && ch == QLatin1Char ('-')) |
|
172 { |
|
173 do { inp (); } |
|
174 while (! ch.isNull () && ch != QLatin1Char ('\n')); |
|
175 goto Lagain; |
|
176 } |
|
177 |
|
178 else if (token == ':' && ch == QLatin1Char (':')) |
|
179 { |
|
180 inp (); |
|
181 if (ch != QLatin1Char ('=')) |
|
182 return (token = ERROR); |
|
183 inp (); |
|
184 return (token = COLON); |
|
185 } |
|
186 |
|
187 else if (token == '/' && ch == QLatin1Char (':')) |
|
188 { |
|
189 _M_action_line = _M_line; |
|
190 |
|
191 text.clear (); |
|
192 if (! _M_no_lines) |
|
193 text += QLatin1String ("\n#line ") + QString::number (_M_action_line) + " \"" + _M_input_file + "\"\n"; |
|
194 inp (); // skip ':' |
|
195 |
|
196 forever |
|
197 { |
|
198 while (! ch.isNull ()) |
|
199 { |
|
200 token = ch.unicode (); |
|
201 inp (); |
|
202 |
|
203 if (token == ':' && ch == QLatin1Char ('/')) |
|
204 break; |
|
205 |
|
206 text += QLatin1Char (token); |
|
207 } |
|
208 |
|
209 if (ch != QLatin1Char ('/')) |
|
210 return (token = ERROR); |
|
211 |
|
212 inp (); |
|
213 |
|
214 if (ch.isNull () || ch.isSpace ()) |
|
215 { |
|
216 _M_current_value = text; |
|
217 return (token = DECL); |
|
218 } |
|
219 else |
|
220 text += QLatin1String (":/"); |
|
221 } |
|
222 } |
|
223 |
|
224 else if (token == '/' && ch == QLatin1Char ('.')) |
|
225 { |
|
226 _M_action_line = _M_line; |
|
227 |
|
228 text.clear (); |
|
229 if (! _M_no_lines) |
|
230 text += QLatin1String ("\n#line ") + QString::number (_M_action_line) + " \"" + _M_input_file + "\"\n"; |
|
231 |
|
232 inp (); // skip ':' |
|
233 |
|
234 forever |
|
235 { |
|
236 while (! ch.isNull ()) |
|
237 { |
|
238 token = ch.unicode (); |
|
239 inp (); |
|
240 |
|
241 if (token == '.' && ch == QLatin1Char ('/')) |
|
242 break; |
|
243 |
|
244 text += QLatin1Char (token); |
|
245 } |
|
246 |
|
247 if (ch != QLatin1Char ('/')) |
|
248 return (token = ERROR); |
|
249 |
|
250 inp (); |
|
251 |
|
252 if (ch.isNull () || ch.isSpace ()) |
|
253 { |
|
254 _M_current_value = text; |
|
255 return (token = IMPL); |
|
256 } |
|
257 else |
|
258 text += QLatin1String (""); |
|
259 } |
|
260 } |
|
261 |
|
262 switch (token) { |
|
263 case ':': |
|
264 return (token = COLON); |
|
265 |
|
266 case ';': |
|
267 return (token = SEMICOLON); |
|
268 |
|
269 case '|': |
|
270 return (token = OR); |
|
271 |
|
272 default: |
|
273 break; |
|
274 } |
|
275 |
|
276 return token; |
|
277 } |
|
278 |
|
279 bool Recognizer::parse (const QString &input_file) |
|
280 { |
|
281 _M_input_file = input_file; |
|
282 |
|
283 QFile file(_M_input_file); |
|
284 if (! file.open(QFile::ReadOnly)) |
|
285 { |
|
286 qerr << "qlalr: no input file\n"; |
|
287 return false; |
|
288 } |
|
289 |
|
290 QString _M_contents = QTextStream(&file).readAll(); |
|
291 _M_firstChar = _M_contents.constBegin(); |
|
292 _M_lastChar = _M_contents.constEnd(); |
|
293 _M_currentChar = _M_firstChar; |
|
294 _M_line = 1; |
|
295 |
|
296 int yytoken = -1; |
|
297 inp (); |
|
298 |
|
299 reallocateStack(); |
|
300 |
|
301 _M_current_rule = _M_grammar->rules.end (); |
|
302 _M_decls.clear (); |
|
303 _M_impls.clear (); |
|
304 |
|
305 tos = 0; |
|
306 state_stack[++tos] = 0; |
|
307 |
|
308 while (true) |
|
309 { |
|
310 if (yytoken == -1 && - TERMINAL_COUNT != action_index [state_stack [tos]]) |
|
311 yytoken = nextToken(); |
|
312 |
|
313 int act = t_action (state_stack [tos], yytoken); |
|
314 |
|
315 if (act == ACCEPT_STATE) |
|
316 return true; |
|
317 |
|
318 else if (act > 0) |
|
319 { |
|
320 if (++tos == stack_size) |
|
321 reallocateStack(); |
|
322 |
|
323 sym_stack [tos] = _M_current_value; |
|
324 state_stack [tos] = act; |
|
325 yytoken = -1; |
|
326 } |
|
327 |
|
328 else if (act < 0) |
|
329 { |
|
330 int r = - act - 1; |
|
331 |
|
332 tos -= rhs [r]; |
|
333 act = state_stack [tos++]; |
|
334 |
|
335 switch (r) { |
|
336 |
|
337 case 3: { |
|
338 Name name = _M_grammar->intern (sym(2)); |
|
339 _M_grammar->start = name; |
|
340 _M_grammar->non_terminals.insert (name); |
|
341 } break; |
|
342 |
|
343 case 5: { |
|
344 _M_grammar->table_name = sym(2); |
|
345 } break; |
|
346 |
|
347 case 6: { |
|
348 _M_grammar->merged_output = sym(2); |
|
349 } break; |
|
350 |
|
351 case 7: { |
|
352 _M_grammar->decl_file_name = sym(2); |
|
353 } break; |
|
354 |
|
355 case 8: { |
|
356 _M_grammar->impl_file_name = sym(2); |
|
357 } break; |
|
358 |
|
359 case 9: { |
|
360 _M_grammar->expected_shift_reduce = sym(2).toInt(); |
|
361 } break; |
|
362 |
|
363 case 10: { |
|
364 _M_grammar->expected_reduce_reduce = sym(2).toInt(); |
|
365 } break; |
|
366 |
|
367 case 11: { |
|
368 _M_grammar->token_prefix = sym(2); |
|
369 } break; |
|
370 case 17:case 18: { |
|
371 Name name = _M_grammar->intern (sym(1)); |
|
372 _M_grammar->terminals.insert (name); |
|
373 _M_grammar->spells.insert (name, sym(2)); |
|
374 } break; |
|
375 |
|
376 case 19: { |
|
377 _M_grammar->current_assoc = Grammar::Left; |
|
378 ++_M_grammar->current_prec; |
|
379 } break; |
|
380 |
|
381 case 20: { |
|
382 _M_grammar->current_assoc = Grammar::Right; |
|
383 ++_M_grammar->current_prec; |
|
384 } break; |
|
385 |
|
386 case 21: { |
|
387 _M_grammar->current_assoc = Grammar::NonAssoc; |
|
388 ++_M_grammar->current_prec; |
|
389 } break; |
|
390 |
|
391 case 25: { |
|
392 Name name = _M_grammar->intern (sym(1)); |
|
393 _M_grammar->terminals.insert (name); |
|
394 |
|
395 Grammar::TokenInfo info; |
|
396 info.prec = _M_grammar->current_prec; |
|
397 info.assoc = _M_grammar->current_assoc; |
|
398 _M_grammar->token_info.insert (name, info); |
|
399 } break; |
|
400 |
|
401 case 26: { |
|
402 _M_decls += expand (sym(1)); |
|
403 } break; |
|
404 |
|
405 case 27: { |
|
406 _M_impls += expand (sym(1)); |
|
407 } break; |
|
408 |
|
409 case 34: { |
|
410 _M_current_rule = _M_grammar->rules.insert (_M_grammar->rules.end (), Rule ()); |
|
411 _M_current_rule->lhs = _M_grammar->intern (sym(1)); |
|
412 _M_grammar->declared_lhs.insert (_M_current_rule->lhs); |
|
413 |
|
414 if (_M_grammar->terminals.find (_M_current_rule->lhs) != _M_grammar->terminals.end ()) |
|
415 { |
|
416 qerr << _M_input_file << ":" << _M_line << ": Invalid non terminal `" << *_M_current_rule->lhs << "'" << endl; |
|
417 return false; |
|
418 } |
|
419 |
|
420 _M_grammar->non_terminals.insert (_M_current_rule->lhs); |
|
421 } break; |
|
422 |
|
423 case 38: { |
|
424 Name lhs = _M_current_rule->lhs; |
|
425 _M_current_rule = _M_grammar->rules.insert (_M_grammar->rules.end (), Rule ()); |
|
426 _M_current_rule->lhs = lhs; |
|
427 _M_grammar->declared_lhs.insert (_M_current_rule->lhs); |
|
428 |
|
429 if (_M_grammar->terminals.find (_M_current_rule->lhs) != _M_grammar->terminals.end ()) |
|
430 { |
|
431 qerr << _M_input_file << ":" << _M_line << ": Invalid non terminal `" << *_M_current_rule->lhs << "'" << endl; |
|
432 return false; |
|
433 } |
|
434 |
|
435 _M_grammar->non_terminals.insert (_M_current_rule->lhs); |
|
436 } break; |
|
437 |
|
438 case 39: { |
|
439 _M_current_rule->prec = _M_grammar->names.end (); |
|
440 |
|
441 for (NameList::iterator it = _M_current_rule->rhs.begin (); it != _M_current_rule->rhs.end (); ++it) |
|
442 { |
|
443 if (! _M_grammar->isTerminal (*it)) |
|
444 continue; |
|
445 |
|
446 _M_current_rule->prec = *it; |
|
447 } |
|
448 } break; |
|
449 |
|
450 case 40: { |
|
451 Name tok = _M_grammar->intern (sym(2)); |
|
452 if (! _M_grammar->isTerminal (tok)) |
|
453 { |
|
454 qerr << _M_input_file << ":" << _M_line << ": `" << *tok << " is not a terminal symbol" << endl; |
|
455 _M_current_rule->prec = _M_grammar->names.end (); |
|
456 } |
|
457 else |
|
458 _M_current_rule->prec = tok; |
|
459 } break; |
|
460 |
|
461 case 42: { |
|
462 Name name = _M_grammar->intern (sym(2)); |
|
463 |
|
464 if (_M_grammar->terminals.find (name) == _M_grammar->terminals.end ()) |
|
465 _M_grammar->non_terminals.insert (name); |
|
466 |
|
467 _M_current_rule->rhs.push_back (name); |
|
468 } break; |
|
469 |
|
470 case 43: { |
|
471 sym(1) = QString(); |
|
472 } break; |
|
473 |
|
474 } // switch |
|
475 |
|
476 state_stack [tos] = nt_action (act, lhs [r] - TERMINAL_COUNT); |
|
477 } |
|
478 |
|
479 else |
|
480 { |
|
481 break; |
|
482 } |
|
483 } |
|
484 |
|
485 qerr << _M_input_file << ":" << _M_line << ": Syntax error" << endl; |
|
486 return false; |
|
487 } |
|
488 |