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 "lalr.h"
5
6#include <limits.h>
7
8#include <algorithm>
9
10#define QLALR_NO_DEBUG_NULLABLES
11#define QLALR_NO_DEBUG_LOOKBACKS
12#define QLALR_NO_DEBUG_DIRECT_READS
13#define QLALR_NO_DEBUG_READS
14#define QLALR_NO_DEBUG_INCLUDES
15#define QLALR_NO_DEBUG_LOOKAHEADS
16
17using namespace Qt::StringLiterals;
18
19QT_BEGIN_NAMESPACE
20QTextStream &qerr()
21{
22 static QTextStream result(stderr, QTextStream::WriteOnly);
23 return result;
24}
25
26QTextStream &qout()
27{
28 static QTextStream result(stdout, QTextStream::WriteOnly);
29 return result;
30}
31QT_END_NAMESPACE
32
33namespace std {
34bool operator < (Name a, Name b)
35{
36 return *a < *b;
37}
38
39bool operator < (ItemPointer a, ItemPointer b)
40{
41 return &*a < &*b;
42}
43
44bool operator < (StatePointer a, StatePointer b)
45{
46 return &*a < &*b;
47}
48}
49
50bool Read::operator < (const Read &other) const
51{
52 if (state == other.state)
53 return nt < other.nt;
54
55 return state < other.state;
56}
57
58bool Include::operator < (const Include &other) const
59{
60 if (state == other.state)
61 return nt < other.nt;
62
63 return state < other.state;
64}
65
66bool Lookback::operator < (const Lookback &other) const
67{
68 if (state == other.state)
69 return nt < other.nt;
70
71 return state < other.state;
72}
73
74QTextStream &operator << (QTextStream &out, const Name &n)
75{
76 return out << *n;
77}
78
79QTextStream &operator << (QTextStream &out, const Rule &r)
80{
81 out << *r.lhs << " ::=";
82
83 for (NameList::const_iterator name = r.rhs.begin (); name != r.rhs.end (); ++name)
84 out << " " << **name;
85
86 return out;
87}
88
89QTextStream &operator << (QTextStream &out, const NameSet &ns)
90{
91 out << "{";
92
93 for (NameSet::const_iterator n = ns.begin (); n != ns.end (); ++n)
94 {
95 if (n != ns.begin ())
96 out << ", ";
97
98 out << *n;
99 }
100
101 return out << "}";
102}
103
104Item Item::next () const
105{
106 Q_ASSERT (! isReduceItem ());
107
108 Item n;
109 n.rule = rule;
110 n.dot = dot;
111 ++n.dot;
112
113 return n;
114}
115
116QTextStream &operator << (QTextStream &out, const Item &item)
117{
118 RulePointer r = item.rule;
119
120 out << *r->lhs << ":";
121 for (NameList::iterator name = r->rhs.begin (); name != r->rhs.end (); ++name)
122 {
123 out << " ";
124
125 if (item.dot == name)
126 out << ". ";
127
128 out << **name;
129 }
130
131 if (item.isReduceItem ())
132 out << " .";
133
134 return out;
135}
136
137State::State (Grammar *g):
138 defaultReduce (g->rules.end ())
139{
140}
141
142std::pair<ItemPointer, bool> State::insert(const Item &item)
143{
144 ItemPointer it = std::find (first: kernel.begin (), last: kernel.end (), val: item);
145
146 if (it != kernel.end ())
147 return {it, false};
148
149 return {kernel.insert(position: it, x: item), true};
150}
151
152std::pair<ItemPointer, bool> State::insertClosure(const Item &item)
153{
154 ItemPointer it = std::find (first: closure.begin (), last: closure.end (), val: item);
155
156 if (it != closure.end ())
157 return {it, false};
158
159 return {closure.insert (position: it, x: item), true};
160}
161
162
163/////////////////////////////////////////////////////////////
164// Grammar
165/////////////////////////////////////////////////////////////
166Grammar::Grammar ():
167 start (names.end ())
168{
169 expected_shift_reduce = 0;
170 expected_reduce_reduce = 0;
171 current_prec = 0;
172 current_assoc = NonAssoc;
173
174 table_name = "parser_table"_L1;
175
176 tk_end = intern (id: "$end");
177 terminals.insert (x: tk_end);
178 spells.insert (key: tk_end, value: "end of file"_L1);
179
180 /*tk_error= terminals.insert (intern ("error"))*/;
181}
182
183Name Grammar::intern (const QString &id)
184{
185 Name name = std::find (first: names.begin (), last: names.end (), val: id);
186
187 if (name == names.end ())
188 name = names.insert (position: names.end (), x: id);
189
190 return name;
191}
192
193void Grammar::buildRuleMap ()
194{
195 NameSet undefined;
196 for (RulePointer rule = rules.begin (); rule != rules.end (); ++rule)
197 {
198 for (NameList::iterator it = rule->rhs.begin (); it != rule->rhs.end (); ++it)
199 {
200 Name name = *it;
201 if (isTerminal (name) || declared_lhs.find (x: name) != declared_lhs.end ()
202 || undefined.find (x: name) != undefined.end ())
203 continue;
204
205 undefined.insert(x: name);
206 fprintf (stderr, format: "*** Warning. Symbol `%s' is not defined\n", qPrintable (*name));
207 }
208
209 rule_map.insert (key: rule->lhs, value: rule);
210 }
211}
212
213void Grammar::buildExtendedGrammar ()
214{
215 accept_symbol = intern (id: "$accept");
216 goal = rules.insert (position: rules.end (), x: Rule ());
217 goal->lhs = accept_symbol;
218 goal->rhs.push_back (x: start);
219 goal->rhs.push_back (x: tk_end);
220
221 non_terminals.insert (x: accept_symbol);
222}
223
224struct NotNullable
225{
226 typedef Name argument_type;
227 Automaton *_M_automaton;
228
229 NotNullable (Automaton *aut):
230 _M_automaton (aut) {}
231
232 bool operator () (Name name) const
233 { return _M_automaton->nullables.find (x: name) == _M_automaton->nullables.end (); }
234};
235
236Automaton::Automaton (Grammar *g):
237 _M_grammar (g),
238 start (states.end ())
239{
240}
241
242int Automaton::id (RulePointer rule)
243{
244 return 1 + std::distance (first: _M_grammar->rules.begin (), last: rule);
245}
246
247int Automaton::id (Name name)
248{
249 return std::distance (first: _M_grammar->names.begin (), last: name);
250}
251
252int Automaton::id (StatePointer state)
253{
254 return std::distance (first: states.begin (), last: state);
255}
256
257void Automaton::build ()
258{
259 Item item;
260 item.rule = _M_grammar->goal;
261 item.dot = _M_grammar->goal->rhs.begin ();
262
263 State tmp (_M_grammar);
264 tmp.insert (item);
265 start = internState (state: tmp).first;
266
267 closure (state: start);
268
269 buildNullables ();
270 buildLookbackSets ();
271 buildReads ();
272 buildIncludesAndFollows ();
273 buildLookaheads ();
274 buildDefaultReduceActions ();
275}
276
277void Automaton::buildNullables ()
278{
279 bool changed = true;
280
281 while (changed)
282 {
283 changed = false;
284
285 for (RulePointer rule = _M_grammar->rules.begin (); rule != _M_grammar->rules.end (); ++rule)
286 {
287 NameList::iterator nn = std::find_if(first: rule->rhs.begin(), last: rule->rhs.end(), pred: NotNullable(this));
288
289 if (nn == rule->rhs.end ())
290 changed |= nullables.insert (x: rule->lhs).second;
291 }
292 }
293
294#ifndef QLALR_NO_DEBUG_NULLABLES
295 qerr() << "nullables = {" << nullables << Qt::endl;
296#endif
297}
298
299std::pair<StatePointer, bool> Automaton::internState(const State &state)
300{
301 StatePointer it = std::find (first: states.begin (), last: states.end (), val: state);
302
303 if (it != states.end ())
304 return {it, false};
305
306 return {states.insert (position: it, x: state), true};
307}
308
309struct _Bucket
310{
311 std::list<ItemPointer> items;
312
313 void insert (ItemPointer item)
314 { items.push_back (x: item); }
315
316 State toState (Automaton *aut)
317 {
318 State st (aut->_M_grammar);
319
320 for (auto &item : items)
321 st.insert(item: item->next());
322
323 return st;
324 }
325};
326
327void Automaton::closure (StatePointer state)
328{
329 if (! state->closure.empty ()) // ### not true.
330 return;
331
332 typedef QMap<Name, _Bucket> bucket_map_type;
333
334 bucket_map_type buckets;
335 QStack<ItemPointer> working_list;
336
337 for (ItemPointer item = state->kernel.begin (); item != state->kernel.end (); ++item)
338 working_list.push (t: item);
339
340 state->closure = state->kernel;
341
342 while (! working_list.empty ())
343 {
344 ItemPointer item = working_list.top ();
345 working_list.pop ();
346
347 if (item->isReduceItem ())
348 continue;
349
350 buckets [*item->dot].insert (item);
351
352 if (_M_grammar->isNonTerminal (name: *item->dot))
353 {
354 const auto range = std::as_const(t&: _M_grammar->rule_map).equal_range(akey: *item->dot);
355 for (auto it = range.first; it != range.second; ++it)
356 {
357 const RulePointer &rule = *it;
358 Item ii;
359 ii.rule = rule;
360 ii.dot = rule->rhs.begin ();
361
362 std::pair<ItemPointer, bool> r = state->insertClosure(item: ii);
363
364 if (r.second)
365 working_list.push (t: r.first);
366 }
367 }
368 }
369
370 QList<StatePointer> todo;
371
372 for (bucket_map_type::iterator bucket = buckets.begin (); bucket != buckets.end (); ++bucket)
373 {
374 std::pair<StatePointer, bool> r = internState(state: bucket->toState(aut: this));
375
376 StatePointer target = r.first;
377
378 if (r.second)
379 todo.push_back (t: target);
380
381 state->bundle.insert (key: bucket.key(), value: target);
382 }
383
384 while (! todo.empty ())
385 {
386 closure (state: todo.front ());
387 todo.pop_front ();
388 }
389}
390
391void Automaton::buildLookbackSets ()
392{
393 for (StatePointer p = states.begin (); p != states.end (); ++p)
394 {
395 for (Bundle::iterator a = p->bundle.begin (); a != p->bundle.end (); ++a)
396 {
397 Name A = a.key ();
398
399 if (! _M_grammar->isNonTerminal (name: A))
400 continue;
401
402 const auto range = std::as_const(t&: _M_grammar->rule_map).equal_range(akey: A);
403 for (auto it = range.first; it != range.second; ++it)
404 {
405 const RulePointer &rule = *it;
406 StatePointer q = p;
407
408 for (NameList::iterator dot = rule->rhs.begin (); dot != rule->rhs.end (); ++dot)
409 q = q->bundle.value (key: *dot, defaultValue: states.end ());
410
411 Q_ASSERT (q != states.end ());
412
413 ItemPointer item = q->closure.begin ();
414
415 for (; item != q->closure.end (); ++item)
416 {
417 if (item->rule == rule && item->dot == item->end_rhs ())
418 break;
419 }
420
421 if (item == q->closure.end ())
422 {
423 Q_ASSERT (q == p);
424 Q_ASSERT (rule->rhs.begin () == rule->rhs.end ());
425
426 for (item = q->closure.begin (); item != q->closure.end (); ++item)
427 {
428 if (item->rule == rule && item->dot == item->end_rhs ())
429 break;
430 }
431 }
432
433 Q_ASSERT (item != q->closure.end ());
434
435 lookbacks.insert (key: item, value: Lookback (p, A));
436
437#ifndef QLALR_NO_DEBUG_LOOKBACKS
438 qerr() << "*** (" << id (q) << ", " << *rule << ") lookback (" << id (p) << ", " << *A << ")" << Qt::endl;
439#endif
440 }
441 }
442 }
443}
444
445void Automaton::buildDirectReads ()
446{
447 for (StatePointer q = states.begin (); q != states.end (); ++q)
448 {
449 for (Bundle::iterator a = q->bundle.begin (); a != q->bundle.end (); ++a)
450 {
451 if (! _M_grammar->isNonTerminal (name: a.key ()))
452 continue;
453
454 StatePointer r = a.value ();
455
456 for (Bundle::iterator z = r->bundle.begin (); z != r->bundle.end (); ++z)
457 {
458 Name sym = z.key ();
459
460 if (! _M_grammar->isTerminal (name: sym))
461 continue;
462
463 q->reads [a.key ()].insert (x: sym);
464 }
465 }
466
467#ifndef QLALR_NO_DEBUG_DIRECT_READS
468 for (QMap<Name, NameSet>::iterator dr = q->reads.begin (); dr != q->reads.end (); ++dr)
469 qerr() << "*** DR(" << id (q) << ", " << dr.key () << ") = " << dr.value () << Qt::endl;
470#endif
471 }
472}
473
474void Automaton::buildReadsDigraph ()
475{
476 for (StatePointer q = states.begin (); q != states.end (); ++q)
477 {
478 for (Bundle::iterator a = q->bundle.begin (); a != q->bundle.end (); ++a)
479 {
480 if (! _M_grammar->isNonTerminal (name: a.key ()))
481 continue;
482
483 StatePointer r = a.value ();
484
485 for (Bundle::iterator z = r->bundle.begin (); z != r->bundle.end (); ++z)
486 {
487 Name sym = z.key ();
488
489 if (! _M_grammar->isNonTerminal(name: sym) || nullables.find (x: sym) == nullables.end ())
490 continue;
491
492 ReadsGraph::iterator source = ReadsGraph::get (data: Read (q, a.key ()));
493 ReadsGraph::iterator target = ReadsGraph::get (data: Read (r, sym));
494
495 source->insertEdge (other: target);
496
497#ifndef QLALR_NO_DEBUG_READS
498 qerr() << "*** ";
499 dump (qerr(), source);
500 qerr() << " reads ";
501 dump (qerr(), target);
502 qerr() << Qt::endl;
503#endif
504 }
505 }
506 }
507}
508
509void Automaton::buildReads ()
510{
511 buildDirectReads ();
512 buildReadsDigraph ();
513
514 _M_reads_dfn = 0;
515
516 for (ReadsGraph::iterator node = ReadsGraph::begin_nodes (); node != ReadsGraph::end_nodes (); ++node)
517 {
518 if (! node->root)
519 continue;
520
521 visitReadNode (node);
522 }
523
524 for (ReadsGraph::iterator node = ReadsGraph::begin_nodes (); node != ReadsGraph::end_nodes (); ++node)
525 visitReadNode (node);
526}
527
528void Automaton::visitReadNode (ReadNode node)
529{
530 if (node->dfn != 0)
531 return; // nothing to do
532
533 int N = node->dfn = ++_M_reads_dfn;
534 _M_reads_stack.push (t: node);
535
536#ifndef QLALR_NO_DEBUG_INCLUDES
537 // qerr() << "*** Debug. visit node (" << id (node->data.state) << ", " << node->data.nt << ") N = " << N << Qt::endl;
538#endif
539
540 for (ReadsGraph::edge_iterator edge = node->begin (); edge != node->end (); ++edge)
541 {
542 ReadsGraph::iterator r = *edge;
543
544 visitReadNode (node: r);
545
546 node->dfn = qMin (a: N, b: r->dfn);
547
548 NameSet &dst = node->data.state->reads [node->data.nt];
549 NameSet &src = r->data.state->reads [r->data.nt];
550 dst.insert (first: src.begin (), last: src.end ());
551 }
552
553 if (node->dfn == N)
554 {
555 ReadsGraph::iterator tos = _M_reads_stack.top ();
556
557 do {
558 tos = _M_reads_stack.top ();
559 _M_reads_stack.pop ();
560 tos->dfn = INT_MAX;
561 } while (tos != node);
562 }
563}
564
565void Automaton::buildIncludesAndFollows ()
566{
567 for (StatePointer p = states.begin (); p != states.end (); ++p)
568 p->follows = p->reads;
569
570 buildIncludesDigraph ();
571
572 _M_includes_dfn = 0;
573
574 for (IncludesGraph::iterator node = IncludesGraph::begin_nodes (); node != IncludesGraph::end_nodes (); ++node)
575 {
576 if (! node->root)
577 continue;
578
579 visitIncludeNode (node);
580 }
581
582 for (IncludesGraph::iterator node = IncludesGraph::begin_nodes (); node != IncludesGraph::end_nodes (); ++node)
583 visitIncludeNode (node);
584}
585
586void Automaton::buildIncludesDigraph ()
587{
588 for (StatePointer pp = states.begin (); pp != states.end (); ++pp)
589 {
590 for (Bundle::iterator a = pp->bundle.begin (); a != pp->bundle.end (); ++a)
591 {
592 Name name = a.key ();
593
594 if (! _M_grammar->isNonTerminal (name))
595 continue;
596
597 const auto range = std::as_const(t&: _M_grammar->rule_map).equal_range(akey: name);
598 for (auto it = range.first; it != range.second; ++it)
599 {
600 const RulePointer &rule = *it;
601 StatePointer p = pp;
602
603 for (NameList::iterator A = rule->rhs.begin (); A != rule->rhs.end (); ++A)
604 {
605 NameList::iterator dot = A;
606 ++dot;
607
608 if (_M_grammar->isNonTerminal (name: *A) && dot == rule->rhs.end ())
609 {
610 // found an include edge.
611 IncludesGraph::iterator target = IncludesGraph::get (data: Include (pp, name));
612 IncludesGraph::iterator source = IncludesGraph::get (data: Include (p, *A));
613
614 source->insertEdge (other: target);
615
616#ifndef QLALR_NO_DEBUG_INCLUDES
617 qerr() << "*** (" << id (p) << ", " << *A << ") includes (" << id (pp) << ", " << *name << ")" << Qt::endl;
618#endif // QLALR_NO_DEBUG_INCLUDES
619
620 continue;
621 }
622
623 p = p->bundle.value (key: *A);
624
625 if (! _M_grammar->isNonTerminal (name: *A))
626 continue;
627
628 NameList::iterator first_not_nullable = std::find_if(first: dot, last: rule->rhs.end(), pred: NotNullable(this));
629 if (first_not_nullable != rule->rhs.end ())
630 continue;
631
632 // found an include edge.
633 IncludesGraph::iterator target = IncludesGraph::get (data: Include (pp, name));
634 IncludesGraph::iterator source = IncludesGraph::get (data: Include (p, *A));
635
636 source->insertEdge (other: target);
637
638#ifndef QLALR_NO_DEBUG_INCLUDES
639 qerr() << "*** (" << id (p) << ", " << *A << ") includes (" << id (pp) << ", " << *name << ")" << Qt::endl;
640#endif // QLALR_NO_DEBUG_INCLUDES
641 }
642 }
643 }
644 }
645}
646
647void Automaton::visitIncludeNode (IncludeNode node)
648{
649 if (node->dfn != 0)
650 return; // nothing to do
651
652 int N = node->dfn = ++_M_includes_dfn;
653 _M_includes_stack.push (t: node);
654
655#ifndef QLALR_NO_DEBUG_INCLUDES
656 // qerr() << "*** Debug. visit node (" << id (node->data.state) << ", " << node->data.nt << ") N = " << N << Qt::endl;
657#endif
658
659 for (IncludesGraph::edge_iterator edge = node->begin (); edge != node->end (); ++edge)
660 {
661 IncludesGraph::iterator r = *edge;
662
663 visitIncludeNode (node: r);
664
665 node->dfn = qMin (a: N, b: r->dfn);
666
667#ifndef QLALR_NO_DEBUG_INCLUDES
668 qerr() << "*** Merge. follows";
669 dump (qerr(), node);
670 qerr() << " += follows";
671 dump (qerr(), r);
672 qerr() << Qt::endl;
673#endif
674
675 NameSet &dst = node->data.state->follows [node->data.nt];
676 NameSet &src = r->data.state->follows [r->data.nt];
677
678 dst.insert (first: src.begin (), last: src.end ());
679 }
680
681 if (node->dfn == N)
682 {
683 IncludesGraph::iterator tos = _M_includes_stack.top ();
684
685 do {
686 tos = _M_includes_stack.top ();
687 _M_includes_stack.pop ();
688 tos->dfn = INT_MAX;
689 } while (tos != node);
690 }
691}
692
693void Automaton::buildLookaheads ()
694{
695 for (StatePointer p = states.begin (); p != states.end (); ++p)
696 {
697 for (ItemPointer item = p->closure.begin (); item != p->closure.end (); ++item)
698 {
699 const auto range = std::as_const(t&: lookbacks).equal_range(akey: item);
700 for (auto it = range.first; it != range.second; ++it)
701 {
702 const Lookback &lookback = *it;
703 StatePointer q = lookback.state;
704
705#ifndef QLALR_NO_DEBUG_LOOKAHEADS
706 qerr() << "(" << id (p) << ", " << *item->rule << ") lookbacks ";
707 dump (qerr(), lookback);
708 qerr() << " with follows (" << id (q) << ", " << lookback.nt << ") = " << q->follows [lookback.nt] << Qt::endl;
709#endif
710
711 lookaheads [item].insert (first: q->follows [lookback.nt].begin (), last: q->follows [lookback.nt].end ());
712 }
713 }
714
715 // propagate the lookahead in the kernel
716 ItemPointer k = p->kernel.begin ();
717 ItemPointer c = p->closure.begin ();
718
719 for (; k != p->kernel.end (); ++k, ++c)
720 lookaheads [k] = lookaheads [c];
721 }
722}
723
724void Automaton::buildDefaultReduceActions ()
725{
726 for (StatePointer state = states.begin (); state != states.end (); ++state)
727 {
728 ItemPointer def = state->closure.end ();
729 int size = -1;
730
731 for (ItemPointer item = state->closure.begin (); item != state->closure.end (); ++item)
732 {
733 if (item->dot != item->end_rhs ())
734 continue;
735
736 int la = static_cast<int>(lookaheads.value(key: item).size());
737 if (def == state->closure.end () || la > size)
738 {
739 def = item;
740 size = la;
741 }
742 }
743
744 if (def != state->closure.end ())
745 {
746 Q_ASSERT (size >= 0);
747 state->defaultReduce = def->rule;
748 }
749 }
750}
751
752void Automaton::dump (QTextStream &out, IncludeNode incl)
753{
754 out << "(" << id (state: incl->data.state) << ", " << incl->data.nt << ")";
755}
756
757void Automaton::dump (QTextStream &out, ReadNode rd)
758{
759 out << "(" << id (state: rd->data.state) << ", " << rd->data.nt << ")";
760}
761
762void Automaton::dump (QTextStream &out, const Lookback &lp)
763{
764 out << "(" << id (state: lp.state) << ", " << lp.nt << ")";
765}
766

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