CodeGenTreeWalker.g revision 324c4644fee44b9898524c09511bd33c3f12e2df 
1/*
2 [The "BSD license"]
3 Copyright (c) 2011 Terence Parr
4 All rights reserved.
5
6 Grammar conversion to ANTLR v3:
7 Copyright (c) 2011 Sam Harwell
8 All rights reserved.
9
10 Redistribution and use in source and binary forms, with or without
11 modification, are permitted provided that the following conditions
12 are met:
13 1. Redistributions of source code must retain the above copyright
14	notice, this list of conditions and the following disclaimer.
15 2. Redistributions in binary form must reproduce the above copyright
16	notice, this list of conditions and the following disclaimer in the
17	documentation and/or other materials provided with the distribution.
18 3. The name of the author may not be used to endorse or promote products
19	derived from this software without specific prior written permission.
20
21 THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
22 IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
23 OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
24 IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
25 INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
26 NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
27 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
28 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
29 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
30 THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31*/
32
33/** Walk a grammar and generate code by gradually building up
34 *  a bigger and bigger ST.
35 *
36 *  Terence Parr
37 *  University of San Francisco
38 *  June 15, 2004
39 */
40tree grammar CodeGenTreeWalker;
41
42options {
43	tokenVocab = ANTLR;
44	ASTLabelType=GrammarAST;
45}
46
47@header {
48package org.antlr.grammar.v3;
49
50import org.antlr.analysis.*;
51import org.antlr.misc.*;
52import org.antlr.tool.*;
53import org.antlr.codegen.*;
54
55import java.util.HashSet;
56import java.util.Set;
57import java.util.Collection;
58import org.antlr.runtime.BitSet;
59import org.antlr.runtime.DFA;
60import org.stringtemplate.v4.ST;
61import org.stringtemplate.v4.STGroup;
62}
63
64@members {
65protected static final int RULE_BLOCK_NESTING_LEVEL = 0;
66protected static final int OUTER_REWRITE_NESTING_LEVEL = 0;
67
68private String currentRuleName = null;
69protected int blockNestingLevel = 0;
70protected int rewriteBlockNestingLevel = 0;
71private int outerAltNum = 0;
72protected ST currentBlockST = null;
73protected boolean currentAltHasASTRewrite = false;
74protected int rewriteTreeNestingLevel = 0;
75protected HashSet<Object> rewriteRuleRefs = null;
76
77public String getCurrentRuleName() {
78    return currentRuleName;
79}
80
81public void setCurrentRuleName(String value) {
82    currentRuleName = value;
83}
84
85public int getOuterAltNum() {
86    return outerAltNum;
87}
88
89public void setOuterAltNum(int value) {
90    outerAltNum = value;
91}
92
93@Override
94public void reportError(RecognitionException ex) {
95    Token token = null;
96    if (ex instanceof MismatchedTokenException) {
97        token = ((MismatchedTokenException)ex).token;
98    } else if (ex instanceof NoViableAltException) {
99        token = ((NoViableAltException)ex).token;
100    }
101
102    ErrorManager.syntaxError(
103        ErrorManager.MSG_SYNTAX_ERROR,
104        grammar,
105        token,
106        "codegen: " + ex.toString(),
107        ex );
108}
109
110public final void reportError(String s) {
111    System.out.println("codegen: error: " + s);
112}
113
114protected CodeGenerator generator;
115protected Grammar grammar;
116protected STGroup templates;
117
118/** The overall lexer/parser template; simulate dynamically scoped
119 *  attributes by making this an instance var of the walker.
120 */
121protected ST recognizerST;
122
123protected ST outputFileST;
124protected ST headerFileST;
125
126protected String outputOption = "";
127
128protected final ST getWildcardST(GrammarAST elementAST, GrammarAST ast_suffix, String label) {
129    String name = "wildcard";
130    if (grammar.type == Grammar.LEXER) {
131        name = "wildcardChar";
132    }
133    return getTokenElementST(name, name, elementAST, ast_suffix, label);
134}
135
136protected final ST getRuleElementST( String name,
137                                          String ruleTargetName,
138                                          GrammarAST elementAST,
139                                          GrammarAST ast_suffix,
140                                          String label ) {
141	Rule r = grammar.getRule( currentRuleName );
142	String suffix = getSTSuffix(elementAST, ast_suffix, label);
143	if ( !r.isSynPred ) {
144		name += suffix;
145	}
146	// if we're building trees and there is no label, gen a label
147	// unless we're in a synpred rule.
148	if ( ( grammar.buildAST() || suffix.length() > 0 ) && label == null &&
149		 ( r == null || !r.isSynPred ) ) {
150		// we will need a label to do the AST or tracking, make one
151		label = generator.createUniqueLabel( ruleTargetName );
152		CommonToken labelTok = new CommonToken( ANTLRParser.ID, label );
153		grammar.defineRuleRefLabel( currentRuleName, labelTok, elementAST );
154	}
155
156	ST elementST = templates.getInstanceOf( name );
157	if ( label != null ) {
158		elementST.add( "label", label );
159	}
160
161
162	return elementST;
163}
164
165protected final ST getTokenElementST( String name,
166                                           String elementName,
167                                           GrammarAST elementAST,
168                                           GrammarAST ast_suffix,
169                                           String label ) {
170    boolean tryUnchecked = false;
171    if (name == "matchSet" && elementAST.enclosingRuleName != null && elementAST.enclosingRuleName.length() > 0 && Rule.getRuleType(elementAST.enclosingRuleName) == Grammar.LEXER)
172    {
173        if ( ( elementAST.getParent().getType() == ANTLRLexer.ALT && elementAST.getParent().getParent().getParent().getType() == RULE && elementAST.getParent().getParent().getChildCount() == 2 )
174            || ( elementAST.getParent().getType() == ANTLRLexer.NOT && elementAST.getParent().getParent().getParent().getParent().getType() == RULE && elementAST.getParent().getParent().getParent().getChildCount() == 2 ) ) {
175            // single alt at the start of the rule needs to be checked
176        } else {
177            tryUnchecked = true;
178        }
179    }
180
181    String suffix = getSTSuffix( elementAST, ast_suffix, label );
182    // if we're building trees and there is no label, gen a label
183    // unless we're in a synpred rule.
184    Rule r = grammar.getRule( currentRuleName );
185    if ( ( grammar.buildAST() || suffix.length() > 0 ) && label == null &&
186         ( r == null || !r.isSynPred ) )
187    {
188        label = generator.createUniqueLabel( elementName );
189        CommonToken labelTok = new CommonToken( ANTLRParser.ID, label );
190        grammar.defineTokenRefLabel( currentRuleName, labelTok, elementAST );
191    }
192
193    ST elementST = null;
194    if ( tryUnchecked && templates.isDefined( name + "Unchecked" + suffix ) )
195        elementST = templates.getInstanceOf( name + "Unchecked" + suffix );
196    if ( elementST == null )
197        elementST = templates.getInstanceOf( name + suffix );
198
199    if ( label != null )
200    {
201        elementST.add( "label", label );
202    }
203    return elementST;
204}
205
206public final boolean isListLabel(String label) {
207    boolean hasListLabel = false;
208    if ( label != null ) {
209        Rule r = grammar.getRule( currentRuleName );
210        //String stName = null;
211        if ( r != null )
212        {
213            Grammar.LabelElementPair pair = r.getLabel( label );
214            if ( pair != null &&
215                 ( pair.type == Grammar.TOKEN_LIST_LABEL ||
216                  pair.type == Grammar.RULE_LIST_LABEL ||
217                  pair.type == Grammar.WILDCARD_TREE_LIST_LABEL ) )
218            {
219                hasListLabel = true;
220            }
221        }
222    }
223    return hasListLabel;
224}
225
226/** Return a non-empty template name suffix if the token is to be
227 *  tracked, added to a tree, or both.
228 */
229protected final String getSTSuffix(GrammarAST elementAST, GrammarAST ast_suffix, String label) {
230    if ( grammar.type == Grammar.LEXER )
231    {
232        return "";
233    }
234    // handle list label stuff; make element use "Track"
235
236    String operatorPart = "";
237    String rewritePart = "";
238    String listLabelPart = "";
239    Rule ruleDescr = grammar.getRule( currentRuleName );
240    if ( ast_suffix != null && !ruleDescr.isSynPred )
241    {
242        if ( ast_suffix.getType() == ANTLRParser.ROOT )
243        {
244            operatorPart = "RuleRoot";
245        }
246        else if ( ast_suffix.getType() == ANTLRParser.BANG )
247        {
248            operatorPart = "Bang";
249        }
250    }
251    if ( currentAltHasASTRewrite && elementAST.getType() != WILDCARD )
252    {
253        rewritePart = "Track";
254    }
255    if ( isListLabel( label ) )
256    {
257        listLabelPart = "AndListLabel";
258    }
259    String STsuffix = operatorPart + rewritePart + listLabelPart;
260    //JSystem.@out.println("suffix = "+STsuffix);
261
262    return STsuffix;
263}
264
265/** Convert rewrite AST lists to target labels list */
266protected final List<String> getTokenTypesAsTargetLabels(Collection<GrammarAST> refs)
267{
268    if ( refs == null || refs.size() == 0 )
269        return null;
270
271    List<String> labels = new ArrayList<String>( refs.size() );
272    for ( GrammarAST t : refs )
273    {
274        String label;
275        if ( t.getType() == ANTLRParser.RULE_REF || t.getType() == ANTLRParser.TOKEN_REF || t.getType() == ANTLRParser.LABEL)
276        {
277            label = t.getText();
278        }
279        else
280        {
281            // must be char or String literal
282            label = generator.getTokenTypeAsTargetLabel(grammar.getTokenType(t.getText()));
283        }
284        labels.add( label );
285    }
286    return labels;
287}
288
289public final void init( Grammar g ) {
290    this.grammar = g;
291    this.generator = grammar.getCodeGenerator();
292    this.templates = generator.getTemplates();
293}
294}
295
296public
297grammar_[Grammar g,
298		ST recognizerST,
299		ST outputFileST,
300		ST headerFileST]
301@init
302{
303	if ( state.backtracking == 0 )
304	{
305		init(g);
306		this.recognizerST = recognizerST;
307		this.outputFileST = outputFileST;
308		this.headerFileST = headerFileST;
309		String superClass = (String)g.getOption("superClass");
310		outputOption = (String)g.getOption("output");
311		if ( superClass!=null ) recognizerST.add("superClass", superClass);
312		if ( g.type!=Grammar.LEXER ) {
313		    Object lt = g.getOption("ASTLabelType");
314			if ( lt!=null ) recognizerST.add("ASTLabelType", lt);
315		}
316		if ( g.type==Grammar.TREE_PARSER && g.getOption("ASTLabelType")==null ) {
317			ErrorManager.grammarWarning(ErrorManager.MSG_MISSING_AST_TYPE_IN_TREE_GRAMMAR,
318									   g,
319									   null,
320									   g.name);
321		}
322		if ( g.type!=Grammar.TREE_PARSER ) {
323		    Object lt = g.getOption("TokenLabelType");
324			if ( lt!=null ) recognizerST.add("labelType", lt);
325		}
326		$recognizerST.add("numRules", grammar.getRules().size());
327		$outputFileST.add("numRules", grammar.getRules().size());
328		$headerFileST.add("numRules", grammar.getRules().size());
329	}
330}
331	:	(	^( LEXER_GRAMMAR grammarSpec )
332		|	^( PARSER_GRAMMAR grammarSpec )
333		|	^( TREE_GRAMMAR grammarSpec )
334		|	^( COMBINED_GRAMMAR grammarSpec )
335		)
336	;
337
338attrScope
339	:	^( 'scope' ID ( ^(AMPERSAND .*) )* ACTION )
340	;
341
342grammarSpec
343	:   name=ID
344		(	cmt=DOC_COMMENT
345			{
346				outputFileST.add("docComment", $cmt.text);
347				headerFileST.add("docComment", $cmt.text);
348			}
349		)?
350		{
351			recognizerST.add("name", grammar.getRecognizerName());
352			outputFileST.add("name", grammar.getRecognizerName());
353			headerFileST.add("name", grammar.getRecognizerName());
354			recognizerST.add("scopes", grammar.getGlobalScopes());
355			headerFileST.add("scopes", grammar.getGlobalScopes());
356		}
357		( ^(OPTIONS .*) )?
358		( ^(IMPORT .*) )?
359		( ^(TOKENS .*) )?
360		(attrScope)*
361		( ^(AMPERSAND .*) )*
362		rules[recognizerST]
363	;
364
365rules[ST recognizerST]
366@init
367{
368	String ruleName = ((GrammarAST)input.LT(1)).getChild(0).getText();
369	boolean generated = grammar.generateMethodForRule(ruleName);
370}
371	:	(	(	options {k=1;} :
372				{generated}? =>
373				rST=rule
374				{
375					if ( $rST.code != null )
376					{
377						recognizerST.add("rules", $rST.code);
378						outputFileST.add("rules", $rST.code);
379						headerFileST.add("rules", $rST.code);
380					}
381				}
382			|	^(RULE .*)
383			|	^(PREC_RULE .*) // ignore
384			)
385			{{
386				if ( input.LA(1) == RULE )
387				{
388					ruleName = ((GrammarAST)input.LT(1)).getChild(0).getText();
389					//System.Diagnostics.Debug.Assert( ruleName == ((GrammarAST)input.LT(1)).enclosingRuleName );
390					generated = grammar.generateMethodForRule(ruleName);
391				}
392			}}
393		)+
394	;
395
396rule returns [ST code=null]
397@init
398{
399	String initAction = null;
400	// get the dfa for the BLOCK
401	GrammarAST block2=(GrammarAST)$start.getFirstChildWithType(BLOCK);
402	org.antlr.analysis.DFA dfa = block2.getLookaheadDFA();
403	// init blockNestingLevel so it's block level RULE_BLOCK_NESTING_LEVEL
404	// for alts of rule
405	blockNestingLevel = RULE_BLOCK_NESTING_LEVEL-1;
406	Rule ruleDescr = grammar.getRule($start.getChild(0).getText());
407	currentRuleName = $start.getChild(0).getText();
408
409	// For syn preds, we don't want any AST code etc... in there.
410	// Save old templates ptr and restore later.  Base templates include Dbg.
411	STGroup saveGroup = templates;
412	if ( ruleDescr.isSynPred )
413	{
414		templates = generator.getBaseTemplates();
415	}
416
417	String description = "";
418}
419	:	^(	RULE id=ID
420			{assert currentRuleName == $id.text;}
421			(mod=modifier)?
422			^(ARG (ARG_ACTION)?)
423			^(RET (ARG_ACTION)?)
424			(throwsSpec)?
425			( ^(OPTIONS .*) )?
426			(ruleScopeSpec)?
427			( ^(AMPERSAND .*) )*
428			b=block["ruleBlock", dfa]
429			{
430				description =
431					grammar.grammarTreeToString((GrammarAST)$start.getFirstChildWithType(BLOCK),
432												false);
433				description =
434					generator.target.getTargetStringLiteralFromString(description);
435				$b.code.add("description", description);
436				// do not generate lexer rules in combined grammar
437				String stName = null;
438				if ( ruleDescr.isSynPred )
439				{
440					stName = "synpredRule";
441				}
442				else if ( grammar.type==Grammar.LEXER )
443				{
444					if ( currentRuleName.equals(Grammar.ARTIFICIAL_TOKENS_RULENAME) )
445					{
446						stName = "tokensRule";
447					}
448					else
449					{
450						stName = "lexerRule";
451					}
452				}
453				else
454				{
455					if ( !(grammar.type==Grammar.COMBINED &&
456						 Rule.getRuleType(currentRuleName) == Grammar.LEXER) )
457					{
458						stName = "rule";
459					}
460				}
461				$code = templates.getInstanceOf(stName);
462				if ( $code.getName().equals("/rule") )
463				{
464					$code.add("emptyRule", grammar.isEmptyRule(block2));
465				}
466				$code.add("ruleDescriptor", ruleDescr);
467				String memo = (String)grammar.getBlockOption($start,"memoize");
468				if ( memo==null )
469				{
470					memo = (String)grammar.getOption("memoize");
471				}
472				if ( memo!=null && memo.equals("true") &&
473					 (stName.equals("rule")||stName.equals("lexerRule")) )
474				{
475					$code.add("memoize", memo!=null && memo.equals("true"));
476				}
477			}
478
479			(exceptionGroup[$code])?
480			EOR
481		)
482		{
483			if ( $code!=null )
484			{
485				if ( grammar.type==Grammar.LEXER )
486				{
487					boolean naked =
488						currentRuleName.equals(Grammar.ARTIFICIAL_TOKENS_RULENAME) ||
489						($mod.start!=null&&$mod.start.getText().equals(Grammar.FRAGMENT_RULE_MODIFIER));
490					$code.add("nakedBlock", naked);
491				}
492				else
493				{
494					description = grammar.grammarTreeToString($start,false);
495					description = generator.target.getTargetStringLiteralFromString(description);
496					$code.add("description", description);
497				}
498				Rule theRule = grammar.getRule(currentRuleName);
499				generator.translateActionAttributeReferencesForSingleScope(
500					theRule,
501					theRule.getActions()
502				);
503				$code.add("ruleName", currentRuleName);
504				$code.add("block", $b.code);
505				if ( initAction!=null )
506				{
507					$code.add("initAction", initAction);
508				}
509			}
510		}
511	;
512finally { templates = saveGroup; }
513
514modifier
515	:	'protected'
516	|	'public'
517	|	'private'
518	|	'fragment'
519	;
520
521throwsSpec
522	:	^('throws' ID+)
523	;
524
525ruleScopeSpec
526	:	^( 'scope' ( ^(AMPERSAND .*) )* (ACTION)? ( ID )* )
527	;
528
529block[String blockTemplateName, org.antlr.analysis.DFA dfa]
530	 returns [ST code=null]
531options { k=1; }
532@init
533{
534	int altNum = 0;
535
536	blockNestingLevel++;
537	if ( state.backtracking == 0 )
538	{
539		ST decision = null;
540		if ( $dfa != null )
541		{
542			$code = templates.getInstanceOf($blockTemplateName);
543			decision = generator.genLookaheadDecision(recognizerST,$dfa);
544			$code.add("decision", decision);
545			$code.add("decisionNumber", $dfa.getDecisionNumber());
546			$code.add("maxK",$dfa.getMaxLookaheadDepth());
547			$code.add("maxAlt",$dfa.getNumberOfAlts());
548		}
549		else
550		{
551			$code = templates.getInstanceOf($blockTemplateName+"SingleAlt");
552		}
553		$code.add("blockLevel", blockNestingLevel);
554		$code.add("enclosingBlockLevel", blockNestingLevel-1);
555		altNum = 1;
556		if ( this.blockNestingLevel==RULE_BLOCK_NESTING_LEVEL ) {
557			this.outerAltNum=1;
558		}
559	}
560}
561	:	{$start.getSetValue()!=null}? => setBlock
562		{
563			$code.add("alts",$setBlock.code);
564		}
565
566	|	^(  BLOCK
567			( ^(OPTIONS .*) )? // ignore
568			( alt=alternative rew=rewrite
569				{
570					if ( this.blockNestingLevel==RULE_BLOCK_NESTING_LEVEL )
571					{
572						this.outerAltNum++;
573					}
574					// add the rewrite code as just another element in the alt :)
575					// (unless it's a " -> ..." rewrite
576					// ( -> ... )
577					GrammarAST firstRewriteAST = (GrammarAST)$rew.start.findFirstType(REWRITE);
578					boolean etc =
579						$rew.start.getType()==REWRITES &&
580						firstRewriteAST.getChild(0)!=null &&
581						firstRewriteAST.getChild(0).getType()==ETC;
582					if ( $rew.code!=null && !etc )
583					{
584						$alt.code.add("rew", $rew.code);
585					}
586					// add this alt to the list of alts for this block
587					$code.add("alts",$alt.code);
588					$alt.code.add("altNum", altNum);
589					$alt.code.add("outerAlt", blockNestingLevel==RULE_BLOCK_NESTING_LEVEL);
590					altNum++;
591				}
592			)+
593			EOB
594		 )
595	;
596finally { blockNestingLevel--; }
597
598setBlock returns [ST code=null]
599@init
600{
601	ST setcode = null;
602	if ( state.backtracking == 0 )
603	{
604		if ( blockNestingLevel==RULE_BLOCK_NESTING_LEVEL && grammar.buildAST() )
605		{
606			Rule r = grammar.getRule(currentRuleName);
607			currentAltHasASTRewrite = r.hasRewrite(outerAltNum);
608			if ( currentAltHasASTRewrite )
609			{
610				r.trackTokenReferenceInAlt($start, outerAltNum);
611			}
612		}
613	}
614}
615	:	^(s=BLOCK .*)
616		{
617			int i = ((CommonToken)$s.getToken()).getTokenIndex();
618			if ( blockNestingLevel==RULE_BLOCK_NESTING_LEVEL )
619			{
620				setcode = getTokenElementST("matchRuleBlockSet", "set", $s, null, null);
621			}
622			else
623			{
624				setcode = getTokenElementST("matchSet", "set", $s, null, null);
625			}
626			setcode.add("elementIndex", i);
627			//if ( grammar.type!=Grammar.LEXER )
628			//{
629			//	generator.generateLocalFOLLOW($s,"set",currentRuleName,i);
630			//}
631			setcode.add("s",
632				generator.genSetExpr(templates,$s.getSetValue(),1,false));
633			ST altcode=templates.getInstanceOf("alt");
634			altcode.addAggr("elements.{el,line,pos}",
635								 setcode,
636								 $s.getLine(),
637								 $s.getCharPositionInLine() + 1
638								);
639			altcode.add("altNum", 1);
640			altcode.add("outerAlt", blockNestingLevel==RULE_BLOCK_NESTING_LEVEL);
641			if ( !currentAltHasASTRewrite && grammar.buildAST() )
642			{
643				altcode.add("autoAST", true);
644			}
645			altcode.add("treeLevel", rewriteTreeNestingLevel);
646			$code = altcode;
647		}
648	;
649
650setAlternative
651	:	^(ALT setElement+ EOA)
652	;
653
654exceptionGroup[ST ruleST]
655	:	( exceptionHandler[$ruleST] )+ (finallyClause[$ruleST])?
656	|	finallyClause[$ruleST]
657	;
658
659exceptionHandler[ST ruleST]
660	:	^('catch' ARG_ACTION ACTION)
661		{
662			List chunks = generator.translateAction(currentRuleName,$ACTION);
663			$ruleST.addAggr("exceptions.{decl,action}",$ARG_ACTION.text,chunks);
664		}
665	;
666
667finallyClause[ST ruleST]
668	:	^('finally' ACTION)
669		{
670			List chunks = generator.translateAction(currentRuleName,$ACTION);
671			$ruleST.add("finally",chunks);
672		}
673	;
674
675alternative returns [ST code]
676@init
677{
678	if ( state.backtracking == 0 )
679	{
680		$code = templates.getInstanceOf("alt");
681		if ( blockNestingLevel==RULE_BLOCK_NESTING_LEVEL && grammar.buildAST() )
682		{
683			Rule r = grammar.getRule(currentRuleName);
684			currentAltHasASTRewrite = r.hasRewrite(outerAltNum);
685		}
686		String description = grammar.grammarTreeToString($start, false);
687		description = generator.target.getTargetStringLiteralFromString(description);
688		$code.add("description", description);
689		$code.add("treeLevel", rewriteTreeNestingLevel);
690		if ( !currentAltHasASTRewrite && grammar.buildAST() )
691		{
692			$code.add("autoAST", true);
693		}
694	}
695}
696	:	^(	a=ALT
697			(
698				e=element[null,null]
699				{
700					if (e != null && e.code != null)
701					{
702						$code.addAggr("elements.{el,line,pos}",
703										  $e.code,
704										  $e.start.getLine(),
705										  $e.start.getCharPositionInLine() + 1
706										 );
707					}
708				}
709			)+
710			EOA
711		)
712	;
713
714element[GrammarAST label, GrammarAST astSuffix] returns [ST code=null]
715options { k=1; }
716@init
717{
718	IntSet elements=null;
719	GrammarAST ast = null;
720}
721	:	^(ROOT e=element[label,$ROOT])
722		{ $code = $e.code; }
723
724	|	^(BANG e=element[label,$BANG])
725		{ $code = $e.code; }
726
727	|	^( n=NOT notElement[$n, $label, $astSuffix] )
728		{ $code = $notElement.code; }
729
730	|	^( ASSIGN alabel=ID e=element[$alabel,$astSuffix] )
731		{ $code = $e.code; }
732
733	|	^( PLUS_ASSIGN label2=ID e=element[$label2,$astSuffix] )
734		{ $code = $e.code; }
735
736	|	^(CHAR_RANGE a=CHAR_LITERAL b=CHAR_LITERAL)
737		{
738			$code = templates.getInstanceOf("charRangeRef");
739			String low = generator.target.getTargetCharLiteralFromANTLRCharLiteral(generator,$a.text);
740			String high = generator.target.getTargetCharLiteralFromANTLRCharLiteral(generator,$b.text);
741			$code.add("a", low);
742			$code.add("b", high);
743			if ( label!=null )
744			{
745				$code.add("label", $label.getText());
746			}
747		}
748
749	|	({((GrammarAST)input.LT(1)).getSetValue()==null}? (BLOCK|OPTIONAL|CLOSURE|POSITIVE_CLOSURE)) => /*{$start.getSetValue()==null}?*/ ebnf
750		{ $code = $ebnf.code; }
751
752	|	atom[null, $label, $astSuffix]
753		{ $code = $atom.code; }
754
755	|	tree_
756		{ $code = $tree_.code; }
757
758	|	element_action
759		{ $code = $element_action.code; }
760
761	|   (sp=SEMPRED|sp=GATED_SEMPRED)
762		{
763			$code = templates.getInstanceOf("validateSemanticPredicate");
764			$code.add("pred", generator.translateAction(currentRuleName,$sp));
765			String description = generator.target.getTargetStringLiteralFromString($sp.text);
766			$code.add("description", description);
767		}
768
769	|	SYN_SEMPRED // used only in lookahead; don't generate validating pred
770
771	|	^(SYNPRED .*)
772
773	|	^(BACKTRACK_SEMPRED .*)
774
775	|   EPSILON
776	;
777
778element_action returns [ST code=null]
779	:	act=ACTION
780		{
781			$code = templates.getInstanceOf("execAction");
782			$code.add("action", generator.translateAction(currentRuleName,$act));
783		}
784	|	act2=FORCED_ACTION
785		{
786			$code = templates.getInstanceOf("execForcedAction");
787			$code.add("action", generator.translateAction(currentRuleName,$act2));
788		}
789	;
790
791notElement[GrammarAST n, GrammarAST label, GrammarAST astSuffix] returns [ST code=null]
792@init
793{
794	IntSet elements=null;
795	String labelText = null;
796	if ( label!=null )
797	{
798		labelText = label.getText();
799	}
800}
801	:	(	assign_c=CHAR_LITERAL
802			{
803				int ttype=0;
804				if ( grammar.type==Grammar.LEXER )
805				{
806					ttype = Grammar.getCharValueFromGrammarCharLiteral($assign_c.text);
807				}
808				else
809				{
810					ttype = grammar.getTokenType($assign_c.text);
811				}
812				elements = grammar.complement(ttype);
813			}
814		|	assign_s=STRING_LITERAL
815			{
816				int ttype=0;
817				if ( grammar.type==Grammar.LEXER )
818				{
819					// TODO: error!
820				}
821				else
822				{
823					ttype = grammar.getTokenType($assign_s.text);
824				}
825				elements = grammar.complement(ttype);
826			}
827		|	assign_t=TOKEN_REF
828			{
829				int ttype = grammar.getTokenType($assign_t.text);
830				elements = grammar.complement(ttype);
831			}
832		|	^(assign_st=BLOCK .*)
833			{
834				elements = $assign_st.getSetValue();
835				elements = grammar.complement(elements);
836			}
837		)
838		{
839			$code = getTokenElementST("matchSet",
840									 "set",
841									 (GrammarAST)$n.getChild(0),
842									 astSuffix,
843									 labelText);
844			$code.add("s",generator.genSetExpr(templates,elements,1,false));
845			int i = ((CommonToken)n.getToken()).getTokenIndex();
846			$code.add("elementIndex", i);
847			if ( grammar.type!=Grammar.LEXER )
848			{
849				generator.generateLocalFOLLOW(n,"set",currentRuleName,i);
850			}
851		}
852	;
853
854ebnf returns [ST code=null]
855@init
856{
857	org.antlr.analysis.DFA dfa=null;
858	GrammarAST b = (GrammarAST)$start.getChild(0);
859	GrammarAST eob = (GrammarAST)b.getLastChild(); // loops will use EOB DFA
860}
861	:	(	{ dfa = $start.getLookaheadDFA(); }
862			blk=block["block", dfa]
863			{ $code = $blk.code; }
864		|	{ dfa = $start.getLookaheadDFA(); }
865			^( OPTIONAL blk=block["optionalBlock", dfa] )
866			{ $code = $blk.code; }
867		|	{ dfa = eob.getLookaheadDFA(); }
868			^( CLOSURE blk=block["closureBlock", dfa] )
869			{ $code = $blk.code; }
870		|	{ dfa = eob.getLookaheadDFA(); }
871			^( POSITIVE_CLOSURE blk=block["positiveClosureBlock", dfa] )
872			{ $code = $blk.code; }
873		)
874		{
875			String description = grammar.grammarTreeToString($start, false);
876			description = generator.target.getTargetStringLiteralFromString(description);
877			$code.add("description", description);
878		}
879	;
880
881tree_ returns [ST code]
882@init
883{
884	rewriteTreeNestingLevel++;
885	GrammarAST rootSuffix = null;
886	if ( state.backtracking == 0 )
887	{
888		$code = templates.getInstanceOf("tree");
889		NFAState afterDOWN = (NFAState)$start.NFATreeDownState.transition(0).target;
890		LookaheadSet s = grammar.LOOK(afterDOWN);
891		if ( s.member(Label.UP) ) {
892			// nullable child list if we can see the UP as the next token
893			// we need an "if ( input.LA(1)==Token.DOWN )" gate around
894			// the child list.
895			$code.add("nullableChildList", "true");
896		}
897		$code.add("enclosingTreeLevel", rewriteTreeNestingLevel-1);
898		$code.add("treeLevel", rewriteTreeNestingLevel);
899		Rule r = grammar.getRule(currentRuleName);
900		if ( grammar.buildAST() && !r.hasRewrite(outerAltNum) ) {
901			rootSuffix = new GrammarAST(ROOT,"ROOT");
902		}
903	}
904}
905	:	^(	TREE_BEGIN
906			el=element[null,rootSuffix]
907			{
908				$code.addAggr("root.{el,line,pos}",
909								  $el.code,
910								  $el.start.getLine(),
911								  $el.start.getCharPositionInLine() + 1
912								  );
913			}
914			// push all the immediately-following actions out before children
915			// so actions aren't guarded by the "if (input.LA(1)==Token.DOWN)"
916			// guard in generated code.
917			(	(element_action) =>
918				act=element_action
919				{
920					$code.addAggr("actionsAfterRoot.{el,line,pos}",
921									  $act.code,
922									  $act.start.getLine(),
923									  $act.start.getCharPositionInLine() + 1
924									);
925				}
926			)*
927			(	 el=element[null,null]
928				 {
929				 $code.addAggr("children.{el,line,pos}",
930								  $el.code,
931								  $el.start.getLine(),
932								  $el.start.getCharPositionInLine() + 1
933								  );
934				 }
935			)*
936		)
937	;
938finally { rewriteTreeNestingLevel--; }
939
940atom[GrammarAST scope, GrammarAST label, GrammarAST astSuffix]
941	returns [ST code=null]
942@init
943{
944	String labelText=null;
945	if ( state.backtracking == 0 )
946	{
947		if ( label!=null )
948		{
949			labelText = label.getText();
950		}
951		if ( grammar.type!=Grammar.LEXER &&
952			 ($start.getType()==RULE_REF||$start.getType()==TOKEN_REF||
953			  $start.getType()==CHAR_LITERAL||$start.getType()==STRING_LITERAL) )
954		{
955			Rule encRule = grammar.getRule(((GrammarAST)$start).enclosingRuleName);
956			if ( encRule!=null && encRule.hasRewrite(outerAltNum) && astSuffix!=null )
957			{
958				ErrorManager.grammarError(ErrorManager.MSG_AST_OP_IN_ALT_WITH_REWRITE,
959										  grammar,
960										  ((GrammarAST)$start).getToken(),
961										  ((GrammarAST)$start).enclosingRuleName,
962										  outerAltNum);
963				astSuffix = null;
964			}
965		}
966	}
967}
968	:   ^( r=RULE_REF (rarg=ARG_ACTION)? )
969		{
970			grammar.checkRuleReference(scope, $r, $rarg, currentRuleName);
971			String scopeName = null;
972			if ( scope!=null ) {
973				scopeName = scope.getText();
974			}
975			Rule rdef = grammar.getRule(scopeName, $r.text);
976			// don't insert label=r() if $label.attr not used, no ret value, ...
977			if ( !rdef.getHasReturnValue() ) {
978				labelText = null;
979			}
980			$code = getRuleElementST("ruleRef", $r.text, $r, astSuffix, labelText);
981			$code.add("rule", rdef);
982			if ( scope!=null ) { // scoped rule ref
983				Grammar scopeG = grammar.composite.getGrammar(scope.getText());
984				$code.add("scope", scopeG);
985			}
986			else if ( rdef.grammar != this.grammar ) { // nonlocal
987				// if rule definition is not in this grammar, it's nonlocal
988				List<Grammar> rdefDelegates = rdef.grammar.getDelegates();
989				if ( rdefDelegates.contains(this.grammar) ) {
990					$code.add("scope", rdef.grammar);
991				}
992				else {
993					// defining grammar is not a delegate, scope all the
994					// back to root, which has delegate methods for all
995					// rules.  Don't use scope if we are root.
996					if ( this.grammar != rdef.grammar.composite.delegateGrammarTreeRoot.grammar ) {
997						$code.add("scope",
998										  rdef.grammar.composite.delegateGrammarTreeRoot.grammar);
999					}
1000				}
1001			}
1002
1003			if ( $rarg!=null ) {
1004				List args = generator.translateAction(currentRuleName,$rarg);
1005				$code.add("args", args);
1006			}
1007			int i = ((CommonToken)r.getToken()).getTokenIndex();
1008			$code.add("elementIndex", i);
1009			generator.generateLocalFOLLOW($r,$r.text,currentRuleName,i);
1010			$r.code = $code;
1011		}
1012
1013	|	^( t=TOKEN_REF (targ=ARG_ACTION)? )
1014		{
1015			if ( currentAltHasASTRewrite && $t.terminalOptions!=null &&
1016				$t.terminalOptions.get(Grammar.defaultTokenOption)!=null )
1017			{
1018				ErrorManager.grammarError(ErrorManager.MSG_HETERO_ILLEGAL_IN_REWRITE_ALT,
1019										grammar,
1020										((GrammarAST)($t)).getToken(),
1021										$t.text);
1022			}
1023			grammar.checkRuleReference(scope, $t, $targ, currentRuleName);
1024			if ( grammar.type==Grammar.LEXER )
1025			{
1026				if ( grammar.getTokenType($t.text)==Label.EOF )
1027				{
1028					$code = templates.getInstanceOf("lexerMatchEOF");
1029				}
1030				else
1031				{
1032					$code = templates.getInstanceOf("lexerRuleRef");
1033					if ( isListLabel(labelText) )
1034					{
1035						$code = templates.getInstanceOf("lexerRuleRefAndListLabel");
1036					}
1037					String scopeName = null;
1038					if ( scope!=null )
1039					{
1040						scopeName = scope.getText();
1041					}
1042					Rule rdef2 = grammar.getRule(scopeName, $t.text);
1043					$code.add("rule", rdef2);
1044					if ( scope!=null )
1045					{ // scoped rule ref
1046						Grammar scopeG = grammar.composite.getGrammar(scope.getText());
1047						$code.add("scope", scopeG);
1048					}
1049					else if ( rdef2.grammar != this.grammar )
1050					{ // nonlocal
1051						// if rule definition is not in this grammar, it's nonlocal
1052						$code.add("scope", rdef2.grammar);
1053					}
1054					if ( $targ!=null )
1055					{
1056						List args = generator.translateAction(currentRuleName,$targ);
1057						$code.add("args", args);
1058					}
1059				}
1060				int i = ((CommonToken)$t.getToken()).getTokenIndex();
1061				$code.add("elementIndex", i);
1062				if ( label!=null )
1063					$code.add("label", labelText);
1064			}
1065			else
1066			{
1067				$code = getTokenElementST("tokenRef", $t.text, $t, astSuffix, labelText);
1068				String tokenLabel =
1069					generator.getTokenTypeAsTargetLabel(grammar.getTokenType(t.getText()));
1070				$code.add("token",tokenLabel);
1071				if ( !currentAltHasASTRewrite && $t.terminalOptions!=null )
1072				{
1073					$code.add("terminalOptions", $t.terminalOptions);
1074				}
1075				int i = ((CommonToken)$t.getToken()).getTokenIndex();
1076				$code.add("elementIndex", i);
1077				generator.generateLocalFOLLOW($t,tokenLabel,currentRuleName,i);
1078			}
1079			$t.code = $code;
1080		}
1081
1082	|	c=CHAR_LITERAL
1083		{
1084			if ( grammar.type==Grammar.LEXER )
1085			{
1086				$code = templates.getInstanceOf("charRef");
1087				$code.add("char",
1088				   generator.target.getTargetCharLiteralFromANTLRCharLiteral(generator,$c.text));
1089				if ( label!=null )
1090				{
1091					$code.add("label", labelText);
1092				}
1093			}
1094			else { // else it's a token type reference
1095				$code = getTokenElementST("tokenRef", "char_literal", $c, astSuffix, labelText);
1096				String tokenLabel = generator.getTokenTypeAsTargetLabel(grammar.getTokenType($c.text));
1097				$code.add("token",tokenLabel);
1098				if ( $c.terminalOptions!=null ) {
1099					$code.add("terminalOptions",$c.terminalOptions);
1100				}
1101				int i = ((CommonToken)$c.getToken()).getTokenIndex();
1102				$code.add("elementIndex", i);
1103				generator.generateLocalFOLLOW($c,tokenLabel,currentRuleName,i);
1104			}
1105		}
1106
1107	|	s=STRING_LITERAL
1108		{
1109			int i = ((CommonToken)$s.getToken()).getTokenIndex();
1110			if ( grammar.type==Grammar.LEXER )
1111			{
1112				$code = templates.getInstanceOf("lexerStringRef");
1113				$code.add("string",
1114					generator.target.getTargetStringLiteralFromANTLRStringLiteral(generator,$s.text));
1115				$code.add("elementIndex", i);
1116				if ( label!=null )
1117				{
1118					$code.add("label", labelText);
1119				}
1120			}
1121			else
1122			{
1123				// else it's a token type reference
1124				$code = getTokenElementST("tokenRef", "string_literal", $s, astSuffix, labelText);
1125				String tokenLabel =
1126					generator.getTokenTypeAsTargetLabel(grammar.getTokenType($s.text));
1127				$code.add("token",tokenLabel);
1128				if ( $s.terminalOptions!=null )
1129				{
1130					$code.add("terminalOptions",$s.terminalOptions);
1131				}
1132				$code.add("elementIndex", i);
1133				generator.generateLocalFOLLOW($s,tokenLabel,currentRuleName,i);
1134			}
1135		}
1136
1137	|	w=WILDCARD
1138		{
1139			$code = getWildcardST($w,astSuffix,labelText);
1140			$code.add("elementIndex", ((CommonToken)$w.getToken()).getTokenIndex());
1141		}
1142
1143	|	^(DOT ID a=atom[$ID, label, astSuffix]) // scope override on rule or token
1144		{ $code = $a.code; }
1145
1146	|	set[label,astSuffix]
1147		{ $code = $set.code; }
1148	;
1149
1150ast_suffix
1151	:	ROOT
1152	|	BANG
1153	;
1154
1155set[GrammarAST label, GrammarAST astSuffix] returns [ST code=null]
1156@init
1157{
1158	String labelText=null;
1159	if ( $label!=null )
1160	{
1161		labelText = $label.getText();
1162	}
1163}
1164	:	^(s=BLOCK .*) // only care that it's a BLOCK with setValue!=null
1165		{
1166			$code = getTokenElementST("matchSet", "set", $s, astSuffix, labelText);
1167			int i = ((CommonToken)$s.getToken()).getTokenIndex();
1168			$code.add("elementIndex", i);
1169			if ( grammar.type!=Grammar.LEXER )
1170			{
1171				generator.generateLocalFOLLOW($s,"set",currentRuleName,i);
1172			}
1173			$code.add("s", generator.genSetExpr(templates,$s.getSetValue(),1,false));
1174		}
1175	;
1176
1177setElement
1178	:	CHAR_LITERAL
1179	|	TOKEN_REF
1180	|	STRING_LITERAL
1181	|	^(CHAR_RANGE CHAR_LITERAL CHAR_LITERAL)
1182	;
1183
1184// REWRITE stuff
1185
1186rewrite returns [ST code=null]
1187@init
1188{
1189	if ( state.backtracking == 0 )
1190	{
1191		if ( $start.getType()==REWRITES )
1192		{
1193			if ( generator.grammar.buildTemplate() )
1194			{
1195				$code = templates.getInstanceOf("rewriteTemplate");
1196			}
1197			else
1198			{
1199				$code = templates.getInstanceOf("rewriteCode");
1200				$code.add("treeLevel", OUTER_REWRITE_NESTING_LEVEL);
1201				$code.add("rewriteBlockLevel", OUTER_REWRITE_NESTING_LEVEL);
1202				$code.add("referencedElementsDeep",
1203								  getTokenTypesAsTargetLabels($start.rewriteRefsDeep));
1204				Set<String> tokenLabels =
1205					grammar.getLabels($start.rewriteRefsDeep, Grammar.TOKEN_LABEL);
1206				Set<String> tokenListLabels =
1207					grammar.getLabels($start.rewriteRefsDeep, Grammar.TOKEN_LIST_LABEL);
1208				Set<String> ruleLabels =
1209					grammar.getLabels($start.rewriteRefsDeep, Grammar.RULE_LABEL);
1210				Set<String> ruleListLabels =
1211					grammar.getLabels($start.rewriteRefsDeep, Grammar.RULE_LIST_LABEL);
1212				Set<String> wildcardLabels =
1213					grammar.getLabels($start.rewriteRefsDeep, Grammar.WILDCARD_TREE_LABEL);
1214				Set<String> wildcardListLabels =
1215					grammar.getLabels($start.rewriteRefsDeep, Grammar.WILDCARD_TREE_LIST_LABEL);
1216				// just in case they ref $r for "previous value", make a stream
1217				// from retval.tree
1218				ST retvalST = templates.getInstanceOf("prevRuleRootRef");
1219				ruleLabels.add(retvalST.render());
1220				$code.add("referencedTokenLabels", tokenLabels);
1221				$code.add("referencedTokenListLabels", tokenListLabels);
1222				$code.add("referencedRuleLabels", ruleLabels);
1223				$code.add("referencedRuleListLabels", ruleListLabels);
1224				$code.add("referencedWildcardLabels", wildcardLabels);
1225				$code.add("referencedWildcardListLabels", wildcardListLabels);
1226			}
1227		}
1228		else
1229		{
1230				$code = templates.getInstanceOf("noRewrite");
1231				$code.add("treeLevel", OUTER_REWRITE_NESTING_LEVEL);
1232				$code.add("rewriteBlockLevel", OUTER_REWRITE_NESTING_LEVEL);
1233		}
1234	}
1235}
1236	:	^(	REWRITES
1237			(
1238				{rewriteRuleRefs = new HashSet<Object>();}
1239				^( r=REWRITE (pred=SEMPRED)? alt=rewrite_alternative)
1240				{
1241					rewriteBlockNestingLevel = OUTER_REWRITE_NESTING_LEVEL;
1242					List predChunks = null;
1243					if ( $pred!=null )
1244					{
1245						//predText = #pred.getText();
1246						predChunks = generator.translateAction(currentRuleName,$pred);
1247					}
1248					String description =
1249						grammar.grammarTreeToString($r,false);
1250					description = generator.target.getTargetStringLiteralFromString(description);
1251					$code.addAggr("alts.{pred,alt,description}",
1252									  predChunks,
1253									  alt,
1254									  description);
1255					pred=null;
1256				}
1257			)*
1258		)
1259	|
1260	;
1261
1262rewrite_block[String blockTemplateName] returns [ST code=null]
1263@init
1264{
1265	rewriteBlockNestingLevel++;
1266	ST save_currentBlockST = currentBlockST;
1267	if ( state.backtracking == 0 )
1268	{
1269		$code = templates.getInstanceOf(blockTemplateName);
1270		currentBlockST = $code;
1271		$code.add("rewriteBlockLevel", rewriteBlockNestingLevel);
1272	}
1273}
1274	:	^(	BLOCK
1275			{
1276				currentBlockST.add("referencedElementsDeep",
1277					getTokenTypesAsTargetLabels($BLOCK.rewriteRefsDeep));
1278				currentBlockST.add("referencedElements",
1279					getTokenTypesAsTargetLabels($BLOCK.rewriteRefsShallow));
1280			}
1281			alt=rewrite_alternative
1282			EOB
1283		)
1284		{
1285			$code.add("alt", $alt.code);
1286		}
1287	;
1288finally { rewriteBlockNestingLevel--; currentBlockST = save_currentBlockST; }
1289
1290rewrite_alternative returns [ST code=null]
1291	:	{generator.grammar.buildAST()}?
1292		^(	a=ALT {$code=templates.getInstanceOf("rewriteElementList");}
1293			(	(
1294					el=rewrite_element
1295					{$code.addAggr("elements.{el,line,pos}",
1296										$el.code,
1297										$el.start.getLine(),
1298										$el.start.getCharPositionInLine() + 1
1299										);
1300					}
1301				)+
1302			|	EPSILON
1303				{$code.addAggr("elements.{el,line,pos}",
1304								   templates.getInstanceOf("rewriteEmptyAlt"),
1305								   $a.getLine(),
1306								   $a.getCharPositionInLine() + 1
1307								   );
1308				}
1309			)
1310			EOA
1311		 )
1312
1313	|	{generator.grammar.buildTemplate()}? rewrite_template
1314		{ $code = $rewrite_template.code; }
1315
1316	|	// reproduce same input (only AST at moment)
1317		ETC
1318	;
1319
1320rewrite_element returns [ST code=null]
1321@init
1322{
1323	IntSet elements=null;
1324	GrammarAST ast = null;
1325}
1326	:	rewrite_atom[false]
1327		{ $code = $rewrite_atom.code; }
1328	|	rewrite_ebnf
1329		{ $code = $rewrite_ebnf.code; }
1330	|	rewrite_tree
1331		{ $code = $rewrite_tree.code; }
1332	;
1333
1334rewrite_ebnf returns [ST code=null]
1335	:	^( OPTIONAL rewrite_block["rewriteOptionalBlock"] )
1336		{ $code = $rewrite_block.code; }
1337		{
1338			String description = grammar.grammarTreeToString($start, false);
1339			description = generator.target.getTargetStringLiteralFromString(description);
1340			$code.add("description", description);
1341		}
1342	|	^( CLOSURE rewrite_block["rewriteClosureBlock"] )
1343		{ $code = $rewrite_block.code; }
1344		{
1345			String description = grammar.grammarTreeToString($start, false);
1346			description = generator.target.getTargetStringLiteralFromString(description);
1347			$code.add("description", description);
1348		}
1349	|	^( POSITIVE_CLOSURE rewrite_block["rewritePositiveClosureBlock"] )
1350		{ $code = $rewrite_block.code; }
1351		{
1352			String description = grammar.grammarTreeToString($start, false);
1353			description = generator.target.getTargetStringLiteralFromString(description);
1354			$code.add("description", description);
1355		}
1356	;
1357
1358rewrite_tree returns [ST code]
1359@init
1360{
1361	rewriteTreeNestingLevel++;
1362	if ( state.backtracking == 0 )
1363	{
1364		$code = templates.getInstanceOf("rewriteTree");
1365		$code.add("treeLevel", rewriteTreeNestingLevel);
1366		$code.add("enclosingTreeLevel", rewriteTreeNestingLevel-1);
1367	}
1368}
1369	:	^(	TREE_BEGIN
1370			r=rewrite_atom[true]
1371			{
1372				$code.addAggr("root.{el,line,pos}",
1373								   $r.code,
1374								   $r.start.getLine(),
1375								   $r.start.getCharPositionInLine() + 1
1376								  );
1377			}
1378			(
1379			  el=rewrite_element
1380			  {
1381				$code.addAggr("children.{el,line,pos}",
1382									$el.code,
1383									$el.start.getLine(),
1384									$el.start.getCharPositionInLine() + 1
1385									);
1386			  }
1387			)*
1388		)
1389		{
1390			String description = grammar.grammarTreeToString($start, false);
1391			description = generator.target.getTargetStringLiteralFromString(description);
1392			$code.add("description", description);
1393		}
1394	;
1395finally { rewriteTreeNestingLevel--; }
1396
1397rewrite_atom[boolean isRoot] returns [ST code=null]
1398	:   r=RULE_REF
1399		{
1400			String ruleRefName = $r.text;
1401			String stName = "rewriteRuleRef";
1402			if ( isRoot )
1403			{
1404				stName += "Root";
1405			}
1406			$code = templates.getInstanceOf(stName);
1407			$code.add("rule", ruleRefName);
1408			if ( grammar.getRule(ruleRefName)==null )
1409			{
1410				ErrorManager.grammarError(ErrorManager.MSG_UNDEFINED_RULE_REF,
1411										  grammar,
1412										  ((GrammarAST)($r)).getToken(),
1413										  ruleRefName);
1414				$code = new ST(""); // blank; no code gen
1415			}
1416			else if ( grammar.getRule(currentRuleName)
1417						 .getRuleRefsInAlt(ruleRefName,outerAltNum)==null )
1418			{
1419				ErrorManager.grammarError(ErrorManager.MSG_REWRITE_ELEMENT_NOT_PRESENT_ON_LHS,
1420										  grammar,
1421										  ((GrammarAST)($r)).getToken(),
1422										  ruleRefName);
1423				$code = new ST(""); // blank; no code gen
1424			}
1425			else
1426			{
1427				// track all rule refs as we must copy 2nd ref to rule and beyond
1428				if ( !rewriteRuleRefs.contains(ruleRefName) )
1429				{
1430					rewriteRuleRefs.add(ruleRefName);
1431				}
1432			}
1433		}
1434
1435	|
1436		(	^(tk=TOKEN_REF (arg=ARG_ACTION)?)
1437		|	cl=CHAR_LITERAL
1438		|	sl=STRING_LITERAL
1439		)
1440		{
1441			GrammarAST term = $tk;
1442			if (term == null) term = $cl;
1443			if (term == null) term = $sl;
1444			String tokenName = $start.getToken().getText();
1445			String stName = "rewriteTokenRef";
1446			Rule rule = grammar.getRule(currentRuleName);
1447			Collection<String> tokenRefsInAlt = rule.getTokenRefsInAlt(outerAltNum);
1448			boolean createNewNode = !tokenRefsInAlt.contains(tokenName) || $arg!=null;
1449			if ( createNewNode )
1450			{
1451				stName = "rewriteImaginaryTokenRef";
1452			}
1453			if ( isRoot )
1454			{
1455				stName += "Root";
1456			}
1457			$code = templates.getInstanceOf(stName);
1458			$code.add("terminalOptions",term.terminalOptions);
1459			if ( $arg!=null )
1460			{
1461				List args = generator.translateAction(currentRuleName,$arg);
1462				$code.add("args", args);
1463			}
1464			$code.add("elementIndex", ((CommonToken)$start.getToken()).getTokenIndex());
1465			int ttype = grammar.getTokenType(tokenName);
1466			String tok = generator.getTokenTypeAsTargetLabel(ttype);
1467			$code.add("token", tok);
1468			if ( grammar.getTokenType(tokenName)==Label.INVALID )
1469			{
1470				ErrorManager.grammarError(ErrorManager.MSG_UNDEFINED_TOKEN_REF_IN_REWRITE,
1471										  grammar,
1472										  ((GrammarAST)($start)).getToken(),
1473										  tokenName);
1474				$code = new ST(""); // blank; no code gen
1475			}
1476		}
1477
1478	|	LABEL
1479		{
1480			String labelName = $LABEL.text;
1481			Rule rule = grammar.getRule(currentRuleName);
1482			Grammar.LabelElementPair pair = rule.getLabel(labelName);
1483			if ( labelName.equals(currentRuleName) )
1484			{
1485				// special case; ref to old value via $ rule
1486				if ( rule.hasRewrite(outerAltNum) &&
1487					 rule.getRuleRefsInAlt(outerAltNum).contains(labelName) )
1488				{
1489					ErrorManager.grammarError(ErrorManager.MSG_RULE_REF_AMBIG_WITH_RULE_IN_ALT,
1490											  grammar,
1491											  ((GrammarAST)($LABEL)).getToken(),
1492											  labelName);
1493				}
1494				ST labelST = templates.getInstanceOf("prevRuleRootRef");
1495				$code = templates.getInstanceOf("rewriteRuleLabelRef"+(isRoot?"Root":""));
1496				$code.add("label", labelST);
1497			}
1498			else if ( pair==null )
1499			{
1500				ErrorManager.grammarError(ErrorManager.MSG_UNDEFINED_LABEL_REF_IN_REWRITE,
1501										  grammar,
1502										  ((GrammarAST)($LABEL)).getToken(),
1503										  labelName);
1504				$code = new ST("");
1505			}
1506			else
1507			{
1508				String stName = null;
1509				switch ( pair.type )
1510				{
1511				case Grammar.TOKEN_LABEL :
1512					stName = "rewriteTokenLabelRef";
1513					break;
1514				case Grammar.WILDCARD_TREE_LABEL :
1515					stName = "rewriteWildcardLabelRef";
1516					break;
1517				case Grammar.WILDCARD_TREE_LIST_LABEL:
1518					stName = "rewriteRuleListLabelRef"; // acts like rule ref list for ref
1519					break;
1520				case Grammar.RULE_LABEL :
1521					stName = "rewriteRuleLabelRef";
1522					break;
1523				case Grammar.TOKEN_LIST_LABEL :
1524					stName = "rewriteTokenListLabelRef";
1525					break;
1526				case Grammar.RULE_LIST_LABEL :
1527					stName = "rewriteRuleListLabelRef";
1528					break;
1529				}
1530				if ( isRoot )
1531				{
1532					stName += "Root";
1533				}
1534				$code = templates.getInstanceOf(stName);
1535				$code.add("label", labelName);
1536			}
1537		}
1538
1539	|	ACTION
1540		{
1541			// actions in rewrite rules yield a tree object
1542			String actText = $ACTION.text;
1543			List chunks = generator.translateAction(currentRuleName,$ACTION);
1544			$code = templates.getInstanceOf("rewriteNodeAction"+(isRoot?"Root":""));
1545			$code.add("action", chunks);
1546		}
1547	;
1548
1549public
1550rewrite_template returns [ST code=null]
1551	:	^( ALT EPSILON EOA ) {$code=templates.getInstanceOf("rewriteEmptyTemplate");}
1552	|	^(	TEMPLATE (id=ID|ind=ACTION)
1553			{
1554				if ( $id!=null && $id.text.equals("template") )
1555				{
1556						$code = templates.getInstanceOf("rewriteInlineTemplate");
1557				}
1558				else if ( $id!=null )
1559				{
1560						$code = templates.getInstanceOf("rewriteExternalTemplate");
1561						$code.add("name", $id.text);
1562				}
1563				else if ( $ind!=null )
1564				{ // must be \%({expr})(args)
1565					$code = templates.getInstanceOf("rewriteIndirectTemplate");
1566					List chunks=generator.translateAction(currentRuleName,$ind);
1567					$code.add("expr", chunks);
1568				}
1569			}
1570			^(	ARGLIST
1571				(	^( ARG arg=ID a=ACTION
1572					{
1573						// must set alt num here rather than in define.g
1574						// because actions like \%foo(name={\$ID.text}) aren't
1575						// broken up yet into trees.
1576						$a.outerAltNum = this.outerAltNum;
1577						List chunks = generator.translateAction(currentRuleName,$a);
1578						$code.addAggr("args.{name,value}", $arg.text, chunks);
1579					}
1580					)
1581				)*
1582			)
1583			(	DOUBLE_QUOTE_STRING_LITERAL
1584				{
1585					String sl = $DOUBLE_QUOTE_STRING_LITERAL.text;
1586					String t = sl.substring( 1, sl.length() - 1 ); // strip quotes
1587					t = generator.target.getTargetStringLiteralFromString(t);
1588					$code.add("template",t);
1589				}
1590			|	DOUBLE_ANGLE_STRING_LITERAL
1591				{
1592					String sl = $DOUBLE_ANGLE_STRING_LITERAL.text;
1593					String t = sl.substring( 2, sl.length() - 2 ); // strip double angle quotes
1594					t = generator.target.getTargetStringLiteralFromString(t);
1595					$code.add("template",t);
1596				}
1597			)?
1598		)
1599
1600	|	act=ACTION
1601		{
1602			// set alt num for same reason as ARGLIST above
1603			$act.outerAltNum = this.outerAltNum;
1604			$code=templates.getInstanceOf("rewriteAction");
1605			$code.add("action",
1606							  generator.translateAction(currentRuleName,$act));
1607		}
1608	;
1609