lalr.cpp

Go to the documentation of this file.

/****************************************************************************
**
** Copyright (C) 2016 The Qt Company Ltd.
** Contact: https://www.qt.io/licensing/
**
** This file is part of the utils of the Qt Toolkit.
**
** $QT_BEGIN_LICENSE:GPL-EXCEPT$
** 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 The Qt Company. For licensing terms
** and conditions see https://www.qt.io/terms-conditions. For further
** information use the contact form at https://www.qt.io/contact-us.
**
** GNU General Public License Usage
** Alternatively, this file may be used under the terms of the GNU
** General Public License version 3 as published by the Free Software
** Foundation with exceptions as appearing in the file LICENSE.GPL3-EXCEPT
** included in the packaging of this file. Please review the following
** information to ensure the GNU General Public License requirements will
** be met: https://www.gnu.org/licenses/gpl-3.0.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()
{
    static QTextStream result(stderr, QTextStream::WriteOnly);
    return result;
}
 
QTextStream &qout()
{
    static QTextStream result(stdout, QTextStream::WriteOnly);
    return result;
}
QT_END_NAMESPACE
 
namespace std {
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;
}
}
 
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, QLatin1String("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 NotNullable
{
  typedef Name argument_type;
  Automaton *_M_automaton;
 
  NotNullable (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(), NotNullable(this));
 
          if (nn == rule->rhs.end ())
            changed |= nullables.insert (rule->lhs).second;
        }
    }
 
#ifndef QLALR_NO_DEBUG_NULLABLES
  qerr() << "nullables = {" << nullables << Qt::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
{
  std::list<ItemPointer> items;
 
  void insert (ItemPointer item)
  { items.push_back (item); }
 
  State toState (Automaton *aut)
  {
    State st (aut->_M_grammar);
 
    for (auto &item : items)
      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))
        {
          const auto range = qAsConst(_M_grammar->rule_map).equal_range(*item->dot);
          for (auto it = range.first; it != range.second; ++it)
            {
              const RulePointer &rule = *it;
              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;
 
          const auto range = qAsConst(_M_grammar->rule_map).equal_range(A);
          for (auto it = range.first; it != range.second; ++it)
            {
              const RulePointer &rule = *it;
              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 << ")" << Qt::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 () << Qt::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() << Qt::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 << Qt::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;
 
          const auto range = qAsConst(_M_grammar->rule_map).equal_range(name);
          for (auto it = range.first; it != range.second; ++it)
            {
              const RulePointer &rule = *it;
              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 << ")" << Qt::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(), NotNullable(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 << ")" << Qt::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 << Qt::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() << Qt::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)
        {
          const auto range = qAsConst(lookbacks).equal_range(item);
          for (auto it = range.first; it != range.second; ++it)
            {
              const Lookback &lookback = *it;
              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] << Qt::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 = static_cast<int>(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 << ")";
}