cpython-lru_cache-weakref: Parser/spark.py annotate

annotate Parser/spark.py @ 79675:c0a2294de787 2.7

Issue #16199: Backport 2to3 typo fix from 3.2.

author	Chris Jerdonek <chris.jerdonek@gmail.com>
date	Thu, 11 Oct 2012 16:15:46 -0700
parents	1d84bf5f9478
children

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

Mercurial > cpython-lru_cache-weakref

annotate Parser/spark.py @ 79675:c0a2294de787 2.7