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.DFA; 31 import org.antlr.analysis.NFAState; 32 import org.antlr.grammar.v3.ANTLRParser; 33 import org.antlr.misc.IntSet; 34 import org.antlr.runtime.CommonToken; 35 import org.antlr.runtime.Token; 36 import org.antlr.runtime.tree.CommonTree; 37 import org.antlr.runtime.tree.Tree; 38 import org.stringtemplate.v4.ST; 39 40 import java.util.*; 41 42 /** Grammars are first converted to ASTs using this class and then are 43 * converted to NFAs via a tree walker. 44 * 45 * The reader may notice that I have made a very non-OO decision in this 46 * class to track variables for many different kinds of nodes. It wastes 47 * space for nodes that don't need the values and OO principles cry out 48 * for a new class type for each kind of node in my tree. I am doing this 49 * on purpose for a variety of reasons. I don't like using the type 50 * system for different node types; it yields too many damn class files 51 * which I hate. Perhaps if I put them all in one file. Most importantly 52 * though I hate all the type casting that would have to go on. I would 53 * have all sorts of extra work to do. Ick. Anyway, I'm doing all this 54 * on purpose, not out of ignorance. ;) 55 */ 56 public class GrammarAST extends CommonTree { 57 static int count = 0; 58 59 public int ID = ++count; 60 61 private String textOverride; 62 63 public String enclosingRuleName; 64 65 /** If this is a decision node, what is the lookahead DFA? */ 66 public DFA lookaheadDFA = null; 67 68 /** What NFA start state was built from this node? */ 69 public NFAState NFAStartState = null; 70 71 /** This is used for TREE_BEGIN nodes to point into 72 * the NFA. TREE_BEGINs point at left edge of DOWN for LOOK computation 73 * purposes (Nullable tree child list needs special code gen when matching). 74 */ 75 public NFAState NFATreeDownState = null; 76 77 /** Rule ref nodes, token refs, set, and NOT set refs need to track their 78 * location in the generated NFA so that local FOLLOW sets can be 79 * computed during code gen for automatic error recovery. 80 */ 81 public NFAState followingNFAState = null; 82 83 /** If this is a SET node, what are the elements? */ 84 protected IntSet setValue = null; 85 86 /** If this is a BLOCK node, track options here */ 87 protected Map<String,Object> blockOptions; 88 89 /** If this is a BLOCK node for a rewrite rule, track referenced 90 * elements here. Don't track elements in nested subrules. 91 */ 92 public Set<GrammarAST> rewriteRefsShallow; 93 94 /* If REWRITE node, track EVERY element and label ref to right of -> 95 * for this rewrite rule. There could be multiple of these per 96 * rule: 97 * 98 * a : ( ... -> ... | ... -> ... ) -> ... ; 99 * 100 * We may need a list of all refs to do definitions for whole rewrite 101 * later. 102 * 103 * If BLOCK then tracks every element at that level and below. 104 */ 105 public Set<GrammarAST> rewriteRefsDeep; 106 107 public Map<String,Object> terminalOptions; 108 109 /** if this is an ACTION node, this is the outermost enclosing 110 * alt num in rule. For actions, define.g sets these (used to 111 * be codegen.g). We need these set so we can examine actions 112 * early, before code gen, for refs to rule predefined properties 113 * and rule labels. For most part define.g sets outerAltNum, but 114 * codegen.g does the ones for %foo(a={$ID.text}) type refs as 115 * the {$ID...} is not seen as an action until code gen pulls apart. 116 */ 117 public int outerAltNum; 118 119 /** if this is a TOKEN_REF or RULE_REF node, this is the code ST 120 * generated for this node. We need to update it later to add 121 * a label if someone does $tokenref or $ruleref in an action. 122 */ 123 public ST code; 124 125 /** 126 * 127 */ getBlockOptions()128 public Map<String, Object> getBlockOptions() { 129 return blockOptions; 130 } 131 132 /** 133 * 134 * @param blockOptions 135 */ setBlockOptions(Map<String, Object> blockOptions)136 public void setBlockOptions(Map<String, Object> blockOptions) { 137 this.blockOptions = blockOptions; 138 } 139 GrammarAST()140 public GrammarAST() {} 141 142 @SuppressWarnings("OverridableMethodCallInConstructor") GrammarAST(int t, String txt)143 public GrammarAST(int t, String txt) { 144 initialize(t,txt); 145 } 146 147 @SuppressWarnings("OverridableMethodCallInConstructor") GrammarAST(Token token)148 public GrammarAST(Token token) { 149 initialize(token); 150 } 151 initialize(int i, String s)152 public void initialize(int i, String s) { 153 token = new CommonToken(i,s); 154 token.setTokenIndex(-1); 155 } 156 initialize(Tree ast)157 public void initialize(Tree ast) { 158 GrammarAST t = ((GrammarAST)ast); 159 this.startIndex = t.startIndex; 160 this.stopIndex = t.stopIndex; 161 this.token = t.token; 162 this.enclosingRuleName = t.enclosingRuleName; 163 this.setValue = t.setValue; 164 this.blockOptions = t.blockOptions; 165 this.outerAltNum = t.outerAltNum; 166 } 167 initialize(Token token)168 public void initialize(Token token) { 169 this.token = token; 170 if ( token!=null ) { 171 startIndex = token.getTokenIndex(); 172 stopIndex = startIndex; 173 } 174 } 175 getLookaheadDFA()176 public DFA getLookaheadDFA() { 177 return lookaheadDFA; 178 } 179 setLookaheadDFA(DFA lookaheadDFA)180 public void setLookaheadDFA(DFA lookaheadDFA) { 181 this.lookaheadDFA = lookaheadDFA; 182 } 183 getNFAStartState()184 public NFAState getNFAStartState() { 185 return NFAStartState; 186 } 187 setNFAStartState(NFAState nfaStartState)188 public void setNFAStartState(NFAState nfaStartState) { 189 this.NFAStartState = nfaStartState; 190 } 191 192 /** Save the option key/value pair and process it; return the key 193 * or null if invalid option. 194 */ setBlockOption(Grammar grammar, String key, Object value)195 public String setBlockOption(Grammar grammar, String key, Object value) { 196 if ( blockOptions == null ) { 197 blockOptions = new HashMap<String, Object>(); 198 } 199 return setOption(blockOptions, Grammar.legalBlockOptions, grammar, key, value); 200 } 201 setTerminalOption(Grammar grammar, String key, Object value)202 public String setTerminalOption(Grammar grammar, String key, Object value) { 203 if ( terminalOptions == null ) { 204 terminalOptions = new HashMap<String,Object>(); 205 } 206 return setOption(terminalOptions, Grammar.legalTokenOptions, grammar, key, value); 207 } 208 setOption(Map<String, Object> options, Set<String> legalOptions, Grammar grammar, String key, Object value)209 public String setOption(Map<String, Object> options, Set<String> legalOptions, Grammar grammar, String key, Object value) { 210 if ( !legalOptions.contains(key) ) { 211 ErrorManager.grammarError(ErrorManager.MSG_ILLEGAL_OPTION, 212 grammar, 213 token, 214 key); 215 return null; 216 } 217 if ( value instanceof String ) { 218 String vs = (String)value; 219 if ( vs.charAt(0)=='"' ) { 220 value = vs.substring(1,vs.length()-1); // strip quotes 221 } 222 } 223 if ( key.equals("k") ) { 224 grammar.numberOfManualLookaheadOptions++; 225 } 226 if ( key.equals("backtrack") && value.toString().equals("true") ) { 227 grammar.composite.getRootGrammar().atLeastOneBacktrackOption = true; 228 } 229 options.put(key, value); 230 return key; 231 } 232 getBlockOption(String key)233 public Object getBlockOption(String key) { 234 Object value = null; 235 if ( blockOptions != null ) { 236 value = blockOptions.get(key); 237 } 238 return value; 239 } 240 setOptions(Grammar grammar, Map<String, Object> options)241 public void setOptions(Grammar grammar, Map<String, Object> options) { 242 if ( options==null ) { 243 this.blockOptions = null; 244 return; 245 } 246 String[] keys = options.keySet().toArray(new String[options.size()]); 247 for (String optionName : keys) { 248 String stored= setBlockOption(grammar, optionName, options.get(optionName)); 249 if ( stored==null ) { 250 options.remove(optionName); 251 } 252 } 253 } 254 255 @Override getText()256 public String getText() { 257 if ( textOverride!=null ) return textOverride; 258 if ( token!=null ) { 259 return token.getText(); 260 } 261 return ""; 262 } 263 setType(int type)264 public void setType(int type) { 265 token.setType(type); 266 } 267 setText(String text)268 public void setText(String text) { 269 textOverride = text; // don't alt tokens as others might see 270 } 271 272 @Override getType()273 public int getType() { 274 if ( token!=null ) { 275 return token.getType(); 276 } 277 return -1; 278 } 279 280 @Override getLine()281 public int getLine() { 282 int line=0; 283 if ( token!=null ) { 284 line = token.getLine(); 285 } 286 if ( line==0 ) { 287 Tree child = getChild(0); 288 if ( child!=null ) { 289 line = child.getLine(); 290 } 291 } 292 return line; 293 } 294 295 @Override getCharPositionInLine()296 public int getCharPositionInLine(){ 297 int col=0; 298 if ( token!=null ) { 299 col = token.getCharPositionInLine(); 300 } 301 if ( col==0 ) { 302 Tree child = getChild(0); 303 if ( child!=null ) { 304 col = child.getCharPositionInLine(); 305 } 306 } 307 return col; 308 } 309 setLine(int line)310 public void setLine(int line) { 311 token.setLine(line); 312 } 313 setCharPositionInLine(int value)314 public void setCharPositionInLine(int value){ 315 token.setCharPositionInLine(value); 316 } 317 getSetValue()318 public IntSet getSetValue() { 319 return setValue; 320 } 321 setSetValue(IntSet setValue)322 public void setSetValue(IntSet setValue) { 323 this.setValue = setValue; 324 } 325 getLastChild()326 public GrammarAST getLastChild() { 327 if (getChildCount() == 0) 328 return null; 329 return (GrammarAST)getChild(getChildCount() - 1); 330 } 331 getNextSibling()332 public GrammarAST getNextSibling() { 333 return (GrammarAST)getParent().getChild(getChildIndex() + 1); 334 } 335 getLastSibling()336 public GrammarAST getLastSibling() { 337 Tree parent = getParent(); 338 if ( parent==null ) { 339 return null; 340 } 341 return (GrammarAST)parent.getChild(parent.getChildCount() - 1); 342 } 343 getChildrenAsArray()344 public GrammarAST[] getChildrenAsArray() { 345 List<? extends Object> children = getChildren(); 346 if (children == null) { 347 return new GrammarAST[0]; 348 } 349 350 return children.toArray(new GrammarAST[children.size()]); 351 } 352 353 private static final GrammarAST DescendantDownNode = new GrammarAST(Token.DOWN, "DOWN"); 354 private static final GrammarAST DescendantUpNode = new GrammarAST(Token.UP, "UP"); 355 descendants(Tree root)356 public static List<Tree> descendants(Tree root){ 357 return descendants(root, false); 358 } 359 descendants(Tree root, boolean insertDownUpNodes)360 public static List<Tree> descendants(Tree root, boolean insertDownUpNodes){ 361 List<Tree> result = new ArrayList<Tree>(); 362 int count = root.getChildCount(); 363 364 if (insertDownUpNodes){ 365 result.add(root); 366 result.add(DescendantDownNode); 367 368 for (int i = 0 ; i < count ; i++){ 369 Tree child = root.getChild(i); 370 for (Tree subchild : descendants(child, true)) 371 result.add(subchild); 372 } 373 374 result.add(DescendantUpNode); 375 }else{ 376 result.add(root); 377 for (int i = 0 ; i < count ; i++){ 378 Tree child = root.getChild(i); 379 for (Tree subchild : descendants(child, false)) 380 result.add(subchild); 381 } 382 } 383 384 return result; 385 } 386 findFirstType(int ttype)387 public GrammarAST findFirstType(int ttype) { 388 // check this node (the root) first 389 if ( this.getType()==ttype ) { 390 return this; 391 } 392 // else check children 393 List<Tree> descendants = descendants(this); 394 for (Tree child : descendants) { 395 if ( child.getType()==ttype ) { 396 return (GrammarAST)child; 397 } 398 } 399 return null; 400 } 401 findAllType(int ttype)402 public List<GrammarAST> findAllType(int ttype) { 403 List<GrammarAST> nodes = new ArrayList<GrammarAST>(); 404 _findAllType(ttype, nodes); 405 return nodes; 406 } 407 _findAllType(int ttype, List<GrammarAST> nodes)408 public void _findAllType(int ttype, List<GrammarAST> nodes) { 409 // check this node (the root) first 410 if ( this.getType()==ttype ) nodes.add(this); 411 // check children 412 for (int i = 0; i < getChildCount(); i++){ 413 GrammarAST child = (GrammarAST)getChild(i); 414 child._findAllType(ttype, nodes); 415 } 416 } 417 418 /** Make nodes unique based upon Token so we can add them to a Set; if 419 * not a GrammarAST, check type. 420 */ 421 @Override equals(Object ast)422 public boolean equals(Object ast) { 423 if ( this == ast ) { 424 return true; 425 } 426 if ( !(ast instanceof GrammarAST) ) { 427 return this.getType() == ((Tree)ast).getType(); 428 } 429 GrammarAST t = (GrammarAST)ast; 430 return token.getLine() == t.getLine() && 431 token.getCharPositionInLine() == t.getCharPositionInLine(); 432 } 433 434 /** Make nodes unique based upon Token so we can add them to a Set; if 435 * not a GrammarAST, check type. 436 */ 437 @Override hashCode()438 public int hashCode(){ 439 if (token == null) 440 return 0; 441 442 return token.hashCode(); 443 } 444 445 /** See if tree has exact token types and structure; no text */ hasSameTreeStructure(Tree other)446 public boolean hasSameTreeStructure(Tree other) { 447 // check roots first. 448 if (this.getType() != other.getType()) return false; 449 // if roots match, do full list match test on children. 450 Iterator<Tree> thisDescendants = descendants(this, true).iterator(); 451 Iterator<Tree> otherDescendants = descendants(other, true).iterator(); 452 while (thisDescendants.hasNext()) { 453 if (!otherDescendants.hasNext()) 454 return false; 455 if (thisDescendants.next().getType() != otherDescendants.next().getType()) 456 return false; 457 } 458 return !otherDescendants.hasNext(); 459 } 460 dup(Tree t)461 public static GrammarAST dup(Tree t) { 462 if ( t==null ) { 463 return null; 464 } 465 GrammarAST dup_t = new GrammarAST(); 466 dup_t.initialize(t); 467 return dup_t; 468 } 469 470 @Override dupNode()471 public Tree dupNode(){ 472 return dup(this); 473 } 474 475 /**Duplicate a tree, assuming this is a root node of a tree-- 476 * duplicate that node and what's below; ignore siblings of root node. 477 */ dupTreeNoActions(GrammarAST t, GrammarAST parent)478 public static GrammarAST dupTreeNoActions(GrammarAST t, GrammarAST parent) { 479 if ( t==null ) { 480 return null; 481 } 482 GrammarAST result = (GrammarAST)t.dupNode(); 483 for (GrammarAST subchild : getChildrenForDupTree(t)) { 484 result.addChild(dupTreeNoActions(subchild, result)); 485 } 486 return result; 487 } 488 getChildrenForDupTree(GrammarAST t)489 private static List<GrammarAST> getChildrenForDupTree(GrammarAST t) { 490 List<GrammarAST> result = new ArrayList<GrammarAST>(); 491 for (int i = 0; i < t.getChildCount(); i++){ 492 GrammarAST child = (GrammarAST)t.getChild(i); 493 int ttype = child.getType(); 494 if (ttype == ANTLRParser.REWRITES || ttype == ANTLRParser.REWRITE || ttype==ANTLRParser.ACTION) { 495 continue; 496 } 497 498 if (ttype == ANTLRParser.BANG || ttype == ANTLRParser.ROOT) { 499 for (GrammarAST subchild : getChildrenForDupTree(child)) 500 result.add(subchild); 501 } else { 502 result.add(child); 503 } 504 } 505 if ( result.size()==1 && result.get(0).getType()==ANTLRParser.EOA && 506 t.getType()==ANTLRParser.ALT ) 507 { 508 // can't have an empty alt, insert epsilon 509 result.add(0, new GrammarAST(ANTLRParser.EPSILON, "epsilon")); 510 } 511 512 return result; 513 } 514 dupTree(GrammarAST t)515 public static GrammarAST dupTree(GrammarAST t) { 516 if ( t==null ) { 517 return null; 518 } 519 GrammarAST root = dup(t); // make copy of root 520 // copy all children of root. 521 for (int i= 0; i < t.getChildCount(); i++) { 522 GrammarAST child = (GrammarAST)t.getChild(i); 523 root.addChild(dupTree(child)); 524 } 525 return root; 526 } 527 setTreeEnclosingRuleNameDeeply(String rname)528 public void setTreeEnclosingRuleNameDeeply(String rname) { 529 enclosingRuleName = rname; 530 if (getChildCount() == 0) return; 531 for (Object child : getChildren()) { 532 if (!(child instanceof GrammarAST)) { 533 continue; 534 } 535 GrammarAST grammarAST = (GrammarAST)child; 536 grammarAST.setTreeEnclosingRuleNameDeeply(rname); 537 } 538 } 539 toStringList()540 public String toStringList() { 541 String result = toStringTree(); 542 if (this.getNextSibling() != null) { 543 result += ' ' + getNextSibling().toStringList(); 544 } 545 546 return result; 547 } 548 549 /** Track start/stop token for subtree root created for a rule. 550 * Only works with Tree nodes. For rules that match nothing, 551 * seems like this will yield start=i and stop=i-1 in a nil node. 552 * Might be useful info so I'll not force to be i..i. 553 */ setTokenBoundaries(Token startToken, Token stopToken)554 public void setTokenBoundaries(Token startToken, Token stopToken) { 555 if ( startToken!=null ) startIndex = startToken.getTokenIndex(); 556 if ( stopToken!=null ) stopIndex = stopToken.getTokenIndex(); 557 } 558 getBlockALT(int i)559 public GrammarAST getBlockALT(int i) { 560 if ( this.getType()!=ANTLRParser.BLOCK ) return null; 561 int alts = 0; 562 for (int j =0 ; j < getChildCount(); j++) { 563 if (getChild(j).getType() == ANTLRParser.ALT) { 564 alts++; 565 } 566 if (alts == i) { 567 return (GrammarAST)getChild(j); 568 } 569 } 570 return null; 571 } 572 } 573