grammar.java

来自「有关编译器的编译器.」· Java 代码 · 共 648 行 · 第 1/2 页

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
 * 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();
      }