1 /* 2 * [The "BSD license"] 3 * Copyright (c) 2010 Terence Parr 4 * All rights reserved. 5 * 6 * Redistribution and use in source and binary forms, with or without 7 * modification, are permitted provided that the following conditions 8 * are met: 9 * 1. Redistributions of source code must retain the above copyright 10 * notice, this list of conditions and the following disclaimer. 11 * 2. Redistributions in binary form must reproduce the above copyright 12 * notice, this list of conditions and the following disclaimer in the 13 * documentation and/or other materials provided with the distribution. 14 * 3. The name of the author may not be used to endorse or promote products 15 * derived from this software without specific prior written permission. 16 * 17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 22 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27 */ 28 package org.antlr.tool; 29 30 import org.antlr.analysis.NFAState; 31 import org.antlr.codegen.CodeGenerator; 32 import org.antlr.grammar.v3.ANTLRParser; 33 import org.antlr.runtime.CommonToken; 34 import org.antlr.runtime.Token; 35 36 import java.util.*; 37 38 /** Combine the info associated with a rule. */ 39 public class Rule { 40 public static final boolean supportsLabelOptimization; 41 static { 42 supportsLabelOptimization = false; 43 } 44 45 public String name; 46 public int index; 47 public String modifier; 48 public NFAState startState; 49 public NFAState stopState; 50 51 /** This rule's options */ 52 protected Map<String, Object> options; 53 54 public static final Set<String> legalOptions = 55 new HashSet<String>() { 56 { 57 add("k"); add("greedy"); add("memoize"); 58 add("backtrack"); 59 } 60 }; 61 62 /** The AST representing the whole rule */ 63 public GrammarAST tree; 64 65 /** To which grammar does this belong? */ 66 public Grammar grammar; 67 68 /** For convenience, track the argument def AST action node if any */ 69 public GrammarAST argActionAST; 70 71 public GrammarAST EORNode; 72 73 /** The return values of a rule and predefined rule attributes */ 74 public AttributeScope returnScope; 75 76 public AttributeScope parameterScope; 77 78 /** the attributes defined with "scope {...}" inside a rule */ 79 public AttributeScope ruleScope; 80 81 /** A list of scope names (String) used by this rule */ 82 public List<String> useScopes; 83 84 /** Exceptions that this rule can throw */ 85 public Set<String> throwsSpec; 86 87 /** A list of all LabelElementPair attached to tokens like id=ID */ 88 public LinkedHashMap<String, Grammar.LabelElementPair> tokenLabels; 89 90 /** A list of all LabelElementPair attached to tokens like x=. in tree grammar */ 91 public LinkedHashMap<String, Grammar.LabelElementPair> wildcardTreeLabels; 92 93 /** A list of all LabelElementPair attached to tokens like x+=. in tree grammar */ 94 public LinkedHashMap<String, Grammar.LabelElementPair> wildcardTreeListLabels; 95 96 /** A list of all LabelElementPair attached to single char literals like x='a' */ 97 public LinkedHashMap<String, Grammar.LabelElementPair> charLabels; 98 99 /** A list of all LabelElementPair attached to rule references like f=field */ 100 public LinkedHashMap<String, Grammar.LabelElementPair> ruleLabels; 101 102 /** A list of all Token list LabelElementPair like ids+=ID */ 103 public LinkedHashMap<String, Grammar.LabelElementPair> tokenListLabels; 104 105 /** A list of all rule ref list LabelElementPair like ids+=expr */ 106 public LinkedHashMap<String, Grammar.LabelElementPair> ruleListLabels; 107 108 /** All labels go in here (plus being split per the above lists) to 109 * catch dup label and label type mismatches. 110 */ 111 protected Map<String, Grammar.LabelElementPair> labelNameSpace = 112 new HashMap<String, Grammar.LabelElementPair>(); 113 114 /** Map a name to an action for this rule. Currently init is only 115 * one we use, but we can add more in future. 116 * The code generator will use this to fill holes in the rule template. 117 * I track the AST node for the action in case I need the line number 118 * for errors. A better name is probably namedActions, but I don't 119 * want everyone to have to change their code gen templates now. 120 */ 121 protected Map<String, Object> actions = 122 new HashMap<String, Object>(); 123 124 /** Track all executable actions other than named actions like @init. 125 * Also tracks exception handlers, predicates, and rewrite rewrites. 126 * We need to examine these actions before code generation so 127 * that we can detect refs to $rule.attr etc... 128 */ 129 protected List<GrammarAST> inlineActions = new ArrayList<GrammarAST>(); 130 131 public int numberOfAlts; 132 133 /** Each alt has a Map<tokenRefName,List<tokenRefAST>>; range 1..numberOfAlts. 134 * So, if there are 3 ID refs in a rule's alt number 2, you'll have 135 * altToTokenRef[2].get("ID").size()==3. This is used to see if $ID is ok. 136 * There must be only one ID reference in the alt for $ID to be ok in 137 * an action--must be unique. 138 * 139 * This also tracks '+' and "int" literal token references 140 * (if not in LEXER). 141 * 142 * Rewrite rules force tracking of all tokens. 143 */ 144 protected Map<String, List<GrammarAST>>[] altToTokenRefMap; 145 146 /** Each alt has a Map<ruleRefName,List<ruleRefAST>>; range 1..numberOfAlts 147 * So, if there are 3 expr refs in a rule's alt number 2, you'll have 148 * altToRuleRef[2].get("expr").size()==3. This is used to see if $expr is ok. 149 * There must be only one expr reference in the alt for $expr to be ok in 150 * an action--must be unique. 151 * 152 * Rewrite rules force tracking of all rule result ASTs. 1..n 153 */ 154 protected Map<String, List<GrammarAST>>[] altToRuleRefMap; 155 156 /** Do not generate start, stop etc... in a return value struct unless 157 * somebody references $r.start somewhere. 158 */ 159 public boolean referencedPredefinedRuleAttributes = false; 160 161 public boolean isSynPred = false; 162 163 public boolean imported = false; 164 165 @SuppressWarnings("unchecked") 166 public Rule(Grammar grammar, 167 String ruleName, 168 int ruleIndex, 169 int numberOfAlts) 170 { 171 this.name = ruleName; 172 this.index = ruleIndex; 173 this.numberOfAlts = numberOfAlts; 174 this.grammar = grammar; 175 throwsSpec = new HashSet<String>(); 176 altToTokenRefMap = (Map<String, List<GrammarAST>>[])new Map<?, ?>[numberOfAlts+1]; 177 altToRuleRefMap = (Map<String, List<GrammarAST>>[])new Map<?, ?>[numberOfAlts+1]; 178 for (int alt=1; alt<=numberOfAlts; alt++) { 179 altToTokenRefMap[alt] = new HashMap<String, List<GrammarAST>>(); 180 altToRuleRefMap[alt] = new HashMap<String, List<GrammarAST>>(); 181 } 182 } 183 184 public static int getRuleType(String ruleName){ 185 if (ruleName == null || ruleName.length() == 0) 186 throw new IllegalArgumentException("The specified rule name is not valid."); 187 return Character.isUpperCase(ruleName.charAt(0)) ? Grammar.LEXER : Grammar.PARSER; 188 } 189 190 public void defineLabel(Token label, GrammarAST elementRef, int type) { 191 Grammar.LabelElementPair pair = grammar.new LabelElementPair(label,elementRef); 192 pair.type = type; 193 labelNameSpace.put(label.getText(), pair); 194 switch ( type ) { 195 case Grammar.TOKEN_LABEL : 196 if ( tokenLabels==null ) tokenLabels = new LinkedHashMap<String, Grammar.LabelElementPair>(); 197 tokenLabels.put(label.getText(), pair); 198 break; 199 case Grammar.WILDCARD_TREE_LABEL : 200 if ( wildcardTreeLabels==null ) wildcardTreeLabels = new LinkedHashMap<String, Grammar.LabelElementPair>(); 201 wildcardTreeLabels.put(label.getText(), pair); 202 break; 203 case Grammar.WILDCARD_TREE_LIST_LABEL : 204 if ( wildcardTreeListLabels==null ) wildcardTreeListLabels = new LinkedHashMap<String, Grammar.LabelElementPair>(); 205 wildcardTreeListLabels.put(label.getText(), pair); 206 break; 207 case Grammar.RULE_LABEL : 208 if ( ruleLabels==null ) ruleLabels = new LinkedHashMap<String, Grammar.LabelElementPair>(); 209 ruleLabels.put(label.getText(), pair); 210 break; 211 case Grammar.TOKEN_LIST_LABEL : 212 if ( tokenListLabels==null ) tokenListLabels = new LinkedHashMap<String, Grammar.LabelElementPair>(); 213 tokenListLabels.put(label.getText(), pair); 214 break; 215 case Grammar.RULE_LIST_LABEL : 216 if ( ruleListLabels==null ) ruleListLabels = new LinkedHashMap<String, Grammar.LabelElementPair>(); 217 ruleListLabels.put(label.getText(), pair); 218 break; 219 case Grammar.CHAR_LABEL : 220 if ( charLabels==null ) charLabels = new LinkedHashMap<String, Grammar.LabelElementPair>(); 221 charLabels.put(label.getText(), pair); 222 break; 223 } 224 } 225 226 public Grammar.LabelElementPair getLabel(String name) { 227 return labelNameSpace.get(name); 228 } 229 230 public Grammar.LabelElementPair getTokenLabel(String name) { 231 Grammar.LabelElementPair pair = null; 232 if ( tokenLabels!=null ) { 233 return tokenLabels.get(name); 234 } 235 return pair; 236 } 237 238 public Map<String, Grammar.LabelElementPair> getRuleLabels() { 239 return ruleLabels; 240 } 241 242 public Map<String, Grammar.LabelElementPair> getRuleListLabels() { 243 return ruleListLabels; 244 } 245 246 public Grammar.LabelElementPair getRuleLabel(String name) { 247 Grammar.LabelElementPair pair = null; 248 if ( ruleLabels!=null ) { 249 return ruleLabels.get(name); 250 } 251 return pair; 252 } 253 254 public Grammar.LabelElementPair getTokenListLabel(String name) { 255 Grammar.LabelElementPair pair = null; 256 if ( tokenListLabels!=null ) { 257 return tokenListLabels.get(name); 258 } 259 return pair; 260 } 261 262 public Grammar.LabelElementPair getRuleListLabel(String name) { 263 Grammar.LabelElementPair pair = null; 264 if ( ruleListLabels!=null ) { 265 return ruleListLabels.get(name); 266 } 267 return pair; 268 } 269 270 /** Track a token ID or literal like '+' and "void" as having been referenced 271 * somewhere within the alts (not rewrite sections) of a rule. 272 * 273 * This differs from Grammar.altReferencesTokenID(), which tracks all 274 * token IDs to check for token IDs without corresponding lexer rules. 275 */ 276 public void trackTokenReferenceInAlt(GrammarAST refAST, int outerAltNum) { 277 List<GrammarAST> refs = altToTokenRefMap[outerAltNum].get(refAST.getText()); 278 if ( refs==null ) { 279 refs = new ArrayList<GrammarAST>(); 280 altToTokenRefMap[outerAltNum].put(refAST.getText(), refs); 281 } 282 refs.add(refAST); 283 } 284 285 public List<GrammarAST> getTokenRefsInAlt(String ref, int outerAltNum) { 286 if ( altToTokenRefMap[outerAltNum]!=null ) { 287 List<GrammarAST> tokenRefASTs = altToTokenRefMap[outerAltNum].get(ref); 288 return tokenRefASTs; 289 } 290 return null; 291 } 292 293 public void trackRuleReferenceInAlt(GrammarAST refAST, int outerAltNum) { 294 List<GrammarAST> refs = altToRuleRefMap[outerAltNum].get(refAST.getText()); 295 if ( refs==null ) { 296 refs = new ArrayList<GrammarAST>(); 297 altToRuleRefMap[outerAltNum].put(refAST.getText(), refs); 298 } 299 refs.add(refAST); 300 } 301 302 public List<GrammarAST> getRuleRefsInAlt(String ref, int outerAltNum) { 303 if ( altToRuleRefMap[outerAltNum]!=null ) { 304 List<GrammarAST> ruleRefASTs = altToRuleRefMap[outerAltNum].get(ref); 305 return ruleRefASTs; 306 } 307 return null; 308 } 309 310 public Set<String> getTokenRefsInAlt(int altNum) { 311 return altToTokenRefMap[altNum].keySet(); 312 } 313 314 /** For use with rewrite rules, we must track all tokens matched on the 315 * left-hand-side; so we need Lists. This is a unique list of all 316 * token types for which the rule needs a list of tokens. This 317 * is called from the rule template not directly by the code generator. 318 */ 319 public Set<String> getAllTokenRefsInAltsWithRewrites() { 320 String output = (String)grammar.getOption("output"); 321 Set<String> tokens = new HashSet<String>(); 322 if ( output==null || !output.equals("AST") ) { 323 // return nothing if not generating trees; i.e., don't do for templates 324 return tokens; 325 } 326 //System.out.println("blk "+tree.findFirstType(ANTLRParser.BLOCK).toStringTree()); 327 for (int i = 1; i <= numberOfAlts; i++) { 328 if ( hasRewrite(i) ) { 329 Map<String, List<GrammarAST>> m = altToTokenRefMap[i]; 330 for (String tokenName : m.keySet()) { 331 // convert token name like ID to ID, "void" to 31 332 int ttype = grammar.getTokenType(tokenName); 333 String label = grammar.generator.getTokenTypeAsTargetLabel(ttype); 334 tokens.add(label); 335 } 336 } 337 } 338 return tokens; 339 } 340 341 public Set<String> getRuleRefsInAlt(int outerAltNum) { 342 return altToRuleRefMap[outerAltNum].keySet(); 343 } 344 345 /** For use with rewrite rules, we must track all rule AST results on the 346 * left-hand-side; so we need Lists. This is a unique list of all 347 * rule results for which the rule needs a list of results. 348 */ 349 public Set<String> getAllRuleRefsInAltsWithRewrites() { 350 Set<String> rules = new HashSet<String>(); 351 for (int i = 1; i <= numberOfAlts; i++) { 352 if ( hasRewrite(i) ) { 353 Map<String, ?> m = altToRuleRefMap[i]; 354 rules.addAll(m.keySet()); 355 } 356 } 357 return rules; 358 } 359 360 public List<GrammarAST> getInlineActions() { 361 return inlineActions; 362 } 363 364 public boolean hasRewrite(int i) { 365 GrammarAST blk = tree.findFirstType(ANTLRParser.BLOCK); 366 GrammarAST alt = blk.getBlockALT(i); 367 GrammarAST rew = alt.getNextSibling(); 368 if ( rew!=null && rew.getType()==ANTLRParser.REWRITES ) return true; 369 if ( alt.findFirstType(ANTLRParser.REWRITES)!=null ) return true; 370 return false; 371 } 372 373 /** Return the scope containing name */ 374 public AttributeScope getAttributeScope(String name) { 375 AttributeScope scope = getLocalAttributeScope(name); 376 if ( scope!=null ) { 377 return scope; 378 } 379 if ( ruleScope!=null && ruleScope.getAttribute(name)!=null ) { 380 scope = ruleScope; 381 } 382 return scope; 383 } 384 385 /** Get the arg, return value, or predefined property for this rule */ 386 public AttributeScope getLocalAttributeScope(String name) { 387 AttributeScope scope = null; 388 if ( returnScope!=null && returnScope.getAttribute(name)!=null ) { 389 scope = returnScope; 390 } 391 else if ( parameterScope!=null && parameterScope.getAttribute(name)!=null ) { 392 scope = parameterScope; 393 } 394 else { 395 AttributeScope rulePropertiesScope = 396 RuleLabelScope.grammarTypeToRulePropertiesScope[grammar.type]; 397 if ( rulePropertiesScope.getAttribute(name)!=null ) { 398 scope = rulePropertiesScope; 399 } 400 } 401 return scope; 402 } 403 404 /** For references to tokens rather than by label such as $ID, we 405 * need to get the existing label for the ID ref or create a new 406 * one. 407 */ 408 public String getElementLabel(String refdSymbol, 409 int outerAltNum, 410 CodeGenerator generator) 411 { 412 GrammarAST uniqueRefAST; 413 if ( grammar.type != Grammar.LEXER && 414 Character.isUpperCase(refdSymbol.charAt(0)) ) 415 { 416 // symbol is a token 417 List<GrammarAST> tokenRefs = getTokenRefsInAlt(refdSymbol, outerAltNum); 418 uniqueRefAST = tokenRefs.get(0); 419 } 420 else { 421 // symbol is a rule 422 List<GrammarAST> ruleRefs = getRuleRefsInAlt(refdSymbol, outerAltNum); 423 uniqueRefAST = ruleRefs.get(0); 424 } 425 if ( uniqueRefAST.code==null ) { 426 // no code? must not have gen'd yet; forward ref 427 return null; 428 } 429 String labelName; 430 String existingLabelName = 431 (String)uniqueRefAST.code.getAttribute("label"); 432 // reuse any label or list label if it exists 433 if ( existingLabelName!=null ) { 434 labelName = existingLabelName; 435 } 436 else { 437 // else create new label 438 labelName = generator.createUniqueLabel(refdSymbol); 439 CommonToken label = new CommonToken(ANTLRParser.ID, labelName); 440 if ( grammar.type != Grammar.LEXER && 441 Character.isUpperCase(refdSymbol.charAt(0)) ) 442 { 443 grammar.defineTokenRefLabel(name, label, uniqueRefAST); 444 } 445 else { 446 grammar.defineRuleRefLabel(name, label, uniqueRefAST); 447 } 448 uniqueRefAST.code.add("label", labelName); 449 } 450 return labelName; 451 } 452 453 /** If a rule has no user-defined return values and nobody references 454 * it's start/stop (predefined attributes), then there is no need to 455 * define a struct; otherwise for now we assume a struct. A rule also 456 * has multiple return values if you are building trees or templates. 457 */ 458 public boolean getHasMultipleReturnValues() { 459 return 460 referencedPredefinedRuleAttributes || grammar.buildAST() || 461 grammar.buildTemplate() || 462 (returnScope!=null && returnScope.attributes.size()>1); 463 } 464 465 public boolean getHasSingleReturnValue() { 466 return 467 !(referencedPredefinedRuleAttributes || grammar.buildAST() || 468 grammar.buildTemplate()) && 469 (returnScope!=null && returnScope.attributes.size()==1); 470 } 471 472 public boolean getHasReturnValue() { 473 return 474 referencedPredefinedRuleAttributes || grammar.buildAST() || 475 grammar.buildTemplate() || 476 (returnScope!=null && returnScope.attributes.size()>0); 477 } 478 479 public String getSingleValueReturnType() { 480 if ( returnScope!=null && returnScope.attributes.size()==1 ) { 481 return returnScope.attributes.values().iterator().next().type; 482 } 483 return null; 484 } 485 486 public String getSingleValueReturnName() { 487 if ( returnScope!=null && returnScope.attributes.size()==1 ) { 488 return returnScope.attributes.values().iterator().next().name; 489 } 490 return null; 491 } 492 493 /** Given @scope::name {action} define it for this grammar. Later, 494 * the code generator will ask for the actions table. 495 */ 496 public void defineNamedAction(GrammarAST ampersandAST, 497 GrammarAST nameAST, 498 GrammarAST actionAST) 499 { 500 //System.out.println("rule @"+nameAST.getText()+"{"+actionAST.getText()+"}"); 501 String actionName = nameAST.getText(); 502 GrammarAST a = (GrammarAST)actions.get(actionName); 503 if ( a!=null ) { 504 ErrorManager.grammarError( 505 ErrorManager.MSG_ACTION_REDEFINITION,grammar, 506 nameAST.getToken(),nameAST.getText()); 507 } 508 else { 509 actions.put(actionName,actionAST); 510 } 511 } 512 513 public void trackInlineAction(GrammarAST actionAST) { 514 inlineActions.add(actionAST); 515 } 516 517 public Map<String, Object> getActions() { 518 return actions; 519 } 520 521 public void setActions(Map<String, Object> actions) { 522 this.actions = actions; 523 } 524 525 /** Save the option key/value pair and process it; return the key 526 * or null if invalid option. 527 */ 528 public String setOption(String key, Object value, Token optionsStartToken) { 529 if ( !legalOptions.contains(key) ) { 530 ErrorManager.grammarError(ErrorManager.MSG_ILLEGAL_OPTION, 531 grammar, 532 optionsStartToken, 533 key); 534 return null; 535 } 536 if ( options==null ) { 537 options = new HashMap<String, Object>(); 538 } 539 if ( key.equals("memoize") && value.toString().equals("true") ) { 540 grammar.composite.getRootGrammar().atLeastOneRuleMemoizes = true; 541 } 542 if ( key.equals("backtrack") && value.toString().equals("true") ) { 543 grammar.composite.getRootGrammar().atLeastOneBacktrackOption = true; 544 } 545 if ( key.equals("k") ) { 546 grammar.numberOfManualLookaheadOptions++; 547 } 548 options.put(key, value); 549 return key; 550 } 551 552 public void setOptions(Map<String, Object> options, Token optionsStartToken) { 553 if ( options==null ) { 554 this.options = null; 555 return; 556 } 557 Set<String> keys = options.keySet(); 558 for (Iterator<String> it = keys.iterator(); it.hasNext();) { 559 String optionName = it.next(); 560 Object optionValue = options.get(optionName); 561 String stored=setOption(optionName, optionValue, optionsStartToken); 562 if ( stored==null ) { 563 it.remove(); 564 } 565 } 566 } 567 568 /** Used during grammar imports to see if sets of rules intersect... This 569 * method and hashCode use the String name as the key for Rule objects. 570 public boolean equals(Object other) { 571 return this.name.equals(((Rule)other).name); 572 } 573 */ 574 575 /** Used during grammar imports to see if sets of rules intersect... 576 public int hashCode() { 577 return name.hashCode(); 578 } 579 * */ 580 581 @Override 582 public String toString() { // used for testing 583 return "["+grammar.name+"."+name+",index="+index+",line="+tree.getToken().getLine()+"]"; 584 } 585 } 586
