/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * This file is part of SableCC.                             * * See the file "LICENSE" for copyright information and the  * * terms and conditions for copying, distribution and        * * modification of SableCC.                                  * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */package org.sablecc.sablecc;import java.util.Vector;import java.util.*;public final class Grammar{  private static TreeMap fastLr0Closure = new TreeMap();  private static TreeMap fastLr1Closure = new TreeMap();  static int startSymbol;  static int startProduction;  static int eof ;  static int dummy ;  static int[][][] action_;  static int[][] goto_;  static  {    reinit();  }  private Grammar()  {}  public static int addTerminal(String name, String errorName)  {    return new Symbol(name, errorName, true).index;  }  public static int addNonterminal(String name)  {    return new Symbol(name, null, false).index;  }  public static int addProduction(String nonterminal, String name)  {    Symbol symbol = Symbol.symbol(nonterminal);    if(symbol.terminal)    {      throw new IllegalArgumentException("The symbol " + nonterminal +                                         " is a terminal.");    }    return new Production(symbol.index, name).index;  }  public static void addSymbolToProduction(String symbol, int production)  {    Production.production(production).addSymbol(Symbol.symbol(symbol));  }  public static void reinit()  {    fastLr0Closure = new TreeMap();    fastLr1Closure = new TreeMap();    startSymbol = 0;    startProduction = -1;    eof = -1;    dummy = -1;    action_ = null;    goto_ = null;  }  public static void computeLALR()  {    // Add EOF to terminals    eof = addTerminal("EOF", "EOF");    // Add dummy to terminals    dummy = addTerminal("#", null);    // Add the production S'->S    startSymbol = addNonterminal("Start");    Production start = new Production(startSymbol, "Start");    start.addSymbol(Symbol.symbol(0, false));    startProduction = start.index;    computeFirst();    LR0ItemSet set      = new LR0ItemSet();    set.set(new LR0Item(startProduction, 0));    LR1Collection collection = new LR1Collection(set                                                );    LR0ItemSet[] sets = collection.collection.sets();    Symbol[] terminals = Symbol.terminals();    Symbol[] nonterminals = Symbol.nonterminals();    action_ = new int[sets.length][terminals.length - 1][];    goto_ = new int[sets.length][nonterminals.length - 1];    for(int i = 0; i < sets.length; i++)    {      System.out.print(".");      LR1ItemSet state = new LR1ItemSet();      {        LR0Item[] items = sets[i].items();        for(int j = 0; j < items.length; j++)        {          Symbol[] lookaheads = ((SymbolSet) collection.lookaheads[i].                                 get                                   (items[j])).getSymbols();          for(int k = 0; k < lookaheads.length; k++)          {            state.set(new LR1Item(items[j], lookaheads[k].index));          }        }      }      state = CLOSURE(state);      LR1Item[] items = state.items();      for(int j = 0; j < terminals.length; j++)      {        Integer destination = collection.collection.GOTO(i, terminals[j]);        if(destination != null)        {          action_[i][j] = new int[] {0, destination.intValue()};        }        for(int k = 0; k < items.length; k++)        {          Production production = Production.                                  production(items[k].lr0Item.production);          try          {            production.rightside(items[k].lr0Item.position);          }          catch(Exception e)          {            if(production.leftside != startSymbol)            {              if(items[k].terminal == terminals[j].index)              {                int[] action = action_[i][j];                if(action != null)                {                  switch(action[0])                  {                  case 0:                    throw new RuntimeException(                      "\n\nshift/reduce conflict in state [stack:" +                      collection.collection.names.elementAt(i) + "*] on " +                      terminals[j] + " in " + state.toString(terminals[j]));                  case 1:                    throw new RuntimeException(                      "\n\nreduce/reduce conflict in state [stack:" +                      collection.collection.names.elementAt(i) + "*] on " +                      terminals[j] + " in " + state.toString(terminals[j]));                  case 2:                    throw new RuntimeException(                      "\n\nreduce/accept conflict in state [stack:" +                      collection.collection.names.elementAt(i) + "*] on " +                      terminals[j] + " in " + state.toString(terminals[j]));                  }                }                else                {                  action_[i][j] = new int[] {1,                                             items[k].lr0Item.production};                }              }            }            else            {              if(terminals[j].index == eof)              {                int[] action = action_[i][j];                if(action != null)                {                  switch(action[0])                  {                  case 0:                    throw new RuntimeException(                      "shift/accept conflict in state [stack:" +                      collection.collection.names.elementAt(i) + "*] on " +                      terminals[j] + " in " + state);                  case 1:                    throw new RuntimeException(                      "reduce/accept conflict in state [stack:" +                      collection.collection.names.elementAt(i) + "*] on " +                      terminals[j] + " in " + state);                  }                }                else                {                  action_[i][j] = new int[] {2};                }              }            }          }        }      }      for(int j = 0; j < nonterminals.length - 1; j++)      {        Integer destination = collection.collection.GOTO(i, nonterminals[j]);        if(destination != null)        {          goto_[i][j] = destination.intValue();        }        else        {          goto_[i][j] = -1;        }      }    }    System.out.println();  }  static SymbolSet[] FIRST_Terminal;  static SymbolSet[] FIRST_Nonterminal;  static void computeFirst()  {    // Get terminals, nonterminals and productions    Symbol[] terminals = Symbol.terminals();    Symbol[] nonterminals = Symbol.nonterminals();    Production[] productions = Production.productions();    // Initialize FIRST(X) to {}    FIRST_Terminal = new SymbolSet[terminals.length];    for(int i = 0; i < terminals.length; i++)    {      FIRST_Terminal[i] = new SymbolSet();    }    FIRST_Nonterminal = new SymbolSet[nonterminals.length];    for(int i = 0; i < nonterminals.length; i++)    {      FIRST_Nonterminal[i] = new SymbolSet();    }    // if X is terminal, then FIRST(X) is {X}    for(int i = 0; i < terminals.length; i++)    {      FIRST_Terminal[i].setTerminal(terminals[i].index);    }    // if X -> empty is a production, then add empty to FIRST(X)    for(int i = 0; i < productions.length; i++)    {      if(productions[i].rightside().length == 0)      {        FIRST_Nonterminal[productions[i].leftside].        setEmpty();      }    }    // if X is nonterminal and X -> Y(1) Y(2) ... Y(k) is a production,    // then place t in FIRST(X) if for some i, t is in FIRST(Y(i)), and    // empty is in all of FIRST(Y(1)), ... , FIRST(Y(i-1)).    boolean changed;    do    {      changed = false;      for(int i = 0; i < productions.length; i++)      {        SymbolSet before =          (SymbolSet) FIRST_Nonterminal[productions[i].leftside].clone();        FIRST_Nonterminal[productions[i].leftside].        or(FIRST(productions[i].rightside()));        if(!before.equals(FIRST_Nonterminal[productions[i].leftside]))        {          changed = true;        }      }    }    while(changed);  }  static SymbolSet FIRST(Symbol[] symbols)  {    return FIRST(symbols, 0, symbols.length);  }  static SymbolSet FIRST(Symbol[] symbols, int begin)  {    return FIRST(symbols, begin, symbols.length);  }  static SymbolSet FIRST(Symbol[] symbols, int begin, int end)  {    SymbolSet result = new SymbolSet();    boolean previousContainsEmpty = true;    for(int i = begin; i < end; i++)    {      if(!previousContainsEmpty)      {        break;      }      if(symbols[i].terminal)      {        result.or(FIRST_Terminal[symbols[i].index]);        previousContainsEmpty = FIRST_Terminal[symbols[i].index].getEmpty();      }      else      {        result.or(FIRST_Nonterminal[symbols[i].index]);        previousContainsEmpty = FIRST_Nonterminal[symbols[i].index].getEmpty();      }