1/*
2 [The "BSD license"]
3 Copyright (c) 2005-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/** Build an NFA from a tree representing an ANTLR grammar. */
34tree grammar TreeToNFAConverter;
35
36options {
37	tokenVocab = ANTLR;
38	ASTLabelType = GrammarAST;
39}
40
41@header {
42package org.antlr.grammar.v3;
43
44import org.antlr.analysis.*;
45import org.antlr.misc.*;
46import org.antlr.tool.*;
47
48import org.antlr.runtime.BitSet;
49import org.antlr.runtime.DFA;
50}
51
52@members {
53/** Factory used to create nodes and submachines */
54protected NFAFactory factory = null;
55
56/** Which NFA object are we filling in? */
57protected NFA nfa = null;
58
59/** Which grammar are we converting an NFA for? */
60protected Grammar grammar = null;
61
62protected String currentRuleName = null;
63
64protected int outerAltNum = 0;
65protected int blockLevel = 0;
66
67protected int inTest = 0;
68
69public TreeToNFAConverter(TreeNodeStream input, Grammar g, NFA nfa, NFAFactory factory) {
70    this(input);
71    this.grammar = g;
72    this.nfa = nfa;
73    this.factory = factory;
74}
75
76public final IntSet setRule(GrammarAST t) throws RecognitionException {
77    TreeToNFAConverter other = new TreeToNFAConverter( new CommonTreeNodeStream( t ), grammar, nfa, factory );
78
79    other.currentRuleName = currentRuleName;
80    other.outerAltNum = outerAltNum;
81    other.blockLevel = blockLevel;
82
83    return other.setRule();
84}
85
86public final int testBlockAsSet( GrammarAST t ) throws RecognitionException {
87    Rule r = grammar.getLocallyDefinedRule( currentRuleName );
88    if ( r.hasRewrite( outerAltNum ) )
89        return -1;
90
91    TreeToNFAConverter other = new TreeToNFAConverter( new CommonTreeNodeStream( t ), grammar, nfa, factory );
92
93    other.state.backtracking++;
94    other.currentRuleName = currentRuleName;
95    other.outerAltNum = outerAltNum;
96    other.blockLevel = blockLevel;
97
98    int result = other.testBlockAsSet();
99    if ( other.state.failed )
100        return -1;
101
102    return result;
103}
104
105public final int testSetRule( GrammarAST t ) throws RecognitionException {
106    TreeToNFAConverter other = new TreeToNFAConverter( new CommonTreeNodeStream( t ), grammar, nfa, factory );
107
108    other.state.backtracking++;
109    other.currentRuleName = currentRuleName;
110    other.outerAltNum = outerAltNum;
111    other.blockLevel = blockLevel;
112
113    int result = other.testSetRule();
114    if ( other.state.failed )
115        state.failed = true;
116
117    return result;
118}
119
120protected void addFollowTransition( String ruleName, NFAState following ) {
121    //System.Console.Out.WriteLine( "adding follow link to rule " + ruleName );
122    // find last link in FOLLOW chain emanating from rule
123    Rule r = grammar.getRule( ruleName );
124    NFAState end = r.stopState;
125    while ( end.transition( 1 ) != null )
126    {
127        end = (NFAState)end.transition( 1 ).target;
128    }
129    if ( end.transition( 0 ) != null )
130    {
131        // already points to a following node
132        // gotta add another node to keep edges to a max of 2
133        NFAState n = factory.newState();
134        Transition e = new Transition( Label.EPSILON, n );
135        end.addTransition( e );
136        end = n;
137    }
138    Transition followEdge = new Transition( Label.EPSILON, following );
139    end.addTransition( followEdge );
140}
141
142protected void finish() {
143    int numEntryPoints = factory.build_EOFStates( grammar.getRules() );
144    if ( numEntryPoints == 0 )
145    {
146        ErrorManager.grammarWarning( ErrorManager.MSG_NO_GRAMMAR_START_RULE,
147                                   grammar,
148                                   null,
149                                   grammar.name );
150    }
151}
152
153@Override
154public void reportError(RecognitionException ex) {
155    if ( inTest > 0 )
156        throw new IllegalStateException(ex);
157
158    Token token = null;
159    if ( ex instanceof MismatchedTokenException )
160    {
161        token = ( (MismatchedTokenException)ex ).token;
162    }
163    else if ( ex instanceof NoViableAltException )
164    {
165        token = ( (NoViableAltException)ex ).token;
166    }
167
168    ErrorManager.syntaxError(
169        ErrorManager.MSG_SYNTAX_ERROR,
170        grammar,
171        token,
172        "buildnfa: " + ex.toString(),
173        ex );
174}
175
176private boolean hasElementOptions(GrammarAST node) {
177    if (node == null)
178        throw new NullPointerException("node");
179    return node.terminalOptions != null && node.terminalOptions.size() > 0;
180}
181}
182
183public
184grammar_
185@after
186{
187	finish();
188}
189	:	(	^( LEXER_GRAMMAR grammarSpec )
190		|	^( PARSER_GRAMMAR grammarSpec )
191		|	^( TREE_GRAMMAR grammarSpec )
192		|	^( COMBINED_GRAMMAR grammarSpec )
193		)
194	;
195
196attrScope
197	:	^( 'scope' ID ( ^(AMPERSAND .*) )* ACTION )
198	;
199
200grammarSpec
201	:	ID
202		(cmt=DOC_COMMENT)?
203		( ^(OPTIONS .*) )?
204		( ^(IMPORT .*) )?
205		( ^(TOKENS .*) )?
206		(attrScope)*
207		( ^(AMPERSAND .*) )* // skip actions
208		rules
209	;
210
211rules
212	:	(rule | ^(PREC_RULE .*))+
213	;
214
215rule
216	:	^(	RULE id=ID
217			{
218				currentRuleName = $id.text;
219				factory.setCurrentRule(grammar.getLocallyDefinedRule(currentRuleName));
220			}
221			(modifier)?
222			^(ARG (ARG_ACTION)?)
223			^(RET (ARG_ACTION)?)
224			(throwsSpec)?
225			( ^(OPTIONS .*) )?
226			( ruleScopeSpec )?
227			( ^(AMPERSAND .*) )*
228			b=block
229			(exceptionGroup)?
230			EOR
231			{
232				StateCluster g = $b.g;
233				if ($b.start.getSetValue() != null)
234				{
235					// if block comes back as a set not BLOCK, make it
236					// a single ALT block
237					g = factory.build_AlternativeBlockFromSet(g);
238				}
239				if (Rule.getRuleType(currentRuleName) == Grammar.PARSER || grammar.type==Grammar.LEXER)
240				{
241					// attach start node to block for this rule
242					Rule thisR = grammar.getLocallyDefinedRule(currentRuleName);
243					NFAState start = thisR.startState;
244					start.associatedASTNode = $id;
245					start.addTransition(new Transition(Label.EPSILON, g.left));
246
247					// track decision if > 1 alts
248					if ( grammar.getNumberOfAltsForDecisionNFA(g.left)>1 )
249					{
250						g.left.setDescription(grammar.grammarTreeToString($start, false));
251						g.left.setDecisionASTNode($b.start);
252						int d = grammar.assignDecisionNumber( g.left );
253						grammar.setDecisionNFA( d, g.left );
254						grammar.setDecisionBlockAST(d, $b.start);
255					}
256
257					// hook to end of rule node
258					NFAState end = thisR.stopState;
259					g.right.addTransition(new Transition(Label.EPSILON,end));
260				}
261			}
262		)
263	;
264
265modifier
266	:	'protected'
267	|	'public'
268	|	'private'
269	|	'fragment'
270	;
271
272throwsSpec
273	:	^('throws' ID+)
274	;
275
276ruleScopeSpec
277	:	^( 'scope' ( ^(AMPERSAND .*) )* (ACTION)? ( ID )* )
278	;
279
280block returns [StateCluster g = null]
281@init
282{
283	List<StateCluster> alts = new ArrayList<StateCluster>();
284	this.blockLevel++;
285	if ( this.blockLevel==1 )
286		this.outerAltNum=1;
287}
288	:	{grammar.isValidSet(this,$start) &&
289		 !currentRuleName.equals(Grammar.ARTIFICIAL_TOKENS_RULENAME)}? =>
290		set {$g = $set.g;}
291
292	|	^(	BLOCK ( ^(OPTIONS .*) )?
293			(	a=alternative rewrite
294				{
295					alts.add($a.g);
296				}
297				{{
298					if ( blockLevel == 1 )
299						outerAltNum++;
300				}}
301			)+
302			EOB
303		)
304		{$g = factory.build_AlternativeBlock(alts);}
305	;
306finally { blockLevel--; }
307
308alternative returns [StateCluster g=null]
309	:	^( ALT (e=element {$g = factory.build_AB($g,$e.g);} )+ EOA )
310		{
311			if ($g==null) { // if alt was a list of actions or whatever
312				$g = factory.build_Epsilon();
313			}
314			else {
315				factory.optimizeAlternative($g);
316			}
317		}
318	;
319
320exceptionGroup
321	:	( exceptionHandler )+ (finallyClause)?
322	|	finallyClause
323	;
324
325exceptionHandler
326	:    ^('catch' ARG_ACTION ACTION)
327	;
328
329finallyClause
330	:    ^('finally' ACTION)
331	;
332
333rewrite
334	:	^(	REWRITES
335			(
336				{
337					if ( grammar.getOption("output")==null )
338					{
339						ErrorManager.grammarError(ErrorManager.MSG_REWRITE_OR_OP_WITH_NO_OUTPUT_OPTION,
340												  grammar, $start.getToken(), currentRuleName);
341					}
342				}
343				^(REWRITE .*)
344			)*
345		)
346	|
347	;
348
349element returns [StateCluster g=null]
350	:   ^(ROOT e=element {$g = $e.g;})
351	|   ^(BANG e=element {$g = $e.g;})
352	|	^(ASSIGN ID e=element {$g = $e.g;})
353	|	^(PLUS_ASSIGN ID e=element {$g = $e.g;})
354	|   ^(RANGE a=atom[null] b=atom[null])
355		{$g = factory.build_Range(grammar.getTokenType($a.text),
356								 grammar.getTokenType($b.text));}
357	|   ^(CHAR_RANGE c1=CHAR_LITERAL c2=CHAR_LITERAL)
358		{
359		if ( grammar.type==Grammar.LEXER ) {
360			$g = factory.build_CharRange($c1.text, $c2.text);
361		}
362		}
363	|   atom_or_notatom {$g = $atom_or_notatom.g;}
364	|   ebnf {$g = $ebnf.g;}
365	|   tree_ {$g = $tree_.g;}
366	|   ^( SYNPRED block )
367	|   ACTION {$g = factory.build_Action($ACTION);}
368	|   FORCED_ACTION {$g = factory.build_Action($FORCED_ACTION);}
369	|   pred=SEMPRED {$g = factory.build_SemanticPredicate($pred);}
370	|   spred=SYN_SEMPRED {$g = factory.build_SemanticPredicate($spred);}
371	|   ^(bpred=BACKTRACK_SEMPRED .*) {$g = factory.build_SemanticPredicate($bpred);}
372	|   gpred=GATED_SEMPRED {$g = factory.build_SemanticPredicate($gpred);}
373	|   EPSILON {$g = factory.build_Epsilon();}
374	;
375
376ebnf returns [StateCluster g=null]
377@init
378{
379	GrammarAST blk = $start;
380	if (blk.getType() != BLOCK) {
381		blk = (GrammarAST)blk.getChild(0);
382	}
383	GrammarAST eob = blk.getLastChild();
384}
385	:	{grammar.isValidSet(this,$start)}? => set {$g = $set.g;}
386
387	|	b=block
388		{
389			// track decision if > 1 alts
390			if ( grammar.getNumberOfAltsForDecisionNFA($b.g.left)>1 )
391			{
392				$b.g.left.setDescription(grammar.grammarTreeToString(blk, false));
393				$b.g.left.setDecisionASTNode(blk);
394				int d = grammar.assignDecisionNumber( $b.g.left );
395				grammar.setDecisionNFA( d, $b.g.left );
396				grammar.setDecisionBlockAST(d, blk);
397			}
398			$g = $b.g;
399		}
400	|	^( OPTIONAL b=block )
401		{
402			StateCluster bg = $b.g;
403			if ( blk.getSetValue()!=null )
404			{
405				// if block comes back SET not BLOCK, make it
406				// a single ALT block
407				bg = factory.build_AlternativeBlockFromSet(bg);
408			}
409			$g = factory.build_Aoptional(bg);
410			$g.left.setDescription(grammar.grammarTreeToString($start, false));
411			// there is always at least one alt even if block has just 1 alt
412			int d = grammar.assignDecisionNumber( $g.left );
413			grammar.setDecisionNFA(d, $g.left);
414			grammar.setDecisionBlockAST(d, blk);
415			$g.left.setDecisionASTNode($start);
416		}
417	|	^( CLOSURE b=block )
418		{
419			StateCluster bg = $b.g;
420			if ( blk.getSetValue()!=null )
421			{
422				bg = factory.build_AlternativeBlockFromSet(bg);
423			}
424			$g = factory.build_Astar(bg);
425			// track the loop back / exit decision point
426			bg.right.setDescription("()* loopback of "+grammar.grammarTreeToString($start, false));
427			int d = grammar.assignDecisionNumber( bg.right );
428			grammar.setDecisionNFA(d, bg.right);
429			grammar.setDecisionBlockAST(d, blk);
430			bg.right.setDecisionASTNode(eob);
431			// make block entry state also have same decision for interpreting grammar
432			NFAState altBlockState = (NFAState)$g.left.transition(0).target;
433			altBlockState.setDecisionASTNode($start);
434			altBlockState.setDecisionNumber(d);
435			$g.left.setDecisionNumber(d); // this is the bypass decision (2 alts)
436			$g.left.setDecisionASTNode($start);
437		}
438	|	^( POSITIVE_CLOSURE b=block )
439		{
440			StateCluster bg = $b.g;
441			if ( blk.getSetValue()!=null )
442			{
443				bg = factory.build_AlternativeBlockFromSet(bg);
444			}
445			$g = factory.build_Aplus(bg);
446			// don't make a decision on left edge, can reuse loop end decision
447			// track the loop back / exit decision point
448			bg.right.setDescription("()+ loopback of "+grammar.grammarTreeToString($start, false));
449			int d = grammar.assignDecisionNumber( bg.right );
450			grammar.setDecisionNFA(d, bg.right);
451			grammar.setDecisionBlockAST(d, blk);
452			bg.right.setDecisionASTNode(eob);
453			// make block entry state also have same decision for interpreting grammar
454			NFAState altBlockState = (NFAState)$g.left.transition(0).target;
455			altBlockState.setDecisionASTNode($start);
456			altBlockState.setDecisionNumber(d);
457		}
458	;
459
460tree_ returns [StateCluster g=null]
461@init
462{
463	StateCluster down=null, up=null;
464}
465	:	^(	TREE_BEGIN
466			e=element { $g = $e.g; }
467			{
468				down = factory.build_Atom(Label.DOWN, $e.start);
469				// TODO set following states for imaginary nodes?
470				//el.followingNFAState = down.right;
471				$g = factory.build_AB($g,down);
472			}
473			( e=element {$g = factory.build_AB($g,$e.g);} )*
474			{
475				up = factory.build_Atom(Label.UP, $e.start);
476				//el.followingNFAState = up.right;
477				$g = factory.build_AB($g,up);
478				// tree roots point at right edge of DOWN for LOOK computation later
479				$start.NFATreeDownState = down.left;
480			}
481		)
482	;
483
484atom_or_notatom returns [StateCluster g=null]
485	:	atom[null] {$g = $atom.g;}
486	|	^(	n=NOT
487			(	c=CHAR_LITERAL (ast1=ast_suffix)?
488				{
489					int ttype=0;
490					if ( grammar.type==Grammar.LEXER )
491					{
492						ttype = Grammar.getCharValueFromGrammarCharLiteral($c.text);
493					}
494					else
495					{
496						ttype = grammar.getTokenType($c.text);
497					}
498					IntSet notAtom = grammar.complement(ttype);
499					if ( notAtom.isNil() )
500					{
501						ErrorManager.grammarError(
502							ErrorManager.MSG_EMPTY_COMPLEMENT,
503							grammar,
504							$c.getToken(),
505							$c.text);
506					}
507					$g=factory.build_Set(notAtom,$n);
508				}
509			|	t=TOKEN_REF (ast3=ast_suffix)?
510				{
511					int ttype=0;
512					IntSet notAtom = null;
513					if ( grammar.type==Grammar.LEXER )
514					{
515						notAtom = grammar.getSetFromRule(this,$t.text);
516						if ( notAtom==null )
517						{
518							ErrorManager.grammarError(
519								ErrorManager.MSG_RULE_INVALID_SET,
520								grammar,
521								$t.getToken(),
522								$t.text);
523						}
524						else
525						{
526							notAtom = grammar.complement(notAtom);
527						}
528					}
529					else
530					{
531						ttype = grammar.getTokenType($t.text);
532						notAtom = grammar.complement(ttype);
533					}
534					if ( notAtom==null || notAtom.isNil() )
535					{
536						ErrorManager.grammarError(
537							ErrorManager.MSG_EMPTY_COMPLEMENT,
538							grammar,
539							$t.getToken(),
540							$t.text);
541					}
542					$g=factory.build_Set(notAtom,$n);
543				}
544			|	set {$g = $set.g;}
545				{
546					GrammarAST stNode = (GrammarAST)$n.getChild(0);
547					//IntSet notSet = grammar.complement(stNode.getSetValue());
548					// let code generator complement the sets
549					IntSet s = stNode.getSetValue();
550					stNode.setSetValue(s);
551					// let code gen do the complement again; here we compute
552					// for NFA construction
553					s = grammar.complement(s);
554					if ( s.isNil() )
555					{
556						ErrorManager.grammarError(
557							ErrorManager.MSG_EMPTY_COMPLEMENT,
558							grammar,
559							$n.getToken());
560					}
561					$g=factory.build_Set(s,$n);
562				}
563			)
564			{$n.followingNFAState = $g.right;}
565		)
566	;
567
568atom[String scopeName] returns [StateCluster g=null]
569	:	^( r=RULE_REF (rarg=ARG_ACTION)? (as1=ast_suffix)? )
570		{
571			NFAState start = grammar.getRuleStartState(scopeName,$r.text);
572			if ( start!=null )
573			{
574				Rule rr = grammar.getRule(scopeName,$r.text);
575				$g = factory.build_RuleRef(rr, start);
576				r.followingNFAState = $g.right;
577				r.NFAStartState = $g.left;
578				if ( $g.left.transition(0) instanceof RuleClosureTransition
579					&& grammar.type!=Grammar.LEXER )
580				{
581					addFollowTransition($r.text, $g.right);
582				}
583				// else rule ref got inlined to a set
584			}
585		}
586
587	|	^( t=TOKEN_REF  (targ=ARG_ACTION)? (as2=ast_suffix)? )
588		{
589			if ( grammar.type==Grammar.LEXER )
590			{
591				NFAState start = grammar.getRuleStartState(scopeName,$t.text);
592				if ( start!=null )
593				{
594					Rule rr = grammar.getRule(scopeName,t.getText());
595					$g = factory.build_RuleRef(rr, start);
596					t.NFAStartState = $g.left;
597					// don't add FOLLOW transitions in the lexer;
598					// only exact context should be used.
599				}
600			}
601			else
602			{
603				$g = factory.build_Atom(t);
604				t.followingNFAState = $g.right;
605			}
606		}
607
608	|	^( c=CHAR_LITERAL  (as3=ast_suffix)? )
609		{
610			if ( grammar.type==Grammar.LEXER )
611			{
612				$g = factory.build_CharLiteralAtom(c);
613			}
614			else
615			{
616				$g = factory.build_Atom(c);
617				c.followingNFAState = $g.right;
618			}
619		}
620
621	|	^( s=STRING_LITERAL  (as4=ast_suffix)? )
622		{
623			if ( grammar.type==Grammar.LEXER )
624			{
625				$g = factory.build_StringLiteralAtom(s);
626			}
627			else
628			{
629				$g = factory.build_Atom(s);
630				s.followingNFAState = $g.right;
631			}
632		}
633
634	|	^(	w=WILDCARD (as5=ast_suffix)? )
635			{
636				if ( nfa.grammar.type == Grammar.TREE_PARSER
637					&& (w.getChildIndex() > 0 || w.getParent().getChild(1).getType() == EOA) )
638				{
639					$g = factory.build_WildcardTree( $w );
640				}
641				else
642				{
643					$g = factory.build_Wildcard( $w );
644				}
645			}
646
647	|	^( DOT scope_=ID a=atom[$scope_.text] {$g = $a.g;} ) // scope override
648	;
649
650ast_suffix
651	:	ROOT
652	|	BANG
653	;
654
655set returns [StateCluster g=null]
656@init
657{
658	IntSet elements=new IntervalSet();
659	if ( state.backtracking == 0 )
660		$start.setSetValue(elements); // track set for use by code gen
661}
662	:	^( b=BLOCK
663		   (^(ALT ( ^(BACKTRACK_SEMPRED .*) )? setElement[elements] EOA))+
664		   EOB
665		 )
666		{
667		$g = factory.build_Set(elements,$b);
668		$b.followingNFAState = $g.right;
669		$b.setSetValue(elements); // track set value of this block
670		}
671		//{System.out.println("set elements="+elements.toString(grammar));}
672	;
673
674setRule returns [IntSet elements=new IntervalSet()]
675@init
676{
677	IntSet s=null;
678}
679	:	^( RULE id=ID (modifier)? ARG RET ( ^(OPTIONS .*) )? ( ruleScopeSpec )?
680			( ^(AMPERSAND .*) )*
681			^( BLOCK ( ^(OPTIONS .*) )?
682			   ( ^(ALT (BACKTRACK_SEMPRED)? setElement[elements] EOA) )+
683			   EOB
684			 )
685			(exceptionGroup)?
686			EOR
687		 )
688	;
689catch[RecognitionException re] { throw re; }
690
691setElement[IntSet elements]
692@init
693{
694	int ttype;
695	IntSet ns=null;
696}
697	:	c=CHAR_LITERAL
698		{
699			if ( grammar.type==Grammar.LEXER )
700			{
701				ttype = Grammar.getCharValueFromGrammarCharLiteral($c.text);
702			}
703			else
704			{
705				ttype = grammar.getTokenType($c.text);
706			}
707			if ( elements.member(ttype) )
708			{
709				ErrorManager.grammarError(
710					ErrorManager.MSG_DUPLICATE_SET_ENTRY,
711					grammar,
712					$c.getToken(),
713					$c.text);
714			}
715			elements.add(ttype);
716		}
717	|	t=TOKEN_REF
718		{
719			if ( grammar.type==Grammar.LEXER )
720			{
721				// recursively will invoke this rule to match elements in target rule ref
722				IntSet ruleSet = grammar.getSetFromRule(this,$t.text);
723				if ( ruleSet==null )
724				{
725					ErrorManager.grammarError(
726						ErrorManager.MSG_RULE_INVALID_SET,
727						grammar,
728						$t.getToken(),
729						$t.text);
730				}
731				else
732				{
733					elements.addAll(ruleSet);
734				}
735			}
736			else
737			{
738				ttype = grammar.getTokenType($t.text);
739				if ( elements.member(ttype) )
740				{
741					ErrorManager.grammarError(
742						ErrorManager.MSG_DUPLICATE_SET_ENTRY,
743						grammar,
744						$t.getToken(),
745						$t.text);
746				}
747				elements.add(ttype);
748			}
749		}
750
751	|	s=STRING_LITERAL
752		{
753			ttype = grammar.getTokenType($s.text);
754			if ( elements.member(ttype) )
755			{
756				ErrorManager.grammarError(
757					ErrorManager.MSG_DUPLICATE_SET_ENTRY,
758					grammar,
759					$s.getToken(),
760					$s.text);
761			}
762			elements.add(ttype);
763		}
764	|	^(CHAR_RANGE c1=CHAR_LITERAL c2=CHAR_LITERAL)
765		{
766			if ( grammar.type==Grammar.LEXER )
767			{
768				int a = Grammar.getCharValueFromGrammarCharLiteral($c1.text);
769				int b = Grammar.getCharValueFromGrammarCharLiteral($c2.text);
770				elements.addAll(IntervalSet.of(a,b));
771			}
772		}
773
774	|	gset=set
775		{
776			Transition setTrans = $gset.g.left.transition(0);
777			elements.addAll(setTrans.label.getSet());
778		}
779
780	|	^(	NOT {ns=new IntervalSet();}
781			setElement[ns]
782			{
783				IntSet not = grammar.complement(ns);
784				elements.addAll(not);
785			}
786		)
787	;
788
789/** Check to see if this block can be a set.  Can't have actions
790 *  etc...  Also can't be in a rule with a rewrite as we need
791 *  to track what's inside set for use in rewrite.
792 *
793 *  This should only be called from the helper function in TreeToNFAConverterHelper.cs
794 *  and from the rule testSetElement below.
795 */
796testBlockAsSet returns [int alts=0]
797options { backtrack = true; }
798@init
799{
800	inTest++;
801}
802	:	^(	BLOCK
803			(	^(ALT (BACKTRACK_SEMPRED)? testSetElement {{$alts += $testSetElement.alts;}} EOA)
804			)+
805			EOB
806		)
807	;
808catch[RecognitionException re] { throw re; }
809finally { inTest--; }
810
811testSetRule returns [int alts=0]
812@init
813{
814	inTest++;
815}
816	:	^(	RULE id=ID (modifier)? ARG RET ( ^(OPTIONS .*) )? ( ruleScopeSpec )?
817			( ^(AMPERSAND .*) )*
818			^(	BLOCK
819				(	^(ALT (BACKTRACK_SEMPRED)? testSetElement {{$alts += $testSetElement.alts;}} EOA)
820				)+
821				EOB
822			)
823			(exceptionGroup)?
824			EOR
825		)
826	;
827catch[RecognitionException re] { throw re; }
828finally { inTest--; }
829
830/** Match just an element; no ast suffix etc.. */
831testSetElement returns [int alts=1]
832	:	c=CHAR_LITERAL {!hasElementOptions($c)}?
833	|	t=TOKEN_REF {!hasElementOptions($t)}?
834		{{
835			if ( grammar.type==Grammar.LEXER )
836			{
837				Rule rule = grammar.getRule($t.text);
838				if ( rule==null )
839				{
840					//throw new RecognitionException("invalid rule");
841					throw new RecognitionException();
842				}
843				// recursively will invoke this rule to match elements in target rule ref
844				$alts += testSetRule(rule.tree);
845			}
846		}}
847	|   {grammar.type!=Grammar.LEXER}? => s=STRING_LITERAL
848	|	^(CHAR_RANGE c1=CHAR_LITERAL c2=CHAR_LITERAL)
849		{{ $alts = IntervalSet.of( Grammar.getCharValueFromGrammarCharLiteral($c1.text), Grammar.getCharValueFromGrammarCharLiteral($c2.text) ).size(); }}
850	|   testBlockAsSet
851		{{ $alts = $testBlockAsSet.alts; }}
852	|   ^( NOT tse=testSetElement )
853		{{ $alts = grammar.getTokenTypes().size() - $tse.alts; }}
854	;
855catch[RecognitionException re] { throw re; }
856