antlr-3.4/tool/src/main/java/org/antlr/tool/Rule.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.NFAState;
 import org.antlr.codegen.CodeGenerator;
 import org.antlr.grammar.v3.ANTLRParser;
 import org.antlr.runtime.CommonToken;
 import org.antlr.runtime.Token;

 import java.util.*;

 /** Combine the info associated with a rule. */
 public class Rule {
 	public String name;
 	public int index;
 	public String modifier;
 	public NFAState startState;
 	public NFAState stopState;

 	/** This rule's options */
 	protected Map options;

 	public static final Set legalOptions =
 			new HashSet() {
                 {
                     add("k"); add("greedy"); add("memoize");
                     add("backtrack");
                 }
             };

 	/** The AST representing the whole rule */
 	public GrammarAST tree;

 	/** To which grammar does this belong? */
 	public Grammar grammar;

 	/** For convenience, track the argument def AST action node if any */
 	public GrammarAST argActionAST;

 	public GrammarAST EORNode;

 	/** The return values of a rule and predefined rule attributes */
 	public AttributeScope returnScope;

 	public AttributeScope parameterScope;

 	/** the attributes defined with "scope {...}" inside a rule */
 	public AttributeScope ruleScope;

 	/** A list of scope names (String) used by this rule */
 	public List useScopes;

     /** Exceptions that this rule can throw */
     public Set<String> throwsSpec;

     /** A list of all LabelElementPair attached to tokens like id=ID */
     public LinkedHashMap tokenLabels;

     /** A list of all LabelElementPair attached to tokens like x=. in tree grammar */
     public LinkedHashMap wildcardTreeLabels;

     /** A list of all LabelElementPair attached to tokens like x+=. in tree grammar */
     public LinkedHashMap wildcardTreeListLabels;

 	/** A list of all LabelElementPair attached to single char literals like x='a' */
 	public LinkedHashMap charLabels;

 	/** A list of all LabelElementPair attached to rule references like f=field */
 	public LinkedHashMap ruleLabels;

 	/** A list of all Token list LabelElementPair like ids+=ID */
 	public LinkedHashMap tokenListLabels;

 	/** A list of all rule ref list LabelElementPair like ids+=expr */
 	public LinkedHashMap ruleListLabels;

 	/** All labels go in here (plus being split per the above lists) to
 	 *  catch dup label and label type mismatches.
 	 */
 	protected Map<String, Grammar.LabelElementPair> labelNameSpace =
 		new HashMap<String, Grammar.LabelElementPair>();

 	/** Map a name to an action for this rule.  Currently init is only
 	 *  one we use, but we can add more in future.
 	 *  The code generator will use this to fill holes in the rule template.
 	 *  I track the AST node for the action in case I need the line number
 	 *  for errors.  A better name is probably namedActions, but I don't
 	 *  want everyone to have to change their code gen templates now.
 	 */
 	protected Map<String, GrammarAST> actions =
 		new HashMap<String, GrammarAST>();

 	/** Track all executable actions other than named actions like @init.
 	 *  Also tracks exception handlers, predicates, and rewrite rewrites.
 	 *  We need to examine these actions before code generation so
 	 *  that we can detect refs to $rule.attr etc...
 	 */
 	protected List<GrammarAST> inlineActions = new ArrayList<GrammarAST>();

 	public int numberOfAlts;

 	/** Each alt has a Map<tokenRefName,List<tokenRefAST>>; range 1..numberOfAlts.
 	 *  So, if there are 3 ID refs in a rule's alt number 2, you'll have
 	 *  altToTokenRef[2].get("ID").size()==3.  This is used to see if $ID is ok.
 	 *  There must be only one ID reference in the alt for $ID to be ok in
 	 *  an action--must be unique.
 	 *
 	 *  This also tracks '+' and "int" literal token references
 	 *  (if not in LEXER).
 	 *
 	 *  Rewrite rules force tracking of all tokens.
 	 */
 	protected Map<String, List<GrammarAST>>[] altToTokenRefMap;

 	/** Each alt has a Map<ruleRefName,List<ruleRefAST>>; range 1..numberOfAlts
 	 *  So, if there are 3 expr refs in a rule's alt number 2, you'll have
 	 *  altToRuleRef[2].get("expr").size()==3.  This is used to see if $expr is ok.
 	 *  There must be only one expr reference in the alt for $expr to be ok in
 	 *  an action--must be unique.
 	 *
 	 *  Rewrite rules force tracking of all rule result ASTs. 1..n
 	 */
 	protected Map<String, List<GrammarAST>>[] altToRuleRefMap;

 	/** Do not generate start, stop etc... in a return value struct unless
 	 *  somebody references $r.start somewhere.
 	 */
 	public boolean referencedPredefinedRuleAttributes = false;

 	public boolean isSynPred = false;

 	public boolean imported = false;

 	public Rule(Grammar grammar,
 				String ruleName,
 				int ruleIndex,
 				int numberOfAlts)
 	{
 		this.name = ruleName;
 		this.index = ruleIndex;
 		this.numberOfAlts = numberOfAlts;
 		this.grammar = grammar;
 		throwsSpec = new HashSet<String>();
 		altToTokenRefMap = new Map[numberOfAlts+1];
 		altToRuleRefMap = new Map[numberOfAlts+1];
 		for (int alt=1; alt<=numberOfAlts; alt++) {
 			altToTokenRefMap[alt] = new HashMap<String, List<GrammarAST>>();
 			altToRuleRefMap[alt] = new HashMap<String, List<GrammarAST>>();
 		}
 	}

 	public static int getRuleType(String ruleName){
 		if (ruleName == null || ruleName.length() == 0)
 			throw new IllegalArgumentException("The specified rule name is not valid.");
 		return Character.isUpperCase(ruleName.charAt(0)) ? Grammar.LEXER : Grammar.PARSER;
 	}

 	public void defineLabel(Token label, GrammarAST elementRef, int type) {
 		Grammar.LabelElementPair pair = grammar.new LabelElementPair(label,elementRef);
 		pair.type = type;
 		labelNameSpace.put(label.getText(), pair);
 		switch ( type ) {
             case Grammar.TOKEN_LABEL :
                 if ( tokenLabels==null ) tokenLabels = new LinkedHashMap();
                 tokenLabels.put(label.getText(), pair);
                 break;
             case Grammar.WILDCARD_TREE_LABEL :
                 if ( wildcardTreeLabels==null ) wildcardTreeLabels = new LinkedHashMap();
                 wildcardTreeLabels.put(label.getText(), pair);
                 break;
             case Grammar.WILDCARD_TREE_LIST_LABEL :
                 if ( wildcardTreeListLabels==null ) wildcardTreeListLabels = new LinkedHashMap();
                 wildcardTreeListLabels.put(label.getText(), pair);
                 break;
 			case Grammar.RULE_LABEL :
 				if ( ruleLabels==null ) ruleLabels = new LinkedHashMap();
 				ruleLabels.put(label.getText(), pair);
 				break;
 			case Grammar.TOKEN_LIST_LABEL :
 				if ( tokenListLabels==null ) tokenListLabels = new LinkedHashMap();
 				tokenListLabels.put(label.getText(), pair);
 				break;
 			case Grammar.RULE_LIST_LABEL :
 				if ( ruleListLabels==null ) ruleListLabels = new LinkedHashMap();
 				ruleListLabels.put(label.getText(), pair);
 				break;
 			case Grammar.CHAR_LABEL :
 				if ( charLabels==null ) charLabels = new LinkedHashMap();
 				charLabels.put(label.getText(), pair);
 				break;
 		}
 	}

 	public Grammar.LabelElementPair getLabel(String name) {
 		return (Grammar.LabelElementPair)labelNameSpace.get(name);
 	}

 	public Grammar.LabelElementPair getTokenLabel(String name) {
 		Grammar.LabelElementPair pair = null;
 		if ( tokenLabels!=null ) {
 			return (Grammar.LabelElementPair)tokenLabels.get(name);
 		}
 		return pair;
 	}

 	public Map getRuleLabels() {
 		return ruleLabels;
 	}

 	public Map getRuleListLabels() {
 		return ruleListLabels;
 	}

 	public Grammar.LabelElementPair getRuleLabel(String name) {
 		Grammar.LabelElementPair pair = null;
 		if ( ruleLabels!=null ) {
 			return (Grammar.LabelElementPair)ruleLabels.get(name);
 		}
 		return pair;
 	}

 	public Grammar.LabelElementPair getTokenListLabel(String name) {
 		Grammar.LabelElementPair pair = null;
 		if ( tokenListLabels!=null ) {
 			return (Grammar.LabelElementPair)tokenListLabels.get(name);
 		}
 		return pair;
 	}

 	public Grammar.LabelElementPair getRuleListLabel(String name) {
 		Grammar.LabelElementPair pair = null;
 		if ( ruleListLabels!=null ) {
 			return (Grammar.LabelElementPair)ruleListLabels.get(name);
 		}
 		return pair;
 	}

 	/** Track a token ID or literal like '+' and "void" as having been referenced
 	 *  somewhere within the alts (not rewrite sections) of a rule.
 	 *
 	 *  This differs from Grammar.altReferencesTokenID(), which tracks all
 	 *  token IDs to check for token IDs without corresponding lexer rules.
 	 */
 	public void trackTokenReferenceInAlt(GrammarAST refAST, int outerAltNum) {
 		List refs = (List)altToTokenRefMap[outerAltNum].get(refAST.getText());
 		if ( refs==null ) {
 			refs = new ArrayList();
 			altToTokenRefMap[outerAltNum].put(refAST.getText(), refs);
 		}
 		refs.add(refAST);
 	}

 	public List getTokenRefsInAlt(String ref, int outerAltNum) {
 		if ( altToTokenRefMap[outerAltNum]!=null ) {
 			List tokenRefASTs = (List)altToTokenRefMap[outerAltNum].get(ref);
 			return tokenRefASTs;
 		}
 		return null;
 	}

 	public void trackRuleReferenceInAlt(GrammarAST refAST, int outerAltNum) {
 		List refs = (List)altToRuleRefMap[outerAltNum].get(refAST.getText());
 		if ( refs==null ) {
 			refs = new ArrayList();
 			altToRuleRefMap[outerAltNum].put(refAST.getText(), refs);
 		}
 		refs.add(refAST);
 	}

 	public List getRuleRefsInAlt(String ref, int outerAltNum) {
 		if ( altToRuleRefMap[outerAltNum]!=null ) {
 			List ruleRefASTs = (List)altToRuleRefMap[outerAltNum].get(ref);
 			return ruleRefASTs;
 		}
 		return null;
 	}

 	public Set getTokenRefsInAlt(int altNum) {
 		return altToTokenRefMap[altNum].keySet();
 	}

 	/** For use with rewrite rules, we must track all tokens matched on the
 	 *  left-hand-side; so we need Lists.  This is a unique list of all
 	 *  token types for which the rule needs a list of tokens.  This
 	 *  is called from the rule template not directly by the code generator.
 	 */
 	public Set getAllTokenRefsInAltsWithRewrites() {
 		String output = (String)grammar.getOption("output");
 		Set<String> tokens = new HashSet<String>();
 		if ( output==null || !output.equals("AST") ) {
 			// return nothing if not generating trees; i.e., don't do for templates
 			return tokens;
 		}
 		//System.out.println("blk "+tree.findFirstType(ANTLRParser.BLOCK).toStringTree());
 		for (int i = 1; i <= numberOfAlts; i++) {
 			if ( hasRewrite(i) ) {
 				Map<String, List<GrammarAST>> m = altToTokenRefMap[i];
 				for (String tokenName : m.keySet()) {
 					// convert token name like ID to ID, "void" to 31
 					int ttype = grammar.getTokenType(tokenName);
 					String label = grammar.generator.getTokenTypeAsTargetLabel(ttype);
 					tokens.add(label);
 				}
 			}
 		}
 		return tokens;
 	}

 	public Set getRuleRefsInAlt(int outerAltNum) {
 		return altToRuleRefMap[outerAltNum].keySet();
 	}

 	/** For use with rewrite rules, we must track all rule AST results on the
 	 *  left-hand-side; so we need Lists.  This is a unique list of all
 	 *  rule results for which the rule needs a list of results.
 	 */
 	public Set getAllRuleRefsInAltsWithRewrites() {
 		Set rules = new HashSet();
 		for (int i = 1; i <= numberOfAlts; i++) {
 			if ( hasRewrite(i) ) {
 				Map m = altToRuleRefMap[i];
 				rules.addAll(m.keySet());
 			}
 		}
 		return rules;
 	}

 	public List<GrammarAST> getInlineActions() {
 		return inlineActions;
 	}

 	public boolean hasRewrite(int i) {
 		GrammarAST blk = tree.findFirstType(ANTLRParser.BLOCK);
 		GrammarAST alt = blk.getBlockALT(i);
 		GrammarAST rew = (GrammarAST)alt.getNextSibling();
 		if ( rew!=null && rew.getType()==ANTLRParser.REWRITES ) return true;
 		if ( alt.findFirstType(ANTLRParser.REWRITES)!=null ) return true;
 		return false;
 	}

 	/** Return the scope containing name */
 	public AttributeScope getAttributeScope(String name) {
 		AttributeScope scope = getLocalAttributeScope(name);
 		if ( scope!=null ) {
 			return scope;
 		}
 		if ( ruleScope!=null && ruleScope.getAttribute(name)!=null ) {
 			scope = ruleScope;
 		}
 		return scope;
 	}

 	/** Get the arg, return value, or predefined property for this rule */
 	public AttributeScope getLocalAttributeScope(String name) {
 		AttributeScope scope = null;
 		if ( returnScope!=null && returnScope.getAttribute(name)!=null ) {
 			scope = returnScope;
 		}
 		else if ( parameterScope!=null && parameterScope.getAttribute(name)!=null ) {
 			scope = parameterScope;
 		}
 		else {
 			AttributeScope rulePropertiesScope =
 				RuleLabelScope.grammarTypeToRulePropertiesScope[grammar.type];
 			if ( rulePropertiesScope.getAttribute(name)!=null ) {
 				scope = rulePropertiesScope;
 			}
 		}
 		return scope;
 	}

 	/** For references to tokens rather than by label such as $ID, we
 	 *  need to get the existing label for the ID ref or create a new
 	 *  one.
 	 */
 	public String getElementLabel(String refdSymbol,
 								  int outerAltNum,
 								  CodeGenerator generator)
 	{
 		GrammarAST uniqueRefAST;
 		if ( grammar.type != Grammar.LEXER &&
 			 Character.isUpperCase(refdSymbol.charAt(0)) )
 		{
 			// symbol is a token
 			List tokenRefs = getTokenRefsInAlt(refdSymbol, outerAltNum);
 			uniqueRefAST = (GrammarAST)tokenRefs.get(0);
 		}
 		else {
 			// symbol is a rule
 			List ruleRefs = getRuleRefsInAlt(refdSymbol, outerAltNum);
 			uniqueRefAST = (GrammarAST)ruleRefs.get(0);
 		}
 		if ( uniqueRefAST.code==null ) {
 			// no code?  must not have gen'd yet; forward ref
 			return null;
 		}
 		String labelName = null;
 		String existingLabelName =
 			(String)uniqueRefAST.code.getAttribute("label");
 		// reuse any label or list label if it exists
 		if ( existingLabelName!=null ) {
 			labelName = existingLabelName;
 		}
 		else {
 			// else create new label
 			labelName = generator.createUniqueLabel(refdSymbol);
 			CommonToken label = new CommonToken(ANTLRParser.ID, labelName);
 			if ( grammar.type != Grammar.LEXER &&
 				 Character.isUpperCase(refdSymbol.charAt(0)) )
 			{
 				grammar.defineTokenRefLabel(name, label, uniqueRefAST);
 			}
 			else {
 				grammar.defineRuleRefLabel(name, label, uniqueRefAST);
 			}
 			uniqueRefAST.code.add("label", labelName);
 		}
 		return labelName;
 	}

 	/** If a rule has no user-defined return values and nobody references
 	 *  it's start/stop (predefined attributes), then there is no need to
 	 *  define a struct; otherwise for now we assume a struct.  A rule also
 	 *  has multiple return values if you are building trees or templates.
 	 */
 	public boolean getHasMultipleReturnValues() {
 		return
 			referencedPredefinedRuleAttributes || grammar.buildAST() ||
 			grammar.buildTemplate() ||
 			(returnScope!=null && returnScope.attributes.size()>1);
 	}

 	public boolean getHasSingleReturnValue() {
 		return
 			!(referencedPredefinedRuleAttributes || grammar.buildAST() ||
 			  grammar.buildTemplate()) &&
 									   (returnScope!=null && returnScope.attributes.size()==1);
 	}

 	public boolean getHasReturnValue() {
 		return
 			referencedPredefinedRuleAttributes || grammar.buildAST() ||
 			grammar.buildTemplate() ||
 			(returnScope!=null && returnScope.attributes.size()>0);
 	}

 	public String getSingleValueReturnType() {
 		if ( returnScope!=null && returnScope.attributes.size()==1 ) {
 			Collection retvalAttrs = returnScope.attributes.values();
 			Object[] javaSucks = retvalAttrs.toArray();
 			return ((Attribute)javaSucks[0]).type;
 		}
 		return null;
 	}

 	public String getSingleValueReturnName() {
 		if ( returnScope!=null && returnScope.attributes.size()==1 ) {
 			Collection retvalAttrs = returnScope.attributes.values();
 			Object[] javaSucks = retvalAttrs.toArray();
 			return ((Attribute)javaSucks[0]).name;
 		}
 		return null;
 	}

 	/** Given @scope::name {action} define it for this grammar.  Later,
 	 *  the code generator will ask for the actions table.
 	 */
 	public void defineNamedAction(GrammarAST ampersandAST,
 								  GrammarAST nameAST,
 								  GrammarAST actionAST)
 	{
 		//System.out.println("rule @"+nameAST.getText()+"{"+actionAST.getText()+"}");
 		String actionName = nameAST.getText();
 		GrammarAST a = (GrammarAST)actions.get(actionName);
 		if ( a!=null ) {
 			ErrorManager.grammarError(
 				ErrorManager.MSG_ACTION_REDEFINITION,grammar,
 				nameAST.getToken(),nameAST.getText());
 		}
 		else {
 			actions.put(actionName,actionAST);
 		}
 	}

 	public void trackInlineAction(GrammarAST actionAST) {
 		inlineActions.add(actionAST);
 	}

 	public Map<String, GrammarAST> getActions() {
 		return actions;
 	}

 	public void setActions(Map<String, GrammarAST> actions) {
 		this.actions = actions;
 	}

 	/** Save the option key/value pair and process it; return the key
 	 *  or null if invalid option.
 	 */
 	public String setOption(String key, Object value, Token optionsStartToken) {
 		if ( !legalOptions.contains(key) ) {
 			ErrorManager.grammarError(ErrorManager.MSG_ILLEGAL_OPTION,
 									  grammar,
 									  optionsStartToken,
 									  key);
 			return null;
 		}
 		if ( options==null ) {
 			options = new HashMap();
 		}
         if ( key.equals("memoize") && value.toString().equals("true") ) {
             grammar.atLeastOneRuleMemoizes = true;
         }
         if ( key.equals("backtrack") && value.toString().equals("true") ) {
             grammar.composite.getRootGrammar().atLeastOneBacktrackOption = true;
         }
 		if ( key.equals("k") ) {
 			grammar.numberOfManualLookaheadOptions++;
 		}
 		 options.put(key, value);
 		return key;
 	}

 	public void setOptions(Map options, Token optionsStartToken) {
 		if ( options==null ) {
 			this.options = null;
 			return;
 		}
 		Set keys = options.keySet();
 		for (Iterator it = keys.iterator(); it.hasNext();) {
 			String optionName = (String) it.next();
 			Object optionValue = options.get(optionName);
 			String stored=setOption(optionName, optionValue, optionsStartToken);
 			if ( stored==null ) {
 				it.remove();
 			}
 		}
 	}

 	/** Used during grammar imports to see if sets of rules intersect... This
 	 *  method and hashCode use the String name as the key for Rule objects.
 	public boolean equals(Object other) {
 		return this.name.equals(((Rule)other).name);
 	}
 	 */

 	/** Used during grammar imports to see if sets of rules intersect...
 	public int hashCode() {
 		return name.hashCode();
 	}
 	 * */

 	public String toString() { // used for testing
 		return "["+grammar.name+"."+name+",index="+index+",line="+tree.getToken().getLine()+"]";
 	}
 }
	/*
	* [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.NFAState;
	import org.antlr.codegen.CodeGenerator;
	import org.antlr.grammar.v3.ANTLRParser;
	import org.antlr.runtime.CommonToken;
	import org.antlr.runtime.Token;

	import java.util.*;

	/** Combine the info associated with a rule. */
	public class Rule {
	public String name;
	public int index;
	public String modifier;
	public NFAState startState;
	public NFAState stopState;

	/** This rule's options */
	protected Map options;

	public static final Set legalOptions =
	new HashSet() {
	{
	add("k"); add("greedy"); add("memoize");
	add("backtrack");
	}
	};

	/** The AST representing the whole rule */
	public GrammarAST tree;

	/** To which grammar does this belong? */
	public Grammar grammar;

	/** For convenience, track the argument def AST action node if any */
	public GrammarAST argActionAST;

	public GrammarAST EORNode;

	/** The return values of a rule and predefined rule attributes */
	public AttributeScope returnScope;

	public AttributeScope parameterScope;

	/** the attributes defined with "scope {...}" inside a rule */
	public AttributeScope ruleScope;

	/** A list of scope names (String) used by this rule */
	public List useScopes;

	/** Exceptions that this rule can throw */
	public Set<String> throwsSpec;

	/** A list of all LabelElementPair attached to tokens like id=ID */
	public LinkedHashMap tokenLabels;

	/** A list of all LabelElementPair attached to tokens like x=. in tree grammar */
	public LinkedHashMap wildcardTreeLabels;

	/** A list of all LabelElementPair attached to tokens like x+=. in tree grammar */
	public LinkedHashMap wildcardTreeListLabels;

	/** A list of all LabelElementPair attached to single char literals like x='a' */
	public LinkedHashMap charLabels;

	/** A list of all LabelElementPair attached to rule references like f=field */
	public LinkedHashMap ruleLabels;

	/** A list of all Token list LabelElementPair like ids+=ID */
	public LinkedHashMap tokenListLabels;

	/** A list of all rule ref list LabelElementPair like ids+=expr */
	public LinkedHashMap ruleListLabels;

	/** All labels go in here (plus being split per the above lists) to
	* catch dup label and label type mismatches.
	*/
	protected Map<String, Grammar.LabelElementPair> labelNameSpace =
	new HashMap<String, Grammar.LabelElementPair>();

	/** Map a name to an action for this rule. Currently init is only
	* one we use, but we can add more in future.
	* The code generator will use this to fill holes in the rule template.
	* I track the AST node for the action in case I need the line number
	* for errors. A better name is probably namedActions, but I don't
	* want everyone to have to change their code gen templates now.
	*/
	protected Map<String, GrammarAST> actions =
	new HashMap<String, GrammarAST>();

	/** Track all executable actions other than named actions like @init.
	* Also tracks exception handlers, predicates, and rewrite rewrites.
	* We need to examine these actions before code generation so
	* that we can detect refs to $rule.attr etc...
	*/
	protected List<GrammarAST> inlineActions = new ArrayList<GrammarAST>();

	public int numberOfAlts;

	/** Each alt has a Map<tokenRefName,List<tokenRefAST>>; range 1..numberOfAlts.
	* So, if there are 3 ID refs in a rule's alt number 2, you'll have
	* altToTokenRef[2].get("ID").size()==3. This is used to see if $ID is ok.
	* There must be only one ID reference in the alt for $ID to be ok in
	* an action--must be unique.
	*
	* This also tracks '+' and "int" literal token references
	* (if not in LEXER).
	*
	* Rewrite rules force tracking of all tokens.
	*/
	protected Map<String, List<GrammarAST>>[] altToTokenRefMap;

	/** Each alt has a Map<ruleRefName,List<ruleRefAST>>; range 1..numberOfAlts
	* So, if there are 3 expr refs in a rule's alt number 2, you'll have
	* altToRuleRef[2].get("expr").size()==3. This is used to see if $expr is ok.
	* There must be only one expr reference in the alt for $expr to be ok in
	* an action--must be unique.
	*
	* Rewrite rules force tracking of all rule result ASTs. 1..n
	*/
	protected Map<String, List<GrammarAST>>[] altToRuleRefMap;

	/** Do not generate start, stop etc... in a return value struct unless
	* somebody references $r.start somewhere.
	*/
	public boolean referencedPredefinedRuleAttributes = false;

	public boolean isSynPred = false;

	public boolean imported = false;

	public Rule(Grammar grammar,
	String ruleName,
	int ruleIndex,
	int numberOfAlts)
	{
	this.name = ruleName;
	this.index = ruleIndex;
	this.numberOfAlts = numberOfAlts;
	this.grammar = grammar;
	throwsSpec = new HashSet<String>();
	altToTokenRefMap = new Map[numberOfAlts+1];
	altToRuleRefMap = new Map[numberOfAlts+1];
	for (int alt=1; alt<=numberOfAlts; alt++) {
	altToTokenRefMap[alt] = new HashMap<String, List<GrammarAST>>();
	altToRuleRefMap[alt] = new HashMap<String, List<GrammarAST>>();
	}
	}

	public static int getRuleType(String ruleName){
	if (ruleName == null \|\| ruleName.length() == 0)
	throw new IllegalArgumentException("The specified rule name is not valid.");
	return Character.isUpperCase(ruleName.charAt(0)) ? Grammar.LEXER : Grammar.PARSER;
	}

	public void defineLabel(Token label, GrammarAST elementRef, int type) {
	Grammar.LabelElementPair pair = grammar.new LabelElementPair(label,elementRef);
	pair.type = type;
	labelNameSpace.put(label.getText(), pair);
	switch ( type ) {
	case Grammar.TOKEN_LABEL :
	if ( tokenLabels==null ) tokenLabels = new LinkedHashMap();
	tokenLabels.put(label.getText(), pair);
	break;
	case Grammar.WILDCARD_TREE_LABEL :
	if ( wildcardTreeLabels==null ) wildcardTreeLabels = new LinkedHashMap();
	wildcardTreeLabels.put(label.getText(), pair);
	break;
	case Grammar.WILDCARD_TREE_LIST_LABEL :
	if ( wildcardTreeListLabels==null ) wildcardTreeListLabels = new LinkedHashMap();
	wildcardTreeListLabels.put(label.getText(), pair);
	break;
	case Grammar.RULE_LABEL :
	if ( ruleLabels==null ) ruleLabels = new LinkedHashMap();
	ruleLabels.put(label.getText(), pair);
	break;
	case Grammar.TOKEN_LIST_LABEL :
	if ( tokenListLabels==null ) tokenListLabels = new LinkedHashMap();
	tokenListLabels.put(label.getText(), pair);
	break;
	case Grammar.RULE_LIST_LABEL :
	if ( ruleListLabels==null ) ruleListLabels = new LinkedHashMap();
	ruleListLabels.put(label.getText(), pair);
	break;
	case Grammar.CHAR_LABEL :
	if ( charLabels==null ) charLabels = new LinkedHashMap();
	charLabels.put(label.getText(), pair);
	break;
	}
	}

	public Grammar.LabelElementPair getLabel(String name) {
	return (Grammar.LabelElementPair)labelNameSpace.get(name);
	}

	public Grammar.LabelElementPair getTokenLabel(String name) {
	Grammar.LabelElementPair pair = null;
	if ( tokenLabels!=null ) {
	return (Grammar.LabelElementPair)tokenLabels.get(name);
	}
	return pair;
	}

	public Map getRuleLabels() {
	return ruleLabels;
	}

	public Map getRuleListLabels() {
	return ruleListLabels;
	}

	public Grammar.LabelElementPair getRuleLabel(String name) {
	Grammar.LabelElementPair pair = null;
	if ( ruleLabels!=null ) {
	return (Grammar.LabelElementPair)ruleLabels.get(name);
	}
	return pair;
	}

	public Grammar.LabelElementPair getTokenListLabel(String name) {
	Grammar.LabelElementPair pair = null;
	if ( tokenListLabels!=null ) {
	return (Grammar.LabelElementPair)tokenListLabels.get(name);
	}
	return pair;
	}

	public Grammar.LabelElementPair getRuleListLabel(String name) {
	Grammar.LabelElementPair pair = null;
	if ( ruleListLabels!=null ) {
	return (Grammar.LabelElementPair)ruleListLabels.get(name);
	}
	return pair;
	}

	/** Track a token ID or literal like '+' and "void" as having been referenced
	* somewhere within the alts (not rewrite sections) of a rule.
	*
	* This differs from Grammar.altReferencesTokenID(), which tracks all
	* token IDs to check for token IDs without corresponding lexer rules.
	*/
	public void trackTokenReferenceInAlt(GrammarAST refAST, int outerAltNum) {
	List refs = (List)altToTokenRefMap[outerAltNum].get(refAST.getText());
	if ( refs==null ) {
	refs = new ArrayList();
	altToTokenRefMap[outerAltNum].put(refAST.getText(), refs);
	}
	refs.add(refAST);
	}

	public List getTokenRefsInAlt(String ref, int outerAltNum) {
	if ( altToTokenRefMap[outerAltNum]!=null ) {
	List tokenRefASTs = (List)altToTokenRefMap[outerAltNum].get(ref);
	return tokenRefASTs;
	}
	return null;
	}

	public void trackRuleReferenceInAlt(GrammarAST refAST, int outerAltNum) {
	List refs = (List)altToRuleRefMap[outerAltNum].get(refAST.getText());
	if ( refs==null ) {
	refs = new ArrayList();
	altToRuleRefMap[outerAltNum].put(refAST.getText(), refs);
	}
	refs.add(refAST);
	}

	public List getRuleRefsInAlt(String ref, int outerAltNum) {
	if ( altToRuleRefMap[outerAltNum]!=null ) {
	List ruleRefASTs = (List)altToRuleRefMap[outerAltNum].get(ref);
	return ruleRefASTs;
	}
	return null;
	}

	public Set getTokenRefsInAlt(int altNum) {
	return altToTokenRefMap[altNum].keySet();
	}

	/** For use with rewrite rules, we must track all tokens matched on the
	* left-hand-side; so we need Lists. This is a unique list of all
	* token types for which the rule needs a list of tokens. This
	* is called from the rule template not directly by the code generator.
	*/
	public Set getAllTokenRefsInAltsWithRewrites() {
	String output = (String)grammar.getOption("output");
	Set<String> tokens = new HashSet<String>();
	if ( output==null \|\| !output.equals("AST") ) {
	// return nothing if not generating trees; i.e., don't do for templates
	return tokens;
	}
	//System.out.println("blk "+tree.findFirstType(ANTLRParser.BLOCK).toStringTree());
	for (int i = 1; i <= numberOfAlts; i++) {
	if ( hasRewrite(i) ) {
	Map<String, List<GrammarAST>> m = altToTokenRefMap[i];
	for (String tokenName : m.keySet()) {
	// convert token name like ID to ID, "void" to 31
	int ttype = grammar.getTokenType(tokenName);
	String label = grammar.generator.getTokenTypeAsTargetLabel(ttype);
	tokens.add(label);
	}
	}
	}
	return tokens;
	}

	public Set getRuleRefsInAlt(int outerAltNum) {
	return altToRuleRefMap[outerAltNum].keySet();
	}

	/** For use with rewrite rules, we must track all rule AST results on the
	* left-hand-side; so we need Lists. This is a unique list of all
	* rule results for which the rule needs a list of results.
	*/
	public Set getAllRuleRefsInAltsWithRewrites() {
	Set rules = new HashSet();
	for (int i = 1; i <= numberOfAlts; i++) {
	if ( hasRewrite(i) ) {
	Map m = altToRuleRefMap[i];
	rules.addAll(m.keySet());
	}
	}
	return rules;
	}

	public List<GrammarAST> getInlineActions() {
	return inlineActions;
	}

	public boolean hasRewrite(int i) {
	GrammarAST blk = tree.findFirstType(ANTLRParser.BLOCK);
	GrammarAST alt = blk.getBlockALT(i);
	GrammarAST rew = (GrammarAST)alt.getNextSibling();
	if ( rew!=null && rew.getType()==ANTLRParser.REWRITES ) return true;
	if ( alt.findFirstType(ANTLRParser.REWRITES)!=null ) return true;
	return false;
	}

	/** Return the scope containing name */
	public AttributeScope getAttributeScope(String name) {
	AttributeScope scope = getLocalAttributeScope(name);
	if ( scope!=null ) {
	return scope;
	}
	if ( ruleScope!=null && ruleScope.getAttribute(name)!=null ) {
	scope = ruleScope;
	}
	return scope;
	}

	/** Get the arg, return value, or predefined property for this rule */
	public AttributeScope getLocalAttributeScope(String name) {
	AttributeScope scope = null;
	if ( returnScope!=null && returnScope.getAttribute(name)!=null ) {
	scope = returnScope;
	}
	else if ( parameterScope!=null && parameterScope.getAttribute(name)!=null ) {
	scope = parameterScope;
	}
	else {
	AttributeScope rulePropertiesScope =
	RuleLabelScope.grammarTypeToRulePropertiesScope[grammar.type];
	if ( rulePropertiesScope.getAttribute(name)!=null ) {
	scope = rulePropertiesScope;
	}
	}
	return scope;
	}

	/** For references to tokens rather than by label such as $ID, we
	* need to get the existing label for the ID ref or create a new
	* one.
	*/
	public String getElementLabel(String refdSymbol,
	int outerAltNum,
	CodeGenerator generator)
	{
	GrammarAST uniqueRefAST;
	if ( grammar.type != Grammar.LEXER &&
	Character.isUpperCase(refdSymbol.charAt(0)) )
	{
	// symbol is a token
	List tokenRefs = getTokenRefsInAlt(refdSymbol, outerAltNum);
	uniqueRefAST = (GrammarAST)tokenRefs.get(0);
	}
	else {
	// symbol is a rule
	List ruleRefs = getRuleRefsInAlt(refdSymbol, outerAltNum);
	uniqueRefAST = (GrammarAST)ruleRefs.get(0);
	}
	if ( uniqueRefAST.code==null ) {
	// no code? must not have gen'd yet; forward ref
	return null;
	}
	String labelName = null;
	String existingLabelName =
	(String)uniqueRefAST.code.getAttribute("label");
	// reuse any label or list label if it exists
	if ( existingLabelName!=null ) {
	labelName = existingLabelName;
	}
	else {
	// else create new label
	labelName = generator.createUniqueLabel(refdSymbol);
	CommonToken label = new CommonToken(ANTLRParser.ID, labelName);
	if ( grammar.type != Grammar.LEXER &&
	Character.isUpperCase(refdSymbol.charAt(0)) )
	{
	grammar.defineTokenRefLabel(name, label, uniqueRefAST);
	}
	else {
	grammar.defineRuleRefLabel(name, label, uniqueRefAST);
	}
	uniqueRefAST.code.add("label", labelName);
	}
	return labelName;
	}

	/** If a rule has no user-defined return values and nobody references
	* it's start/stop (predefined attributes), then there is no need to
	* define a struct; otherwise for now we assume a struct. A rule also
	* has multiple return values if you are building trees or templates.
	*/
	public boolean getHasMultipleReturnValues() {
	return
	referencedPredefinedRuleAttributes \|\| grammar.buildAST() \|\|
	grammar.buildTemplate() \|\|
	(returnScope!=null && returnScope.attributes.size()>1);
	}

	public boolean getHasSingleReturnValue() {
	return
	!(referencedPredefinedRuleAttributes \|\| grammar.buildAST() \|\|
	grammar.buildTemplate()) &&
	(returnScope!=null && returnScope.attributes.size()==1);
	}

	public boolean getHasReturnValue() {
	return
	referencedPredefinedRuleAttributes \|\| grammar.buildAST() \|\|
	grammar.buildTemplate() \|\|
	(returnScope!=null && returnScope.attributes.size()>0);
	}

	public String getSingleValueReturnType() {
	if ( returnScope!=null && returnScope.attributes.size()==1 ) {
	Collection retvalAttrs = returnScope.attributes.values();
	Object[] javaSucks = retvalAttrs.toArray();
	return ((Attribute)javaSucks[0]).type;
	}
	return null;
	}

	public String getSingleValueReturnName() {
	if ( returnScope!=null && returnScope.attributes.size()==1 ) {
	Collection retvalAttrs = returnScope.attributes.values();
	Object[] javaSucks = retvalAttrs.toArray();
	return ((Attribute)javaSucks[0]).name;
	}
	return null;
	}

	/** Given @scope::name {action} define it for this grammar. Later,
	* the code generator will ask for the actions table.
	*/
	public void defineNamedAction(GrammarAST ampersandAST,
	GrammarAST nameAST,
	GrammarAST actionAST)
	{
	//System.out.println("rule @"+nameAST.getText()+"{"+actionAST.getText()+"}");
	String actionName = nameAST.getText();
	GrammarAST a = (GrammarAST)actions.get(actionName);
	if ( a!=null ) {
	ErrorManager.grammarError(
	ErrorManager.MSG_ACTION_REDEFINITION,grammar,
	nameAST.getToken(),nameAST.getText());
	}
	else {
	actions.put(actionName,actionAST);
	}
	}

	public void trackInlineAction(GrammarAST actionAST) {
	inlineActions.add(actionAST);
	}

	public Map<String, GrammarAST> getActions() {
	return actions;
	}

	public void setActions(Map<String, GrammarAST> actions) {
	this.actions = actions;
	}

	/** Save the option key/value pair and process it; return the key
	* or null if invalid option.
	*/
	public String setOption(String key, Object value, Token optionsStartToken) {
	if ( !legalOptions.contains(key) ) {
	ErrorManager.grammarError(ErrorManager.MSG_ILLEGAL_OPTION,
	grammar,
	optionsStartToken,
	key);
	return null;
	}
	if ( options==null ) {
	options = new HashMap();
	}
	if ( key.equals("memoize") && value.toString().equals("true") ) {
	grammar.atLeastOneRuleMemoizes = true;
	}
	if ( key.equals("backtrack") && value.toString().equals("true") ) {
	grammar.composite.getRootGrammar().atLeastOneBacktrackOption = true;
	}
	if ( key.equals("k") ) {
	grammar.numberOfManualLookaheadOptions++;
	}
	options.put(key, value);
	return key;
	}

	public void setOptions(Map options, Token optionsStartToken) {
	if ( options==null ) {
	this.options = null;
	return;
	}
	Set keys = options.keySet();
	for (Iterator it = keys.iterator(); it.hasNext();) {
	String optionName = (String) it.next();
	Object optionValue = options.get(optionName);
	String stored=setOption(optionName, optionValue, optionsStartToken);
	if ( stored==null ) {
	it.remove();
	}
	}
	}

	/** Used during grammar imports to see if sets of rules intersect... This
	* method and hashCode use the String name as the key for Rule objects.
	public boolean equals(Object other) {
	return this.name.equals(((Rule)other).name);
	}
	*/

	/** Used during grammar imports to see if sets of rules intersect...
	public int hashCode() {
	return name.hashCode();
	}
	* */

	public String toString() { // used for testing
	return "["+grammar.name+"."+name+",index="+index+",line="+tree.getToken().getLine()+"]";
	}
	}