antlr-3.4/tool/src/main/java/org/antlr/tool/GrammarAST.java - platform/external/antlr - Git at Google

 /*
  * [The "BSD license"]
  *  Copyright (c) 2010 Terence Parr
  *  All rights reserved.
  *
  *  Redistribution and use in source and binary forms, with or without
  *  modification, are permitted provided that the following conditions
  *  are met:
  *  1. Redistributions of source code must retain the above copyright
  *      notice, this list of conditions and the following disclaimer.
  *  2. Redistributions in binary form must reproduce the above copyright
  *      notice, this list of conditions and the following disclaimer in the
  *      documentation and/or other materials provided with the distribution.
  *  3. The name of the author may not be used to endorse or promote products
  *      derived from this software without specific prior written permission.
  *
  *  THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  *  IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  *  OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  *  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  *  INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  *  NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  *  DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  *  THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  *  (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  *  THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  */
 package org.antlr.tool;

 import org.antlr.analysis.DFA;
 import org.antlr.analysis.NFAState;
 import org.antlr.grammar.v3.ANTLRParser;
 import org.antlr.misc.IntSet;
 import org.antlr.misc.Interval;
 import org.antlr.runtime.CommonToken;
 import org.antlr.runtime.Token;
 import org.antlr.runtime.TokenSource;
 import org.antlr.runtime.tree.CommonTree;
 import org.antlr.runtime.tree.Tree;
 import org.antlr.runtime.tree.TreeAdaptor;
 import org.stringtemplate.v4.ST;
 import org.omg.PortableInterceptor.ORBInitInfoPackage.DuplicateName;

 import java.util.*;

 /** Grammars are first converted to ASTs using this class and then are
  *  converted to NFAs via a tree walker.
  *
  *  The reader may notice that I have made a very non-OO decision in this
  *  class to track variables for many different kinds of nodes.  It wastes
  *  space for nodes that don't need the values and OO principles cry out
  *  for a new class type for each kind of node in my tree.  I am doing this
  *  on purpose for a variety of reasons.  I don't like using the type
  *  system for different node types; it yields too many damn class files
  *  which I hate.  Perhaps if I put them all in one file.  Most importantly
  *  though I hate all the type casting that would have to go on.  I would
  *  have all sorts of extra work to do.  Ick.  Anyway, I'm doing all this
  *  on purpose, not out of ignorance. ;)
  */
 public class GrammarAST extends CommonTree {
 	static int count = 0;

 	public int ID = ++count;

 	private String textOverride;

     public String enclosingRuleName;

     /** If this is a decision node, what is the lookahead DFA? */
     public DFA lookaheadDFA = null;

     /** What NFA start state was built from this node? */
     public NFAState NFAStartState = null;

 	/** This is used for TREE_BEGIN nodes to point into
 	 *  the NFA.  TREE_BEGINs point at left edge of DOWN for LOOK computation
      *  purposes (Nullable tree child list needs special code gen when matching).
 	 */
 	public NFAState NFATreeDownState = null;

 	/** Rule ref nodes, token refs, set, and NOT set refs need to track their
 	 *  location in the generated NFA so that local FOLLOW sets can be
 	 *  computed during code gen for automatic error recovery.
 	 */
 	public NFAState followingNFAState = null;

 	/** If this is a SET node, what are the elements? */
     protected IntSet setValue = null;

     /** If this is a BLOCK node, track options here */
     protected Map<String,Object> blockOptions;

 	/** If this is a BLOCK node for a rewrite rule, track referenced
 	 *  elements here.  Don't track elements in nested subrules.
 	 */
 	public Set<GrammarAST> rewriteRefsShallow;

 	/*	If REWRITE node, track EVERY element and label ref to right of ->
 	 *  for this rewrite rule.  There could be multiple of these per
 	 *  rule:
 	 *
 	 *     a : ( ... -> ... | ... -> ... ) -> ... ;
 	 *
 	 *  We may need a list of all refs to do definitions for whole rewrite
 	 *  later.
 	 *
 	 *  If BLOCK then tracks every element at that level and below.
 	 */
 	public Set<GrammarAST> rewriteRefsDeep;

 	public Map<String,Object> terminalOptions;

 	/** if this is an ACTION node, this is the outermost enclosing
 	 *  alt num in rule.  For actions, define.g sets these (used to
 	 *  be codegen.g).  We need these set so we can examine actions
 	 *  early, before code gen, for refs to rule predefined properties
 	 *  and rule labels.  For most part define.g sets outerAltNum, but
 	 *  codegen.g does the ones for %foo(a={$ID.text}) type refs as
 	 *  the {$ID...} is not seen as an action until code gen pulls apart.
 	 */
 	public int outerAltNum;

 	/** if this is a TOKEN_REF or RULE_REF node, this is the code ST
 	 *  generated for this node.  We need to update it later to add
 	 *  a label if someone does $tokenref or $ruleref in an action.
 	 */
 	public ST code;

     /**
      *
      * @return
      */
     public Map<String, Object> getBlockOptions() {
         return blockOptions;
     }

     /**
      *
      * @param blockOptions
      */
     public void setBlockOptions(Map<String, Object> blockOptions) {
         this.blockOptions = blockOptions;
     }

 	public GrammarAST() {;}

 	public GrammarAST(int t, String txt) {
 		initialize(t,txt);
 	}

 	public GrammarAST(Token token) {
 		initialize(token);
 	}

 	public void initialize(int i, String s) {
         token = new CommonToken(i,s);
 		token.setTokenIndex(-1);
     }

     public void initialize(Tree ast) {
 		GrammarAST t = ((GrammarAST)ast);
 		this.startIndex = t.startIndex;
 		this.stopIndex = t.stopIndex;
 		this.token = t.token;
 		this.enclosingRuleName = t.enclosingRuleName;
 		this.setValue = t.setValue;
 		this.blockOptions = t.blockOptions;
 		this.outerAltNum = t.outerAltNum;
 	}

     public void initialize(Token token) {
         this.token = token;
 		if ( token!=null ) {
 			startIndex = token.getTokenIndex();
 			stopIndex = startIndex;
 		}
     }

     public DFA getLookaheadDFA() {
         return lookaheadDFA;
     }

     public void setLookaheadDFA(DFA lookaheadDFA) {
         this.lookaheadDFA = lookaheadDFA;
     }

     public NFAState getNFAStartState() {
         return NFAStartState;
     }

     public void setNFAStartState(NFAState nfaStartState) {
 		this.NFAStartState = nfaStartState;
 	}

 	/** Save the option key/value pair and process it; return the key
 	 *  or null if invalid option.
 	 */
 	public String setBlockOption(Grammar grammar, String key, Object value) {
 		if ( blockOptions == null ) {
 			blockOptions = new HashMap();
 		}
 		return setOption(blockOptions, Grammar.legalBlockOptions, grammar, key, value);
 	}

 	public String setTerminalOption(Grammar grammar, String key, Object value) {
 		if ( terminalOptions == null ) {
 			terminalOptions = new HashMap<String,Object>();
 		}
 		return setOption(terminalOptions, Grammar.legalTokenOptions, grammar, key, value);
 	}

 	public String setOption(Map options, Set legalOptions, Grammar grammar, String key, Object value) {
 		if ( !legalOptions.contains(key) ) {
 			ErrorManager.grammarError(ErrorManager.MSG_ILLEGAL_OPTION,
 									  grammar,
 									  token,
 									  key);
 			return null;
 		}
 		if ( value instanceof String ) {
 			String vs = (String)value;
 			if ( vs.charAt(0)=='"' ) {
 				value = vs.substring(1,vs.length()-1); // strip quotes
             }
         }
 		if ( key.equals("k") ) {
 			grammar.numberOfManualLookaheadOptions++;
 		}
         if ( key.equals("backtrack") && value.toString().equals("true") ) {
             grammar.composite.getRootGrammar().atLeastOneBacktrackOption = true;
         }
         options.put(key, value);
 		return key;
     }

     public Object getBlockOption(String key) {
 		Object value = null;
 		if ( blockOptions != null ) {
 			value = blockOptions.get(key);
 		}
 		return value;
 	}

     public void setOptions(Grammar grammar, Map options) {
 		if ( options==null ) {
 			this.blockOptions = null;
 			return;
 		}
 		String[] keys = (String[])options.keySet().toArray(new String[options.size()]);
 		for (String optionName : keys) {
 			String stored= setBlockOption(grammar, optionName, options.get(optionName));
 			if ( stored==null ) {
 				options.remove(optionName);
 			}
 		}
     }

     @Override
     public String getText() {
 		if ( textOverride!=null ) return textOverride;
         if ( token!=null ) {
             return token.getText();
         }
         return "";
     }

 	public void setType(int type) {
 		token.setType(type);
 	}

 	public void setText(String text) {
 		textOverride = text; // don't alt tokens as others might see
 	}

     @Override
     public int getType() {
         if ( token!=null ) {
             return token.getType();
         }
         return -1;
     }

     @Override
     public int getLine() {
 		int line=0;
         if ( token!=null ) {
             line = token.getLine();
         }
 		if ( line==0 ) {
 			Tree child = getChild(0);
 			if ( child!=null ) {
 				line = child.getLine();
 			}
 		}
         return line;
     }

     @Override
     public int getCharPositionInLine(){
 		int col=0;
         if ( token!=null ) {
             col = token.getCharPositionInLine();
         }
 		if ( col==0 ) {
 			Tree child = getChild(0);
 			if ( child!=null ) {
 				col = child.getCharPositionInLine();
 			}
 		}
         return col;
     }

     public void setLine(int line) {
         token.setLine(line);
     }

     public void setCharPositionInLine(int value){
         token.setCharPositionInLine(value);
     }

  	public IntSet getSetValue() {
         return setValue;
     }

     public void setSetValue(IntSet setValue) {
         this.setValue = setValue;
     }

     public GrammarAST getLastChild() {
         if (getChildCount() == 0)
             return null;
         return (GrammarAST)getChild(getChildCount() - 1);
     }

     public GrammarAST getNextSibling() {
         return (GrammarAST)getParent().getChild(getChildIndex() + 1);
     }

     public GrammarAST getLastSibling() {
         Tree parent = getParent();
         if ( parent==null ) {
             return null;
         }
         return (GrammarAST)parent.getChild(parent.getChildCount() - 1);
     }


     public GrammarAST[] getChildrenAsArray() {
         return (GrammarAST[])getChildren().toArray(new GrammarAST[getChildCount()]);
     }

     private static final GrammarAST DescendantDownNode = new GrammarAST(Token.DOWN, "DOWN");
     private static final GrammarAST DescendantUpNode = new GrammarAST(Token.UP, "UP");

     public static List<Tree> descendants(Tree root){
         return descendants(root, false);
     }

     public static List<Tree> descendants(Tree root, boolean insertDownUpNodes){
         List<Tree> result = new ArrayList<Tree>();
         int count = root.getChildCount();

         if (insertDownUpNodes){
             result.add(root);
             result.add(DescendantDownNode);

             for (int i = 0 ; i < count ; i++){
                 Tree child = root.getChild(i);
                 for (Tree subchild : descendants(child, true))
                     result.add(subchild);
             }

             result.add(DescendantUpNode);
         }else{
             result.add(root);
             for (int i = 0 ; i < count ; i++){
                 Tree child = root.getChild(i);
                 for (Tree subchild : descendants(child, false))
                     result.add(subchild);
             }
         }

         return result;
     }

 	public GrammarAST findFirstType(int ttype) {
 		// check this node (the root) first
 		if ( this.getType()==ttype ) {
 			return this;
 		}
 		// else check children
 		List<Tree> descendants = descendants(this);
 		for (Tree child : descendants) {
 			if ( child.getType()==ttype ) {
 				return (GrammarAST)child;
 			}
 		}
 		return null;
 	}

 	public List<GrammarAST> findAllType(int ttype) {
 		List<GrammarAST> nodes = new ArrayList<GrammarAST>();
 		_findAllType(ttype, nodes);
 		return nodes;
 	}

 	public void _findAllType(int ttype, List<GrammarAST> nodes) {
 		// check this node (the root) first
 		if ( this.getType()==ttype ) nodes.add(this);
 		// check children
 		for (int i = 0; i < getChildCount(); i++){
 			GrammarAST child = (GrammarAST)getChild(i);
 			child._findAllType(ttype, nodes);
 		}
 	}

     /** Make nodes unique based upon Token so we can add them to a Set; if
 	 *  not a GrammarAST, check type.
 	 */
 	@Override
 	public boolean equals(Object ast) {
 		if ( this == ast ) {
 			return true;
 		}
 		if ( !(ast instanceof GrammarAST) ) {
 			return this.getType() == ((Tree)ast).getType();
 		}
 		GrammarAST t = (GrammarAST)ast;
 		return token.getLine() == t.getLine() &&
 			   token.getCharPositionInLine() == t.getCharPositionInLine();
 	}

     /** Make nodes unique based upon Token so we can add them to a Set; if
 	 *  not a GrammarAST, check type.
 	 */
     @Override
     public int hashCode(){
         if (token == null)
             return 0;

         return token.hashCode();
     }

 	/** See if tree has exact token types and structure; no text */
 	public boolean hasSameTreeStructure(Tree other) {
 		// check roots first.
 		if (this.getType() != other.getType()) return false;
 		// if roots match, do full list match test on children.
 		Iterator<Tree> thisDescendants = descendants(this, true).iterator();
 		Iterator<Tree> otherDescendants = descendants(other, true).iterator();
 		while (thisDescendants.hasNext()) {
 			if (!otherDescendants.hasNext())
 				return false;
 			if (thisDescendants.next().getType() != otherDescendants.next().getType())
 				return false;
 		}
 		return !otherDescendants.hasNext();
 	}

 	public static GrammarAST dup(Tree t) {
 		if ( t==null ) {
 			return null;
 		}
 		GrammarAST dup_t = new GrammarAST();
 		dup_t.initialize(t);
 		return dup_t;
 	}

     @Override
     public Tree dupNode(){
         return dup(this);
     }

 	/**Duplicate a tree, assuming this is a root node of a tree--
 	 * duplicate that node and what's below; ignore siblings of root node.
 	 */
 	public static GrammarAST dupTreeNoActions(GrammarAST t, GrammarAST parent) {
 		if ( t==null ) {
 			return null;
 		}
 		GrammarAST result = (GrammarAST)t.dupNode();
 		for (GrammarAST subchild : getChildrenForDupTree(t)) {
 			result.addChild(dupTreeNoActions(subchild, result));
 		}
 		return result;
 	}

 	private static List<GrammarAST> getChildrenForDupTree(GrammarAST t) {
 		List<GrammarAST> result = new ArrayList<GrammarAST>();
 		for (int i = 0; i < t.getChildCount(); i++){
 			GrammarAST child = (GrammarAST)t.getChild(i);
 			int ttype = child.getType();
 			if (ttype == ANTLRParser.REWRITES || ttype == ANTLRParser.REWRITE || ttype==ANTLRParser.ACTION) {
 				continue;
 			}

 			if (ttype == ANTLRParser.BANG || ttype == ANTLRParser.ROOT) {
 				for (GrammarAST subchild : getChildrenForDupTree(child))
 					result.add(subchild);
 			} else {
 				result.add(child);
 			}
 		}
 		if ( result.size()==1 && result.get(0).getType()==ANTLRParser.EOA &&
 			 t.getType()==ANTLRParser.ALT )
 		{
 			// can't have an empty alt, insert epsilon
 			result.add(0, new GrammarAST(ANTLRParser.EPSILON, "epsilon"));
 		}

 		return result;
 	}

 	public static GrammarAST dupTree(GrammarAST t) {
 		if ( t==null ) {
 			return null;
 		}
 		GrammarAST root = dup(t);		// make copy of root
 		// copy all children of root.
 		for (int i= 0; i < t.getChildCount(); i++) {
 			GrammarAST child = (GrammarAST)t.getChild(i);
 			root.addChild(dupTree(child));
 		}
 		return root;
 	}

 	public void setTreeEnclosingRuleNameDeeply(String rname) {
 		enclosingRuleName = rname;
 		if (getChildCount() == 0) return;
 		for (Object child : getChildren()) {
 			if (!(child instanceof GrammarAST)) {
 				continue;
 			}
 			GrammarAST grammarAST = (GrammarAST)child;
 			grammarAST.setTreeEnclosingRuleNameDeeply(rname);
 		}
 	}

 	String toStringList() {
 		return "";
 	}

 	/** Track start/stop token for subtree root created for a rule.
 	 *  Only works with Tree nodes.  For rules that match nothing,
 	 *  seems like this will yield start=i and stop=i-1 in a nil node.
 	 *  Might be useful info so I'll not force to be i..i.
 	 */
 	public void setTokenBoundaries(Token startToken, Token stopToken) {
 		if ( startToken!=null ) startIndex = startToken.getTokenIndex();
 		if ( stopToken!=null ) stopIndex = stopToken.getTokenIndex();
 	}

 	public GrammarAST getBlockALT(int i) {
 		if ( this.getType()!=ANTLRParser.BLOCK ) return null;
 		int alts = 0;
 		for (int j =0 ; j < getChildCount(); j++) {
 			if (getChild(j).getType() == ANTLRParser.ALT) {
 				alts++;
 			}
 			if (alts == i) {
 				return (GrammarAST)getChild(j);
 			}
 		}
 		return null;
 	}
 }
	/*
	* [The "BSD license"]
	* Copyright (c) 2010 Terence Parr
	* All rights reserved.
	*
	* Redistribution and use in source and binary forms, with or without
	* modification, are permitted provided that the following conditions
	* are met:
	* 1. Redistributions of source code must retain the above copyright
	* notice, this list of conditions and the following disclaimer.
	* 2. Redistributions in binary form must reproduce the above copyright
	* notice, this list of conditions and the following disclaimer in the
	* documentation and/or other materials provided with the distribution.
	* 3. The name of the author may not be used to endorse or promote products
	* derived from this software without specific prior written permission.
	*
	* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
	* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
	* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
	* IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
	* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
	* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
	* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
	* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
	* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
	* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
	*/
	package org.antlr.tool;

	import org.antlr.analysis.DFA;
	import org.antlr.analysis.NFAState;
	import org.antlr.grammar.v3.ANTLRParser;
	import org.antlr.misc.IntSet;
	import org.antlr.misc.Interval;
	import org.antlr.runtime.CommonToken;
	import org.antlr.runtime.Token;
	import org.antlr.runtime.TokenSource;
	import org.antlr.runtime.tree.CommonTree;
	import org.antlr.runtime.tree.Tree;
	import org.antlr.runtime.tree.TreeAdaptor;
	import org.stringtemplate.v4.ST;
	import org.omg.PortableInterceptor.ORBInitInfoPackage.DuplicateName;

	import java.util.*;

	/** Grammars are first converted to ASTs using this class and then are
	* converted to NFAs via a tree walker.
	*
	* The reader may notice that I have made a very non-OO decision in this
	* class to track variables for many different kinds of nodes. It wastes
	* space for nodes that don't need the values and OO principles cry out
	* for a new class type for each kind of node in my tree. I am doing this
	* on purpose for a variety of reasons. I don't like using the type
	* system for different node types; it yields too many damn class files
	* which I hate. Perhaps if I put them all in one file. Most importantly
	* though I hate all the type casting that would have to go on. I would
	* have all sorts of extra work to do. Ick. Anyway, I'm doing all this
	* on purpose, not out of ignorance. ;)
	*/
	public class GrammarAST extends CommonTree {
	static int count = 0;

	public int ID = ++count;

	private String textOverride;

	public String enclosingRuleName;

	/** If this is a decision node, what is the lookahead DFA? */
	public DFA lookaheadDFA = null;

	/** What NFA start state was built from this node? */
	public NFAState NFAStartState = null;

	/** This is used for TREE_BEGIN nodes to point into
	* the NFA. TREE_BEGINs point at left edge of DOWN for LOOK computation
	* purposes (Nullable tree child list needs special code gen when matching).
	*/
	public NFAState NFATreeDownState = null;

	/** Rule ref nodes, token refs, set, and NOT set refs need to track their
	* location in the generated NFA so that local FOLLOW sets can be
	* computed during code gen for automatic error recovery.
	*/
	public NFAState followingNFAState = null;

	/** If this is a SET node, what are the elements? */
	protected IntSet setValue = null;

	/** If this is a BLOCK node, track options here */
	protected Map<String,Object> blockOptions;

	/** If this is a BLOCK node for a rewrite rule, track referenced
	* elements here. Don't track elements in nested subrules.
	*/
	public Set<GrammarAST> rewriteRefsShallow;

	/* If REWRITE node, track EVERY element and label ref to right of ->
	* for this rewrite rule. There could be multiple of these per
	* rule:
	*
	* a : ( ... -> ... \| ... -> ... ) -> ... ;
	*
	* We may need a list of all refs to do definitions for whole rewrite
	* later.
	*
	* If BLOCK then tracks every element at that level and below.
	*/
	public Set<GrammarAST> rewriteRefsDeep;

	public Map<String,Object> terminalOptions;

	/** if this is an ACTION node, this is the outermost enclosing
	* alt num in rule. For actions, define.g sets these (used to
	* be codegen.g). We need these set so we can examine actions
	* early, before code gen, for refs to rule predefined properties
	* and rule labels. For most part define.g sets outerAltNum, but
	* codegen.g does the ones for %foo(a={$ID.text}) type refs as
	* the {$ID...} is not seen as an action until code gen pulls apart.
	*/
	public int outerAltNum;

	/** if this is a TOKEN_REF or RULE_REF node, this is the code ST
	* generated for this node. We need to update it later to add
	* a label if someone does $tokenref or $ruleref in an action.
	*/
	public ST code;

	/**
	*
	* @return
	*/
	public Map<String, Object> getBlockOptions() {
	return blockOptions;
	}

	/**
	*
	* @param blockOptions
	*/
	public void setBlockOptions(Map<String, Object> blockOptions) {
	this.blockOptions = blockOptions;
	}

	public GrammarAST() {;}

	public GrammarAST(int t, String txt) {
	initialize(t,txt);
	}

	public GrammarAST(Token token) {
	initialize(token);
	}

	public void initialize(int i, String s) {
	token = new CommonToken(i,s);
	token.setTokenIndex(-1);
	}

	public void initialize(Tree ast) {
	GrammarAST t = ((GrammarAST)ast);
	this.startIndex = t.startIndex;
	this.stopIndex = t.stopIndex;
	this.token = t.token;
	this.enclosingRuleName = t.enclosingRuleName;
	this.setValue = t.setValue;
	this.blockOptions = t.blockOptions;
	this.outerAltNum = t.outerAltNum;
	}

	public void initialize(Token token) {
	this.token = token;
	if ( token!=null ) {
	startIndex = token.getTokenIndex();
	stopIndex = startIndex;
	}
	}

	public DFA getLookaheadDFA() {
	return lookaheadDFA;
	}

	public void setLookaheadDFA(DFA lookaheadDFA) {
	this.lookaheadDFA = lookaheadDFA;
	}

	public NFAState getNFAStartState() {
	return NFAStartState;
	}

	public void setNFAStartState(NFAState nfaStartState) {
	this.NFAStartState = nfaStartState;
	}

	/** Save the option key/value pair and process it; return the key
	* or null if invalid option.
	*/
	public String setBlockOption(Grammar grammar, String key, Object value) {
	if ( blockOptions == null ) {
	blockOptions = new HashMap();
	}
	return setOption(blockOptions, Grammar.legalBlockOptions, grammar, key, value);
	}

	public String setTerminalOption(Grammar grammar, String key, Object value) {
	if ( terminalOptions == null ) {
	terminalOptions = new HashMap<String,Object>();
	}
	return setOption(terminalOptions, Grammar.legalTokenOptions, grammar, key, value);
	}

	public String setOption(Map options, Set legalOptions, Grammar grammar, String key, Object value) {
	if ( !legalOptions.contains(key) ) {
	ErrorManager.grammarError(ErrorManager.MSG_ILLEGAL_OPTION,
	grammar,
	token,
	key);
	return null;
	}
	if ( value instanceof String ) {
	String vs = (String)value;
	if ( vs.charAt(0)=='"' ) {
	value = vs.substring(1,vs.length()-1); // strip quotes
	}
	}
	if ( key.equals("k") ) {
	grammar.numberOfManualLookaheadOptions++;
	}
	if ( key.equals("backtrack") && value.toString().equals("true") ) {
	grammar.composite.getRootGrammar().atLeastOneBacktrackOption = true;
	}
	options.put(key, value);
	return key;
	}

	public Object getBlockOption(String key) {
	Object value = null;
	if ( blockOptions != null ) {
	value = blockOptions.get(key);
	}
	return value;
	}

	public void setOptions(Grammar grammar, Map options) {
	if ( options==null ) {
	this.blockOptions = null;
	return;
	}
	String[] keys = (String[])options.keySet().toArray(new String[options.size()]);
	for (String optionName : keys) {
	String stored= setBlockOption(grammar, optionName, options.get(optionName));
	if ( stored==null ) {
	options.remove(optionName);
	}
	}
	}

	@Override
	public String getText() {
	if ( textOverride!=null ) return textOverride;
	if ( token!=null ) {
	return token.getText();
	}
	return "";
	}

	public void setType(int type) {
	token.setType(type);
	}

	public void setText(String text) {
	textOverride = text; // don't alt tokens as others might see
	}

	@Override
	public int getType() {
	if ( token!=null ) {
	return token.getType();
	}
	return -1;
	}

	@Override
	public int getLine() {
	int line=0;
	if ( token!=null ) {
	line = token.getLine();
	}
	if ( line==0 ) {
	Tree child = getChild(0);
	if ( child!=null ) {
	line = child.getLine();
	}
	}
	return line;
	}

	@Override
	public int getCharPositionInLine(){
	int col=0;
	if ( token!=null ) {
	col = token.getCharPositionInLine();
	}
	if ( col==0 ) {
	Tree child = getChild(0);
	if ( child!=null ) {
	col = child.getCharPositionInLine();
	}
	}
	return col;
	}

	public void setLine(int line) {
	token.setLine(line);
	}

	public void setCharPositionInLine(int value){
	token.setCharPositionInLine(value);
	}

	public IntSet getSetValue() {
	return setValue;
	}

	public void setSetValue(IntSet setValue) {
	this.setValue = setValue;
	}

	public GrammarAST getLastChild() {
	if (getChildCount() == 0)
	return null;
	return (GrammarAST)getChild(getChildCount() - 1);
	}

	public GrammarAST getNextSibling() {
	return (GrammarAST)getParent().getChild(getChildIndex() + 1);
	}

	public GrammarAST getLastSibling() {
	Tree parent = getParent();
	if ( parent==null ) {
	return null;
	}
	return (GrammarAST)parent.getChild(parent.getChildCount() - 1);
	}


	public GrammarAST[] getChildrenAsArray() {
	return (GrammarAST[])getChildren().toArray(new GrammarAST[getChildCount()]);
	}

	private static final GrammarAST DescendantDownNode = new GrammarAST(Token.DOWN, "DOWN");
	private static final GrammarAST DescendantUpNode = new GrammarAST(Token.UP, "UP");

	public static List<Tree> descendants(Tree root){
	return descendants(root, false);
	}

	public static List<Tree> descendants(Tree root, boolean insertDownUpNodes){
	List<Tree> result = new ArrayList<Tree>();
	int count = root.getChildCount();

	if (insertDownUpNodes){
	result.add(root);
	result.add(DescendantDownNode);

	for (int i = 0 ; i < count ; i++){
	Tree child = root.getChild(i);
	for (Tree subchild : descendants(child, true))
	result.add(subchild);
	}

	result.add(DescendantUpNode);
	}else{
	result.add(root);
	for (int i = 0 ; i < count ; i++){
	Tree child = root.getChild(i);
	for (Tree subchild : descendants(child, false))
	result.add(subchild);
	}
	}

	return result;
	}

	public GrammarAST findFirstType(int ttype) {
	// check this node (the root) first
	if ( this.getType()==ttype ) {
	return this;
	}
	// else check children
	List<Tree> descendants = descendants(this);
	for (Tree child : descendants) {
	if ( child.getType()==ttype ) {
	return (GrammarAST)child;
	}
	}
	return null;
	}

	public List<GrammarAST> findAllType(int ttype) {
	List<GrammarAST> nodes = new ArrayList<GrammarAST>();
	_findAllType(ttype, nodes);
	return nodes;
	}

	public void _findAllType(int ttype, List<GrammarAST> nodes) {
	// check this node (the root) first
	if ( this.getType()==ttype ) nodes.add(this);
	// check children
	for (int i = 0; i < getChildCount(); i++){
	GrammarAST child = (GrammarAST)getChild(i);
	child._findAllType(ttype, nodes);
	}
	}

	/** Make nodes unique based upon Token so we can add them to a Set; if
	* not a GrammarAST, check type.
	*/
	@Override
	public boolean equals(Object ast) {
	if ( this == ast ) {
	return true;
	}
	if ( !(ast instanceof GrammarAST) ) {
	return this.getType() == ((Tree)ast).getType();
	}
	GrammarAST t = (GrammarAST)ast;
	return token.getLine() == t.getLine() &&
	token.getCharPositionInLine() == t.getCharPositionInLine();
	}

	/** Make nodes unique based upon Token so we can add them to a Set; if
	* not a GrammarAST, check type.
	*/
	@Override
	public int hashCode(){
	if (token == null)
	return 0;

	return token.hashCode();
	}

	/** See if tree has exact token types and structure; no text */
	public boolean hasSameTreeStructure(Tree other) {
	// check roots first.
	if (this.getType() != other.getType()) return false;
	// if roots match, do full list match test on children.
	Iterator<Tree> thisDescendants = descendants(this, true).iterator();
	Iterator<Tree> otherDescendants = descendants(other, true).iterator();
	while (thisDescendants.hasNext()) {
	if (!otherDescendants.hasNext())
	return false;
	if (thisDescendants.next().getType() != otherDescendants.next().getType())
	return false;
	}
	return !otherDescendants.hasNext();
	}

	public static GrammarAST dup(Tree t) {
	if ( t==null ) {
	return null;
	}
	GrammarAST dup_t = new GrammarAST();
	dup_t.initialize(t);
	return dup_t;
	}

	@Override
	public Tree dupNode(){
	return dup(this);
	}

	/**Duplicate a tree, assuming this is a root node of a tree--
	* duplicate that node and what's below; ignore siblings of root node.
	*/
	public static GrammarAST dupTreeNoActions(GrammarAST t, GrammarAST parent) {
	if ( t==null ) {
	return null;
	}
	GrammarAST result = (GrammarAST)t.dupNode();
	for (GrammarAST subchild : getChildrenForDupTree(t)) {
	result.addChild(dupTreeNoActions(subchild, result));
	}
	return result;
	}

	private static List<GrammarAST> getChildrenForDupTree(GrammarAST t) {
	List<GrammarAST> result = new ArrayList<GrammarAST>();
	for (int i = 0; i < t.getChildCount(); i++){
	GrammarAST child = (GrammarAST)t.getChild(i);
	int ttype = child.getType();
	if (ttype == ANTLRParser.REWRITES \|\| ttype == ANTLRParser.REWRITE \|\| ttype==ANTLRParser.ACTION) {
	continue;
	}

	if (ttype == ANTLRParser.BANG \|\| ttype == ANTLRParser.ROOT) {
	for (GrammarAST subchild : getChildrenForDupTree(child))
	result.add(subchild);
	} else {
	result.add(child);
	}
	}
	if ( result.size()==1 && result.get(0).getType()==ANTLRParser.EOA &&
	t.getType()==ANTLRParser.ALT )
	{
	// can't have an empty alt, insert epsilon
	result.add(0, new GrammarAST(ANTLRParser.EPSILON, "epsilon"));
	}

	return result;
	}

	public static GrammarAST dupTree(GrammarAST t) {
	if ( t==null ) {
	return null;
	}
	GrammarAST root = dup(t); // make copy of root
	// copy all children of root.
	for (int i= 0; i < t.getChildCount(); i++) {
	GrammarAST child = (GrammarAST)t.getChild(i);
	root.addChild(dupTree(child));
	}
	return root;
	}

	public void setTreeEnclosingRuleNameDeeply(String rname) {
	enclosingRuleName = rname;
	if (getChildCount() == 0) return;
	for (Object child : getChildren()) {
	if (!(child instanceof GrammarAST)) {
	continue;
	}
	GrammarAST grammarAST = (GrammarAST)child;
	grammarAST.setTreeEnclosingRuleNameDeeply(rname);
	}
	}

	String toStringList() {
	return "";
	}

	/** Track start/stop token for subtree root created for a rule.
	* Only works with Tree nodes. For rules that match nothing,
	* seems like this will yield start=i and stop=i-1 in a nil node.
	* Might be useful info so I'll not force to be i..i.
	*/
	public void setTokenBoundaries(Token startToken, Token stopToken) {
	if ( startToken!=null ) startIndex = startToken.getTokenIndex();
	if ( stopToken!=null ) stopIndex = stopToken.getTokenIndex();
	}

	public GrammarAST getBlockALT(int i) {
	if ( this.getType()!=ANTLRParser.BLOCK ) return null;
	int alts = 0;
	for (int j =0 ; j < getChildCount(); j++) {
	if (getChild(j).getType() == ANTLRParser.ALT) {
	alts++;
	}
	if (alts == i) {
	return (GrammarAST)getChild(j);
	}
	}
	return null;
	}
	}