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

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