• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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