move and build qlalr

Change-Id: I852e1a33fc056a52f6dbba8aaf7dd75274bbe815
Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>

1 files changed, 781 insertions, 0 deletions

diff --git a/src/tools/qlalr/lalr.cpp b/src/tools/qlalr/lalr.cpp
new file mode 100644
index 0000000000..c68076477f
--- /dev/null
+++ b/src/tools/qlalr/lalr.cpp
@@ -0,0 +1,781 @@
+/****************************************************************************
+**
+** Copyright (C) 2013 Digia Plc and/or its subsidiary(-ies).
+** Contact: http://www.qt-project.org/legal
+**
+** This file is part of the utils of the Qt Toolkit.
+**
+** $QT_BEGIN_LICENSE:LGPL$
+** Commercial License Usage
+** Licensees holding valid commercial Qt licenses may use this file in
+** accordance with the commercial license agreement provided with the
+** Software or, alternatively, in accordance with the terms contained in
+** a written agreement between you and Digia.  For licensing terms and
+** conditions see http://qt.digia.com/licensing.  For further information
+** use the contact form at http://qt.digia.com/contact-us.
+**
+** GNU Lesser General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU Lesser
+** General Public License version 2.1 as published by the Free Software
+** Foundation and appearing in the file LICENSE.LGPL included in the
+** packaging of this file.  Please review the following information to
+** ensure the GNU Lesser General Public License version 2.1 requirements
+** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
+**
+** In addition, as a special exception, Digia gives you certain additional
+** rights.  These rights are described in the Digia Qt LGPL Exception
+** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
+**
+** GNU General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU
+** General Public License version 3.0 as published by the Free Software
+** Foundation and appearing in the file LICENSE.GPL included in the
+** packaging of this file.  Please review the following information to
+** ensure the GNU General Public License version 3.0 requirements will be
+** met: http://www.gnu.org/copyleft/gpl.html.
+**
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+#include "lalr.h"
+
+#include <limits.h>
+
+#include <algorithm>
+
+#define QLALR_NO_DEBUG_NULLABLES
+#define QLALR_NO_DEBUG_LOOKBACKS
+#define QLALR_NO_DEBUG_DIRECT_READS
+#define QLALR_NO_DEBUG_READS
+#define QLALR_NO_DEBUG_INCLUDES
+#define QLALR_NO_DEBUG_LOOKAHEADS
+
+QT_BEGIN_NAMESPACE
+QTextStream qerr (stderr, QIODevice::WriteOnly);
+QTextStream qout (stdout, QIODevice::WriteOnly);
+
+bool operator < (Name a, Name b)
+{
+    return *a < *b;
+}
+
+bool operator < (ItemPointer a, ItemPointer b)
+{
+    return &*a < &*b;
+}
+
+bool operator < (StatePointer a, StatePointer b)
+{
+  return &*a < &*b;
+}
+QT_END_NAMESPACE
+
+bool Read::operator < (const Read &other) const
+{
+  if (state == other.state)
+    return nt < other.nt;
+
+  return state < other.state;
+}
+
+bool Include::operator < (const Include &other) const
+{
+  if (state == other.state)
+    return nt < other.nt;
+
+  return state < other.state;
+}
+
+bool Lookback::operator < (const Lookback &other) const
+{
+  if (state == other.state)
+    return nt < other.nt;
+
+  return state < other.state;
+}
+
+QTextStream &operator << (QTextStream &out, const Name &n)
+{
+  return out << *n;
+}
+
+QTextStream &operator << (QTextStream &out, const Rule &r)
+{
+  out << *r.lhs << " ::=";
+
+  for (NameList::const_iterator name = r.rhs.begin (); name != r.rhs.end (); ++name)
+    out << " " << **name;
+
+  return out;
+}
+
+QTextStream &operator << (QTextStream &out, const NameSet &ns)
+{
+  out << "{";
+
+  for (NameSet::const_iterator n = ns.begin (); n != ns.end (); ++n)
+    {
+      if (n != ns.begin ())
+        out << ", ";
+
+      out << *n;
+    }
+
+  return out << "}";
+}
+
+Item Item::next () const
+{
+  Q_ASSERT (! isReduceItem ());
+
+  Item n;
+  n.rule = rule;
+  n.dot = dot;
+  ++n.dot;
+
+  return n;
+}
+
+QTextStream &operator << (QTextStream &out, const Item &item)
+{
+  RulePointer r = item.rule;
+
+  out << *r->lhs << ":";
+  for (NameList::iterator name = r->rhs.begin (); name != r->rhs.end (); ++name)
+    {
+      out << " ";
+
+      if (item.dot == name)
+        out << ". ";
+
+      out << **name;
+    }
+
+  if (item.isReduceItem ())
+    out << " .";
+
+  return out;
+}
+
+State::State (Grammar *g):
+  defaultReduce (g->rules.end ())
+{
+}
+
+QPair<ItemPointer, bool> State::insert (const Item &item)
+{
+  ItemPointer it = std::find (kernel.begin (), kernel.end (), item);
+
+  if (it != kernel.end ())
+    return qMakePair (it, false);
+
+  return qMakePair (kernel.insert (it, item), true);
+}
+
+QPair<ItemPointer, bool> State::insertClosure (const Item &item)
+{
+  ItemPointer it = std::find (closure.begin (), closure.end (), item);
+
+  if (it != closure.end ())
+    return qMakePair (it, false);
+
+  return qMakePair (closure.insert (it, item), true);
+}
+
+
+/////////////////////////////////////////////////////////////
+// Grammar
+/////////////////////////////////////////////////////////////
+Grammar::Grammar ():
+    start (names.end ())
+{
+  expected_shift_reduce = 0;
+  expected_reduce_reduce = 0;
+  current_prec = 0;
+  current_assoc = NonAssoc;
+
+  table_name = QLatin1String ("parser_table");
+
+  tk_end = intern ("$end");
+  terminals.insert (tk_end);
+  spells.insert (tk_end, "end of file");
+
+  /*tk_error= terminals.insert (intern ("error"))*/;
+}
+
+Name Grammar::intern (const QString &id)
+{
+  Name name = std::find (names.begin (), names.end (), id);
+
+  if (name == names.end ())
+    name = names.insert (names.end (), id);
+
+  return name;
+}
+
+void Grammar::buildRuleMap ()
+{
+  NameSet undefined;
+  for (RulePointer rule = rules.begin (); rule != rules.end (); ++rule)
+    {
+      for (NameList::iterator it = rule->rhs.begin (); it != rule->rhs.end (); ++it)
+        {
+          Name name = *it;
+          if (isTerminal (name) || declared_lhs.find (name) != declared_lhs.end ()
+              || undefined.find (name) != undefined.end ())
+            continue;
+
+          undefined.insert(name);
+          fprintf (stderr, "*** Warning. Symbol `%s' is not defined\n", qPrintable (*name));
+        }
+
+      rule_map.insert (rule->lhs, rule);
+    }
+}
+
+void Grammar::buildExtendedGrammar ()
+{
+  accept_symbol = intern ("$accept");
+  goal = rules.insert (rules.end (), Rule ());
+  goal->lhs = accept_symbol;
+  goal->rhs.push_back (start);
+  goal->rhs.push_back (tk_end);
+
+  non_terminals.insert (accept_symbol);
+}
+
+struct _Nullable: public std::unary_function<Name, bool>
+{
+  Automaton *_M_automaton;
+
+  _Nullable (Automaton *aut):
+    _M_automaton (aut) {}
+
+  bool operator () (Name name) const
+  { return _M_automaton->nullables.find (name) != _M_automaton->nullables.end (); }
+};
+
+Automaton::Automaton (Grammar *g):
+  _M_grammar (g),
+  start (states.end ())
+{
+}
+
+int Automaton::id (RulePointer rule)
+{
+  return 1 + std::distance (_M_grammar->rules.begin (), rule);
+}
+
+int Automaton::id (Name name)
+{
+  return std::distance (_M_grammar->names.begin (), name);
+}
+
+int Automaton::id (StatePointer state)
+{
+  return std::distance (states.begin (), state);
+}
+
+void Automaton::build ()
+{
+  Item item;
+  item.rule = _M_grammar->goal;
+  item.dot = _M_grammar->goal->rhs.begin ();
+
+  State tmp (_M_grammar);
+  tmp.insert (item);
+  start = internState (tmp).first;
+
+  closure (start);
+
+  buildNullables ();
+  buildLookbackSets ();
+  buildReads ();
+  buildIncludesAndFollows ();
+  buildLookaheads ();
+  buildDefaultReduceActions ();
+}
+
+void Automaton::buildNullables ()
+{
+  bool changed = true;
+
+  while (changed)
+    {
+      changed = false;
+
+      for (RulePointer rule = _M_grammar->rules.begin (); rule != _M_grammar->rules.end (); ++rule)
+        {
+          NameList::iterator nn = std::find_if (rule->rhs.begin (), rule->rhs.end (), std::not1 (_Nullable (this)));
+
+          if (nn == rule->rhs.end ())
+            changed |= nullables.insert (rule->lhs).second;
+        }
+    }
+
+#ifndef QLALR_NO_DEBUG_NULLABLES
+  qerr << "nullables = {" << nullables << endl;
+#endif
+}
+
+QPair<StatePointer, bool> Automaton::internState (const State &state)
+{
+  StatePointer it = std::find (states.begin (), states.end (), state);
+
+  if (it != states.end ())
+    return qMakePair (it, false);
+
+  return qMakePair (states.insert (it, state), true);
+}
+
+struct _Bucket
+{
+  QLinkedList<ItemPointer> items;
+
+  void insert (ItemPointer item)
+  { items.push_back (item); }
+
+  State toState (Automaton *aut)
+  {
+    State st (aut->_M_grammar);
+
+    for (QLinkedList<ItemPointer>::iterator item = items.begin (); item != items.end (); ++item)
+      st.insert ((*item)->next ());
+
+    return st;
+  }
+};
+
+void Automaton::closure (StatePointer state)
+{
+  if (! state->closure.empty ()) // ### not true.
+    return;
+
+  typedef QMap<Name, _Bucket> bucket_map_type;
+
+  bucket_map_type buckets;
+  QStack<ItemPointer> working_list;
+
+  for (ItemPointer item = state->kernel.begin (); item != state->kernel.end (); ++item)
+    working_list.push (item);
+
+  state->closure = state->kernel;
+
+  while (! working_list.empty ())
+    {
+      ItemPointer item = working_list.top ();
+      working_list.pop ();
+
+      if (item->isReduceItem ())
+        continue;
+
+      buckets [*item->dot].insert (item);
+
+      if (_M_grammar->isNonTerminal (*item->dot))
+        {
+          foreach (RulePointer rule, _M_grammar->rule_map.values (*item->dot))
+            {
+              Item ii;
+              ii.rule = rule;
+              ii.dot = rule->rhs.begin ();
+
+              QPair<ItemPointer, bool> r = state->insertClosure (ii);
+
+              if (r.second)
+                working_list.push (r.first);
+            }
+        }
+    }
+
+  QList<StatePointer> todo;
+
+  for (bucket_map_type::iterator bucket = buckets.begin (); bucket != buckets.end (); ++bucket)
+    {
+      QPair<StatePointer, bool> r = internState (bucket->toState (this));
+
+      StatePointer target = r.first;
+
+      if (r.second)
+        todo.push_back (target);
+
+      state->bundle.insert (bucket.key(), target);
+    }
+
+  while (! todo.empty ())
+    {
+      closure (todo.front ());
+      todo.pop_front ();
+    }
+}
+
+void Automaton::buildLookbackSets ()
+{
+  for (StatePointer p = states.begin (); p != states.end (); ++p)
+    {
+      for (Bundle::iterator a = p->bundle.begin (); a != p->bundle.end (); ++a)
+        {
+          Name A = a.key ();
+
+          if (! _M_grammar->isNonTerminal (A))
+            continue;
+
+          foreach (RulePointer rule, _M_grammar->rule_map.values (A))
+            {
+              StatePointer q = p;
+
+              for (NameList::iterator dot = rule->rhs.begin (); dot != rule->rhs.end (); ++dot)
+                q = q->bundle.value (*dot, states.end ());
+
+              Q_ASSERT (q != states.end ());
+
+              ItemPointer item = q->closure.begin ();
+
+              for (; item != q->closure.end (); ++item)
+                {
+                  if (item->rule == rule && item->dot == item->end_rhs ())
+                    break;
+                }
+
+              if (item == q->closure.end ())
+                {
+                  Q_ASSERT (q == p);
+                  Q_ASSERT (rule->rhs.begin () == rule->rhs.end ());
+
+                  for (item = q->closure.begin (); item != q->closure.end (); ++item)
+                    {
+                      if (item->rule == rule && item->dot == item->end_rhs ())
+                        break;
+                    }
+                }
+
+              Q_ASSERT (item != q->closure.end ());
+
+              lookbacks.insert (item, Lookback (p, A));
+
+#ifndef QLALR_NO_DEBUG_LOOKBACKS
+              qerr << "*** (" << id (q) << ", " << *rule << ") lookback (" << id (p) << ", " << *A << ")" << endl;
+#endif
+            }
+        }
+    }
+}
+
+void Automaton::buildDirectReads ()
+{
+  for (StatePointer q = states.begin (); q != states.end (); ++q)
+    {
+      for (Bundle::iterator a = q->bundle.begin (); a != q->bundle.end (); ++a)
+        {
+          if (! _M_grammar->isNonTerminal (a.key ()))
+            continue;
+
+          StatePointer r = a.value ();
+
+          for (Bundle::iterator z = r->bundle.begin (); z != r->bundle.end (); ++z)
+            {
+              Name sym = z.key ();
+
+              if (! _M_grammar->isTerminal (sym))
+                continue;
+
+              q->reads [a.key ()].insert (sym);
+            }
+        }
+
+#ifndef QLALR_NO_DEBUG_DIRECT_READS
+      for (QMap<Name, NameSet>::iterator dr = q->reads.begin (); dr != q->reads.end (); ++dr)
+        qerr << "*** DR(" << id (q) << ", " << dr.key () << ") = " << dr.value () << endl;
+#endif
+    }
+}
+
+void Automaton::buildReadsDigraph ()
+{
+  for (StatePointer q = states.begin (); q != states.end (); ++q)
+    {
+      for (Bundle::iterator a = q->bundle.begin (); a != q->bundle.end (); ++a)
+        {
+          if (! _M_grammar->isNonTerminal (a.key ()))
+            continue;
+
+          StatePointer r = a.value ();
+
+          for (Bundle::iterator z = r->bundle.begin (); z != r->bundle.end (); ++z)
+            {
+              Name sym = z.key ();
+
+              if (! _M_grammar->isNonTerminal(sym) || nullables.find (sym) == nullables.end ())
+                continue;
+
+              ReadsGraph::iterator source = ReadsGraph::get (Read (q, a.key ()));
+              ReadsGraph::iterator target = ReadsGraph::get (Read (r, sym));
+
+              source->insertEdge (target);
+
+#ifndef QLALR_NO_DEBUG_READS
+              qerr << "*** ";
+              dump (qerr, source);
+              qerr << " reads ";
+              dump (qerr, target);
+              qerr << endl;
+#endif
+            }
+        }
+    }
+}
+
+void Automaton::buildReads ()
+{
+  buildDirectReads ();
+  buildReadsDigraph ();
+
+  _M_reads_dfn = 0;
+
+  for (ReadsGraph::iterator node = ReadsGraph::begin_nodes (); node != ReadsGraph::end_nodes (); ++node)
+    {
+      if (! node->root)
+        continue;
+
+      visitReadNode (node);
+    }
+
+  for (ReadsGraph::iterator node = ReadsGraph::begin_nodes (); node != ReadsGraph::end_nodes (); ++node)
+    visitReadNode (node);
+}
+
+void Automaton::visitReadNode (ReadNode node)
+{
+  if (node->dfn != 0)
+    return; // nothing to do
+
+  int N = node->dfn = ++_M_reads_dfn;
+  _M_reads_stack.push (node);
+
+#ifndef QLALR_NO_DEBUG_INCLUDES
+  // qerr << "*** Debug. visit node (" << id (node->data.state) << ", " << node->data.nt << ")  N = " << N << endl;
+#endif
+
+  for (ReadsGraph::edge_iterator edge = node->begin (); edge != node->end (); ++edge)
+    {
+      ReadsGraph::iterator r = *edge;
+
+      visitReadNode (r);
+
+      node->dfn = qMin (N, r->dfn);
+
+      NameSet &dst = node->data.state->reads [node->data.nt];
+      NameSet &src = r->data.state->reads [r->data.nt];
+      dst.insert (src.begin (), src.end ());
+    }
+
+  if (node->dfn == N)
+    {
+      ReadsGraph::iterator tos = _M_reads_stack.top ();
+
+      do {
+        tos = _M_reads_stack.top ();
+        _M_reads_stack.pop ();
+        tos->dfn = INT_MAX;
+      } while (tos != node);
+    }
+}
+
+void Automaton::buildIncludesAndFollows ()
+{
+  for (StatePointer p = states.begin (); p != states.end (); ++p)
+    p->follows = p->reads;
+
+  buildIncludesDigraph ();
+
+  _M_includes_dfn = 0;
+
+  for (IncludesGraph::iterator node = IncludesGraph::begin_nodes (); node != IncludesGraph::end_nodes (); ++node)
+    {
+      if (! node->root)
+        continue;
+
+      visitIncludeNode (node);
+    }
+
+  for (IncludesGraph::iterator node = IncludesGraph::begin_nodes (); node != IncludesGraph::end_nodes (); ++node)
+    visitIncludeNode (node);
+}
+
+void Automaton::buildIncludesDigraph ()
+{
+  for (StatePointer pp = states.begin (); pp != states.end (); ++pp)
+    {
+      for (Bundle::iterator a = pp->bundle.begin (); a != pp->bundle.end (); ++a)
+        {
+          Name name = a.key ();
+
+          if (! _M_grammar->isNonTerminal (name))
+            continue;
+
+          foreach (RulePointer rule, _M_grammar->rule_map.values (name))
+            {
+              StatePointer p = pp;
+
+              for (NameList::iterator A = rule->rhs.begin (); A != rule->rhs.end (); ++A)
+                {
+                  NameList::iterator dot = A;
+                  ++dot;
+
+                  if (_M_grammar->isNonTerminal (*A) && dot == rule->rhs.end ())
+                    {
+                      // found an include edge.
+                      IncludesGraph::iterator target = IncludesGraph::get (Include (pp, name));
+                      IncludesGraph::iterator source = IncludesGraph::get (Include (p, *A));
+
+                      source->insertEdge (target);
+
+#ifndef QLALR_NO_DEBUG_INCLUDES
+                      qerr << "*** (" << id (p) << ", " << *A << ") includes (" << id (pp) << ", " << *name << ")" << endl;
+#endif // QLALR_NO_DEBUG_INCLUDES
+
+                      continue;
+                    }
+
+                  p = p->bundle.value (*A);
+
+                  if (! _M_grammar->isNonTerminal (*A))
+                    continue;
+
+                  NameList::iterator first_not_nullable = std::find_if (dot, rule->rhs.end (), std::not1 (_Nullable (this)));
+                  if (first_not_nullable != rule->rhs.end ())
+                    continue;
+
+                  // found an include edge.
+                  IncludesGraph::iterator target = IncludesGraph::get (Include (pp, name));
+                  IncludesGraph::iterator source = IncludesGraph::get (Include (p, *A));
+
+                  source->insertEdge (target);
+
+#ifndef QLALR_NO_DEBUG_INCLUDES
+                  qerr << "*** (" << id (p) << ", " << *A << ") includes (" << id (pp) << ", " << *name << ")" << endl;
+#endif // QLALR_NO_DEBUG_INCLUDES
+                }
+            }
+        }
+    }
+}
+
+void Automaton::visitIncludeNode (IncludeNode node)
+{
+  if (node->dfn != 0)
+    return; // nothing to do
+
+  int N = node->dfn = ++_M_includes_dfn;
+  _M_includes_stack.push (node);
+
+#ifndef QLALR_NO_DEBUG_INCLUDES
+  // qerr << "*** Debug. visit node (" << id (node->data.state) << ", " << node->data.nt << ")  N = " << N << endl;
+#endif
+
+  for (IncludesGraph::edge_iterator edge = node->begin (); edge != node->end (); ++edge)
+    {
+      IncludesGraph::iterator r = *edge;
+
+      visitIncludeNode (r);
+
+      node->dfn = qMin (N, r->dfn);
+
+#ifndef QLALR_NO_DEBUG_INCLUDES
+      qerr << "*** Merge. follows";
+      dump (qerr, node);
+      qerr << " += follows";
+      dump (qerr, r);
+      qerr << endl;
+#endif
+
+      NameSet &dst = node->data.state->follows [node->data.nt];
+      NameSet &src = r->data.state->follows [r->data.nt];
+
+      dst.insert (src.begin (), src.end ());
+    }
+
+  if (node->dfn == N)
+    {
+      IncludesGraph::iterator tos = _M_includes_stack.top ();
+
+      do {
+        tos = _M_includes_stack.top ();
+        _M_includes_stack.pop ();
+        tos->dfn = INT_MAX;
+      } while (tos != node);
+    }
+}
+
+void Automaton::buildLookaheads ()
+{
+  for (StatePointer p = states.begin (); p != states.end (); ++p)
+    {
+      for (ItemPointer item = p->closure.begin (); item != p->closure.end (); ++item)
+        {
+          foreach (Lookback lookback, lookbacks.values (item))
+            {
+              StatePointer q = lookback.state;
+
+#ifndef QLALR_NO_DEBUG_LOOKAHEADS
+              qerr << "(" << id (p) << ", " << *item->rule << ") lookbacks ";
+              dump (qerr, lookback);
+              qerr << " with follows (" << id (q) << ", " << lookback.nt << ") = " << q->follows [lookback.nt] << endl;
+#endif
+
+              lookaheads [item].insert (q->follows [lookback.nt].begin (), q->follows [lookback.nt].end ());
+            }
+        }
+
+      // propagate the lookahead in the kernel
+      ItemPointer k = p->kernel.begin ();
+      ItemPointer c = p->closure.begin ();
+
+      for (; k != p->kernel.end (); ++k, ++c)
+        lookaheads [k] = lookaheads [c];
+    }
+}
+
+void Automaton::buildDefaultReduceActions ()
+{
+  for (StatePointer state = states.begin (); state != states.end (); ++state)
+    {
+      ItemPointer def = state->closure.end ();
+      int size = -1;
+
+      for (ItemPointer item = state->closure.begin (); item != state->closure.end (); ++item)
+        {
+          if (item->dot != item->end_rhs ())
+            continue;
+
+          int la = lookaheads.value (item).size ();
+          if (def == state->closure.end () || la > size)
+            {
+              def = item;
+              size = la;
+            }
+        }
+
+      if (def != state->closure.end ())
+        {
+          Q_ASSERT (size >= 0);
+          state->defaultReduce = def->rule;
+        }
+    }
+}
+
+void Automaton::dump (QTextStream &out, IncludeNode incl)
+{
+  out << "(" << id (incl->data.state) << ", " << incl->data.nt << ")";
+}
+
+void Automaton::dump (QTextStream &out, ReadNode rd)
+{
+  out << "(" << id (rd->data.state) << ", " << rd->data.nt << ")";
+}
+
+void Automaton::dump (QTextStream &out, const Lookback &lp)
+{
+  out << "(" << id (lp.state) << ", " << lp.nt << ")";
+}