Python code coverage for Parser/spark.py

#	count	content
1	n/a	# Copyright (c) 1998-2002 John Aycock
2	n/a	#
3	n/a	# Permission is hereby granted, free of charge, to any person obtaining
4	n/a	# a copy of this software and associated documentation files (the
5	n/a	# "Software"), to deal in the Software without restriction, including
6	n/a	# without limitation the rights to use, copy, modify, merge, publish,
7	n/a	# distribute, sublicense, and/or sell copies of the Software, and to
8	n/a	# permit persons to whom the Software is furnished to do so, subject to
9	n/a	# the following conditions:
10	n/a	#
11	n/a	# The above copyright notice and this permission notice shall be
12	n/a	# included in all copies or substantial portions of the Software.
13	n/a	#
14	n/a	# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
15	n/a	# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
16	n/a	# MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
17	n/a	# IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
18	n/a	# CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
19	n/a	# TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
20	n/a	# SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
21	n/a
22	n/a	__version__ = 'SPARK-0.7 (pre-alpha-5)'
23	n/a
24	n/a	import re
25	n/a
26	n/a	# Compatibility with older pythons.
27	n/a	def output(string='', end='\n'):
28	n/a	sys.stdout.write(string + end)
29	n/a
30	n/a	try:
31	n/a	sorted
32	n/a	except NameError:
33	n/a	def sorted(seq):
34	n/a	seq2 = seq[:]
35	n/a	seq2.sort()
36	n/a	return seq2
37	n/a
38	n/a	def _namelist(instance):
39	n/a	namelist, namedict, classlist = [], {}, [instance.__class__]
40	n/a	for c in classlist:
41	n/a	for b in c.__bases__:
42	n/a	classlist.append(b)
43	n/a	for name in c.__dict__.keys():
44	n/a	if name not in namedict:
45	n/a	namelist.append(name)
46	n/a	namedict[name] = 1
47	n/a	return namelist
48	n/a
49	n/a	class GenericScanner:
50	n/a	def __init__(self, flags=0):
51	n/a	pattern = self.reflect()
52	n/a	self.re = re.compile(pattern, re.VERBOSE\|flags)
53	n/a
54	n/a	self.index2func = {}
55	n/a	for name, number in self.re.groupindex.items():
56	n/a	self.index2func[number-1] = getattr(self, 't_' + name)
57	n/a
58	n/a	def makeRE(self, name):
59	n/a	doc = getattr(self, name).__doc__
60	n/a	rv = '(?P<%s>%s)' % (name[2:], doc)
61	n/a	return rv
62	n/a
63	n/a	def reflect(self):
64	n/a	rv = []
65	n/a	for name in _namelist(self):
66	n/a	if name[:2] == 't_' and name != 't_default':
67	n/a	rv.append(self.makeRE(name))
68	n/a
69	n/a	rv.append(self.makeRE('t_default'))
70	n/a	return '\|'.join(rv)
71	n/a
72	n/a	def error(self, s, pos):
73	n/a	output("Lexical error at position %s" % pos)
74	n/a	raise SystemExit
75	n/a
76	n/a	def tokenize(self, s):
77	n/a	pos = 0
78	n/a	n = len(s)
79	n/a	while pos < n:
80	n/a	m = self.re.match(s, pos)
81	n/a	if m is None:
82	n/a	self.error(s, pos)
83	n/a
84	n/a	groups = m.groups()
85	n/a	for i in range(len(groups)):
86	n/a	if groups[i] and i in self.index2func:
87	n/a	self.index2func[i](groups[i])
88	n/a	pos = m.end()
89	n/a
90	n/a	def t_default(self, s):
91	n/a	r'( . \| \n )+'
92	n/a	output("Specification error: unmatched input")
93	n/a	raise SystemExit
94	n/a
95	n/a	#
96	n/a	# Extracted from GenericParser and made global so that [un]picking works.
97	n/a	#
98	n/a	class _State:
99	n/a	def __init__(self, stateno, items):
100	n/a	self.T, self.complete, self.items = [], [], items
101	n/a	self.stateno = stateno
102	n/a
103	n/a	class GenericParser:
104	n/a	#
105	n/a	# An Earley parser, as per J. Earley, "An Efficient Context-Free
106	n/a	# Parsing Algorithm", CACM 13(2), pp. 94-102. Also J. C. Earley,
107	n/a	# "An Efficient Context-Free Parsing Algorithm", Ph.D. thesis,
108	n/a	# Carnegie-Mellon University, August 1968. New formulation of
109	n/a	# the parser according to J. Aycock, "Practical Earley Parsing
110	n/a	# and the SPARK Toolkit", Ph.D. thesis, University of Victoria,
111	n/a	# 2001, and J. Aycock and R. N. Horspool, "Practical Earley
112	n/a	# Parsing", unpublished paper, 2001.
113	n/a	#
114	n/a
115	n/a	def __init__(self, start):
116	n/a	self.rules = {}
117	n/a	self.rule2func = {}
118	n/a	self.rule2name = {}
119	n/a	self.collectRules()
120	n/a	self.augment(start)
121	n/a	self.ruleschanged = 1
122	n/a
123	n/a	_NULLABLE = '\e_'
124	n/a	_START = 'START'
125	n/a	_BOF = '\|-'
126	n/a
127	n/a	#
128	n/a	# When pickling, take the time to generate the full state machine;
129	n/a	# some information is then extraneous, too. Unfortunately we
130	n/a	# can't save the rule2func map.
131	n/a	#
132	n/a	def __getstate__(self):
133	n/a	if self.ruleschanged:
134	n/a	#
135	n/a	# XXX - duplicated from parse()
136	n/a	#
137	n/a	self.computeNull()
138	n/a	self.newrules = {}
139	n/a	self.new2old = {}
140	n/a	self.makeNewRules()
141	n/a	self.ruleschanged = 0
142	n/a	self.edges, self.cores = {}, {}
143	n/a	self.states = { 0: self.makeState0() }
144	n/a	self.makeState(0, self._BOF)
145	n/a	#
146	n/a	# XXX - should find a better way to do this..
147	n/a	#
148	n/a	changes = 1
149	n/a	while changes:
150	n/a	changes = 0
151	n/a	for k, v in self.edges.items():
152	n/a	if v is None:
153	n/a	state, sym = k
154	n/a	if state in self.states:
155	n/a	self.goto(state, sym)
156	n/a	changes = 1
157	n/a	rv = self.__dict__.copy()
158	n/a	for s in self.states.values():
159	n/a	del s.items
160	n/a	del rv['rule2func']
161	n/a	del rv['nullable']
162	n/a	del rv['cores']
163	n/a	return rv
164	n/a
165	n/a	def __setstate__(self, D):
166	n/a	self.rules = {}
167	n/a	self.rule2func = {}
168	n/a	self.rule2name = {}
169	n/a	self.collectRules()
170	n/a	start = D['rules'][self._START][0][1][1] # Blech.
171	n/a	self.augment(start)
172	n/a	D['rule2func'] = self.rule2func
173	n/a	D['makeSet'] = self.makeSet_fast
174	n/a	self.__dict__ = D
175	n/a
176	n/a	#
177	n/a	# A hook for GenericASTBuilder and GenericASTMatcher. Mess
178	n/a	# thee not with this; nor shall thee toucheth the _preprocess
179	n/a	# argument to addRule.
180	n/a	#
181	n/a	def preprocess(self, rule, func): return rule, func
182	n/a
183	n/a	def addRule(self, doc, func, _preprocess=1):
184	n/a	fn = func
185	n/a	rules = doc.split()
186	n/a
187	n/a	index = []
188	n/a	for i in range(len(rules)):
189	n/a	if rules[i] == '::=':
190	n/a	index.append(i-1)
191	n/a	index.append(len(rules))
192	n/a
193	n/a	for i in range(len(index)-1):
194	n/a	lhs = rules[index[i]]
195	n/a	rhs = rules[index[i]+2:index[i+1]]
196	n/a	rule = (lhs, tuple(rhs))
197	n/a
198	n/a	if _preprocess:
199	n/a	rule, fn = self.preprocess(rule, func)
200	n/a
201	n/a	if lhs in self.rules:
202	n/a	self.rules[lhs].append(rule)
203	n/a	else:
204	n/a	self.rules[lhs] = [ rule ]
205	n/a	self.rule2func[rule] = fn
206	n/a	self.rule2name[rule] = func.__name__[2:]
207	n/a	self.ruleschanged = 1
208	n/a
209	n/a	def collectRules(self):
210	n/a	for name in _namelist(self):
211	n/a	if name[:2] == 'p_':
212	n/a	func = getattr(self, name)
213	n/a	doc = func.__doc__
214	n/a	self.addRule(doc, func)
215	n/a
216	n/a	def augment(self, start):
217	n/a	rule = '%s ::= %s %s' % (self._START, self._BOF, start)
218	n/a	self.addRule(rule, lambda args: args[1], 0)
219	n/a
220	n/a	def computeNull(self):
221	n/a	self.nullable = {}
222	n/a	tbd = []
223	n/a
224	n/a	for rulelist in self.rules.values():
225	n/a	lhs = rulelist[0][0]
226	n/a	self.nullable[lhs] = 0
227	n/a	for rule in rulelist:
228	n/a	rhs = rule[1]
229	n/a	if len(rhs) == 0:
230	n/a	self.nullable[lhs] = 1
231	n/a	continue
232	n/a	#
233	n/a	# We only need to consider rules which
234	n/a	# consist entirely of nonterminal symbols.
235	n/a	# This should be a savings on typical
236	n/a	# grammars.
237	n/a	#
238	n/a	for sym in rhs:
239	n/a	if sym not in self.rules:
240	n/a	break
241	n/a	else:
242	n/a	tbd.append(rule)
243	n/a	changes = 1
244	n/a	while changes:
245	n/a	changes = 0
246	n/a	for lhs, rhs in tbd:
247	n/a	if self.nullable[lhs]:
248	n/a	continue
249	n/a	for sym in rhs:
250	n/a	if not self.nullable[sym]:
251	n/a	break
252	n/a	else:
253	n/a	self.nullable[lhs] = 1
254	n/a	changes = 1
255	n/a
256	n/a	def makeState0(self):
257	n/a	s0 = _State(0, [])
258	n/a	for rule in self.newrules[self._START]:
259	n/a	s0.items.append((rule, 0))
260	n/a	return s0
261	n/a
262	n/a	def finalState(self, tokens):
263	n/a	#
264	n/a	# Yuck.
265	n/a	#
266	n/a	if len(self.newrules[self._START]) == 2 and len(tokens) == 0:
267	n/a	return 1
268	n/a	start = self.rules[self._START][0][1][1]
269	n/a	return self.goto(1, start)
270	n/a
271	n/a	def makeNewRules(self):
272	n/a	worklist = []
273	n/a	for rulelist in self.rules.values():
274	n/a	for rule in rulelist:
275	n/a	worklist.append((rule, 0, 1, rule))
276	n/a
277	n/a	for rule, i, candidate, oldrule in worklist:
278	n/a	lhs, rhs = rule
279	n/a	n = len(rhs)
280	n/a	while i < n:
281	n/a	sym = rhs[i]
282	n/a	if sym not in self.rules or \
283	n/a	not self.nullable[sym]:
284	n/a	candidate = 0
285	n/a	i = i + 1
286	n/a	continue
287	n/a
288	n/a	newrhs = list(rhs)
289	n/a	newrhs[i] = self._NULLABLE+sym
290	n/a	newrule = (lhs, tuple(newrhs))
291	n/a	worklist.append((newrule, i+1,
292	n/a	candidate, oldrule))
293	n/a	candidate = 0
294	n/a	i = i + 1
295	n/a	else:
296	n/a	if candidate:
297	n/a	lhs = self._NULLABLE+lhs
298	n/a	rule = (lhs, rhs)
299	n/a	if lhs in self.newrules:
300	n/a	self.newrules[lhs].append(rule)
301	n/a	else:
302	n/a	self.newrules[lhs] = [ rule ]
303	n/a	self.new2old[rule] = oldrule
304	n/a
305	n/a	def typestring(self, token):
306	n/a	return None
307	n/a
308	n/a	def error(self, token):
309	n/a	output("Syntax error at or near `%s' token" % token)
310	n/a	raise SystemExit
311	n/a
312	n/a	def parse(self, tokens):
313	n/a	sets = [ [(1,0), (2,0)] ]
314	n/a	self.links = {}
315	n/a
316	n/a	if self.ruleschanged:
317	n/a	self.computeNull()
318	n/a	self.newrules = {}
319	n/a	self.new2old = {}
320	n/a	self.makeNewRules()
321	n/a	self.ruleschanged = 0
322	n/a	self.edges, self.cores = {}, {}
323	n/a	self.states = { 0: self.makeState0() }
324	n/a	self.makeState(0, self._BOF)
325	n/a
326	n/a	for i in range(len(tokens)):
327	n/a	sets.append([])
328	n/a
329	n/a	if sets[i] == []:
330	n/a	break
331	n/a	self.makeSet(tokens[i], sets, i)
332	n/a	else:
333	n/a	sets.append([])
334	n/a	self.makeSet(None, sets, len(tokens))
335	n/a
336	n/a	#_dump(tokens, sets, self.states)
337	n/a
338	n/a	finalitem = (self.finalState(tokens), 0)
339	n/a	if finalitem not in sets[-2]:
340	n/a	if len(tokens) > 0:
341	n/a	self.error(tokens[i-1])
342	n/a	else:
343	n/a	self.error(None)
344	n/a
345	n/a	return self.buildTree(self._START, finalitem,
346	n/a	tokens, len(sets)-2)
347	n/a
348	n/a	def isnullable(self, sym):
349	n/a	#
350	n/a	# For symbols in G_e only. If we weren't supporting 1.5,
351	n/a	# could just use sym.startswith().
352	n/a	#
353	n/a	return self._NULLABLE == sym[0:len(self._NULLABLE)]
354	n/a
355	n/a	def skip(self, hs, pos=0):
356	n/a	n = len(hs[1])
357	n/a	while pos < n:
358	n/a	if not self.isnullable(hs[1][pos]):
359	n/a	break
360	n/a	pos = pos + 1
361	n/a	return pos
362	n/a
363	n/a	def makeState(self, state, sym):
364	n/a	assert sym is not None
365	n/a	#
366	n/a	# Compute \epsilon-kernel state's core and see if
367	n/a	# it exists already.
368	n/a	#
369	n/a	kitems = []
370	n/a	for rule, pos in self.states[state].items:
371	n/a	lhs, rhs = rule
372	n/a	if rhs[pos:pos+1] == (sym,):
373	n/a	kitems.append((rule, self.skip(rule, pos+1)))
374	n/a	core = kitems
375	n/a
376	n/a	core.sort()
377	n/a	tcore = tuple(core)
378	n/a	if tcore in self.cores:
379	n/a	return self.cores[tcore]
380	n/a	#
381	n/a	# Nope, doesn't exist. Compute it and the associated
382	n/a	# \epsilon-nonkernel state together; we'll need it right away.
383	n/a	#
384	n/a	k = self.cores[tcore] = len(self.states)
385	n/a	K, NK = _State(k, kitems), _State(k+1, [])
386	n/a	self.states[k] = K
387	n/a	predicted = {}
388	n/a
389	n/a	edges = self.edges
390	n/a	rules = self.newrules
391	n/a	for X in K, NK:
392	n/a	worklist = X.items
393	n/a	for item in worklist:
394	n/a	rule, pos = item
395	n/a	lhs, rhs = rule
396	n/a	if pos == len(rhs):
397	n/a	X.complete.append(rule)
398	n/a	continue
399	n/a
400	n/a	nextSym = rhs[pos]
401	n/a	key = (X.stateno, nextSym)
402	n/a	if nextSym not in rules:
403	n/a	if key not in edges:
404	n/a	edges[key] = None
405	n/a	X.T.append(nextSym)
406	n/a	else:
407	n/a	edges[key] = None
408	n/a	if nextSym not in predicted:
409	n/a	predicted[nextSym] = 1
410	n/a	for prule in rules[nextSym]:
411	n/a	ppos = self.skip(prule)
412	n/a	new = (prule, ppos)
413	n/a	NK.items.append(new)
414	n/a	#
415	n/a	# Problem: we know K needs generating, but we
416	n/a	# don't yet know about NK. Can't commit anything
417	n/a	# regarding NK to self.edges until we're sure. Should
418	n/a	# we delay committing on both K and NK to avoid this
419	n/a	# hacky code? This creates other problems..
420	n/a	#
421	n/a	if X is K:
422	n/a	edges = {}
423	n/a
424	n/a	if NK.items == []:
425	n/a	return k
426	n/a
427	n/a	#
428	n/a	# Check for \epsilon-nonkernel's core. Unfortunately we
429	n/a	# need to know the entire set of predicted nonterminals
430	n/a	# to do this without accidentally duplicating states.
431	n/a	#
432	n/a	core = sorted(predicted.keys())
433	n/a	tcore = tuple(core)
434	n/a	if tcore in self.cores:
435	n/a	self.edges[(k, None)] = self.cores[tcore]
436	n/a	return k
437	n/a
438	n/a	nk = self.cores[tcore] = self.edges[(k, None)] = NK.stateno
439	n/a	self.edges.update(edges)
440	n/a	self.states[nk] = NK
441	n/a	return k
442	n/a
443	n/a	def goto(self, state, sym):
444	n/a	key = (state, sym)
445	n/a	if key not in self.edges:
446	n/a	#
447	n/a	# No transitions from state on sym.
448	n/a	#
449	n/a	return None
450	n/a
451	n/a	rv = self.edges[key]
452	n/a	if rv is None:
453	n/a	#
454	n/a	# Target state isn't generated yet. Remedy this.
455	n/a	#
456	n/a	rv = self.makeState(state, sym)
457	n/a	self.edges[key] = rv
458	n/a	return rv
459	n/a
460	n/a	def gotoT(self, state, t):
461	n/a	return [self.goto(state, t)]
462	n/a
463	n/a	def gotoST(self, state, st):
464	n/a	rv = []
465	n/a	for t in self.states[state].T:
466	n/a	if st == t:
467	n/a	rv.append(self.goto(state, t))
468	n/a	return rv
469	n/a
470	n/a	def add(self, set, item, i=None, predecessor=None, causal=None):
471	n/a	if predecessor is None:
472	n/a	if item not in set:
473	n/a	set.append(item)
474	n/a	else:
475	n/a	key = (item, i)
476	n/a	if item not in set:
477	n/a	self.links[key] = []
478	n/a	set.append(item)
479	n/a	self.links[key].append((predecessor, causal))
480	n/a
481	n/a	def makeSet(self, token, sets, i):
482	n/a	cur, next = sets[i], sets[i+1]
483	n/a
484	n/a	ttype = token is not None and self.typestring(token) or None
485	n/a	if ttype is not None:
486	n/a	fn, arg = self.gotoT, ttype
487	n/a	else:
488	n/a	fn, arg = self.gotoST, token
489	n/a
490	n/a	for item in cur:
491	n/a	ptr = (item, i)
492	n/a	state, parent = item
493	n/a	add = fn(state, arg)
494	n/a	for k in add:
495	n/a	if k is not None:
496	n/a	self.add(next, (k, parent), i+1, ptr)
497	n/a	nk = self.goto(k, None)
498	n/a	if nk is not None:
499	n/a	self.add(next, (nk, i+1))
500	n/a
501	n/a	if parent == i:
502	n/a	continue
503	n/a
504	n/a	for rule in self.states[state].complete:
505	n/a	lhs, rhs = rule
506	n/a	for pitem in sets[parent]:
507	n/a	pstate, pparent = pitem
508	n/a	k = self.goto(pstate, lhs)
509	n/a	if k is not None:
510	n/a	why = (item, i, rule)
511	n/a	pptr = (pitem, parent)
512	n/a	self.add(cur, (k, pparent),
513	n/a	i, pptr, why)
514	n/a	nk = self.goto(k, None)
515	n/a	if nk is not None:
516	n/a	self.add(cur, (nk, i))
517	n/a
518	n/a	def makeSet_fast(self, token, sets, i):
519	n/a	#
520	n/a	# Call only when the entire state machine has been built!
521	n/a	# It relies on self.edges being filled in completely, and
522	n/a	# then duplicates and inlines code to boost speed at the
523	n/a	# cost of extreme ugliness.
524	n/a	#
525	n/a	cur, next = sets[i], sets[i+1]
526	n/a	ttype = token is not None and self.typestring(token) or None
527	n/a
528	n/a	for item in cur:
529	n/a	ptr = (item, i)
530	n/a	state, parent = item
531	n/a	if ttype is not None:
532	n/a	k = self.edges.get((state, ttype), None)
533	n/a	if k is not None:
534	n/a	#self.add(next, (k, parent), i+1, ptr)
535	n/a	#INLINED --v
536	n/a	new = (k, parent)
537	n/a	key = (new, i+1)
538	n/a	if new not in next:
539	n/a	self.links[key] = []
540	n/a	next.append(new)
541	n/a	self.links[key].append((ptr, None))
542	n/a	#INLINED --^
543	n/a	#nk = self.goto(k, None)
544	n/a	nk = self.edges.get((k, None), None)
545	n/a	if nk is not None:
546	n/a	#self.add(next, (nk, i+1))
547	n/a	#INLINED --v
548	n/a	new = (nk, i+1)
549	n/a	if new not in next:
550	n/a	next.append(new)
551	n/a	#INLINED --^
552	n/a	else:
553	n/a	add = self.gotoST(state, token)
554	n/a	for k in add:
555	n/a	if k is not None:
556	n/a	self.add(next, (k, parent), i+1, ptr)
557	n/a	#nk = self.goto(k, None)
558	n/a	nk = self.edges.get((k, None), None)
559	n/a	if nk is not None:
560	n/a	self.add(next, (nk, i+1))
561	n/a
562	n/a	if parent == i:
563	n/a	continue
564	n/a
565	n/a	for rule in self.states[state].complete:
566	n/a	lhs, rhs = rule
567	n/a	for pitem in sets[parent]:
568	n/a	pstate, pparent = pitem
569	n/a	#k = self.goto(pstate, lhs)
570	n/a	k = self.edges.get((pstate, lhs), None)
571	n/a	if k is not None:
572	n/a	why = (item, i, rule)
573	n/a	pptr = (pitem, parent)
574	n/a	#self.add(cur, (k, pparent),
575	n/a	# i, pptr, why)
576	n/a	#INLINED --v
577	n/a	new = (k, pparent)
578	n/a	key = (new, i)
579	n/a	if new not in cur:
580	n/a	self.links[key] = []
581	n/a	cur.append(new)
582	n/a	self.links[key].append((pptr, why))
583	n/a	#INLINED --^
584	n/a	#nk = self.goto(k, None)
585	n/a	nk = self.edges.get((k, None), None)
586	n/a	if nk is not None:
587	n/a	#self.add(cur, (nk, i))
588	n/a	#INLINED --v
589	n/a	new = (nk, i)
590	n/a	if new not in cur:
591	n/a	cur.append(new)
592	n/a	#INLINED --^
593	n/a
594	n/a	def predecessor(self, key, causal):
595	n/a	for p, c in self.links[key]:
596	n/a	if c == causal:
597	n/a	return p
598	n/a	assert 0
599	n/a
600	n/a	def causal(self, key):
601	n/a	links = self.links[key]
602	n/a	if len(links) == 1:
603	n/a	return links[0][1]
604	n/a	choices = []
605	n/a	rule2cause = {}
606	n/a	for p, c in links:
607	n/a	rule = c[2]
608	n/a	choices.append(rule)
609	n/a	rule2cause[rule] = c
610	n/a	return rule2cause[self.ambiguity(choices)]
611	n/a
612	n/a	def deriveEpsilon(self, nt):
613	n/a	if len(self.newrules[nt]) > 1:
614	n/a	rule = self.ambiguity(self.newrules[nt])
615	n/a	else:
616	n/a	rule = self.newrules[nt][0]
617	n/a	#output(rule)
618	n/a
619	n/a	rhs = rule[1]
620	n/a	attr = [None] * len(rhs)
621	n/a
622	n/a	for i in range(len(rhs)-1, -1, -1):
623	n/a	attr[i] = self.deriveEpsilon(rhs[i])
624	n/a	return self.rule2func[self.new2old[rule]](attr)
625	n/a
626	n/a	def buildTree(self, nt, item, tokens, k):
627	n/a	state, parent = item
628	n/a
629	n/a	choices = []
630	n/a	for rule in self.states[state].complete:
631	n/a	if rule[0] == nt:
632	n/a	choices.append(rule)
633	n/a	rule = choices[0]
634	n/a	if len(choices) > 1:
635	n/a	rule = self.ambiguity(choices)
636	n/a	#output(rule)
637	n/a
638	n/a	rhs = rule[1]
639	n/a	attr = [None] * len(rhs)
640	n/a
641	n/a	for i in range(len(rhs)-1, -1, -1):
642	n/a	sym = rhs[i]
643	n/a	if sym not in self.newrules:
644	n/a	if sym != self._BOF:
645	n/a	attr[i] = tokens[k-1]
646	n/a	key = (item, k)
647	n/a	item, k = self.predecessor(key, None)
648	n/a	#elif self.isnullable(sym):
649	n/a	elif self._NULLABLE == sym[0:len(self._NULLABLE)]:
650	n/a	attr[i] = self.deriveEpsilon(sym)
651	n/a	else:
652	n/a	key = (item, k)
653	n/a	why = self.causal(key)
654	n/a	attr[i] = self.buildTree(sym, why[0],
655	n/a	tokens, why[1])
656	n/a	item, k = self.predecessor(key, why)
657	n/a	return self.rule2func[self.new2old[rule]](attr)
658	n/a
659	n/a	def ambiguity(self, rules):
660	n/a	#
661	n/a	# XXX - problem here and in collectRules() if the same rule
662	n/a	# appears in >1 method. Also undefined results if rules
663	n/a	# causing the ambiguity appear in the same method.
664	n/a	#
665	n/a	sortlist = []
666	n/a	name2index = {}
667	n/a	for i in range(len(rules)):
668	n/a	lhs, rhs = rule = rules[i]
669	n/a	name = self.rule2name[self.new2old[rule]]
670	n/a	sortlist.append((len(rhs), name))
671	n/a	name2index[name] = i
672	n/a	sortlist.sort()
673	n/a	list = [b for a, b in sortlist]
674	n/a	return rules[name2index[self.resolve(list)]]
675	n/a
676	n/a	def resolve(self, list):
677	n/a	#
678	n/a	# Resolve ambiguity in favor of the shortest RHS.
679	n/a	# Since we walk the tree from the top down, this
680	n/a	# should effectively resolve in favor of a "shift".
681	n/a	#
682	n/a	return list[0]
683	n/a
684	n/a	#
685	n/a	# GenericASTBuilder automagically constructs a concrete/abstract syntax tree
686	n/a	# for a given input. The extra argument is a class (not an instance!)
687	n/a	# which supports the "__setslice__" and "__len__" methods.
688	n/a	#
689	n/a	# XXX - silently overrides any user code in methods.
690	n/a	#
691	n/a
692	n/a	class GenericASTBuilder(GenericParser):
693	n/a	def __init__(self, AST, start):
694	n/a	GenericParser.__init__(self, start)
695	n/a	self.AST = AST
696	n/a
697	n/a	def preprocess(self, rule, func):
698	n/a	rebind = lambda lhs, self=self: \
699	n/a	lambda args, lhs=lhs, self=self: \
700	n/a	self.buildASTNode(args, lhs)
701	n/a	lhs, rhs = rule
702	n/a	return rule, rebind(lhs)
703	n/a
704	n/a	def buildASTNode(self, args, lhs):
705	n/a	children = []
706	n/a	for arg in args:
707	n/a	if isinstance(arg, self.AST):
708	n/a	children.append(arg)
709	n/a	else:
710	n/a	children.append(self.terminal(arg))
711	n/a	return self.nonterminal(lhs, children)
712	n/a
713	n/a	def terminal(self, token): return token
714	n/a
715	n/a	def nonterminal(self, type, args):
716	n/a	rv = self.AST(type)
717	n/a	rv[:len(args)] = args
718	n/a	return rv
719	n/a
720	n/a	#
721	n/a	# GenericASTTraversal is a Visitor pattern according to Design Patterns. For
722	n/a	# each node it attempts to invoke the method n_<node type>, falling
723	n/a	# back onto the default() method if the n_* can't be found. The preorder
724	n/a	# traversal also looks for an exit hook named n_<node type>_exit (no default
725	n/a	# routine is called if it's not found). To prematurely halt traversal
726	n/a	# of a subtree, call the prune() method -- this only makes sense for a
727	n/a	# preorder traversal. Node type is determined via the typestring() method.
728	n/a	#
729	n/a
730	n/a	class GenericASTTraversalPruningException:
731	n/a	pass
732	n/a
733	n/a	class GenericASTTraversal:
734	n/a	def __init__(self, ast):
735	n/a	self.ast = ast
736	n/a
737	n/a	def typestring(self, node):
738	n/a	return node.type
739	n/a
740	n/a	def prune(self):
741	n/a	raise GenericASTTraversalPruningException
742	n/a
743	n/a	def preorder(self, node=None):
744	n/a	if node is None:
745	n/a	node = self.ast
746	n/a
747	n/a	try:
748	n/a	name = 'n_' + self.typestring(node)
749	n/a	if hasattr(self, name):
750	n/a	func = getattr(self, name)
751	n/a	func(node)
752	n/a	else:
753	n/a	self.default(node)
754	n/a	except GenericASTTraversalPruningException:
755	n/a	return
756	n/a
757	n/a	for kid in node:
758	n/a	self.preorder(kid)
759	n/a
760	n/a	name = name + '_exit'
761	n/a	if hasattr(self, name):
762	n/a	func = getattr(self, name)
763	n/a	func(node)
764	n/a
765	n/a	def postorder(self, node=None):
766	n/a	if node is None:
767	n/a	node = self.ast
768	n/a
769	n/a	for kid in node:
770	n/a	self.postorder(kid)
771	n/a
772	n/a	name = 'n_' + self.typestring(node)
773	n/a	if hasattr(self, name):
774	n/a	func = getattr(self, name)
775	n/a	func(node)
776	n/a	else:
777	n/a	self.default(node)
778	n/a
779	n/a
780	n/a	def default(self, node):
781	n/a	pass
782	n/a
783	n/a	#
784	n/a	# GenericASTMatcher. AST nodes must have "__getitem__" and "__cmp__"
785	n/a	# implemented.
786	n/a	#
787	n/a	# XXX - makes assumptions about how GenericParser walks the parse tree.
788	n/a	#
789	n/a
790	n/a	class GenericASTMatcher(GenericParser):
791	n/a	def __init__(self, start, ast):
792	n/a	GenericParser.__init__(self, start)
793	n/a	self.ast = ast
794	n/a
795	n/a	def preprocess(self, rule, func):
796	n/a	rebind = lambda func, self=self: \
797	n/a	lambda args, func=func, self=self: \
798	n/a	self.foundMatch(args, func)
799	n/a	lhs, rhs = rule
800	n/a	rhslist = list(rhs)
801	n/a	rhslist.reverse()
802	n/a
803	n/a	return (lhs, tuple(rhslist)), rebind(func)
804	n/a
805	n/a	def foundMatch(self, args, func):
806	n/a	func(args[-1])
807	n/a	return args[-1]
808	n/a
809	n/a	def match_r(self, node):
810	n/a	self.input.insert(0, node)
811	n/a	children = 0
812	n/a
813	n/a	for child in node:
814	n/a	if children == 0:
815	n/a	self.input.insert(0, '(')
816	n/a	children = children + 1
817	n/a	self.match_r(child)
818	n/a
819	n/a	if children > 0:
820	n/a	self.input.insert(0, ')')
821	n/a
822	n/a	def match(self, ast=None):
823	n/a	if ast is None:
824	n/a	ast = self.ast
825	n/a	self.input = []
826	n/a
827	n/a	self.match_r(ast)
828	n/a	self.parse(self.input)
829	n/a
830	n/a	def resolve(self, list):
831	n/a	#
832	n/a	# Resolve ambiguity in favor of the longest RHS.
833	n/a	#
834	n/a	return list[-1]
835	n/a
836	n/a	def _dump(tokens, sets, states):
837	n/a	for i in range(len(sets)):
838	n/a	output('set %d' % i)
839	n/a	for item in sets[i]:
840	n/a	output('\t', item)
841	n/a	for (lhs, rhs), pos in states[item[0]].items:
842	n/a	output('\t\t', lhs, '::=', end='')
843	n/a	output(' '.join(rhs[:pos]), end='')
844	n/a	output('.', end='')
845	n/a	output(' '.join(rhs[pos:]))
846	n/a	if i < len(tokens):
847	n/a	output()
848	n/a	output('token %s' % str(tokens[i]))
849	n/a	output()