192617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri/* 292617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri [The "BSD license"] 392617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri Copyright (c) 2005-2009 Terence Parr 492617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri All rights reserved. 592617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri 692617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri Redistribution and use in source and binary forms, with or without 792617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri modification, are permitted provided that the following conditions 892617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri are met: 992617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri 1. Redistributions of source code must retain the above copyright 1092617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri notice, this list of conditions and the following disclaimer. 1192617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri 2. Redistributions in binary form must reproduce the above copyright 1292617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri notice, this list of conditions and the following disclaimer in the 1392617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri documentation and/or other materials provided with the distribution. 1492617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri 3. The name of the author may not be used to endorse or promote products 1592617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri derived from this software without specific prior written permission. 1692617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri 1792617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 1892617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 1992617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 2092617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 2192617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 2292617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2392617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2492617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2592617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 2692617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2792617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri */ 2892617aeac109481258f0c3863d09c1b8903d438bLuca Barbieripackage org.antlr.runtime.debug; 2992617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri 3092617aeac109481258f0c3863d09c1b8903d438bLuca Barbieriimport org.antlr.runtime.RecognitionException; 3192617aeac109481258f0c3863d09c1b8903d438bLuca Barbieriimport org.antlr.runtime.Token; 3292617aeac109481258f0c3863d09c1b8903d438bLuca Barbieriimport org.antlr.runtime.tree.ParseTree; 3392617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri 3492617aeac109481258f0c3863d09c1b8903d438bLuca Barbieriimport java.util.Stack; 3592617aeac109481258f0c3863d09c1b8903d438bLuca Barbieriimport java.util.ArrayList; 3692617aeac109481258f0c3863d09c1b8903d438bLuca Barbieriimport java.util.List; 3792617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri 3892617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri/** This parser listener tracks rule entry/exit and token matches 3992617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri * to build a simple parse tree using ParseTree nodes. 4092617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri */ 4192617aeac109481258f0c3863d09c1b8903d438bLuca Barbieripublic class ParseTreeBuilder extends BlankDebugEventListener { 4292617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri public static final String EPSILON_PAYLOAD = "<epsilon>"; 4392617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri 4492617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri Stack callStack = new Stack(); 4592617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri List hiddenTokens = new ArrayList(); 4692617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri int backtracking = 0; 4792617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri 4892617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri public ParseTreeBuilder(String grammarName) { 4992617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri ParseTree root = create("<grammar "+grammarName+">"); 5092617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri callStack.push(root); 5192617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri } 5292617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri 5392617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri public ParseTree getTree() { 5492617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri return (ParseTree)callStack.elementAt(0); 5592617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri } 5692617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri 5792617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri /** What kind of node to create. You might want to override 5892617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri * so I factored out creation here. 5992617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri */ 6092617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri public ParseTree create(Object payload) { 6192617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri return new ParseTree(payload); 6292617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri } 6392617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri 6492617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri public ParseTree epsilonNode() { 6592617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri return create(EPSILON_PAYLOAD); 6692617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri } 6792617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri 6892617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri /** Backtracking or cyclic DFA, don't want to add nodes to tree */ 6992617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri public void enterDecision(int d, boolean couldBacktrack) { backtracking++; } 7092617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri public void exitDecision(int i) { backtracking--; } 7192617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri 7292617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri public void enterRule(String filename, String ruleName) { 7392617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri if ( backtracking>0 ) return; 7492617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri ParseTree parentRuleNode = (ParseTree)callStack.peek(); 7592617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri ParseTree ruleNode = create(ruleName); 7692617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri parentRuleNode.addChild(ruleNode); 7792617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri callStack.push(ruleNode); 7892617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri } 7992617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri 8092617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri public void exitRule(String filename, String ruleName) { 8192617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri if ( backtracking>0 ) return; 8292617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri ParseTree ruleNode = (ParseTree)callStack.peek(); 8392617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri if ( ruleNode.getChildCount()==0 ) { 8492617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri ruleNode.addChild(epsilonNode()); 8592617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri } 8692617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri callStack.pop(); 8792617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri } 8892617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri 8992617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri public void consumeToken(Token token) { 9092617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri if ( backtracking>0 ) return; 9192617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri ParseTree ruleNode = (ParseTree)callStack.peek(); 9292617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri ParseTree elementNode = create(token); 9392617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri elementNode.hiddenTokens = this.hiddenTokens; 9492617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri this.hiddenTokens = new ArrayList(); 9592617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri ruleNode.addChild(elementNode); 9692617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri } 9792617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri 9892617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri public void consumeHiddenToken(Token token) { 9992617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri if ( backtracking>0 ) return; 10092617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri hiddenTokens.add(token); 10192617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri } 10292617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri 10392617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri public void recognitionException(RecognitionException e) { 10492617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri if ( backtracking>0 ) return; 10592617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri ParseTree ruleNode = (ParseTree)callStack.peek(); 10692617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri ParseTree errorNode = create(e); 10792617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri ruleNode.addChild(errorNode); 10892617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri } 10992617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri} 11092617aeac109481258f0c3863d09c1b8903d438bLuca Barbieri