Browse code

Replace pydot and pyparsing by a much faster hand written lexer and parser.

Jose.R.Fonseca authored on 26/10/2008 15:18:31
Showing 1 changed files
1 1
deleted file mode 100644
... ...
@@ -1,380 +0,0 @@
1
-# -*- coding: Latin-1 -*-
2
-"""Graphviz's dot language parser.
3
-
4
-The dotparser parses graphviz files in dot and dot files and transforms them
5
-into a class representation defined by pydot.
6
-
7
-The module needs pyparsing (tested with version 1.2.2) and pydot (tested with 0.9.10)
8
-
9
-Author: Michael Krause <michael@krause-software.de>
10
-"""
11
-
12
-__author__ = 'Michael Krause'
13
-__license__ = 'MIT'
14
-
15
-import sys
16
-import glob
17
-import pydot
18
-import re
19
-
20
-from pyparsing import __version__ as pyparsing_version
21
-from pyparsing import Literal, CaselessLiteral, Word,	\
22
-	Upcase, OneOrMore, ZeroOrMore, Forward, NotAny,		\
23
-	delimitedList, oneOf, Group, Optional, Combine,		\
24
-	alphas, nums, restOfLine, cStyleComment, nums,		\
25
-	alphanums, printables, empty, quotedString,			\
26
-	ParseException, ParseResults, CharsNotIn, _noncomma,\
27
-	dblQuotedString
28
-
29
-
30
-class P_AttrList:
31
-	def __init__(self, toks):
32
-		self.attrs = {}
33
-		i = 0
34
-		while i < len(toks):
35
-			attrname = toks[i]
36
-			attrvalue = toks[i+1]
37
-			self.attrs[attrname] = attrvalue
38
-			i += 2
39
-
40
-	def __repr__(self):
41
-		return "%s(%r)" % (self.__class__.__name__, self.attrs)
42
-
43
-
44
-class DefaultStatement(P_AttrList):
45
-	def __init__(self, default_type, attrs):
46
-		self.default_type = default_type
47
-		self.attrs = attrs
48
-
49
-	def __repr__(self):
50
-		return "%s(%s, %r)" %	\
51
-			(self.__class__.__name__, self.default_type, self.attrs)
52
-
53
-
54
-def push_top_graph_stmt(str, loc, toks):
55
-	attrs = {}
56
-	g = None
57
-	
58
-	for element in toks:
59
-		if 	isinstance(element, ParseResults) or	\
60
-			isinstance(element, tuple) or			\
61
-			isinstance(element, list):
62
-			
63
-			element = element[0]
64
-
65
-		if element == 'strict':
66
-			attrs['strict'] = True
67
-		elif element in ['graph', 'digraph']:
68
-			attrs['graph_type'] = element
69
-		elif type(element) == type(''):
70
-			attrs['graph_name'] = element
71
-		elif isinstance(element, pydot.Graph):
72
-			g = pydot.Graph(**attrs)
73
-			g.__dict__.update(element.__dict__)
74
-			for e in g.get_edge_list():
75
-				e.parent_graph = g
76
-			for e in g.get_node_list():
77
-				e.parent_graph = g
78
-			for e in g.get_subgraph_list():
79
-				e.set_graph_parent(g)
80
-
81
-		elif isinstance(element, P_AttrList):
82
-			attrs.update(element.attrs)
83
-		else:
84
-			raise ValueError, "Unknown element statement: %r " % element
85
-	
86
-	if g is not None:
87
-		g.__dict__.update(attrs)
88
-		return g
89
-
90
-
91
-def add_defaults(element, defaults):
92
-	d = element.__dict__
93
-	for key, value in defaults.items():
94
-		if not d.get(key):
95
-			d[key] = value
96
-
97
-
98
-def add_elements(g, toks, defaults_graph=None, defaults_node=None, defaults_edge=None):
99
-	
100
-	if defaults_graph is None:
101
-		defaults_graph = {}
102
-	if defaults_node is None:
103
-		defaults_node = {}
104
-	if defaults_edge is None:
105
-		defaults_edge = {}
106
-		
107
-	for element in toks:
108
-		if isinstance(element, pydot.Graph):
109
-			add_defaults(element, defaults_graph)
110
-			g.add_subgraph(element)
111
-		elif isinstance(element, pydot.Node):
112
-			add_defaults(element, defaults_node)
113
-			g.add_node(element)
114
-		elif isinstance(element, pydot.Edge):
115
-			add_defaults(element, defaults_edge)
116
-			g.add_edge(element)
117
-		elif isinstance(element, ParseResults):
118
-			for e in element:
119
-				add_elements(g, [e], defaults_graph, defaults_node, defaults_edge)
120
-		elif isinstance(element, DefaultStatement):
121
-			if element.default_type == 'graph':
122
-				default_graph_attrs = pydot.Node('graph')
123
-				default_graph_attrs.__dict__.update(element.attrs)
124
-				g.add_node(default_graph_attrs)
125
-				defaults_graph.update(element.attrs)
126
-				g.__dict__.update(element.attrs)
127
-			elif element.default_type == 'node':
128
-				default_node_attrs = pydot.Node('node')
129
-				default_node_attrs.__dict__.update(element.attrs)
130
-				g.add_node(default_node_attrs)
131
-# 				defaults_node.update(element.attrs)
132
-			elif element.default_type == 'edge':
133
-				default_edge_attrs = pydot.Node('edge')
134
-				default_edge_attrs.__dict__.update(element.attrs)
135
-				g.add_node(default_edge_attrs)
136
-				defaults_edge.update(element.attrs)
137
-			else:
138
-				raise ValueError, "Unknown DefaultStatement: %s " % element.default_type
139
-		elif isinstance(element, P_AttrList):
140
-			g.__dict__.update(element.attrs)
141
-		else:
142
-			raise ValueError, "Unknown element statement: %r " % element
143
-
144
-
145
-def push_graph_stmt(str, loc, toks):
146
-	g = pydot.Subgraph()
147
-	add_elements(g, toks)
148
-	return g
149
-
150
-
151
-def push_subgraph_stmt(str, loc, toks):	
152
-
153
-	for e in toks:
154
-		if len(e)==3:
155
-			g = e[2]
156
-			g.set_name(e[1])
157
-		if len(e)==1:
158
-			e[0].set_name('')
159
-			return e[0]
160
-
161
-	return g
162
-
163
-
164
-def push_default_stmt(str, loc, toks):
165
-	# The pydot class instances should be marked as
166
-	# default statements to be inherited by actual
167
-	# graphs, nodes and edges.
168
-	# print "push_default_stmt", toks
169
-	default_type = toks[0][0]
170
-	if len(toks) > 1:
171
-		attrs = toks[1].attrs
172
-	else:
173
-		attrs = {}
174
-
175
-	if default_type in ['graph', 'node', 'edge']:
176
-		return DefaultStatement(default_type, attrs)
177
-	else:
178
-		raise ValueError, "Unknown default statement: %r " % toks
179
-
180
-
181
-def push_attr_list(str, loc, toks):
182
-	p = P_AttrList(toks)
183
-	return p
184
-
185
-
186
-def get_port(node):
187
-
188
-	if len(node)>1:
189
-		if isinstance(node[1], ParseResults):
190
-			if len(node[1][0])==2:
191
-				if node[1][0][0]==':':
192
-					return node[1][0][1]
193
-					
194
-	return None
195
-
196
-	
197
-def do_node_ports(n_prev, n_next):
198
-	port = get_port(n_prev)
199
-	if port is not None:
200
-		n_prev_port = ':'+port
201
-	else:
202
-		n_prev_port = ''
203
-		
204
-	port = get_port(n_next)
205
-	if port is not None:
206
-		n_next_port = ':'+port
207
-	else:
208
-		n_next_port = ''
209
-		
210
-	return (n_prev_port, n_next_port)
211
-
212
-	
213
-def push_edge_stmt(str, loc, toks):
214
-	
215
-	tok_attrs = [a for a in toks if isinstance(a, P_AttrList)]
216
-	attrs = {}
217
-	for a in tok_attrs:
218
-		attrs.update(a.attrs)
219
-	
220
-	e = []
221
-	n_prev = toks[0]
222
-	if isinstance(toks[2][0], pydot.Graph):
223
-		n_next_list = [[n.get_name(),] for n in toks[2][0].get_node_list()]
224
-		for n_next in [n for n in n_next_list]:
225
-			n_prev_port, n_next_port = do_node_ports(n_prev, n_next)
226
-			e.append(pydot.Edge(n_prev[0]+n_prev_port, n_next[0]+n_next_port, **attrs))
227
-	else:		
228
-		for n_next in [n for n in tuple(toks)[2::2]]:
229
-			n_prev_port, n_next_port = do_node_ports(n_prev, n_next)
230
-			e.append(pydot.Edge(n_prev[0]+n_prev_port, n_next[0]+n_next_port, **attrs))
231
-			n_prev = n_next
232
-		
233
-	return e
234
-
235
-
236
-def push_node_stmt(str, loc, toks):
237
-
238
-	if len(toks) == 2:
239
-		attrs = toks[1].attrs
240
-	else:
241
-		attrs = {}
242
-		
243
-	node_name = toks[0]
244
-	if isinstance(node_name, list) or isinstance(node_name, tuple):
245
-		if len(node_name)>0:
246
-			node_name = node_name[0]
247
-	
248
-	n = pydot.Node('"'+node_name+'"', **attrs)
249
-	return n
250
-
251
-
252
-def strip_quotes( s, l, t ):
253
-	return [ t[0].strip('"') ]
254
-
255
-
256
-graphparser = None
257
-def graph_definition():
258
-	global graphparser
259
-	
260
-	if not graphparser:
261
-		# punctuation
262
-		colon  = Literal(":")
263
-		lbrace = Literal("{")
264
-		rbrace = Literal("}")
265
-		lbrack = Literal("[")
266
-		rbrack = Literal("]")
267
-		lparen = Literal("(")
268
-		rparen = Literal(")")
269
-		equals = Literal("=")
270
-		comma  = Literal(",")
271
-		dot    = Literal(".")
272
-		slash  = Literal("/")
273
-		bslash = Literal("\\")
274
-		star   = Literal("*")
275
-		semi   = Literal(";")
276
-		at     = Literal("@")
277
-		minus  = Literal("-")
278
-		
279
-		# keywords
280
-		strict_    = Literal("strict")
281
-		graph_     = Literal("graph")
282
-		digraph_   = Literal("digraph")
283
-		subgraph_  = Literal("subgraph")
284
-		node_      = Literal("node")
285
-		edge_      = Literal("edge")
286
-
287
-		
288
-		# token definitions
289
-		
290
-		identifier = Word(alphanums + "_" ).setName("identifier")
291
-		
292
- 		double_quoted_string = dblQuotedString
293
-
294
-		alphastring_ = OneOrMore(CharsNotIn(_noncomma))
295
-
296
-		ID = (identifier | double_quoted_string.setParseAction(strip_quotes) |\
297
-			alphastring_).setName("ID")
298
-			
299
-		html_text = Combine(Literal("<<") + OneOrMore(CharsNotIn(",]")))
300
-		
301
-		float_number = Combine(Optional(minus) +	\
302
-			OneOrMore(Word(nums + "."))).setName("float_number")
303
-			
304
-		righthand_id =  (float_number | ID | html_text).setName("righthand_id")
305
-
306
-		port_angle = (at + ID).setName("port_angle")
307
-		
308
-		port_location = (Group(colon + ID) |	\
309
-			Group(colon + lparen + ID + comma + ID + rparen)).setName("port_location")
310
-			
311
-		port = (Group(port_location + Optional(port_angle)) |	\
312
-			Group(port_angle + Optional(port_location))).setName("port")
313
-			
314
-		node_id = (ID + Optional(port))
315
-		a_list = OneOrMore(ID + Optional(equals.suppress() + righthand_id) +	\
316
-			Optional(comma.suppress())).setName("a_list")
317
-			
318
-		attr_list = OneOrMore(lbrack.suppress() + Optional(a_list) +	\
319
-			rbrack.suppress()).setName("attr_list")
320
-			
321
-		attr_stmt = (Group(graph_ | node_ | edge_) + attr_list).setName("attr_stmt")
322
-
323
-		edgeop = (Literal("--") | Literal("->")).setName("edgeop")
324
-
325
-		stmt_list = Forward()
326
-		graph_stmt = Group(lbrace.suppress() + Optional(stmt_list) +	\
327
-			rbrace.suppress()).setName("graph_stmt")
328
-			
329
-		subgraph = (Group(Optional(subgraph_ + Optional(ID)) + graph_stmt) |	\
330
-			Group(subgraph_ + ID)).setName("subgraph")
331
-			
332
-		edgeRHS = OneOrMore(edgeop + Group(node_id | subgraph))
333
-		
334
-		edge_stmt = Group(node_id | subgraph) + edgeRHS + Optional(attr_list)
335
-
336
-		node_stmt = (node_id + Optional(attr_list) + Optional(semi.suppress())).setName("node_stmt")
337
-		
338
-		assignment = (ID + equals.suppress() + righthand_id).setName("assignment")
339
-		stmt =  (assignment | edge_stmt | attr_stmt | subgraph | node_stmt).setName("stmt")
340
-		stmt_list << OneOrMore(stmt + Optional(semi.suppress()))
341
-
342
-		graphparser = (Optional(strict_) + Group((graph_ | digraph_)) +	\
343
-			Optional(ID) + graph_stmt).setResultsName("graph")
344
-
345
-		singleLineComment = "//" + restOfLine
346
-		
347
-		
348
-		# actions
349
-		
350
-		graphparser.ignore(singleLineComment)
351
-		graphparser.ignore(cStyleComment)
352
-
353
-		assignment.setParseAction(push_attr_list)
354
-		a_list.setParseAction(push_attr_list)
355
-		edge_stmt.setParseAction(push_edge_stmt)
356
-		node_stmt.setParseAction(push_node_stmt)
357
-		attr_stmt.setParseAction(push_default_stmt)
358
-
359
-		subgraph.setParseAction(push_subgraph_stmt)
360
-		graph_stmt.setParseAction(push_graph_stmt)
361
-		graphparser.setParseAction(push_top_graph_stmt)
362
-
363
-		
364
-	return graphparser
365
-
366
-
367
-def parse_dot_data(data):
368
-	try:
369
-		data = data.replace('\\\n', '')
370
-		graphparser = graph_definition()
371
-		if pyparsing_version >= '1.2':
372
-			graphparser.parseWithTabs()
373
-		tokens = graphparser.parseString(data)
374
-		graph = tokens.graph
375
-		return graph
376
-	except ParseException, err:
377
-		print err.line
378
-		print " "*(err.column-1) + "^"
379
-		print err
380
-		return None
Browse code

