xref: /aosp_15_r20/external/antlr/tool/src/main/antlr3/org/antlr/grammar/v3/LeftRecursiveRuleWalker.g (revision 16467b971bd3e2009fad32dd79016f2c7e421deb) 
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/** Find left-recursive rules */
34tree grammar LeftRecursiveRuleWalker;
35
36options {
37	language=Java;
38	tokenVocab=ANTLR;
39    ASTLabelType=GrammarAST;
40}
41
42@header {
43package org.antlr.grammar.v3;
44
45import org.antlr.analysis.*;
46import org.antlr.misc.*;
47import org.antlr.tool.*;
48
49import org.antlr.runtime.BitSet;
50import org.antlr.runtime.DFA;
51}
52
53@members {
54protected Grammar grammar;
55private String ruleName;
56private int outerAlt; // which outer alt of rule?
57public int numAlts;  // how many alts for this rule total?
58
59@Override
60public void reportError(RecognitionException ex)
61{
62    Token token = null;
63    if (ex instanceof MismatchedTokenException)
64    {
65        token = ((MismatchedTokenException)ex).token;
66    }
67    else if (ex instanceof NoViableAltException)
68    {
69        token = ((NoViableAltException)ex).token;
70    }
71
72    ErrorManager.syntaxError(
73        ErrorManager.MSG_SYNTAX_ERROR,
74        grammar,
75        token,
76        "assign.types: " + ex.toString(),
77        ex);
78}
79
80public void setTokenPrec(GrammarAST t, int alt) {}
81public void binaryAlt(GrammarAST altTree, GrammarAST rewriteTree, int alt) {}
82public void ternaryAlt(GrammarAST altTree, GrammarAST rewriteTree, int alt) {}
83public void prefixAlt(GrammarAST altTree, GrammarAST rewriteTree, int alt) {}
84public void suffixAlt(GrammarAST altTree, GrammarAST rewriteTree, int alt) {}
85public void otherAlt(GrammarAST altTree, GrammarAST rewriteTree, int alt) {}
86public void setReturnValues(GrammarAST t) {}
87}
88
89optionsSpec
90	:	^(OPTIONS option+)
91	;
92
93option
94	:	^(ASSIGN ID optionValue)
95	;
96
97optionValue
98	:	ID
99	|	STRING_LITERAL
100	|	CHAR_LITERAL
101	|	INT
102	;
103
104charSetElement
105	:	CHAR_LITERAL
106	|	^(OR CHAR_LITERAL CHAR_LITERAL)
107	|	^(RANGE CHAR_LITERAL CHAR_LITERAL)
108	;
109
110public
111rec_rule[Grammar g] returns [boolean isLeftRec]
112@init
113{
114	grammar = g;
115	outerAlt = 1;
116}
117	:	^(	r=RULE id=ID {ruleName=$id.getText();}
118			modifier?
119			^(ARG ARG_ACTION?)
120			^(RET ARG_ACTION?)
121			optionsSpec?
122			ruleScopeSpec?
123			(^(AMPERSAND .*))*
124			ruleBlock {$isLeftRec = $ruleBlock.isLeftRec;}
125			exceptionGroup?
126			EOR
127		)
128		{if ($ruleBlock.isLeftRec) $r.setType(PREC_RULE);}
129	;
130
131modifier
132	:	'protected'
133	|	'public'
134	|	'private'
135	|	'fragment'
136	;
137
138ruleScopeSpec
139 	:	^('scope' ACTION? ID*)
140 	;
141
142ruleBlock returns [boolean isLeftRec]
143@init{boolean lr=false; this.numAlts = $start.getChildCount();}
144	:	^(	BLOCK
145			optionsSpec?
146			(	outerAlternative
147				{if ($outerAlternative.isLeftRec) $isLeftRec = true;}
148				rewrite?
149				{outerAlt++;}
150			)+
151			EOB
152		)
153	;
154
155block
156    :   ^(  BLOCK
157            optionsSpec?
158            ( ^(ALT element+ EOA) rewrite? )+
159            EOB
160         )
161    ;
162
163/** An alt is either prefix, suffix, binary, or ternary operation or "other" */
164outerAlternative returns [boolean isLeftRec]
165@init
166{
167GrammarAST rew = $start.getNextSibling();
168if (rew.getType() != REWRITES)
169	rew = null;
170}
171    :   (binaryMultipleOp)=> binaryMultipleOp
172                             {binaryAlt($start, rew, outerAlt); $isLeftRec=true;}
173    |   (binary)=>           binary
174                             {binaryAlt($start, rew, outerAlt); $isLeftRec=true;}
175    |   (ternary)=>          ternary
176                             {ternaryAlt($start, rew, outerAlt); $isLeftRec=true;}
177    |   (prefix)=>           prefix
178                             {prefixAlt($start, rew, outerAlt);}
179    |   (suffix)=>           suffix
180                             {suffixAlt($start, rew, outerAlt); $isLeftRec=true;}
181    |   ^(ALT element+ EOA) // "other" case
182                             {otherAlt($start, rew, outerAlt);}
183    ;
184
185binary
186	:	^( ALT (^(BACKTRACK_SEMPRED .*))? recurseNoLabel op=token recurse EOA ) {setTokenPrec($op.t, outerAlt);}
187	;
188
189binaryMultipleOp
190	:	^( ALT (^(BACKTRACK_SEMPRED .*))? recurseNoLabel ^( BLOCK ( ^( ALT op=token EOA {setTokenPrec($op.t, outerAlt);} ) )+ EOB ) recurse EOA )
191	;
192
193ternary
194	:	^( ALT (^(BACKTRACK_SEMPRED .*))? recurseNoLabel op=token recurse token recurse EOA ) {setTokenPrec($op.t, outerAlt);}
195	;
196
197prefix : ^( ALT (^(BACKTRACK_SEMPRED .*))? {setTokenPrec((GrammarAST)input.LT(1), outerAlt);} ({!((CommonTree)input.LT(1)).getText().equals(ruleName)}? element)+ recurse EOA ) ;
198
199suffix : ^( ALT (^(BACKTRACK_SEMPRED .*))? recurseNoLabel {setTokenPrec((GrammarAST)input.LT(1), outerAlt);} element+  EOA ) ;
200
201recurse
202	:	^(ASSIGN ID recurseNoLabel)
203	|	^(PLUS_ASSIGN ID recurseNoLabel)
204	|	recurseNoLabel
205	;
206
207recurseNoLabel : {((CommonTree)input.LT(1)).getText().equals(ruleName)}? RULE_REF;
208
209/*
210elementNotRecursiveRule
211    :   {_t.findFirstType(RULE_REF)!=null && _t.findFirstType(RULE_REF).getText().equals(ruleName)}?
212        e:element
213    ;
214*/
215
216token returns [GrammarAST t=null]
217	:	^(ASSIGN ID s=token {$t = $s.t;})
218	|	^(PLUS_ASSIGN ID s=token {$t = $s.t;})
219	|	^(ROOT s=token {$t = $s.t;})
220	|	^(BANG s=token {$t = $s.t;})
221	|	a=CHAR_LITERAL      {$t = $a;}
222	|	b=STRING_LITERAL    {$t = $b;}
223	|	c=TOKEN_REF         {$t = $c;}
224	;
225
226exceptionGroup
227	:	exceptionHandler+ finallyClause?
228	|	finallyClause
229    ;
230
231exceptionHandler
232	:	^('catch' ARG_ACTION ACTION)
233	;
234
235finallyClause
236	:	^('finally' ACTION)
237	;
238
239rewrite
240	:	^(REWRITES ( ^( REWRITE SEMPRED? (^(ALT .*)|^(TEMPLATE .*)|ACTION|ETC) ) )* )
241	;
242
243element
244	:	^(ROOT element)
245	|	^(BANG element)
246	|	atom
247	|	^(NOT element)
248	|	^(RANGE atom atom)
249	|	^(ASSIGN ID element)
250	|	^(PLUS_ASSIGN ID element)
251	|	ebnf
252	|	tree_
253	|	^(SYNPRED block)
254	|	FORCED_ACTION
255	|	ACTION
256	|	SEMPRED
257	|	SYN_SEMPRED
258	|	BACKTRACK_SEMPRED
259	|	GATED_SEMPRED
260	|	EPSILON
261	;
262
263ebnf:   block
264    |   ^( OPTIONAL block )
265    |   ^( CLOSURE block )
266    |   ^( POSITIVE_CLOSURE block )
267    ;
268
269tree_
270	:	^(TREE_BEGIN element+)
271	;
272
273atom
274	:	^(RULE_REF ARG_ACTION?)
275	|	^(TOKEN_REF ARG_ACTION?)
276	|	CHAR_LITERAL
277	|	STRING_LITERAL
278	|	WILDCARD
279	|	^(DOT ID atom) // scope override on rule
280	;
281
282ast_suffix
283	:	ROOT
284	|	BANG
285	;
286