1/* 2 [The "BSD license"] 3 Copyright (c) 2005-2009 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 */ 28package org.antlr.runtime.tree; 29 30import org.antlr.runtime.*; 31 32import java.util.regex.Matcher; 33import java.util.regex.Pattern; 34 35/** A parser for a stream of tree nodes. "tree grammars" result in a subclass 36 * of this. All the error reporting and recovery is shared with Parser via 37 * the BaseRecognizer superclass. 38*/ 39public class TreeParser extends BaseRecognizer { 40 public static final int DOWN = Token.DOWN; 41 public static final int UP = Token.UP; 42 43 // precompiled regex used by inContext 44 static String dotdot = ".*[^.]\\.\\.[^.].*"; 45 static String doubleEtc = ".*\\.\\.\\.\\s+\\.\\.\\..*"; 46 static Pattern dotdotPattern = Pattern.compile(dotdot); 47 static Pattern doubleEtcPattern = Pattern.compile(doubleEtc); 48 49 protected TreeNodeStream input; 50 51 public TreeParser(TreeNodeStream input) { 52 super(); // highlight that we go to super to set state object 53 setTreeNodeStream(input); 54 } 55 56 public TreeParser(TreeNodeStream input, RecognizerSharedState state) { 57 super(state); // share the state object with another parser 58 setTreeNodeStream(input); 59 } 60 61 public void reset() { 62 super.reset(); // reset all recognizer state variables 63 if ( input!=null ) { 64 input.seek(0); // rewind the input 65 } 66 } 67 68 /** Set the input stream */ 69 public void setTreeNodeStream(TreeNodeStream input) { 70 this.input = input; 71 } 72 73 public TreeNodeStream getTreeNodeStream() { 74 return input; 75 } 76 77 public String getSourceName() { 78 return input.getSourceName(); 79 } 80 81 protected Object getCurrentInputSymbol(IntStream input) { 82 return ((TreeNodeStream)input).LT(1); 83 } 84 85 protected Object getMissingSymbol(IntStream input, 86 RecognitionException e, 87 int expectedTokenType, 88 BitSet follow) 89 { 90 String tokenText = 91 "<missing "+getTokenNames()[expectedTokenType]+">"; 92 TreeAdaptor adaptor = ((TreeNodeStream)e.input).getTreeAdaptor(); 93 return adaptor.create(new CommonToken(expectedTokenType, tokenText)); 94 } 95 96 /** Match '.' in tree parser has special meaning. Skip node or 97 * entire tree if node has children. If children, scan until 98 * corresponding UP node. 99 */ 100 public void matchAny(IntStream ignore) { // ignore stream, copy of input 101 state.errorRecovery = false; 102 state.failed = false; 103 Object look = input.LT(1); 104 if ( input.getTreeAdaptor().getChildCount(look)==0 ) { 105 input.consume(); // not subtree, consume 1 node and return 106 return; 107 } 108 // current node is a subtree, skip to corresponding UP. 109 // must count nesting level to get right UP 110 int level=0; 111 int tokenType = input.getTreeAdaptor().getType(look); 112 while ( tokenType!=Token.EOF && !(tokenType==UP && level==0) ) { 113 input.consume(); 114 look = input.LT(1); 115 tokenType = input.getTreeAdaptor().getType(look); 116 if ( tokenType == DOWN ) { 117 level++; 118 } 119 else if ( tokenType == UP ) { 120 level--; 121 } 122 } 123 input.consume(); // consume UP 124 } 125 126 /** We have DOWN/UP nodes in the stream that have no line info; override. 127 * plus we want to alter the exception type. Don't try to recover 128 * from tree parser errors inline... 129 */ 130 protected Object recoverFromMismatchedToken(IntStream input, 131 int ttype, 132 BitSet follow) 133 throws RecognitionException 134 { 135 throw new MismatchedTreeNodeException(ttype, (TreeNodeStream)input); 136 } 137 138 /** Prefix error message with the grammar name because message is 139 * always intended for the programmer because the parser built 140 * the input tree not the user. 141 */ 142 public String getErrorHeader(RecognitionException e) { 143 return getGrammarFileName()+": node from "+ 144 (e.approximateLineInfo?"after ":"")+"line "+e.line+":"+e.charPositionInLine; 145 } 146 147 /** Tree parsers parse nodes they usually have a token object as 148 * payload. Set the exception token and do the default behavior. 149 */ 150 public String getErrorMessage(RecognitionException e, String[] tokenNames) { 151 if ( this instanceof TreeParser ) { 152 TreeAdaptor adaptor = ((TreeNodeStream)e.input).getTreeAdaptor(); 153 e.token = adaptor.getToken(e.node); 154 if ( e.token==null ) { // could be an UP/DOWN node 155 e.token = new CommonToken(adaptor.getType(e.node), 156 adaptor.getText(e.node)); 157 } 158 } 159 return super.getErrorMessage(e, tokenNames); 160 } 161 162 /** Check if current node in input has a context. Context means sequence 163 * of nodes towards root of tree. For example, you might say context 164 * is "MULT" which means my parent must be MULT. "CLASS VARDEF" says 165 * current node must be child of a VARDEF and whose parent is a CLASS node. 166 * You can use "..." to mean zero-or-more nodes. "METHOD ... VARDEF" 167 * means my parent is VARDEF and somewhere above that is a METHOD node. 168 * The first node in the context is not necessarily the root. The context 169 * matcher stops matching and returns true when it runs out of context. 170 * There is no way to force the first node to be the root. 171 */ 172 public boolean inContext(String context) { 173 return inContext(input.getTreeAdaptor(), getTokenNames(), input.LT(1), context); 174 } 175 176 /** The worker for inContext. It's static and full of parameters for 177 * testing purposes. 178 */ 179 public static boolean inContext(TreeAdaptor adaptor, 180 String[] tokenNames, 181 Object t, 182 String context) 183 { 184 Matcher dotdotMatcher = dotdotPattern.matcher(context); 185 Matcher doubleEtcMatcher = doubleEtcPattern.matcher(context); 186 if ( dotdotMatcher.find() ) { // don't allow "..", must be "..." 187 throw new IllegalArgumentException("invalid syntax: .."); 188 } 189 if ( doubleEtcMatcher.find() ) { // don't allow double "..." 190 throw new IllegalArgumentException("invalid syntax: ... ..."); 191 } 192 context = context.replaceAll("\\.\\.\\.", " ... "); // ensure spaces around ... 193 context = context.trim(); 194 String[] nodes = context.split("\\s+"); 195 int ni = nodes.length-1; 196 t = adaptor.getParent(t); 197 while ( ni>=0 && t!=null ) { 198 if ( nodes[ni].equals("...") ) { 199 // walk upwards until we see nodes[ni-1] then continue walking 200 if ( ni==0 ) return true; // ... at start is no-op 201 String goal = nodes[ni-1]; 202 Object ancestor = getAncestor(adaptor, tokenNames, t, goal); 203 if ( ancestor==null ) return false; 204 t = ancestor; 205 ni--; 206 } 207 String name = tokenNames[adaptor.getType(t)]; 208 if ( !name.equals(nodes[ni]) ) { 209 //System.err.println("not matched: "+nodes[ni]+" at "+t); 210 return false; 211 } 212 // advance to parent and to previous element in context node list 213 ni--; 214 t = adaptor.getParent(t); 215 } 216 217 if ( t==null && ni>=0 ) return false; // at root but more nodes to match 218 return true; 219 } 220 221 /** Helper for static inContext */ 222 protected static Object getAncestor(TreeAdaptor adaptor, String[] tokenNames, Object t, String goal) { 223 while ( t!=null ) { 224 String name = tokenNames[adaptor.getType(t)]; 225 if ( name.equals(goal) ) return t; 226 t = adaptor.getParent(t); 227 } 228 return null; 229 } 230 231 public void traceIn(String ruleName, int ruleIndex) { 232 super.traceIn(ruleName, ruleIndex, input.LT(1)); 233 } 234 235 public void traceOut(String ruleName, int ruleIndex) { 236 super.traceOut(ruleName, ruleIndex, input.LT(1)); 237 } 238} 239