1324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver""" @package antlr3.dottreegenerator 2324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver@brief ANTLR3 runtime package, tree module 3324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 4324c4644fee44b9898524c09511bd33c3f12e2dfBen GruverThis module contains all support classes for AST construction and tree parsers. 5324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 6324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver""" 7324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 8324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver# begin[licence] 9324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver# 10324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver# [The "BSD licence"] 11324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver# Copyright (c) 2005-2008 Terence Parr 12324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver# All rights reserved. 13324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver# 14324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver# Redistribution and use in source and binary forms, with or without 15324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver# modification, are permitted provided that the following conditions 16324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver# are met: 17324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver# 1. Redistributions of source code must retain the above copyright 18324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver# notice, this list of conditions and the following disclaimer. 19324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver# 2. Redistributions in binary form must reproduce the above copyright 20324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver# notice, this list of conditions and the following disclaimer in the 21324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver# documentation and/or other materials provided with the distribution. 22324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver# 3. The name of the author may not be used to endorse or promote products 23324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver# derived from this software without specific prior written permission. 24324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver# 25324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver# THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 26324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver# IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 27324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver# OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 28324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver# IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 29324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver# INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 30324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver# NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 31324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver# DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 32324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver# THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 33324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver# (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 34324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver# THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 35324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver# 36324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver# end[licence] 37324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 38324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver# lot's of docstrings are missing, don't complain for now... 39324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver# pylint: disable-msg=C0111 40324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 41324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverfrom antlr3.tree import CommonTreeAdaptor 42324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverimport stringtemplate3 43324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 44324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverclass DOTTreeGenerator(object): 45324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver """ 46324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver A utility class to generate DOT diagrams (graphviz) from 47324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver arbitrary trees. You can pass in your own templates and 48324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver can pass in any kind of tree or use Tree interface method. 49324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver """ 50324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 51324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver _treeST = stringtemplate3.StringTemplate( 52324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver template=( 53324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver "digraph {\n" + 54324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver " ordering=out;\n" + 55324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver " ranksep=.4;\n" + 56324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver " node [shape=plaintext, fixedsize=true, fontsize=11, fontname=\"Courier\",\n" + 57324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver " width=.25, height=.25];\n" + 58324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver " edge [arrowsize=.5]\n" + 59324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver " $nodes$\n" + 60324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver " $edges$\n" + 61324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver "}\n") 62324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ) 63324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 64324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver _nodeST = stringtemplate3.StringTemplate( 65324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver template="$name$ [label=\"$text$\"];\n" 66324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ) 67324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 68324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver _edgeST = stringtemplate3.StringTemplate( 69324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver template="$parent$ -> $child$ // \"$parentText$\" -> \"$childText$\"\n" 70324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ) 71324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 72324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver def __init__(self): 73324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ## Track node to number mapping so we can get proper node name back 74324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver self.nodeToNumberMap = {} 75324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 76324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ## Track node number so we can get unique node names 77324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver self.nodeNumber = 0 78324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 79324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 80324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver def toDOT(self, tree, adaptor=None, treeST=_treeST, edgeST=_edgeST): 81324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if adaptor is None: 82324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver adaptor = CommonTreeAdaptor() 83324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 84324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver treeST = treeST.getInstanceOf() 85324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 86324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver self.nodeNumber = 0 87324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver self.toDOTDefineNodes(tree, adaptor, treeST) 88324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 89324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver self.nodeNumber = 0 90324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver self.toDOTDefineEdges(tree, adaptor, treeST, edgeST) 91324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return treeST 92324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 93324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 94324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver def toDOTDefineNodes(self, tree, adaptor, treeST, knownNodes=None): 95324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if knownNodes is None: 96324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver knownNodes = set() 97324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 98324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if tree is None: 99324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return 100324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 101324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver n = adaptor.getChildCount(tree) 102324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if n == 0: 103324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver # must have already dumped as child from previous 104324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver # invocation; do nothing 105324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return 106324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 107324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver # define parent node 108324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver number = self.getNodeNumber(tree) 109324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if number not in knownNodes: 110324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver parentNodeST = self.getNodeST(adaptor, tree) 111324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver treeST.setAttribute("nodes", parentNodeST) 112324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver knownNodes.add(number) 113324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 114324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver # for each child, do a "<unique-name> [label=text]" node def 115324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for i in range(n): 116324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver child = adaptor.getChild(tree, i) 117324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 118324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver number = self.getNodeNumber(child) 119324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if number not in knownNodes: 120324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver nodeST = self.getNodeST(adaptor, child) 121324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver treeST.setAttribute("nodes", nodeST) 122324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver knownNodes.add(number) 123324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 124324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver self.toDOTDefineNodes(child, adaptor, treeST, knownNodes) 125324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 126324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 127324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver def toDOTDefineEdges(self, tree, adaptor, treeST, edgeST): 128324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if tree is None: 129324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return 130324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 131324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver n = adaptor.getChildCount(tree) 132324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if n == 0: 133324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver # must have already dumped as child from previous 134324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver # invocation; do nothing 135324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return 136324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 137324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver parentName = "n%d" % self.getNodeNumber(tree) 138324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 139324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver # for each child, do a parent -> child edge using unique node names 140324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver parentText = adaptor.getText(tree) 141324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for i in range(n): 142324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver child = adaptor.getChild(tree, i) 143324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver childText = adaptor.getText(child) 144324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver childName = "n%d" % self.getNodeNumber(child) 145324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver edgeST = edgeST.getInstanceOf() 146324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver edgeST.setAttribute("parent", parentName) 147324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver edgeST.setAttribute("child", childName) 148324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver edgeST.setAttribute("parentText", parentText) 149324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver edgeST.setAttribute("childText", childText) 150324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver treeST.setAttribute("edges", edgeST) 151324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver self.toDOTDefineEdges(child, adaptor, treeST, edgeST) 152324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 153324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 154324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver def getNodeST(self, adaptor, t): 155324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver text = adaptor.getText(t) 156324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver nodeST = self._nodeST.getInstanceOf() 157324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver uniqueName = "n%d" % self.getNodeNumber(t) 158324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver nodeST.setAttribute("name", uniqueName) 159324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if text is not None: 160324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver text = text.replace('"', r'\\"') 161324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver nodeST.setAttribute("text", text) 162324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return nodeST 163324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 164324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 165324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver def getNodeNumber(self, t): 166324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver try: 167324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return self.nodeToNumberMap[t] 168324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver except KeyError: 169324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver self.nodeToNumberMap[t] = self.nodeNumber 170324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver self.nodeNumber += 1 171324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return self.nodeNumber - 1 172324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 173324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 174324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverdef toDOT(tree, adaptor=None, treeST=DOTTreeGenerator._treeST, edgeST=DOTTreeGenerator._edgeST): 175324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver """ 176324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Generate DOT (graphviz) for a whole tree not just a node. 177324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver For example, 3+4*5 should generate: 178324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 179324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver digraph { 180324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver node [shape=plaintext, fixedsize=true, fontsize=11, fontname="Courier", 181324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver width=.4, height=.2]; 182324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver edge [arrowsize=.7] 183324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver "+"->3 184324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver "+"->"*" 185324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver "*"->4 186324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver "*"->5 187324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 188324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 189324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Return the ST not a string in case people want to alter. 190324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 191324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Takes a Tree interface object. 192324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 193324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Example of invokation: 194324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 195324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver import antlr3 196324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver import antlr3.extras 197324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 198324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver input = antlr3.ANTLRInputStream(sys.stdin) 199324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver lex = TLexer(input) 200324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver tokens = antlr3.CommonTokenStream(lex) 201324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver parser = TParser(tokens) 202324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver tree = parser.e().tree 203324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver print tree.toStringTree() 204324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver st = antlr3.extras.toDOT(t) 205324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver print st 206324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 207324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver """ 208324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 209324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver gen = DOTTreeGenerator() 210324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return gen.toDOT(tree, adaptor, treeST, edgeST) 211