grammar.java

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

    }

    if(previousContainsEmpty)
    {
      result.setEmpty();
    }
    else
    {
      result.clearEmpty();
    }

    return result;
  }

  static SymbolSet[] FOLLOW;

  static void computeFollow()
  {
    // Get terminals, nonterminals and productions
    Symbol[] terminals = Symbol.terminals();
    Symbol[] nonterminals = Symbol.nonterminals();
    Production[] productions = Production.productions();

    // Initialize FOLLOW(A) to {}
    FOLLOW = new SymbolSet[nonterminals.length];
    for(int i = 0; i < nonterminals.length; i++)
    {
      FOLLOW[i] = new SymbolSet();
    }

    // Place eof in FOLLOW(S) where S is the start symbol.
    FOLLOW[startSymbol].setTerminal(eof);

    // If there is a production A->xBy, then everything in FIRST(y) except
    // for empty is placed in FOLLOW(B).
    for(int i = 0; i < productions.length; i++)
    {
      Symbol[] rightside = productions[i].rightside();

      for(int j = 0; j < rightside.length; j++)
      {
        if(!rightside[j].terminal)
        {
          SymbolSet set
            = FIRST(rightside, j + 1);
          set.clearEmpty();
          FOLLOW[rightside[j].index].or(set
                                       );
        }
      }
    }

    // If there is a production A->xB, or a production A->xBy where FIRST(y)
    // contains empty, then everything in FOLLOW(A) is in FOLLOW(B).
    boolean changed;
    do
    {
      changed = false;

      for(int i = 0; i < productions.length; i++)
      {
        Symbol[] rightside = productions[i].rightside();

        for(int j = 0; j < rightside.length; j++)
        {
          if(!rightside[j].terminal)
          {
            SymbolSet before =
              (SymbolSet) FOLLOW[rightside[j].index].clone();

            if(FIRST(rightside, j + 1).getEmpty())
            {
              FOLLOW[rightside[j].index].
              or(FOLLOW[productions[i].leftside]);
            }

            if(!before.equals(FOLLOW[rightside[j].index]))
            {
              changed = true;
            }
          }
        }
      }
    }
    while(changed);
  }

  static SymbolSet FOLLOW(int nonterminal)
  {
    return FOLLOW[nonterminal];
  }

  static LR0ItemSet CLOSURE(LR0Item item)
  {
    LR0ItemSet result = (LR0ItemSet) fastLr0Closure.get(item);

    if(result != null)
    {
      return result;
    }

    result = new LR0ItemSet();
    result.set(item);

    LR0ItemSet newItems = result;
    boolean modified;
    do
    {
      modified = false;
      LR0Item[] items = newItems.items();
      newItems = new LR0ItemSet();

      for(int i = 0; i < items.length; i++)
      {
        Production production = Production.production(items[i].production);
        Symbol[] rightside = production.rightside();
        if(items[i].position < rightside.length)
        {
          Symbol symbol = rightside[items[i].position];

          if(!symbol.terminal)
          {
            Production[] alternatives =
              Production.alternatives(symbol.index);

            for(int j = 0; j < alternatives.length; j++)
            {
              LR0Item newItem = new LR0Item(alternatives[j].index, 0);

              if(!result.get(newItem))
              {
                result.set(newItem);
                newItems.set(newItem);
                modified = true;
              }
            }
          }
        }
      }
    }
    while(modified);

    fastLr0Closure.put(item, result);

    return result;
  }

  //    private static final SplayTreeMap fastLr0SetClosure = new SplayTreeMap();

  static LR0ItemSet CLOSURE(LR0ItemSet set
                             )
  {
    LR0ItemSet result =
      /*
        (LR0ItemSet) fastLr0SetClosure.get(set);
        
        if(result != null)
        {
        return result;
        }
        
        result =*/
      new LR0ItemSet();

    LR0Item[] setItems = set.items();

    for(int i = 0; i < setItems.length; i++)
    {
      LR0Item[] items = CLOSURE(setItems[i]).items();

      for(int j = 0; j < items.length; j++)
      {
        result.set(items[j]);
      }
    }

    // fastLr0SetClosure.put(set, result);

    return result;
  }

  static LR1ItemSet CLOSURE(LR1Item item)
  {
    LR1ItemSet result = (LR1ItemSet) fastLr1Closure.get(item);

    if(result != null)
    {
      return result;
    }

    result = new LR1ItemSet();
    result.set(item);

    LR1ItemSet newItems = result;
    boolean modified;
    do
    {
      modified = false;
      LR1Item[] items = newItems.items();
      newItems = new LR1ItemSet();

      for(int i = 0; i < items.length; i++)
      {
        Production production = Production.production(items[i].lr0Item.production);
        Symbol[] rightside = production.rightside();
        if(items[i].lr0Item.position < rightside.length)
        {
          Symbol symbol = rightside[items[i].lr0Item.position];

          if(!symbol.terminal)
          {
            Vector tailVector = new Vector(0);

            for(int k = items[i].lr0Item.position + 1; k < rightside.length; k++)
            {
              tailVector.addElement(rightside[k]);
            }

            tailVector.addElement(Symbol.symbol(items[i].terminal, true));

            Symbol[] tail = new Symbol[tailVector.size()];
            tailVector.copyInto(tail);

            Symbol[] symbols = FIRST(tail).getSymbols();

            Production[] alternatives =
              Production.alternatives(symbol.index);

            for(int k = 0; k < symbols.length; k++)
            {
              if(symbols[k].terminal)
              {
                for(int j = 0; j < alternatives.length; j++)
                {
                  LR1Item newItem = new LR1Item(
                                      new LR0Item(alternatives[j].index, 0),
                                      symbols[k].index);

                  if(!result.get(newItem))
                  {
                    result.set(newItem);
                    newItems.set(newItem);
                    modified = true;
                  }
                }
              }
            }
          }
        }
      }
    }
    while(modified);

    fastLr1Closure.put(item, result);

    return result;
  }

  // private static final SplayTreeMap fastLr1SetClosure = new SplayTreeMap();

  static LR1ItemSet CLOSURE(LR1ItemSet set
                             )
  {
    LR1ItemSet result =
      /*
        (LR1ItemSet) fastLr1SetClosure.get(set);
        
        if(result != null)
        {
        return result;
        }
        
        result =*/
      new LR1ItemSet();

    LR1Item[] setItems = set.items();

    for(int i = 0; i < setItems.length; i++)
    {
      LR1Item[] items = CLOSURE(new LR1Item(setItems[i].lr0Item, dummy)).items();

      for(int j = 0; j < items.length; j++)
      {
        result.set(new LR1Item(items[j].lr0Item,
                               items[j].terminal == dummy ? setItems[i].terminal : items[j].terminal));
      }
    }

    //        fastLr1SetClosure.put(set, result);

    return result;
  }

  static LR0ItemSet GOTO(LR0ItemSet set
                           , Symbol symbol)
  {
    LR0ItemSet initialset = set
                              ;
    set
      = CLOSURE(set
               );
    LR0ItemSet result = new LR0ItemSet();

    // return all items A->xS.y such that A->x.Sy is in set. (S=symbol)
    LR0Item[] items = set.items();
    for(int i = 0; i < items.length; i++)
    {
      Production production = Production.production(items[i].production);
      Symbol[] rightside = production.rightside();
      if(items[i].position < rightside.length)
      {
        if(symbol.equals(rightside[items[i].position]))
        {
          result.set(new LR0Item(items[i].production,
                                 items[i].position + 1));
        }
      }
    }

    return result;
  }
}