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