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