lr_parser_simple.C

/*
 * This file is part of the "Archon" framework.
 * (http://files3d.sourceforge.net)
 *
 * Copyright © 2002 by Kristian Spangsege and Brian Kristiansen.
 *
 * Permission to use, copy, modify, and distribute this software and
 * its documentation under the terms of the GNU General Public License is
 * hereby granted. No representations are made about the suitability of
 * this software for any purpose. It is provided "as is" without express
 * or implied warranty. See the GNU General Public License
 * (http://www.gnu.org/copyleft/gpl.html) for more details.
 *
 * The characters in this file are ISO8859-1 encoded.
 *
 * The documentation in this file is in "Doxygen" style
 * (http://www.doxygen.org).
 */

#include <string>
#include <iostream>

#include <archon/util/nfa.H>
#include <archon/util/dfa.H>
#include <archon/util/text.H>

#include <archon/util/lr_parser_simple.H>

using namespace std;

namespace Archon
{
  namespace Utilities
  {
    int SlrParser::getAction(int state, int terminal) const
    {
      return actionTable[state+numberOfStates*(terminal+1)];
    }

    int SlrParser::getGoto(int state, int nonterminal) const
    {
      return gotoTable[state+numberOfStates*nonterminal];
    }

    string SlrParser::printItemSets(const vector<pair<int, int> > &items,
                                    const vector<set<int> > &itemSets, int width)
    {
      vector<double> columnWidthFractions;
      columnWidthFractions.push_back(0.2);
      columnWidthFractions.push_back(0.9);
      Text::Table<string> table(itemSets.size()+1, columnWidthFractions);
      table(0, 0) = "State";
      table(0, 1) = "LR(0) item set";
      for(unsigned i=0; i<itemSets.size(); ++i)
      {
        const set<int> &s = itemSets[i];
        table(i+1, 0) = Text::toString(i);
        for(set<int>::const_iterator j=s.begin(); j!=s.end(); ++j)
        {
          if(j!=s.begin()) table(i+1, 1) += ", ";
          const pair<int, int> &item = items[*j];
          const Production &p = productions[item.first];
          table(i+1, 1) += grammar.printItem(CFG::Item(p.rule, p.production, item.second));
        }
      }

      return Text::format(table, width, 2, true);
    }

    struct AutomatonSymbolPrinter: NFA::Printer, DFA::Printer
    {
      const CFG &g;
      AutomatonSymbolPrinter(const CFG &g): g(g) {}
      string printSymbol(unsigned i) const
      {
        const int s = static_cast<int>(i) - g.getNumberOfRules();
        return s<0 ? g.printNonterminal(-s-1) : g.printTerminal(s);
      }
    };

