1 /****************************************************************************

     2 **

     3 ** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).

     4 ** All rights reserved.

     5 ** Contact: Nokia Corporation (qt-info@nokia.com)

     6 **

     7 ** This file is part of the utils of the Qt Toolkit.

     8 **

     9 ** $QT_BEGIN_LICENSE:LGPL$

    10 ** No Commercial Usage

    11 ** This file contains pre-release code and may not be distributed.

    12 ** You may use this file in accordance with the terms and conditions

    13 ** contained in the Technology Preview License Agreement accompanying

    14 ** this package.

    15 **

    16 ** GNU Lesser General Public License Usage

    17 ** Alternatively, this file may be used under the terms of the GNU Lesser

    18 ** General Public License version 2.1 as published by the Free Software

    19 ** Foundation and appearing in the file LICENSE.LGPL included in the

    20 ** packaging of this file.  Please review the following information to

    21 ** ensure the GNU Lesser General Public License version 2.1 requirements

    22 ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.

    23 **

    24 ** In addition, as a special exception, Nokia gives you certain additional

    25 ** rights.  These rights are described in the Nokia Qt LGPL Exception

    26 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.

    27 **

    28 ** If you have questions regarding the use of this file, please contact

    29 ** Nokia at qt-info@nokia.com.

    30 **

    31 **

    32 **

    33 **

    34 **

    35 **

    36 **

    37 **

    38 ** $QT_END_LICENSE$

    39 **

    40 ****************************************************************************/

    41 

    42 

    43 #include "lalr.h"

    44 #include <limits.h>

    45 

    46 #include <algorithm>

    47 

    48 #define QLALR_NO_DEBUG_NULLABLES

    49 #define QLALR_NO_DEBUG_LOOKBACKS

    50 #define QLALR_NO_DEBUG_DIRECT_READS

    51 #define QLALR_NO_DEBUG_READS

    52 #define QLALR_NO_DEBUG_INCLUDES

    53 #define QLALR_NO_DEBUG_LOOKAHEADS

    54 

    55 QT_BEGIN_NAMESPACE

    56 QTextStream qerr (stderr, QIODevice::WriteOnly);

    57 QTextStream qout (stdout, QIODevice::WriteOnly);

    58 

    59 bool operator < (Name a, Name b)

    60 {

    61     return *a < *b;

    62 }

    63 

    64 bool operator < (ItemPointer a, ItemPointer b)

    65 {

    66     return &*a < &*b;

    67 }

    68 

    69 bool operator < (StatePointer a, StatePointer b)

    70 {

    71   return &*a < &*b;

    72 }

    73 QT_END_NAMESPACE

    74 

    75 bool Read::operator < (const Read &other) const

    76 {

    77   if (state == other.state)

    78     return nt < other.nt;

    79 

    80   return state < other.state;

    81 }

    82 

    83 bool Include::operator < (const Include &other) const

    84 {

    85   if (state == other.state)

    86     return nt < other.nt;

    87 

    88   return state < other.state;

    89 }

    90 

    91 bool Lookback::operator < (const Lookback &other) const

    92 {

    93   if (state == other.state)

    94     return nt < other.nt;

    95 

    96   return state < other.state;

    97 }

    98 

    99 QTextStream &operator << (QTextStream &out, const Name &n)

   100 {

   101   return out << *n;

   102 }

   103 

   104 QTextStream &operator << (QTextStream &out, const Rule &r)

   105 {

   106   out << *r.lhs << " ::=";

   107 

   108   for (NameList::const_iterator name = r.rhs.begin (); name != r.rhs.end (); ++name)

   109     out << " " << **name;

   110 

   111   return out;

   112 }

   113 

   114 QTextStream &operator << (QTextStream &out, const NameSet &ns)

   115 {

   116   out << "{";

   117 

   118   for (NameSet::const_iterator n = ns.begin (); n != ns.end (); ++n)

   119     {

   120       if (n != ns.begin ())

   121         out << ", ";

   122 

   123       out << *n;

   124     }

   125 

   126   return out << "}";

   127 }

   128 

   129 Item Item::next () const

   130 {

   131   Q_ASSERT (! isReduceItem ());

   132 

   133   Item n;

   134   n.rule = rule;

   135   n.dot = dot;

   136   ++n.dot;

   137 

   138   return n;

   139 }

   140 

   141 QTextStream &operator << (QTextStream &out, const Item &item)

   142 {

   143   RulePointer r = item.rule;

   144 

   145   out << *r->lhs << ":";

   146   for (NameList::iterator name = r->rhs.begin (); name != r->rhs.end (); ++name)

   147     {

   148       out << " ";

   149 

   150       if (item.dot == name)

   151         out << ". ";

   152 

   153       out << **name;

   154     }

   155 

   156   if (item.isReduceItem ())

   157     out << " .";

   158 

   159   return out;

   160 }

   161 

   162 State::State (Grammar *g):

   163   defaultReduce (g->rules.end ())

   164 {

   165 }

   166 

   167 QPair<ItemPointer, bool> State::insert (const Item &item)

   168 {

   169   ItemPointer it = qFind (kernel.begin (), kernel.end (), item);

   170 

   171   if (it != kernel.end ())

   172     return qMakePair (it, false);

   173 

   174   return qMakePair (kernel.insert (it, item), true);

   175 }

   176 

   177 QPair<ItemPointer, bool> State::insertClosure (const Item &item)

   178 {

   179   ItemPointer it = qFind (closure.begin (), closure.end (), item);

   180 

   181   if (it != closure.end ())

   182     return qMakePair (it, false);

   183 

   184   return qMakePair (closure.insert (it, item), true);

   185 }

   186 

   187 

   188 /////////////////////////////////////////////////////////////

   189 // Grammar

   190 /////////////////////////////////////////////////////////////

   191 Grammar::Grammar ():

   192     start (names.end ())

   193 {

   194   expected_shift_reduce = 0;

   195   expected_reduce_reduce = 0;

   196   current_prec = 0;

   197   current_assoc = NonAssoc;

   198 

   199   table_name = QLatin1String ("parser_table");

   200 

   201   tk_end = intern ("$end");

   202   terminals.insert (tk_end);

   203   spells.insert (tk_end, "end of file");

   204 

   205   /*tk_error= terminals.insert (intern ("error"))*/;

   206 }

   207 

   208 Name Grammar::intern (const QString &id)

   209 {

   210   Name name = qFind (names.begin (), names.end (), id);

   211 

   212   if (name == names.end ())

   213     name = names.insert (names.end (), id);

   214 

   215   return name;

   216 }

   217 

   218 void Grammar::buildRuleMap ()

   219 {

   220   NameSet undefined;

   221   for (RulePointer rule = rules.begin (); rule != rules.end (); ++rule)

   222     {

   223       for (NameList::iterator it = rule->rhs.begin (); it != rule->rhs.end (); ++it)

   224         {

   225           Name name = *it;

   226           if (isTerminal (name) || declared_lhs.find (name) != declared_lhs.end ()

   227               || undefined.find (name) != undefined.end ())

   228             continue;

   229 

   230           undefined.insert(name);

   231           fprintf (stderr, "*** Warning. Symbol `%s' is not defined\n", qPrintable (*name));

   232         }

   233 

   234       rule_map.insert (rule->lhs, rule);

   235     }

   236 }

   237 

   238 void Grammar::buildExtendedGrammar ()

   239 {

   240   accept_symbol = intern ("$accept");

   241   goal = rules.insert (rules.end (), Rule ());

   242   goal->lhs = accept_symbol;

   243   goal->rhs.push_back (start);

   244   goal->rhs.push_back (tk_end);

   245 

   246   non_terminals.insert (accept_symbol);

   247 }

   248 

   249 struct _Nullable: public std::unary_function<Name, bool>

   250 {

   251   Automaton *_M_automaton;

   252 

   253   _Nullable (Automaton *aut):

   254     _M_automaton (aut) {}

   255 

   256   bool operator () (Name name) const

   257   { return _M_automaton->nullables.find (name) != _M_automaton->nullables.end (); }

   258 };

   259 

   260 Automaton::Automaton (Grammar *g):

   261   _M_grammar (g),

   262   start (states.end ())

   263 {

   264 }

   265 

   266 int Automaton::id (RulePointer rule)

   267 {

   268   return 1 + std::distance (_M_grammar->rules.begin (), rule);

   269 }

   270 

   271 int Automaton::id (Name name)

   272 {

   273   return std::distance (_M_grammar->names.begin (), name);

   274 }

   275 

   276 int Automaton::id (StatePointer state)

   277 {

   278   return std::distance (states.begin (), state);

   279 }

   280 

   281 void Automaton::build ()

   282 {

   283   Item item;

   284   item.rule = _M_grammar->goal;

   285   item.dot = _M_grammar->goal->rhs.begin ();

   286 

   287   State tmp (_M_grammar);

   288   tmp.insert (item);

   289   start = internState (tmp).first;

   290 

   291   closure (start);

   292 

   293   buildNullables ();

   294   buildLookbackSets ();

   295   buildReads ();

   296   buildIncludesAndFollows ();

   297   buildLookaheads ();

   298   buildDefaultReduceActions ();

   299 }

   300 

   301 void Automaton::buildNullables ()

   302 {

   303   bool changed = true;

   304 

   305   while (changed)

   306     {

   307       changed = false;

   308 

   309       for (RulePointer rule = _M_grammar->rules.begin (); rule != _M_grammar->rules.end (); ++rule)

   310         {

   311           NameList::iterator nn = std::find_if (rule->rhs.begin (), rule->rhs.end (), std::not1 (_Nullable (this)));

   312 

   313           if (nn == rule->rhs.end ())

   314             changed |= nullables.insert (rule->lhs).second;

   315         }

   316     }

   317 

   318 #ifndef QLALR_NO_DEBUG_NULLABLES

   319   qerr << "nullables = {" << nullables << endl;

   320 #endif

   321 }

   322 

   323 QPair<StatePointer, bool> Automaton::internState (const State &state)

   324 {

   325   StatePointer it = qFind (states.begin (), states.end (), state);

   326 

   327   if (it != states.end ())

   328     return qMakePair (it, false);

   329 

   330   return qMakePair (states.insert (it, state), true);

   331 }

   332 

   333 struct _Bucket

   334 {

   335   QLinkedList<ItemPointer> items;

   336 

   337   void insert (ItemPointer item)

   338   { items.push_back (item); }

   339 

   340   State toState (Automaton *aut)

   341   {

   342     State st (aut->_M_grammar);

   343 

   344     for (QLinkedList<ItemPointer>::iterator item = items.begin (); item != items.end (); ++item)

   345       st.insert ((*item)->next ());

   346 

   347     return st;

   348   }

   349 };

   350 

   351 void Automaton::closure (StatePointer state)

   352 {

   353   if (! state->closure.empty ()) // ### not true.

   354     return;

   355 

   356   typedef QMap<Name, _Bucket> bucket_map_type;

   357 

   358   bucket_map_type buckets;

   359   QStack<ItemPointer> working_list;

   360 

   361   for (ItemPointer item = state->kernel.begin (); item != state->kernel.end (); ++item)

   362     working_list.push (item);

   363 

   364   state->closure = state->kernel;

   365 

   366   while (! working_list.empty ())

   367     {

   368       ItemPointer item = working_list.top ();

   369       working_list.pop ();

   370 

   371       if (item->isReduceItem ())

   372         continue;

   373 

   374       buckets [*item->dot].insert (item);

   375 

   376       if (_M_grammar->isNonTerminal (*item->dot))

   377         {

   378           foreach (RulePointer rule, _M_grammar->rule_map.values (*item->dot))

   379             {

   380               Item ii;

   381               ii.rule = rule;

   382               ii.dot = rule->rhs.begin ();

   383 

   384               QPair<ItemPointer, bool> r = state->insertClosure (ii);

   385 

   386               if (r.second)

   387                 working_list.push (r.first);

   388             }

   389         }

   390     }

   391 

   392   QList<StatePointer> todo;

   393 

   394   for (bucket_map_type::iterator bucket = buckets.begin (); bucket != buckets.end (); ++bucket)

   395     {

   396       QPair<StatePointer, bool> r = internState (bucket->toState (this));

   397 

   398       StatePointer target = r.first;

   399 

   400       if (r.second)

   401         todo.push_back (target);

   402 

   403       state->bundle.insert (bucket.key(), target);

   404     }

   405 

   406   while (! todo.empty ())

   407     {

   408       closure (todo.front ());

   409       todo.pop_front ();

   410     }

   411 }

   412 

   413 void Automaton::buildLookbackSets ()

   414 {

   415   for (StatePointer p = states.begin (); p != states.end (); ++p)

   416     {

   417       for (Bundle::iterator a = p->bundle.begin (); a != p->bundle.end (); ++a)

   418         {

   419           Name A = a.key ();

   420 

   421           if (! _M_grammar->isNonTerminal (A))

   422             continue;

   423 

   424           foreach (RulePointer rule, _M_grammar->rule_map.values (A))

   425             {

   426               StatePointer q = p;

   427 

   428               for (NameList::iterator dot = rule->rhs.begin (); dot != rule->rhs.end (); ++dot)

   429                 q = q->bundle.value (*dot, states.end ());

   430 

   431               Q_ASSERT (q != states.end ());

   432 

   433               ItemPointer item = q->closure.begin ();

   434 

   435               for (; item != q->closure.end (); ++item)

   436                 {

   437                   if (item->rule == rule && item->dot == item->end_rhs ())

   438                     break;

   439                 }

   440 

   441               if (item == q->closure.end ())

   442                 {

   443                   Q_ASSERT (q == p);

   444                   Q_ASSERT (rule->rhs.begin () == rule->rhs.end ());

   445 

   446                   for (item = q->closure.begin (); item != q->closure.end (); ++item)

   447                     {

   448                       if (item->rule == rule && item->dot == item->end_rhs ())

   449                         break;

   450                     }

   451                 }

   452 

   453               Q_ASSERT (item != q->closure.end ());

   454 

   455               lookbacks.insert (item, Lookback (p, A));

   456 

   457 #ifndef QLALR_NO_DEBUG_LOOKBACKS

   458               qerr << "*** (" << id (q) << ", " << *rule << ") lookback (" << id (p) << ", " << *A << ")" << endl;

   459 #endif

   460             }

   461         }

   462     }

   463 }

   464 

   465 void Automaton::buildDirectReads ()

   466 {

   467   for (StatePointer q = states.begin (); q != states.end (); ++q)

   468     {

   469       for (Bundle::iterator a = q->bundle.begin (); a != q->bundle.end (); ++a)

   470         {

   471           if (! _M_grammar->isNonTerminal (a.key ()))

   472             continue;

   473 

   474           StatePointer r = a.value ();

   475 

   476           for (Bundle::iterator z = r->bundle.begin (); z != r->bundle.end (); ++z)

   477             {

   478               Name sym = z.key ();

   479 

   480               if (! _M_grammar->isTerminal (sym))

   481                 continue;

   482 

   483               q->reads [a.key ()].insert (sym);

   484             }

   485         }

   486 

   487 #ifndef QLALR_NO_DEBUG_DIRECT_READS

   488       for (QMap<Name, NameSet>::iterator dr = q->reads.begin (); dr != q->reads.end (); ++dr)

   489         qerr << "*** DR(" << id (q) << ", " << dr.key () << ") = " << dr.value () << endl;

   490 #endif

   491     }

   492 }

   493 

   494 void Automaton::buildReadsDigraph ()

   495 {

   496   for (StatePointer q = states.begin (); q != states.end (); ++q)

   497     {

   498       for (Bundle::iterator a = q->bundle.begin (); a != q->bundle.end (); ++a)

   499         {

   500           if (! _M_grammar->isNonTerminal (a.key ()))

   501             continue;

   502 

   503           StatePointer r = a.value ();

   504 

   505           for (Bundle::iterator z = r->bundle.begin (); z != r->bundle.end (); ++z)

   506             {

   507               Name sym = z.key ();

   508 

   509               if (! _M_grammar->isNonTerminal(sym) || nullables.find (sym) == nullables.end ())

   510                 continue;

   511 

   512               ReadsGraph::iterator source = ReadsGraph::get (Read (q, a.key ()));

   513               ReadsGraph::iterator target = ReadsGraph::get (Read (r, sym));

   514 

   515               source->insertEdge (target);

   516 

   517 #ifndef QLALR_NO_DEBUG_READS

   518               qerr << "*** ";

   519               dump (qerr, source);

   520               qerr << " reads ";

   521               dump (qerr, target);

   522               qerr << endl;

   523 #endif

   524             }

   525         }

   526     }

   527 }

   528 

   529 void Automaton::buildReads ()

   530 {

   531   buildDirectReads ();

   532   buildReadsDigraph ();

   533 

   534   _M_reads_dfn = 0;

   535 

   536   for (ReadsGraph::iterator node = ReadsGraph::begin_nodes (); node != ReadsGraph::end_nodes (); ++node)

   537     {

   538       if (! node->root)

   539         continue;

   540 

   541       visitReadNode (node);

   542     }

   543 

   544   for (ReadsGraph::iterator node = ReadsGraph::begin_nodes (); node != ReadsGraph::end_nodes (); ++node)

   545     visitReadNode (node);

   546 }

   547 

   548 void Automaton::visitReadNode (ReadNode node)

   549 {

   550   if (node->dfn != 0)

   551     return; // nothing to do

   552 

   553   int N = node->dfn = ++_M_reads_dfn;

   554   _M_reads_stack.push (node);

   555 

   556 #ifndef QLALR_NO_DEBUG_INCLUDES

   557   // qerr << "*** Debug. visit node (" << id (node->data.state) << ", " << node->data.nt << ")  N = " << N << endl;

   558 #endif

   559 

   560   for (ReadsGraph::edge_iterator edge = node->begin (); edge != node->end (); ++edge)

   561     {

   562       ReadsGraph::iterator r = *edge;

   563       Name nt = r->data.nt;

   564 

   565       visitReadNode (r);

   566 

   567       node->dfn = qMin (N, r->dfn);

   568 

   569       NameSet &dst = node->data.state->reads [node->data.nt];

   570       NameSet &src = r->data.state->reads [r->data.nt];

   571       dst.insert (src.begin (), src.end ());

   572     }

   573 

   574   if (node->dfn == N)

   575     {

   576       ReadsGraph::iterator tos = _M_reads_stack.top ();

   577 

   578       do {

   579         tos = _M_reads_stack.top ();

   580         _M_reads_stack.pop ();

   581         tos->dfn = INT_MAX;

   582       } while (tos != node);

   583     }

   584 }

   585 

   586 void Automaton::buildIncludesAndFollows ()

   587 {

   588   for (StatePointer p = states.begin (); p != states.end (); ++p)

   589     p->follows = p->reads;

   590 

   591   buildIncludesDigraph ();

   592 

   593   _M_includes_dfn = 0;

   594 

   595   for (IncludesGraph::iterator node = IncludesGraph::begin_nodes (); node != IncludesGraph::end_nodes (); ++node)

   596     {

   597       if (! node->root)

   598         continue;

   599 

   600       visitIncludeNode (node);

   601     }

   602 

   603   for (IncludesGraph::iterator node = IncludesGraph::begin_nodes (); node != IncludesGraph::end_nodes (); ++node)

   604     visitIncludeNode (node);

   605 }

   606 

   607 void Automaton::buildIncludesDigraph ()

   608 {

   609   for (StatePointer pp = states.begin (); pp != states.end (); ++pp)

   610     {

   611       for (Bundle::iterator a = pp->bundle.begin (); a != pp->bundle.end (); ++a)

   612         {

   613           Name name = a.key ();

   614 

   615           if (! _M_grammar->isNonTerminal (name))

   616             continue;

   617 

   618           foreach (RulePointer rule, _M_grammar->rule_map.values (name))

   619             {

   620               StatePointer p = pp;

   621 

   622               for (NameList::iterator A = rule->rhs.begin (); A != rule->rhs.end (); ++A)

   623                 {

   624                   NameList::iterator dot = A;

   625                   ++dot;

   626 

   627                   if (_M_grammar->isNonTerminal (*A) && dot == rule->rhs.end ())

   628                     {

   629                       // found an include edge.

   630                       IncludesGraph::iterator target = IncludesGraph::get (Include (pp, name));

   631                       IncludesGraph::iterator source = IncludesGraph::get (Include (p, *A));

   632 

   633                       source->insertEdge (target);

   634 

   635 #ifndef QLALR_NO_DEBUG_INCLUDES

   636                       qerr << "*** (" << id (p) << ", " << *A << ") includes (" << id (pp) << ", " << *name << ")" << endl;

   637 #endif // QLALR_NO_DEBUG_INCLUDES

   638 

   639                       continue;

   640                     }

   641 

   642                   p = p->bundle.value (*A);

   643 

   644                   if (! _M_grammar->isNonTerminal (*A))

   645                     continue;

   646 

   647                   NameList::iterator first_not_nullable = std::find_if (dot, rule->rhs.end (), std::not1 (_Nullable (this)));

   648                   if (first_not_nullable != rule->rhs.end ())

   649                     continue;

   650 

   651                   // found an include edge.

   652                   IncludesGraph::iterator target = IncludesGraph::get (Include (pp, name));

   653                   IncludesGraph::iterator source = IncludesGraph::get (Include (p, *A));

   654 

   655                   source->insertEdge (target);

   656 

   657 #ifndef QLALR_NO_DEBUG_INCLUDES

   658                   qerr << "*** (" << id (p) << ", " << *A << ") includes (" << id (pp) << ", " << *name << ")" << endl;

   659 #endif // QLALR_NO_DEBUG_INCLUDES

   660                 }

   661             }

   662         }

   663     }

   664 }

   665 

   666 void Automaton::visitIncludeNode (IncludeNode node)

   667 {

   668   if (node->dfn != 0)

   669     return; // nothing to do

   670 

   671   int N = node->dfn = ++_M_includes_dfn;

   672   _M_includes_stack.push (node);

   673 

   674 #ifndef QLALR_NO_DEBUG_INCLUDES

   675   // qerr << "*** Debug. visit node (" << id (node->data.state) << ", " << node->data.nt << ")  N = " << N << endl;

   676 #endif

   677 

   678   for (IncludesGraph::edge_iterator edge = node->begin (); edge != node->end (); ++edge)

   679     {

   680       IncludesGraph::iterator r = *edge;

   681       Name nt = r->data.nt;

   682 

   683       visitIncludeNode (r);

   684 

   685       node->dfn = qMin (N, r->dfn);

   686 

   687 #ifndef QLALR_NO_DEBUG_INCLUDES

   688       qerr << "*** Merge. follows";

   689       dump (qerr, node);

   690       qerr << " += follows";

   691       dump (qerr, r);

   692       qerr << endl;

   693 #endif

   694 

   695       NameSet &dst = node->data.state->follows [node->data.nt];

   696       NameSet &src = r->data.state->follows [r->data.nt];

   697 

   698       dst.insert (src.begin (), src.end ());

   699     }

   700 

   701   if (node->dfn == N)

   702     {

   703       IncludesGraph::iterator tos = _M_includes_stack.top ();

   704 

   705       do {

   706         tos = _M_includes_stack.top ();

   707         _M_includes_stack.pop ();

   708         tos->dfn = INT_MAX;

   709       } while (tos != node);

   710     }

   711 }

   712 

   713 void Automaton::buildLookaheads ()

   714 {

   715   for (StatePointer p = states.begin (); p != states.end (); ++p)

   716     {

   717       for (ItemPointer item = p->closure.begin (); item != p->closure.end (); ++item)

   718         {

   719           foreach (Lookback lookback, lookbacks.values (item))

   720             {

   721               StatePointer q = lookback.state;

   722 

   723 #ifndef QLALR_NO_DEBUG_LOOKAHEADS

   724               qerr << "(" << id (p) << ", " << *item->rule << ") lookbacks ";

   725               dump (qerr, lookback);

   726               qerr << " with follows (" << id (q) << ", " << lookback.nt << ") = " << q->follows [lookback.nt] << endl;

   727 #endif

   728 

   729               lookaheads [item].insert (q->follows [lookback.nt].begin (), q->follows [lookback.nt].end ());

   730             }

   731         }

   732 

   733       // propagate the lookahead in the kernel

   734       ItemPointer k = p->kernel.begin ();

   735       ItemPointer c = p->closure.begin ();

   736 

   737       for (; k != p->kernel.end (); ++k, ++c)

   738         lookaheads [k] = lookaheads [c];

   739     }

   740 }

   741 

   742 void Automaton::buildDefaultReduceActions ()

   743 {

   744   for (StatePointer state = states.begin (); state != states.end (); ++state)

   745     {

   746       ItemPointer def = state->closure.end ();

   747       int size = -1;

   748 

   749       for (ItemPointer item = state->closure.begin (); item != state->closure.end (); ++item)

   750         {

   751           if (item->dot != item->end_rhs ())

   752             continue;

   753 

   754           int la = lookaheads.value (item).size ();

   755           if (def == state->closure.end () || la > size)

   756             {

   757               def = item;

   758               size = la;

   759             }

   760         }

   761 

   762       if (def != state->closure.end ())

   763         {

   764           Q_ASSERT (size >= 0);

   765           state->defaultReduce = def->rule;

   766         }

   767     }

   768 }

   769 

   770 void Automaton::dump (QTextStream &out, IncludeNode incl)

   771 {

   772   out << "(" << id (incl->data.state) << ", " << incl->data.nt << ")";

   773 }

   774 

   775 void Automaton::dump (QTextStream &out, ReadNode rd)

   776 {

   777   out << "(" << id (rd->data.state) << ", " << rd->data.nt << ")";

   778 }

   779 

   780 void Automaton::dump (QTextStream &out, const Lookback &lp)

   781 {

   782   out << "(" << id (lp.state) << ", " << lp.nt << ")";

   783 }