Require pydot version 0.9.10.

Last commit was bogus, as I had leftover pydot-0.9.10's .pyc files.

Actually, this is just temporary solution -- pydot broke backwards
compatability in many ways and it is better to cut its dependency as it does
not provide a reliable API.

Jose.R.Fonseca authored on 13/07/2008 02:19:21
Showing 1 changed files
1 1
new file mode 100644
... ...
@@ -0,0 +1,380 @@
1
+# -*- coding: Latin-1 -*-
2
+"""Graphviz's dot language parser.
3
+
4
+The dotparser parses graphviz files in dot and dot files and transforms them
5
+into a class representation defined by pydot.
6
+
7
+The module needs pyparsing (tested with version 1.2.2) and pydot (tested with 0.9.10)
8
+
9
+Author: Michael Krause <michael@krause-software.de>
10
+"""
11
+
12
+__author__ = 'Michael Krause'
13
+__license__ = 'MIT'
14
+
15
+import sys
16
+import glob
17
+import pydot
18
+import re
19
+
20
+from pyparsing import __version__ as pyparsing_version
21
+from pyparsing import Literal, CaselessLiteral, Word,	\
22
+	Upcase, OneOrMore, ZeroOrMore, Forward, NotAny,		\
23
+	delimitedList, oneOf, Group, Optional, Combine,		\
24
+	alphas, nums, restOfLine, cStyleComment, nums,		\
25
+	alphanums, printables, empty, quotedString,			\
26
+	ParseException, ParseResults, CharsNotIn, _noncomma,\
27
+	dblQuotedString
28
+
29
+
30
+class P_AttrList:
31
+	def __init__(self, toks):
32
+		self.attrs = {}
33
+		i = 0
34
+		while i < len(toks):
35
+			attrname = toks[i]
36
+			attrvalue = toks[i+1]
37
+			self.attrs[attrname] = attrvalue
38
+			i += 2
39
+
40
+	def __repr__(self):
41
+		return "%s(%r)" % (self.__class__.__name__, self.attrs)
42
+
43
+
44
+class DefaultStatement(P_AttrList):
45
+	def __init__(self, default_type, attrs):
46
+		self.default_type = default_type
47
+		self.attrs = attrs
48
+
49
+	def __repr__(self):
50
+		return "%s(%s, %r)" %	\
51
+			(self.__class__.__name__, self.default_type, self.attrs)
52
+
53
+
54
+def push_top_graph_stmt(str, loc, toks):
55
+	attrs = {}
56
+	g = None
57
+	
58
+	for element in toks:
59
+		if 	isinstance(element, ParseResults) or	\
60
+			isinstance(element, tuple) or			\
61
+			isinstance(element, list):
62
+			
63
+			element = element[0]
64
+
65
+		if element == 'strict':
66
+			attrs['strict'] = True
67
+		elif element in ['graph', 'digraph']:
68
+			attrs['graph_type'] = element
69
+		elif type(element) == type(''):
70
+			attrs['graph_name'] = element
71
+		elif isinstance(element, pydot.Graph):
72
+			g = pydot.Graph(**attrs)
73
+			g.__dict__.update(element.__dict__)
74
+			for e in g.get_edge_list():
75
+				e.parent_graph = g
76
+			for e in g.get_node_list():
77
+				e.parent_graph = g
78
+			for e in g.get_subgraph_list():
79
+				e.set_graph_parent(g)
80
+
81
+		elif isinstance(element, P_AttrList):
82
+			attrs.update(element.attrs)
83
+		else:
84
+			raise ValueError, "Unknown element statement: %r " % element
85
+	
86
+	if g is not None:
87
+		g.__dict__.update(attrs)
88
+		return g
89
+
90
+
91
+def add_defaults(element, defaults):
92
+	d = element.__dict__
93
+	for key, value in defaults.items():
94
+		if not d.get(key):
95
+			d[key] = value
96
+
97
+
98
+def add_elements(g, toks, defaults_graph=None, defaults_node=None, defaults_edge=None):
99
+	
100
+	if defaults_graph is None:
101
+		defaults_graph = {}
102
+	if defaults_node is None:
103
+		defaults_node = {}
104
+	if defaults_edge is None:
105
+		defaults_edge = {}
106
+		
107
+	for element in toks:
108
+		if isinstance(element, pydot.Graph):
109
+			add_defaults(element, defaults_graph)
110
+			g.add_subgraph(element)
111
+		elif isinstance(element, pydot.Node):
112
+			add_defaults(element, defaults_node)
113
+			g.add_node(element)
114
+		elif isinstance(element, pydot.Edge):
115
+			add_defaults(element, defaults_edge)
116
+			g.add_edge(element)
117
+		elif isinstance(element, ParseResults):
118
+			for e in element:
119
+				add_elements(g, [e], defaults_graph, defaults_node, defaults_edge)
120
+		elif isinstance(element, DefaultStatement):
121
+			if element.default_type == 'graph':
122
+				default_graph_attrs = pydot.Node('graph')
123
+				default_graph_attrs.__dict__.update(element.attrs)
124
+				g.add_node(default_graph_attrs)
125
+				defaults_graph.update(element.attrs)
126
+				g.__dict__.update(element.attrs)
127
+			elif element.default_type == 'node':
128
+				default_node_attrs = pydot.Node('node')
129
+				default_node_attrs.__dict__.update(element.attrs)
130
+				g.add_node(default_node_attrs)
131
+# 				defaults_node.update(element.attrs)
132
+			elif element.default_type == 'edge':
133
+				default_edge_attrs = pydot.Node('edge')
134
+				default_edge_attrs.__dict__.update(element.attrs)
135
+				g.add_node(default_edge_attrs)
136
+				defaults_edge.update(element.attrs)
137
+			else:
138
+				raise ValueError, "Unknown DefaultStatement: %s " % element.default_type
139
+		elif isinstance(element, P_AttrList):
140
+			g.__dict__.update(element.attrs)
141
+		else:
142
+			raise ValueError, "Unknown element statement: %r " % element
143
+
144
+
145
+def push_graph_stmt(str, loc, toks):
146
+	g = pydot.Subgraph()
147
+	add_elements(g, toks)
148
+	return g
149
+
150
+
151
+def push_subgraph_stmt(str, loc, toks):	
152
+
153
+	for e in toks:
154
+		if len(e)==3:
155
+			g = e[2]
156
+			g.set_name(e[1])
157
+		if len(e)==1:
158
+			e[0].set_name('')
159
+			return e[0]
160
+
161
+	return g
162
+
163
+
164
+def push_default_stmt(str, loc, toks):
165
+	# The pydot class instances should be marked as
166
+	# default statements to be inherited by actual
167
+	# graphs, nodes and edges.
168
+	# print "push_default_stmt", toks
169
+	default_type = toks[0][0]
170
+	if len(toks) > 1:
171
+		attrs = toks[1].attrs
172
+	else:
173
+		attrs = {}
174
+
175
+	if default_type in ['graph', 'node', 'edge']:
176
+		return DefaultStatement(default_type, attrs)
177
+	else:
178
+		raise ValueError, "Unknown default statement: %r " % toks
179
+
180
+
181
+def push_attr_list(str, loc, toks):
182
+	p = P_AttrList(toks)
183
+	return p
184
+
185
+
186
+def get_port(node):
187
+
188
+	if len(node)>1:
189
+		if isinstance(node[1], ParseResults):
190
+			if len(node[1][0])==2:
191
+				if node[1][0][0]==':':
192
+					return node[1][0][1]
193
+					
194
+	return None
195
+
196
+	
197
+def do_node_ports(n_prev, n_next):
198
+	port = get_port(n_prev)
199
+	if port is not None:
200
+		n_prev_port = ':'+port
201
+	else:
202
+		n_prev_port = ''
203
+		
204
+	port = get_port(n_next)
205
+	if port is not None:
206
+		n_next_port = ':'+port
207
+	else:
208
+		n_next_port = ''
209
+		
210
+	return (n_prev_port, n_next_port)
211
+
212
+	
213
+def push_edge_stmt(str, loc, toks):
214
+	
215
+	tok_attrs = [a for a in toks if isinstance(a, P_AttrList)]
216
+	attrs = {}
217
+	for a in tok_attrs:
218
+		attrs.update(a.attrs)
219
+	
220
+	e = []
221
+	n_prev = toks[0]
222
+	if isinstance(toks[2][0], pydot.Graph):
223
+		n_next_list = [[n.get_name(),] for n in toks[2][0].get_node_list()]
224
+		for n_next in [n for n in n_next_list]:
225
+			n_prev_port, n_next_port = do_node_ports(n_prev, n_next)
226
+			e.append(pydot.Edge(n_prev[0]+n_prev_port, n_next[0]+n_next_port, **attrs))
227
+	else:		
228
+		for n_next in [n for n in tuple(toks)[2::2]]:
229
+			n_prev_port, n_next_port = do_node_ports(n_prev, n_next)
230
+			e.append(pydot.Edge(n_prev[0]+n_prev_port, n_next[0]+n_next_port, **attrs))
231
+			n_prev = n_next
232
+		
233
+	return e
234
+
235
+
236
+def push_node_stmt(str, loc, toks):
237
+
238
+	if len(toks) == 2:
239
+		attrs = toks[1].attrs
240
+	else:
241
+		attrs = {}
242
+		
243
+	node_name = toks[0]
244
+	if isinstance(node_name, list) or isinstance(node_name, tuple):
245
+		if len(node_name)>0:
246
+			node_name = node_name[0]
247
+	
248
+	n = pydot.Node('"'+node_name+'"', **attrs)
249
+	return n
250
+
251
+
252
+def strip_quotes( s, l, t ):
253
+	return [ t[0].strip('"') ]
254
+
255
+
256
+graphparser = None
257
+def graph_definition():
258
+	global graphparser
259
+	
260
+	if not graphparser:
261
+		# punctuation
262
+		colon  = Literal(":")
263
+		lbrace = Literal("{")
264
+		rbrace = Literal("}")
265
+		lbrack = Literal("[")
266
+		rbrack = Literal("]")
267
+		lparen = Literal("(")
268
+		rparen = Literal(")")
269
+		equals = Literal("=")
270
+		comma  = Literal(",")
271
+		dot    = Literal(".")
272
+		slash  = Literal("/")
273
+		bslash = Literal("\\")
274
+		star   = Literal("*")
275
+		semi   = Literal(";")
276
+		at     = Literal("@")
277
+		minus  = Literal("-")
278
+		
279
+		# keywords
280
+		strict_    = Literal("strict")
281
+		graph_     = Literal("graph")
282
+		digraph_   = Literal("digraph")
283
+		subgraph_  = Literal("subgraph")
284
+		node_      = Literal("node")
285
+		edge_      = Literal("edge")
286
+
287
+		
288
+		# token definitions
289
+		
290
+		identifier = Word(alphanums + "_" ).setName("identifier")
291
+		
292
+ 		double_quoted_string = dblQuotedString
293
+
294
+		alphastring_ = OneOrMore(CharsNotIn(_noncomma))
295
+
296
+		ID = (identifier | double_quoted_string.setParseAction(strip_quotes) |\
297
+			alphastring_).setName("ID")
298
+			
299
+		html_text = Combine(Literal("<<") + OneOrMore(CharsNotIn(",]")))
300
+		
301
+		float_number = Combine(Optional(minus) +	\
302
+			OneOrMore(Word(nums + "."))).setName("float_number")
303
+			
304
+		righthand_id =  (float_number | ID | html_text).setName("righthand_id")
305
+
306
+		port_angle = (at + ID).setName("port_angle")
307
+		
308
+		port_location = (Group(colon + ID) |	\
309
+			Group(colon + lparen + ID + comma + ID + rparen)).setName("port_location")
310
+			
311
+		port = (Group(port_location + Optional(port_angle)) |	\
312
+			Group(port_angle + Optional(port_location))).setName("port")
313
+			
314
+		node_id = (ID + Optional(port))
315
+		a_list = OneOrMore(ID + Optional(equals.suppress() + righthand_id) +	\
316
+			Optional(comma.suppress())).setName("a_list")
317
+			
318
+		attr_list = OneOrMore(lbrack.suppress() + Optional(a_list) +	\
319
+			rbrack.suppress()).setName("attr_list")
320
+			
321
+		attr_stmt = (Group(graph_ | node_ | edge_) + attr_list).setName("attr_stmt")
322
+
323
+		edgeop = (Literal("--") | Literal("->")).setName("edgeop")
324
+
325
+		stmt_list = Forward()
326
+		graph_stmt = Group(lbrace.suppress() + Optional(stmt_list) +	\
327
+			rbrace.suppress()).setName("graph_stmt")
328
+			
329
+		subgraph = (Group(Optional(subgraph_ + Optional(ID)) + graph_stmt) |	\
330
+			Group(subgraph_ + ID)).setName("subgraph")
331
+			
332
+		edgeRHS = OneOrMore(edgeop + Group(node_id | subgraph))
333
+		
334
+		edge_stmt = Group(node_id | subgraph) + edgeRHS + Optional(attr_list)
335
+
336
+		node_stmt = (node_id + Optional(attr_list) + Optional(semi.suppress())).setName("node_stmt")
337
+		
338
+		assignment = (ID + equals.suppress() + righthand_id).setName("assignment")
339
+		stmt =  (assignment | edge_stmt | attr_stmt | subgraph | node_stmt).setName("stmt")
340
+		stmt_list << OneOrMore(stmt + Optional(semi.suppress()))
341
+
342
+		graphparser = (Optional(strict_) + Group((graph_ | digraph_)) +	\
343
+			Optional(ID) + graph_stmt).setResultsName("graph")
344
+
345
+		singleLineComment = "//" + restOfLine
346
+		
347
+		
348
+		# actions
349
+		
350
+		graphparser.ignore(singleLineComment)
351
+		graphparser.ignore(cStyleComment)
352
+
353
+		assignment.setParseAction(push_attr_list)
354
+		a_list.setParseAction(push_attr_list)
355
+		edge_stmt.setParseAction(push_edge_stmt)
356
+		node_stmt.setParseAction(push_node_stmt)
357
+		attr_stmt.setParseAction(push_default_stmt)
358
+
359
+		subgraph.setParseAction(push_subgraph_stmt)
360
+		graph_stmt.setParseAction(push_graph_stmt)
361
+		graphparser.setParseAction(push_top_graph_stmt)
362
+
363
+		
364
+	return graphparser
365
+
366
+
367
+def parse_dot_data(data):
368
+	try:
369
+		data = data.replace('\\\n', '')
370
+		graphparser = graph_definition()
371
+		if pyparsing_version >= '1.2':
372
+			graphparser.parseWithTabs()
373
+		tokens = graphparser.parseString(data)
374
+		graph = tokens.graph
375
+		return graph
376
+	except ParseException, err:
377
+		print err.line
378
+		print " "*(err.column-1) + "^"
379
+		print err
380
+		return None