lr_parser_canonical.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).
 */



/*

HAS A BUG (OR MANY)

*/

/*

DFA construction takes a looooong time on grammars like REGEX.

*/


#include <string>
#include <iostream>

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

#include <archon/util/lr_parser_canonical.H>

using namespace std;

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

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

    string ClrParser::printItemSets(const vector<LR1Item> &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(1) 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 LR1Item &item = items[*j];
          const Production &p = productions[item.production];
          table(i+1, 1) +=
            grammar.printItem(CFG::Item(p.rule, p.production, item.position)) +
            ":" + grammar.printTerminal(item.lookahead);
        }
      }

      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);
      }
    };

    ClrParser::ClrParser(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";

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

      const int automatonSymbolShift = grammar.getNumberOfRules();

      // Construct the NFA
      NFA nfa;
      vector<LR1Item> items;
      {
        bool f = true;
        map<LR1Item, 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));
          for(int k=-1; k<grammar.getNumberOfTerminals(); ++k)
          {
            int s = nfaStateMap[LR1Item(i, 0, k)] =
              f ? nfa.addStartState() : nfa.addState();
            f = false;
            for(unsigned j=0; j<p.right.size(); ++j)
            {
              const int t = nfaStateMap[LR1Item(i, j+1, k)] = 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;
            CFG::Item h(p.rule, p.production, j+1);
            set<int> f;
            const bool e = firstSets.includeFirstSet(h, f);
            /*
              cerr << "first(" << grammar.printItem(h) << ") = " << e << ", {";
              for(set<int>::iterator m=f.begin(); m!=f.end(); ++m)
              {
              if(m!=f.begin()) cerr << " ";
              cerr << grammar.printTerminal(*m);
              }
              cerr << "}\n";
            */
            for(int k=-1; k<grammar.getNumberOfTerminals(); ++k)
            {
              const int s = nfaStateMap[LR1Item(i, j, k)];
              pair<multimap<int, int>::iterator, multimap<int, int>::iterator> r =
                nonterminalToProductionMap.equal_range(-1-t);
              for(multimap<int, int>::iterator l=r.first; l!=r.second; ++l)
              {
                for(set<int>::iterator m=f.begin(); m!=f.end(); ++m)
                {
                  nfa.addEdge(s, nfaStateMap[LR1Item(l->second, 0, *m)]);
                }
                if(e && (k == -1 || f.find(k) == f.end()))
                {
                  nfa.addEdge(s, nfaStateMap[LR1Item(l->second, 0, k)]);
                }
              }
            }
          }
        }

        items.resize(nfaStateMap.size());
        for(map<LR1Item, 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(1) 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();
          }
        }
      }

      // Construct the reduce actions from the items with end position
      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 LR1Item &item = items[*j];
          const Production &p = productions[item.production];
          if(static_cast<unsigned>(item.position) != p.right.size()) continue;
          if(item.production == 0)
          {
            if(item.lookahead == -1) actionTable[i] = -2;
            continue;
          }
          int &v = actionTable[i+numberOfStates*(item.lookahead+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(item.lookahead) +
                          ": " +
                          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(item.lookahead) +
                          ": shift and goto state " +
                          Text::toString(v) + " or reduce by " +
                          grammar.printProduction(p.rule,
                                                  p.production));

          v = -3 - item.production;
        }
      }
    }

    ClrParser::~ClrParser()
    {
    }
  }
}

---