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