1// REUSE-IgnoreStart
2// Copyright (C) 2016 The Qt Company Ltd.
3// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR GPL-3.0-only WITH Qt-GPL-exception-1.0
4// REUSE-IgnoreEnd
5
6#include "cppgenerator.h"
7
8#include "lalr.h"
9#include "recognizer.h"
10
11#include <QtCore/qbitarray.h>
12#include <QtCore/qtextstream.h>
13#include <QtCore/qfile.h>
14#include <QtCore/qmap.h>
15#include <QtCore/private/qconfig_p.h>
16
17#include <iterator>
18
19using namespace Qt::StringLiterals;
20
21namespace {
22
23void generateSeparator(int i, QTextStream &out)
24{
25 if (!(i % 10)) {
26 if (i)
27 out << ",";
28 out << Qt::endl << " ";
29 } else {
30 out << ", ";
31 }
32}
33
34void generateList(const QList<int> &list, QTextStream &out)
35{
36 for (int i = 0; i < list.size(); ++i) {
37 generateSeparator(i, out);
38
39 out << list[i];
40 }
41}
42
43}
44// REUSE-IgnoreStart
45QString CppGenerator::copyrightHeader() const
46{
47 return
48 "// " QT_COPYRIGHT "\n"
49 "// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR GPL-3.0-only WITH Qt-GPL-exception-1.0\n"
50 "\n"_L1;
51}
52// REUSE-IgnoreEnd
53
54QString CppGenerator::privateCopyrightHeader() const
55{
56 return
57 "//\n"
58 "// W A R N I N G\n"
59 "// -------------\n"
60 "//\n"
61 "// This file is not part of the Qt API. It exists for the convenience\n"
62 "// of other Qt classes. This header file may change from version to\n"
63 "// version without notice, or even be removed.\n"
64 "//\n"
65 "// We mean it.\n"
66 "//\n"_L1;
67}
68
69QString CppGenerator::startIncludeGuard(const QString &fileName)
70{
71 const QString normalized(QString(fileName).replace(before: u'.', after: u'_').toUpper());
72
73 return QString::fromLatin1(ba: "#ifndef %1\n"
74 "#define %2\n").arg(args: normalized, args: normalized);
75}
76
77QString CppGenerator::endIncludeGuard(const QString &fileName)
78{
79 const QString normalized(QString(fileName).replace(before: u'.', after: u'_').toUpper());
80
81 return QString::fromLatin1(ba: "#endif // %1\n").arg(a: normalized);
82}
83
84void CppGenerator::operator () ()
85{
86 // action table...
87 state_count = static_cast<int>(aut.states.size());
88 terminal_count = static_cast<int>(grammar.terminals.size());
89 non_terminal_count = static_cast<int>(grammar.non_terminals.size());
90
91#define ACTION(i, j) table [(i) * terminal_count + (j)]
92#define GOTO(i, j) pgoto [(i) * non_terminal_count + (j)]
93
94 int *table = new int [state_count * terminal_count];
95 ::memset (s: table, c: 0, n: state_count * terminal_count * sizeof (int));
96
97 int *pgoto = new int [state_count * non_terminal_count];
98 ::memset (s: pgoto, c: 0, n: state_count * non_terminal_count * sizeof (int));
99
100 accept_state = -1;
101 int shift_reduce_conflict_count = 0;
102 int reduce_reduce_conflict_count = 0;
103
104 for (StatePointer state = aut.states.begin (); state != aut.states.end (); ++state)
105 {
106 int q = aut.id (state);
107
108 for (Bundle::iterator a = state->bundle.begin (); a != state->bundle.end (); ++a)
109 {
110 int symbol = aut.id (name: a.key ());
111 int r = aut.id (state: a.value ());
112
113 Q_ASSERT (r < state_count);
114
115 if (grammar.isNonTerminal (name: a.key ()))
116 {
117 Q_ASSERT(symbol >= terminal_count && symbol < static_cast<int>(grammar.names.size()));
118 GOTO (q, symbol - terminal_count) = r;
119 }
120
121 else
122 ACTION (q, symbol) = r;
123 }
124
125 for (ItemPointer item = state->closure.begin (); item != state->closure.end (); ++item)
126 {
127 if (item->dot != item->end_rhs ())
128 continue;
129
130 int r = aut.id (rule: item->rule);
131
132 const NameSet lookaheads = aut.lookaheads.value (key: item);
133
134 if (item->rule == grammar.goal)
135 accept_state = q;
136
137 for (const Name &s : lookaheads)
138 {
139 int &u = ACTION (q, aut.id (s));
140
141 if (u == 0)
142 u = - r;
143
144 else if (u < 0)
145 {
146 if (verbose)
147 qout() << "*** Warning. Found a reduce/reduce conflict in state " << q << " on token ``" << s << "'' between rule "
148 << r << " and " << -u << Qt::endl;
149
150 ++reduce_reduce_conflict_count;
151
152 u = qMax (a: u, b: -r);
153
154 if (verbose)
155 qout() << "\tresolved using rule " << -u << Qt::endl;
156 }
157
158 else if (u > 0)
159 {
160 if (item->rule->prec != grammar.names.end() && grammar.token_info.contains (key: s))
161 {
162 Grammar::TokenInfo info_r = grammar.token_info.value (key: item->rule->prec);
163 Grammar::TokenInfo info_s = grammar.token_info.value (key: s);
164
165 if (info_r.prec > info_s.prec)
166 u = -r;
167 else if (info_r.prec == info_s.prec)
168 {
169 switch (info_r.assoc) {
170 case Grammar::Left:
171 u = -r;
172 break;
173 case Grammar::Right:
174 // shift... nothing to do
175 break;
176 case Grammar::NonAssoc:
177 u = 0;
178 break;
179 } // switch
180 }
181 }
182
183 else
184 {
185 ++shift_reduce_conflict_count;
186
187 if (verbose)
188 qout() << "*** Warning. Found a shift/reduce conflict in state " << q << " on token ``" << s << "'' with rule " << r << Qt::endl;
189 }
190 }
191 }
192 }
193 }
194
195 if (shift_reduce_conflict_count || reduce_reduce_conflict_count)
196 {
197 if (shift_reduce_conflict_count != grammar.expected_shift_reduce
198 || reduce_reduce_conflict_count != grammar.expected_reduce_reduce)
199 {
200 qerr() << "*** Conflicts: " << shift_reduce_conflict_count << " shift/reduce, " << reduce_reduce_conflict_count << " reduce/reduce" << Qt::endl;
201 if (warnings_are_errors)
202 {
203 qerr() << "qlalr: error: warning occurred, treating as error due to "
204 "--exit-on-warn." << Qt::endl;
205 exit(status: 2);
206 }
207 }
208
209 if (verbose)
210 qout() << Qt::endl << "*** Conflicts: " << shift_reduce_conflict_count << " shift/reduce, " << reduce_reduce_conflict_count << " reduce/reduce" << Qt::endl
211 << Qt::endl;
212 }
213
214 QBitArray used_rules{static_cast<int>(grammar.rules.size())};
215
216 int q = 0;
217 for (StatePointer state = aut.states.begin (); state != aut.states.end (); ++state, ++q)
218 {
219 for (int j = 0; j < terminal_count; ++j)
220 {
221 int &u = ACTION (q, j);
222
223 if (u < 0)
224 used_rules.setBit (-u - 1);
225 }
226 }
227
228 auto rule = grammar.rules.begin();
229 for (int i = 0; i < used_rules.size(); ++i, ++rule)
230 {
231 if (! used_rules.testBit (i))
232 {
233 if (rule != grammar.goal)
234 {
235 qerr() << "*** Warning: Rule ``" << *rule << "'' is useless!" << Qt::endl;
236 if (warnings_are_errors)
237 {
238 qerr() << "qlalr: error: warning occurred, treating as error due to "
239 "--exit-on-warn." << Qt::endl;
240 exit(status: 2);
241 }
242 }
243 }
244 }
245
246 q = 0;
247 for (StatePointer state = aut.states.begin (); state != aut.states.end (); ++state, ++q)
248 {
249 for (int j = 0; j < terminal_count; ++j)
250 {
251 int &u = ACTION (q, j);
252
253 if (u >= 0)
254 continue;
255
256 RulePointer rule = std::next(x: grammar.rules.begin(), n: - u - 1);
257
258 if (state->defaultReduce == rule)
259 u = 0;
260 }
261 }
262
263 // ... compress the goto table
264 defgoto.resize (size: non_terminal_count);
265 for (int j = 0; j < non_terminal_count; ++j)
266 {
267 count.fill (t: 0, newSize: state_count);
268
269 int &mx = defgoto [j];
270
271 for (int i = 0; i < state_count; ++i)
272 {
273 int r = GOTO (i, j);
274
275 if (! r)
276 continue;
277
278 ++count [r];
279
280 if (count [r] > count [mx])
281 mx = r;
282 }
283 }
284
285 for (int i = 0; i < state_count; ++i)
286 {
287 for (int j = 0; j < non_terminal_count; ++j)
288 {
289 int &r = GOTO (i, j);
290
291 if (r == defgoto [j])
292 r = 0;
293 }
294 }
295
296 compressed_action (table, state_count, terminal_count);
297 compressed_goto (pgoto, state_count, non_terminal_count);
298
299 delete[] table;
300 table = nullptr;
301
302 delete[] pgoto;
303 pgoto = nullptr;
304
305#undef ACTION
306#undef GOTO
307
308 if (! grammar.merged_output.isEmpty())
309 {
310 QFile f(grammar.merged_output);
311 if (! f.open (flags: QFile::WriteOnly))
312 {
313 fprintf (stderr, format: "*** cannot create %s\n", qPrintable(grammar.merged_output));
314 return;
315 }
316
317 QTextStream out (&f);
318
319 // copyright headers must come first, otherwise the headers tests will fail
320 if (copyright)
321 {
322 out << copyrightHeader()
323 << privateCopyrightHeader()
324 << Qt::endl;
325 }
326
327 out << "// This file was generated by qlalr - DO NOT EDIT!\n";
328
329 out << startIncludeGuard(fileName: grammar.merged_output) << Qt::endl;
330
331 if (copyright) {
332 out << "#if defined(ERROR)" << Qt::endl
333 << "# undef ERROR" << Qt::endl
334 << "#endif" << Qt::endl << Qt::endl;
335 }
336
337 generateDecl (out);
338 generateImpl (out);
339 out << p.decls();
340 out << p.impls();
341 out << Qt::endl;
342
343 out << endIncludeGuard(fileName: grammar.merged_output) << Qt::endl;
344
345 return;
346 }
347
348 // default behaviour
349 QString declFileName = grammar.table_name.toLower () + "_p.h"_L1;
350 QString bitsFileName = grammar.table_name.toLower () + ".cpp"_L1;
351
352 { // decls...
353 QFile f (declFileName);
354 if (! f.open (flags: QFile::WriteOnly))
355 {
356 fprintf (stderr, format: "*** cannot create %s: %s\n",
357 qPrintable(declFileName), qPrintable(f.errorString()));
358 return;
359 }
360 QTextStream out (&f);
361
362 QString prot = declFileName.toUpper ().replace (before: QLatin1Char ('.'), after: QLatin1Char ('_'));
363
364 // copyright headers must come first, otherwise the headers tests will fail
365 if (copyright)
366 {
367 out << copyrightHeader()
368 << privateCopyrightHeader()
369 << Qt::endl;
370 }
371
372 out << "// This file was generated by qlalr - DO NOT EDIT!\n";
373
374 out << "#ifndef " << prot << Qt::endl
375 << "#define " << prot << Qt::endl
376 << Qt::endl;
377
378 if (copyright) {
379 out << "#include <QtCore/qglobal.h>" << Qt::endl << Qt::endl;
380 out << "QT_BEGIN_NAMESPACE" << Qt::endl << Qt::endl;
381 }
382 generateDecl (out);
383 if (copyright)
384 out << "QT_END_NAMESPACE" << Qt::endl;
385
386 out << "#endif // " << prot << Qt::endl << Qt::endl;
387 } // end decls
388
389 { // bits...
390 QFile f (bitsFileName);
391 if (! f.open (flags: QFile::WriteOnly))
392 {
393 fprintf (stderr, format: "*** cannot create %s: %s\n",
394 qPrintable(bitsFileName), qPrintable(f.errorString()));
395 return;
396 }
397 QTextStream out (&f);
398
399 // copyright headers must come first, otherwise the headers tests will fail
400 if (copyright)
401 out << copyrightHeader();
402
403 out << "// This file was generated by qlalr - DO NOT EDIT!\n";
404
405 out << "#include \"" << declFileName << "\"" << Qt::endl << Qt::endl;
406 if (copyright)
407 out << "QT_BEGIN_NAMESPACE" << Qt::endl << Qt::endl;
408 generateImpl(out);
409 if (copyright)
410 out << "QT_END_NAMESPACE" << Qt::endl;
411
412 } // end bits
413
414 if (! grammar.decl_file_name.isEmpty ())
415 {
416 QFile f (grammar.decl_file_name);
417 if (! f.open (flags: QFile::WriteOnly))
418 {
419 fprintf (stderr, format: "*** cannot create %s: %s\n",
420 qPrintable(grammar.decl_file_name), qPrintable(f.errorString()));
421 return;
422 }
423 QTextStream out (&f);
424 out << p.decls();
425 }
426
427 if (! grammar.impl_file_name.isEmpty ())
428 {
429 QFile f (grammar.impl_file_name);
430 if (! f.open (flags: QFile::WriteOnly))
431 {
432 fprintf (stderr, format: "*** cannot create %s: %s\n",
433 qPrintable(grammar.impl_file_name), qPrintable(f.errorString()));
434 return;
435 }
436 QTextStream out (&f);
437 out << p.impls();
438 }
439}
440
441QString CppGenerator::debugInfoProt() const
442{
443 QString prot = "QLALR_NO_"_L1;
444 prot += grammar.table_name.toUpper();
445 prot += "_DEBUG_INFO"_L1;
446 return prot;
447}
448
449void CppGenerator::generateDecl (QTextStream &out)
450{
451 out << "class " << grammar.table_name << Qt::endl
452 << "{" << Qt::endl
453 << "public:" << Qt::endl
454 << " enum VariousConstants {" << Qt::endl;
455
456 for (const Name &t : std::as_const(t&: grammar.terminals))
457 {
458 QString name = *t;
459 int value = std::distance (first: grammar.names.begin (), last: t);
460
461 if (name == "$end"_L1)
462 name = "EOF_SYMBOL"_L1;
463
464 else if (name == "$accept"_L1)
465 name = "ACCEPT_SYMBOL"_L1;
466
467 else
468 name.prepend (s: grammar.token_prefix);
469
470 out << " " << name << " = " << value << "," << Qt::endl;
471 }
472
473 out << Qt::endl
474 << " ACCEPT_STATE = " << accept_state << "," << Qt::endl
475 << " RULE_COUNT = " << grammar.rules.size () << "," << Qt::endl
476 << " STATE_COUNT = " << state_count << "," << Qt::endl
477 << " TERMINAL_COUNT = " << terminal_count << "," << Qt::endl
478 << " NON_TERMINAL_COUNT = " << non_terminal_count << "," << Qt::endl
479 << Qt::endl
480 << " GOTO_INDEX_OFFSET = " << compressed_action.index.size () << "," << Qt::endl
481 << " GOTO_INFO_OFFSET = " << compressed_action.info.size () << "," << Qt::endl
482 << " GOTO_CHECK_OFFSET = " << compressed_action.check.size () << Qt::endl
483 << " };" << Qt::endl
484 << Qt::endl
485 << " static const char *const spell[];" << Qt::endl
486 << " static const short lhs[];" << Qt::endl
487 << " static const short rhs[];" << Qt::endl;
488
489 if (debug_info)
490 {
491 QString prot = debugInfoProt();
492
493 out << Qt::endl << "#ifndef " << prot << Qt::endl
494 << " static const int rule_index[];" << Qt::endl
495 << " static const int rule_info[];" << Qt::endl
496 << "#endif // " << prot << Qt::endl << Qt::endl;
497 }
498
499 out << " static const short goto_default[];" << Qt::endl
500 << " static const short action_default[];" << Qt::endl
501 << " static const short action_index[];" << Qt::endl
502 << " static const short action_info[];" << Qt::endl
503 << " static const short action_check[];" << Qt::endl
504 << Qt::endl
505 << " static inline int nt_action (int state, int nt)" << Qt::endl
506 << " {" << Qt::endl
507 << " const int yyn = action_index [GOTO_INDEX_OFFSET + state] + nt;" << Qt::endl
508 << " if (yyn < 0 || action_check [GOTO_CHECK_OFFSET + yyn] != nt)" << Qt::endl
509 << " return goto_default [nt];" << Qt::endl
510 << Qt::endl
511 << " return action_info [GOTO_INFO_OFFSET + yyn];" << Qt::endl
512 << " }" << Qt::endl
513 << Qt::endl
514 << " static inline int t_action (int state, int token)" << Qt::endl
515 << " {" << Qt::endl
516 << " const int yyn = action_index [state] + token;" << Qt::endl
517 << Qt::endl
518 << " if (yyn < 0 || action_check [yyn] != token)" << Qt::endl
519 << " return - action_default [state];" << Qt::endl
520 << Qt::endl
521 << " return action_info [yyn];" << Qt::endl
522 << " }" << Qt::endl
523 << "};" << Qt::endl
524 << Qt::endl
525 << Qt::endl;
526}
527
528void CppGenerator::generateImpl (QTextStream &out)
529{
530 int idx = 0;
531
532 out << "const char *const " << grammar.table_name << "::spell [] = {";
533 idx = 0;
534
535 QMap<Name, int> name_ids;
536 bool first_nt = true;
537
538 for (Name t = grammar.names.begin (); t != grammar.names.end (); ++t, ++idx)
539 {
540 bool terminal = grammar.isTerminal (name: t);
541
542 if (! (debug_info || terminal))
543 break;
544
545 name_ids.insert (key: t, value: idx);
546
547 generateSeparator(i: idx, out);
548
549 if (terminal)
550 {
551 QString spell = grammar.spells.value (key: t);
552
553 if (spell.isEmpty ())
554 out << "0";
555 else
556 out << "\"" << spell << "\"";
557 }
558 else
559 {
560 if (first_nt)
561 {
562 first_nt = false;
563 QString prot = debugInfoProt();
564 out << Qt::endl << "#ifndef " << prot << Qt::endl;
565 }
566 out << "\"" << *t << "\"";
567 }
568 }
569
570 if (debug_info)
571 out << Qt::endl << "#endif // " << debugInfoProt() << Qt::endl;
572
573 out << Qt::endl << "};" << Qt::endl << Qt::endl;
574
575 out << "const short " << grammar.table_name << "::lhs [] = {";
576 idx = 0;
577 for (RulePointer rule = grammar.rules.begin (); rule != grammar.rules.end (); ++rule, ++idx)
578 {
579 generateSeparator(i: idx, out);
580
581 out << aut.id (name: rule->lhs);
582 }
583 out << Qt::endl << "};" << Qt::endl << Qt::endl;
584
585 out << "const short " << grammar.table_name << "::rhs [] = {";
586 idx = 0;
587 for (RulePointer rule = grammar.rules.begin (); rule != grammar.rules.end (); ++rule, ++idx)
588 {
589 generateSeparator(i: idx, out);
590
591 out << rule->rhs.size ();
592 }
593 out << Qt::endl << "};" << Qt::endl << Qt::endl;
594
595 if (debug_info)
596 {
597 QString prot = debugInfoProt();
598
599 out << Qt::endl << "#ifndef " << prot << Qt::endl;
600 out << "const int " << grammar.table_name << "::rule_info [] = {";
601 idx = 0;
602 for (auto rule = grammar.rules.cbegin (); rule != grammar.rules.cend (); ++rule, ++idx)
603 {
604 generateSeparator(i: idx, out);
605
606 out << name_ids.value(key: rule->lhs);
607
608 for (const Name &n : rule->rhs)
609 out << ", " << name_ids.value (key: n);
610 }
611 out << Qt::endl << "};" << Qt::endl << Qt::endl;
612
613 out << "const int " << grammar.table_name << "::rule_index [] = {";
614 idx = 0;
615 size_t offset = 0;
616 for (RulePointer rule = grammar.rules.begin (); rule != grammar.rules.end (); ++rule, ++idx)
617 {
618 generateSeparator(i: idx, out);
619
620 out << offset;
621 offset += rule->rhs.size () + 1;
622 }
623 out << Qt::endl << "};" << Qt::endl
624 << "#endif // " << prot << Qt::endl << Qt::endl;
625 }
626
627 out << "const short " << grammar.table_name << "::action_default [] = {";
628 idx = 0;
629 for (StatePointer state = aut.states.begin (); state != aut.states.end (); ++state, ++idx)
630 {
631 generateSeparator(i: idx, out);
632
633 if (state->defaultReduce != grammar.rules.end ())
634 out << aut.id (rule: state->defaultReduce);
635 else
636 out << "0";
637 }
638 out << Qt::endl << "};" << Qt::endl << Qt::endl;
639
640 out << "const short " << grammar.table_name << "::goto_default [] = {";
641 generateList(list: defgoto, out);
642 out << Qt::endl << "};" << Qt::endl << Qt::endl;
643
644 out << "const short " << grammar.table_name << "::action_index [] = {";
645 generateList(list: compressed_action.index, out);
646 out << "," << Qt::endl;
647 generateList(list: compressed_goto.index, out);
648 out << Qt::endl << "};" << Qt::endl << Qt::endl;
649
650 out << "const short " << grammar.table_name << "::action_info [] = {";
651 generateList(list: compressed_action.info, out);
652 out << "," << Qt::endl;
653 generateList(list: compressed_goto.info, out);
654 out << Qt::endl << "};" << Qt::endl << Qt::endl;
655
656 out << "const short " << grammar.table_name << "::action_check [] = {";
657 generateList(list: compressed_action.check, out);
658 out << "," << Qt::endl;
659 generateList(list: compressed_goto.check, out);
660 out << Qt::endl << "};" << Qt::endl << Qt::endl;
661}
662

Provided by KDAB

Privacy Policy
Learn to use CMake with our Intro Training
Find out more

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