    SlrParser::SlrParser(CFG &g, const ActorBase *actor, const Printer *printer):
      LrParserBase((g.introduceNewStartSymbol(), g), actor, printer)
    {
      //cerr << "Augmented Grammar without mid-rule actions:\n" << grammar.print(80) << "\n";

      const int automatonSymbolShift = grammar.getNumberOfRules();

      // Construct the NFA
      NFA nfa;
      vector<pair<int, int> > items;
      {
        map<pair<int, int>, int> nfaStateMap;
        multimap<int, int> nonterminalToProductionMap;

        for(unsigned i=0; i<productions.size(); ++i)
        {
          const Production &p = productions[i];
          nonterminalToProductionMap.insert(make_pair(p.rule, i));
          int s = nfaStateMap[make_pair(i, 0)] =
            i ? nfa.addState() : nfa.addStartState();
          for(unsigned j=0; j<p.right.size(); ++j)
          {
            const int t = nfaStateMap[make_pair(i, j+1)] = nfa.addState();
            nfa.addEdge(s, t, automatonSymbolShift + p.right[j]);
            s = t;
          }
        }

        for(unsigned i=0; i<productions.size(); ++i)
        {
          const Production &p = productions[i];
          for(unsigned j=0; j<p.right.size(); ++j)
          {
            const int t = p.right[j];
            if(t > -1) continue;
            const int s = nfaStateMap[make_pair(i, j)];
            pair<multimap<int, int>::iterator, multimap<int, int>::iterator> r =
              nonterminalToProductionMap.equal_range(-1-t);
            for(multimap<int, int>::iterator k=r.first; k!=r.second; ++k)
              nfa.addEdge(s, nfaStateMap[make_pair(k->second, 0)]);
          }
        }

        items.resize(nfaStateMap.size());
        for(map<pair<int, int>, int>::iterator i=nfaStateMap.begin(); i!=nfaStateMap.end(); ++i)
          items[i->second] = i->first;
      }

      //AutomatonSymbolPrinter p(grammar);

      //cerr << "NFA for grammar (recognition of viable prefixes):\n" << nfa.print(p, 80) << "\n";

      // Construct the DFA
      vector<set<int> > itemSets; // One outer entry per new state
      DFA dfa(nfa, &itemSets);

      //cerr << "DFA for grammar (recognition of viable prefixes):\n" << dfa.print(p, 80) << "\n";

      //cerr << "Cannonical LR(0) collection of item sets:\n";
      //cerr << printItemSets(items, itemSets, 80) << "\n";

      numberOfStates = dfa.getNumberOfStates();

      actionTable.resize((grammar.getNumberOfTerminals()+1) * numberOfStates, -1); // Fill with error
      gotoTable.resize(grammar.getNumberOfRules() * numberOfStates, -1); // Fill with error

      // Construct the shift actions and the goto table from the DFA
      for(int i=0; i<numberOfStates; ++i)
      {
        const DFA::State &s = dfa.getState(i);
        for(int j=0; j<s.getNumberOfEdges(); ++j)
        {
          const DFA::Edge &e = s.getEdge(j);
          for(unsigned k=e.getBegin(); k<=e.getEnd(); ++k)
          {
            if(k<static_cast<unsigned>(automatonSymbolShift))
              gotoTable[i+numberOfStates*(automatonSymbolShift-k-1)] =
                e.getTargetState();
            else actionTable[i+numberOfStates*(k-automatonSymbolShift+1)] =
                   e.getTargetState();
          }
        }
      }

      CFG::FirstSets firstSets(grammar);
      //cerr << firstSets.print() << "\n";
      CFG::FollowSets followSets(firstSets);
      //cerr << followSets.print() << "\n";

      /*
       * In the item sets find all items with end position, then for
       * each terminal in the follow set of the left hand side
       * nonterminal of the item, set 'action[i, a] = reduce by p'
       * where 'i' is the state associated with the current item set
       * and 'a' is the terminal and 'p' is the production index from
       * the current item item.
       */
      for(unsigned i=0; i<itemSets.size(); ++i)
      {
        const set<int> &s = itemSets[i];
        for(set<int>::const_iterator j=s.begin(); j!=s.end(); ++j)
        {
          const pair<int, int> &item = items[*j];
          const Production &p = productions[item.first];
          if(static_cast<unsigned>(item.second) != p.right.size()) continue;
          if(item.first == 0)
          {
            actionTable[i] = -2;
            continue;
          }
          const set<int> &f = followSets.get(p.rule);
          for(set<int>::const_iterator k=f.begin(); k!=f.end(); ++k)
          {
            int &v = actionTable[i+numberOfStates*(*k+1)];
            if(v < -2)
            {
              const Production &q = productions[-3-v];
              ARCHON_THROW1(ArgumentException,
                            "reduce/reduce conflict at state " +
                            Text::toString(i) + " on input terminal " +
                            grammar.printTerminal(*k) + ": " +
                            grammar.printProduction(q.rule,
                                                    q.production) +
                            " or " +
                            grammar.printProduction(p.rule,
                                                    p.production));
            }
            if(v > -1)
              ARCHON_THROW1(ArgumentException,
                            "shift/reduce conflict at state " +
                            Text::toString(i) + " on input terminal " +
                            grammar.printTerminal(*k) + ": shift " +
                            "and goto state " + Text::toString(v) +
                            " or reduce by " +
                            grammar.printProduction(p.rule,
                                                    p.production));
            v = -3 - item.first;
          }
        }
      }
    }

    SlrParser::~SlrParser()
    {
    }
  }
}

---