| /* |
| * [The "BSD license"] |
| * Copyright (c) 2010 Terence Parr |
| * All rights reserved. |
| * |
| * Redistribution and use in source and binary forms, with or without |
| * modification, are permitted provided that the following conditions |
| * are met: |
| * 1. Redistributions of source code must retain the above copyright |
| * notice, this list of conditions and the following disclaimer. |
| * 2. Redistributions in binary form must reproduce the above copyright |
| * notice, this list of conditions and the following disclaimer in the |
| * documentation and/or other materials provided with the distribution. |
| * 3. The name of the author may not be used to endorse or promote products |
| * derived from this software without specific prior written permission. |
| * |
| * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR |
| * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES |
| * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. |
| * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, |
| * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT |
| * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
| * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
| * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
| * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF |
| * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| */ |
| package org.antlr.tool; |
| |
| import org.antlr.analysis.DFA; |
| import org.antlr.analysis.NFAState; |
| import org.antlr.grammar.v3.ANTLRParser; |
| import org.antlr.misc.IntSet; |
| import org.antlr.misc.Interval; |
| import org.antlr.runtime.CommonToken; |
| import org.antlr.runtime.Token; |
| import org.antlr.runtime.TokenSource; |
| import org.antlr.runtime.tree.CommonTree; |
| import org.antlr.runtime.tree.Tree; |
| import org.antlr.runtime.tree.TreeAdaptor; |
| import org.stringtemplate.v4.ST; |
| import org.omg.PortableInterceptor.ORBInitInfoPackage.DuplicateName; |
| |
| import java.util.*; |
| |
| /** Grammars are first converted to ASTs using this class and then are |
| * converted to NFAs via a tree walker. |
| * |
| * The reader may notice that I have made a very non-OO decision in this |
| * class to track variables for many different kinds of nodes. It wastes |
| * space for nodes that don't need the values and OO principles cry out |
| * for a new class type for each kind of node in my tree. I am doing this |
| * on purpose for a variety of reasons. I don't like using the type |
| * system for different node types; it yields too many damn class files |
| * which I hate. Perhaps if I put them all in one file. Most importantly |
| * though I hate all the type casting that would have to go on. I would |
| * have all sorts of extra work to do. Ick. Anyway, I'm doing all this |
| * on purpose, not out of ignorance. ;) |
| */ |
| public class GrammarAST extends CommonTree { |
| static int count = 0; |
| |
| public int ID = ++count; |
| |
| private String textOverride; |
| |
| public String enclosingRuleName; |
| |
| /** If this is a decision node, what is the lookahead DFA? */ |
| public DFA lookaheadDFA = null; |
| |
| /** What NFA start state was built from this node? */ |
| public NFAState NFAStartState = null; |
| |
| /** This is used for TREE_BEGIN nodes to point into |
| * the NFA. TREE_BEGINs point at left edge of DOWN for LOOK computation |
| * purposes (Nullable tree child list needs special code gen when matching). |
| */ |
| public NFAState NFATreeDownState = null; |
| |
| /** Rule ref nodes, token refs, set, and NOT set refs need to track their |
| * location in the generated NFA so that local FOLLOW sets can be |
| * computed during code gen for automatic error recovery. |
| */ |
| public NFAState followingNFAState = null; |
| |
| /** If this is a SET node, what are the elements? */ |
| protected IntSet setValue = null; |
| |
| /** If this is a BLOCK node, track options here */ |
| protected Map<String,Object> blockOptions; |
| |
| /** If this is a BLOCK node for a rewrite rule, track referenced |
| * elements here. Don't track elements in nested subrules. |
| */ |
| public Set<GrammarAST> rewriteRefsShallow; |
| |
| /* If REWRITE node, track EVERY element and label ref to right of -> |
| * for this rewrite rule. There could be multiple of these per |
| * rule: |
| * |
| * a : ( ... -> ... | ... -> ... ) -> ... ; |
| * |
| * We may need a list of all refs to do definitions for whole rewrite |
| * later. |
| * |
| * If BLOCK then tracks every element at that level and below. |
| */ |
| public Set<GrammarAST> rewriteRefsDeep; |
| |
| public Map<String,Object> terminalOptions; |
| |
| /** if this is an ACTION node, this is the outermost enclosing |
| * alt num in rule. For actions, define.g sets these (used to |
| * be codegen.g). We need these set so we can examine actions |
| * early, before code gen, for refs to rule predefined properties |
| * and rule labels. For most part define.g sets outerAltNum, but |
| * codegen.g does the ones for %foo(a={$ID.text}) type refs as |
| * the {$ID...} is not seen as an action until code gen pulls apart. |
| */ |
| public int outerAltNum; |
| |
| /** if this is a TOKEN_REF or RULE_REF node, this is the code ST |
| * generated for this node. We need to update it later to add |
| * a label if someone does $tokenref or $ruleref in an action. |
| */ |
| public ST code; |
| |
| /** |
| * |
| * @return |
| */ |
| public Map<String, Object> getBlockOptions() { |
| return blockOptions; |
| } |
| |
| /** |
| * |
| * @param blockOptions |
| */ |
| public void setBlockOptions(Map<String, Object> blockOptions) { |
| this.blockOptions = blockOptions; |
| } |
| |
| public GrammarAST() {;} |
| |
| public GrammarAST(int t, String txt) { |
| initialize(t,txt); |
| } |
| |
| public GrammarAST(Token token) { |
| initialize(token); |
| } |
| |
| public void initialize(int i, String s) { |
| token = new CommonToken(i,s); |
| token.setTokenIndex(-1); |
| } |
| |
| public void initialize(Tree ast) { |
| GrammarAST t = ((GrammarAST)ast); |
| this.startIndex = t.startIndex; |
| this.stopIndex = t.stopIndex; |
| this.token = t.token; |
| this.enclosingRuleName = t.enclosingRuleName; |
| this.setValue = t.setValue; |
| this.blockOptions = t.blockOptions; |
| this.outerAltNum = t.outerAltNum; |
| } |
| |
| public void initialize(Token token) { |
| this.token = token; |
| if ( token!=null ) { |
| startIndex = token.getTokenIndex(); |
| stopIndex = startIndex; |
| } |
| } |
| |
| public DFA getLookaheadDFA() { |
| return lookaheadDFA; |
| } |
| |
| public void setLookaheadDFA(DFA lookaheadDFA) { |
| this.lookaheadDFA = lookaheadDFA; |
| } |
| |
| public NFAState getNFAStartState() { |
| return NFAStartState; |
| } |
| |
| public void setNFAStartState(NFAState nfaStartState) { |
| this.NFAStartState = nfaStartState; |
| } |
| |
| /** Save the option key/value pair and process it; return the key |
| * or null if invalid option. |
| */ |
| public String setBlockOption(Grammar grammar, String key, Object value) { |
| if ( blockOptions == null ) { |
| blockOptions = new HashMap(); |
| } |
| return setOption(blockOptions, Grammar.legalBlockOptions, grammar, key, value); |
| } |
| |
| public String setTerminalOption(Grammar grammar, String key, Object value) { |
| if ( terminalOptions == null ) { |
| terminalOptions = new HashMap<String,Object>(); |
| } |
| return setOption(terminalOptions, Grammar.legalTokenOptions, grammar, key, value); |
| } |
| |
| public String setOption(Map options, Set legalOptions, Grammar grammar, String key, Object value) { |
| if ( !legalOptions.contains(key) ) { |
| ErrorManager.grammarError(ErrorManager.MSG_ILLEGAL_OPTION, |
| grammar, |
| token, |
| key); |
| return null; |
| } |
| if ( value instanceof String ) { |
| String vs = (String)value; |
| if ( vs.charAt(0)=='"' ) { |
| value = vs.substring(1,vs.length()-1); // strip quotes |
| } |
| } |
| if ( key.equals("k") ) { |
| grammar.numberOfManualLookaheadOptions++; |
| } |
| if ( key.equals("backtrack") && value.toString().equals("true") ) { |
| grammar.composite.getRootGrammar().atLeastOneBacktrackOption = true; |
| } |
| options.put(key, value); |
| return key; |
| } |
| |
| public Object getBlockOption(String key) { |
| Object value = null; |
| if ( blockOptions != null ) { |
| value = blockOptions.get(key); |
| } |
| return value; |
| } |
| |
| public void setOptions(Grammar grammar, Map options) { |
| if ( options==null ) { |
| this.blockOptions = null; |
| return; |
| } |
| String[] keys = (String[])options.keySet().toArray(new String[options.size()]); |
| for (String optionName : keys) { |
| String stored= setBlockOption(grammar, optionName, options.get(optionName)); |
| if ( stored==null ) { |
| options.remove(optionName); |
| } |
| } |
| } |
| |
| @Override |
| public String getText() { |
| if ( textOverride!=null ) return textOverride; |
| if ( token!=null ) { |
| return token.getText(); |
| } |
| return ""; |
| } |
| |
| public void setType(int type) { |
| token.setType(type); |
| } |
| |
| public void setText(String text) { |
| textOverride = text; // don't alt tokens as others might see |
| } |
| |
| @Override |
| public int getType() { |
| if ( token!=null ) { |
| return token.getType(); |
| } |
| return -1; |
| } |
| |
| @Override |
| public int getLine() { |
| int line=0; |
| if ( token!=null ) { |
| line = token.getLine(); |
| } |
| if ( line==0 ) { |
| Tree child = getChild(0); |
| if ( child!=null ) { |
| line = child.getLine(); |
| } |
| } |
| return line; |
| } |
| |
| @Override |
| public int getCharPositionInLine(){ |
| int col=0; |
| if ( token!=null ) { |
| col = token.getCharPositionInLine(); |
| } |
| if ( col==0 ) { |
| Tree child = getChild(0); |
| if ( child!=null ) { |
| col = child.getCharPositionInLine(); |
| } |
| } |
| return col; |
| } |
| |
| public void setLine(int line) { |
| token.setLine(line); |
| } |
| |
| public void setCharPositionInLine(int value){ |
| token.setCharPositionInLine(value); |
| } |
| |
| public IntSet getSetValue() { |
| return setValue; |
| } |
| |
| public void setSetValue(IntSet setValue) { |
| this.setValue = setValue; |
| } |
| |
| public GrammarAST getLastChild() { |
| if (getChildCount() == 0) |
| return null; |
| return (GrammarAST)getChild(getChildCount() - 1); |
| } |
| |
| public GrammarAST getNextSibling() { |
| return (GrammarAST)getParent().getChild(getChildIndex() + 1); |
| } |
| |
| public GrammarAST getLastSibling() { |
| Tree parent = getParent(); |
| if ( parent==null ) { |
| return null; |
| } |
| return (GrammarAST)parent.getChild(parent.getChildCount() - 1); |
| } |
| |
| |
| public GrammarAST[] getChildrenAsArray() { |
| return (GrammarAST[])getChildren().toArray(new GrammarAST[getChildCount()]); |
| } |
| |
| private static final GrammarAST DescendantDownNode = new GrammarAST(Token.DOWN, "DOWN"); |
| private static final GrammarAST DescendantUpNode = new GrammarAST(Token.UP, "UP"); |
| |
| public static List<Tree> descendants(Tree root){ |
| return descendants(root, false); |
| } |
| |
| public static List<Tree> descendants(Tree root, boolean insertDownUpNodes){ |
| List<Tree> result = new ArrayList<Tree>(); |
| int count = root.getChildCount(); |
| |
| if (insertDownUpNodes){ |
| result.add(root); |
| result.add(DescendantDownNode); |
| |
| for (int i = 0 ; i < count ; i++){ |
| Tree child = root.getChild(i); |
| for (Tree subchild : descendants(child, true)) |
| result.add(subchild); |
| } |
| |
| result.add(DescendantUpNode); |
| }else{ |
| result.add(root); |
| for (int i = 0 ; i < count ; i++){ |
| Tree child = root.getChild(i); |
| for (Tree subchild : descendants(child, false)) |
| result.add(subchild); |
| } |
| } |
| |
| return result; |
| } |
| |
| public GrammarAST findFirstType(int ttype) { |
| // check this node (the root) first |
| if ( this.getType()==ttype ) { |
| return this; |
| } |
| // else check children |
| List<Tree> descendants = descendants(this); |
| for (Tree child : descendants) { |
| if ( child.getType()==ttype ) { |
| return (GrammarAST)child; |
| } |
| } |
| return null; |
| } |
| |
| public List<GrammarAST> findAllType(int ttype) { |
| List<GrammarAST> nodes = new ArrayList<GrammarAST>(); |
| _findAllType(ttype, nodes); |
| return nodes; |
| } |
| |
| public void _findAllType(int ttype, List<GrammarAST> nodes) { |
| // check this node (the root) first |
| if ( this.getType()==ttype ) nodes.add(this); |
| // check children |
| for (int i = 0; i < getChildCount(); i++){ |
| GrammarAST child = (GrammarAST)getChild(i); |
| child._findAllType(ttype, nodes); |
| } |
| } |
| |
| /** Make nodes unique based upon Token so we can add them to a Set; if |
| * not a GrammarAST, check type. |
| */ |
| @Override |
| public boolean equals(Object ast) { |
| if ( this == ast ) { |
| return true; |
| } |
| if ( !(ast instanceof GrammarAST) ) { |
| return this.getType() == ((Tree)ast).getType(); |
| } |
| GrammarAST t = (GrammarAST)ast; |
| return token.getLine() == t.getLine() && |
| token.getCharPositionInLine() == t.getCharPositionInLine(); |
| } |
| |
| /** Make nodes unique based upon Token so we can add them to a Set; if |
| * not a GrammarAST, check type. |
| */ |
| @Override |
| public int hashCode(){ |
| if (token == null) |
| return 0; |
| |
| return token.hashCode(); |
| } |
| |
| /** See if tree has exact token types and structure; no text */ |
| public boolean hasSameTreeStructure(Tree other) { |
| // check roots first. |
| if (this.getType() != other.getType()) return false; |
| // if roots match, do full list match test on children. |
| Iterator<Tree> thisDescendants = descendants(this, true).iterator(); |
| Iterator<Tree> otherDescendants = descendants(other, true).iterator(); |
| while (thisDescendants.hasNext()) { |
| if (!otherDescendants.hasNext()) |
| return false; |
| if (thisDescendants.next().getType() != otherDescendants.next().getType()) |
| return false; |
| } |
| return !otherDescendants.hasNext(); |
| } |
| |
| public static GrammarAST dup(Tree t) { |
| if ( t==null ) { |
| return null; |
| } |
| GrammarAST dup_t = new GrammarAST(); |
| dup_t.initialize(t); |
| return dup_t; |
| } |
| |
| @Override |
| public Tree dupNode(){ |
| return dup(this); |
| } |
| |
| /**Duplicate a tree, assuming this is a root node of a tree-- |
| * duplicate that node and what's below; ignore siblings of root node. |
| */ |
| public static GrammarAST dupTreeNoActions(GrammarAST t, GrammarAST parent) { |
| if ( t==null ) { |
| return null; |
| } |
| GrammarAST result = (GrammarAST)t.dupNode(); |
| for (GrammarAST subchild : getChildrenForDupTree(t)) { |
| result.addChild(dupTreeNoActions(subchild, result)); |
| } |
| return result; |
| } |
| |
| private static List<GrammarAST> getChildrenForDupTree(GrammarAST t) { |
| List<GrammarAST> result = new ArrayList<GrammarAST>(); |
| for (int i = 0; i < t.getChildCount(); i++){ |
| GrammarAST child = (GrammarAST)t.getChild(i); |
| int ttype = child.getType(); |
| if (ttype == ANTLRParser.REWRITES || ttype == ANTLRParser.REWRITE || ttype==ANTLRParser.ACTION) { |
| continue; |
| } |
| |
| if (ttype == ANTLRParser.BANG || ttype == ANTLRParser.ROOT) { |
| for (GrammarAST subchild : getChildrenForDupTree(child)) |
| result.add(subchild); |
| } else { |
| result.add(child); |
| } |
| } |
| if ( result.size()==1 && result.get(0).getType()==ANTLRParser.EOA && |
| t.getType()==ANTLRParser.ALT ) |
| { |
| // can't have an empty alt, insert epsilon |
| result.add(0, new GrammarAST(ANTLRParser.EPSILON, "epsilon")); |
| } |
| |
| return result; |
| } |
| |
| public static GrammarAST dupTree(GrammarAST t) { |
| if ( t==null ) { |
| return null; |
| } |
| GrammarAST root = dup(t); // make copy of root |
| // copy all children of root. |
| for (int i= 0; i < t.getChildCount(); i++) { |
| GrammarAST child = (GrammarAST)t.getChild(i); |
| root.addChild(dupTree(child)); |
| } |
| return root; |
| } |
| |
| public void setTreeEnclosingRuleNameDeeply(String rname) { |
| enclosingRuleName = rname; |
| if (getChildCount() == 0) return; |
| for (Object child : getChildren()) { |
| if (!(child instanceof GrammarAST)) { |
| continue; |
| } |
| GrammarAST grammarAST = (GrammarAST)child; |
| grammarAST.setTreeEnclosingRuleNameDeeply(rname); |
| } |
| } |
| |
| String toStringList() { |
| return ""; |
| } |
| |
| /** Track start/stop token for subtree root created for a rule. |
| * Only works with Tree nodes. For rules that match nothing, |
| * seems like this will yield start=i and stop=i-1 in a nil node. |
| * Might be useful info so I'll not force to be i..i. |
| */ |
| public void setTokenBoundaries(Token startToken, Token stopToken) { |
| if ( startToken!=null ) startIndex = startToken.getTokenIndex(); |
| if ( stopToken!=null ) stopIndex = stopToken.getTokenIndex(); |
| } |
| |
| public GrammarAST getBlockALT(int i) { |
| if ( this.getType()!=ANTLRParser.BLOCK ) return null; |
| int alts = 0; |
| for (int j =0 ; j < getChildCount(); j++) { |
| if (getChild(j).getType() == ANTLRParser.ALT) { |
| alts++; |
| } |
| if (alts == i) { |
| return (GrammarAST)getChild(j); |
| } |
| } |
| return null; |
| } |
| } |