1// Copyright (C) 2016 The Qt Company Ltd.
2// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR GPL-3.0-only WITH Qt-GPL-exception-1.0
3
4#include "recognizer.h"
5
6#include <QtCore/qdir.h>
7
8#include <cstdlib>
9#include <cstring>
10#include <cctype>
11
12using namespace Qt::StringLiterals;
13
14Recognizer::Recognizer (Grammar *grammar, bool no_lines):
15 tos(0),
16 stack_size(0),
17 state_stack(nullptr),
18 _M_line(1),
19 _M_action_line(0),
20 _M_grammar(grammar),
21 _M_no_lines(no_lines)
22{
23}
24
25Recognizer::~Recognizer()
26{
27 if (stack_size)
28 ::free(ptr: state_stack);
29}
30
31inline void Recognizer::reallocateStack()
32{
33 if (! stack_size)
34 stack_size = 128;
35 else
36 stack_size <<= 1;
37
38 sym_stack.resize (size: stack_size);
39
40 if (! state_stack)
41 state_stack = reinterpret_cast<int*> (::malloc(size: stack_size * sizeof(int)));
42 else
43 state_stack = reinterpret_cast<int*> (::realloc(ptr: state_stack, size: stack_size * sizeof(int)));
44}
45
46int Recognizer::nextToken()
47{
48 QString text;
49
50 Lagain:
51 while (ch.isSpace ())
52 inp ();
53
54 if (ch.isNull ())
55 return EOF_SYMBOL;
56
57 int token = ch.unicode ();
58
59 if (token == '"')
60 {
61 inp(); // skip "
62 text.clear ();
63 while (!ch.isNull () && ch != u'"')
64 {
65 if (ch == u'\\')
66 {
67 text += ch;
68 inp();
69 }
70 text += ch;
71 inp ();
72 }
73
74 if (ch == u'"')
75 inp ();
76 else
77 qerr() << _M_input_file << ":" << _M_line << ": Warning. Expected `\"'" << Qt::endl;
78
79 _M_current_value = text;
80 return (token = STRING_LITERAL);
81 }
82
83 else if (ch.isLetterOrNumber () || ch == u'_')
84 {
85 text.clear ();
86 do { text += ch; inp (); }
87 while (ch.isLetterOrNumber () || ch == u'_' || ch == u'.');
88 _M_current_value = text;
89 return (token = ID);
90 }
91
92 else if (token == '%')
93 {
94 text.clear ();
95
96 do { inp (); }
97 while (ch.isSpace ());
98
99 do { text += ch; inp (); }
100 while (ch.isLetterOrNumber () || ch == u'_' || ch == u'-');
101
102 if (text == "token_prefix"_L1)
103 return (token = TOKEN_PREFIX);
104 else if (text == "merged_output"_L1)
105 return (token = MERGED_OUTPUT);
106 else if (text == "token"_L1)
107 return (token = TOKEN);
108 else if (text == "start"_L1)
109 return (token = START);
110 else if (text == "parser"_L1)
111 return (token = PARSER);
112 else if (text == "decl"_L1)
113 return (token = DECL_FILE);
114 else if (text == "impl"_L1)
115 return (token = IMPL_FILE);
116 else if (text == "expect"_L1)
117 return (token = EXPECT);
118 else if (text == "expect-rr"_L1)
119 return (token = EXPECT_RR);
120 else if (text == "left"_L1)
121 return (token = LEFT);
122 else if (text == "right"_L1)
123 return (token = RIGHT);
124 else if (text == "nonassoc"_L1)
125 return (token = NONASSOC);
126 else if (text == "prec"_L1)
127 return (token = PREC);
128 else
129 {
130 qerr() << _M_input_file << ":" << _M_line << ": Unknown keyword `" << text << "'" << Qt::endl;
131 exit (EXIT_FAILURE);
132 return (token = ERROR);
133 }
134 }
135
136 inp ();
137
138 if (token == '-' && ch == u'-')
139 {
140 do { inp (); }
141 while (!ch.isNull () && ch != u'\n');
142 goto Lagain;
143 }
144
145 else if (token == ':' && ch == u':')
146 {
147 inp ();
148 if (ch != u'=')
149 return (token = ERROR);
150 inp ();
151 return (token = COLON);
152 }
153
154 else if (token == '/' && ch == u':')
155 {
156 _M_action_line = _M_line;
157
158 text.clear ();
159 if (! _M_no_lines)
160 text += "\n#line "_L1 + QString::number(_M_action_line) +
161 " \""_L1 + QDir::fromNativeSeparators(pathName: _M_input_file) + "\"\n"_L1;
162 inp (); // skip ':'
163
164 forever
165 {
166 while (! ch.isNull ())
167 {
168 token = ch.unicode ();
169 inp ();
170
171 if (token == ':' && ch == u'/')
172 break;
173
174 text += QLatin1Char (token);
175 }
176
177 if (ch != u'/')
178 return (token = ERROR);
179
180 inp ();
181
182 if (ch.isNull () || ch.isSpace ())
183 {
184 _M_current_value = text;
185 return (token = DECL);
186 }
187 else
188 text += ":/"_L1;
189 }
190 }
191
192 else if (token == '/' && ch == u'.')
193 {
194 _M_action_line = _M_line;
195
196 text.clear ();
197 if (! _M_no_lines)
198 text += "\n#line "_L1 + QString::number(_M_action_line) +
199 " \""_L1 + QDir::fromNativeSeparators(pathName: _M_input_file) + "\"\n"_L1;
200
201 inp (); // skip ':'
202
203 forever
204 {
205 while (! ch.isNull ())
206 {
207 token = ch.unicode ();
208 inp ();
209
210 if (token == '.' && ch == u'/')
211 break;
212
213 text += QLatin1Char (token);
214 }
215
216 if (ch != u'/')
217 return (token = ERROR);
218
219 inp ();
220
221 if (ch.isNull () || ch.isSpace ())
222 {
223 _M_current_value = text;
224 return (token = IMPL);
225 }
226 else
227 text += ""_L1;
228 }
229 }
230
231 switch (token) {
232 case ':':
233 return (token = COLON);
234
235 case ';':
236 return (token = SEMICOLON);
237
238 case '|':
239 return (token = OR);
240
241 default:
242 break;
243 }
244
245 return token;
246}
247
248bool Recognizer::parse (const QString &input_file)
249{
250 _M_input_file = input_file;
251
252 QFile file(_M_input_file);
253 if (! file.open(flags: QFile::ReadOnly))
254 {
255 qerr() << "qlalr: no input file\n";
256 return false;
257 }
258
259 QString _M_contents = QTextStream(&file).readAll();
260 _M_firstChar = _M_contents.constBegin();
261 _M_lastChar = _M_contents.constEnd();
262 _M_currentChar = _M_firstChar;
263 _M_line = 1;
264
265 int yytoken = -1;
266 inp ();
267
268 reallocateStack();
269
270 _M_current_rule = _M_grammar->rules.end ();
271 _M_decls.clear ();
272 _M_impls.clear ();
273
274 tos = 0;
275 state_stack[++tos] = 0;
276
277 while (true)
278 {
279 if (yytoken == -1 && - TERMINAL_COUNT != action_index [state_stack [tos]])
280 yytoken = nextToken();
281
282 int act = t_action (state: state_stack [tos], token: yytoken);
283
284 if (act == ACCEPT_STATE)
285 return true;
286
287 else if (act > 0)
288 {
289 if (++tos == stack_size)
290 reallocateStack();
291
292 sym_stack [tos] = _M_current_value;
293 state_stack [tos] = act;
294 yytoken = -1;
295 }
296
297 else if (act < 0)
298 {
299 int r = - act - 1;
300
301 tos -= rhs [r];
302 act = state_stack [tos++];
303
304 switch (r) {
305
306case 3: {
307 Name name = _M_grammar->intern (id: sym(index: 2));
308 _M_grammar->start = name;
309 _M_grammar->non_terminals.insert (x: name);
310} break;
311
312case 5: {
313 _M_grammar->table_name = sym(index: 2);
314} break;
315
316case 6: {
317 _M_grammar->merged_output = sym(index: 2);
318} break;
319
320case 7: {
321 _M_grammar->decl_file_name = sym(index: 2);
322} break;
323
324case 8: {
325 _M_grammar->impl_file_name = sym(index: 2);
326} break;
327
328case 9: {
329 _M_grammar->expected_shift_reduce = sym(index: 2).toInt();
330} break;
331
332case 10: {
333 _M_grammar->expected_reduce_reduce = sym(index: 2).toInt();
334} break;
335
336case 11: {
337 _M_grammar->token_prefix = sym(index: 2);
338} break;
339case 17:case 18: {
340 Name name = _M_grammar->intern (id: sym(index: 1));
341 _M_grammar->terminals.insert (x: name);
342 _M_grammar->spells.insert (key: name, value: sym(index: 2));
343} break;
344
345case 19: {
346 _M_grammar->current_assoc = Grammar::Left;
347 ++_M_grammar->current_prec;
348} break;
349
350case 20: {
351 _M_grammar->current_assoc = Grammar::Right;
352 ++_M_grammar->current_prec;
353} break;
354
355case 21: {
356 _M_grammar->current_assoc = Grammar::NonAssoc;
357 ++_M_grammar->current_prec;
358} break;
359
360case 25: {
361 Name name = _M_grammar->intern (id: sym(index: 1));
362 _M_grammar->terminals.insert (x: name);
363
364 Grammar::TokenInfo info;
365 info.prec = _M_grammar->current_prec;
366 info.assoc = _M_grammar->current_assoc;
367 _M_grammar->token_info.insert (key: name, value: info);
368} break;
369
370case 26: {
371 _M_decls += expand (text: sym(index: 1));
372} break;
373
374case 27: {
375 _M_impls += expand (text: sym(index: 1));
376} break;
377
378case 34: {
379 _M_current_rule = _M_grammar->rules.insert (position: _M_grammar->rules.end (), x: Rule ());
380 _M_current_rule->lhs = _M_grammar->intern (id: sym(index: 1));
381 _M_grammar->declared_lhs.insert (x: _M_current_rule->lhs);
382
383 if (_M_grammar->terminals.find (x: _M_current_rule->lhs) != _M_grammar->terminals.end ())
384 {
385 qerr() << _M_input_file << ":" << _M_line << ": Invalid non terminal `" << *_M_current_rule->lhs << "'" << Qt::endl;
386 return false;
387 }
388
389 _M_grammar->non_terminals.insert (x: _M_current_rule->lhs);
390} break;
391
392case 38: {
393 Name lhs = _M_current_rule->lhs;
394 _M_current_rule = _M_grammar->rules.insert (position: _M_grammar->rules.end (), x: Rule ());
395 _M_current_rule->lhs = lhs;
396 _M_grammar->declared_lhs.insert (x: _M_current_rule->lhs);
397
398 if (_M_grammar->terminals.find (x: _M_current_rule->lhs) != _M_grammar->terminals.end ())
399 {
400 qerr() << _M_input_file << ":" << _M_line << ": Invalid non terminal `" << *_M_current_rule->lhs << "'" << Qt::endl;
401 return false;
402 }
403
404 _M_grammar->non_terminals.insert (x: _M_current_rule->lhs);
405} break;
406
407case 39: {
408 _M_current_rule->prec = _M_grammar->names.end ();
409
410 for (NameList::iterator it = _M_current_rule->rhs.begin (); it != _M_current_rule->rhs.end (); ++it)
411 {
412 if (! _M_grammar->isTerminal (name: *it))
413 continue;
414
415 _M_current_rule->prec = *it;
416 }
417} break;
418
419case 40: {
420 Name tok = _M_grammar->intern (id: sym(index: 2));
421 if (! _M_grammar->isTerminal (name: tok))
422 {
423 qerr() << _M_input_file << ":" << _M_line << ": `" << *tok << " is not a terminal symbol" << Qt::endl;
424 _M_current_rule->prec = _M_grammar->names.end ();
425 }
426 else
427 _M_current_rule->prec = tok;
428} break;
429
430case 42: {
431 Name name = _M_grammar->intern (id: sym(index: 2));
432
433 if (_M_grammar->terminals.find (x: name) == _M_grammar->terminals.end ())
434 _M_grammar->non_terminals.insert (x: name);
435
436 _M_current_rule->rhs.push_back (x: name);
437} break;
438
439case 43: {
440 sym(index: 1) = QString();
441} break;
442
443 } // switch
444
445 state_stack [tos] = nt_action (state: act, nt: lhs [r] - TERMINAL_COUNT);
446 }
447
448 else
449 {
450 break;
451 }
452 }
453
454 qerr() << _M_input_file << ":" << _M_line << ": Syntax error" << Qt::endl;
455 return false;
456}
457
458

source code of qtbase/src/tools/qlalr/recognizer.cpp