pysynphot.spark

1 from __future__ import division 2 # Copyright (c) 1998-2000 John Aycock 3 # 4 # Permission is hereby granted, free of charge, to any person obtaining 5 # a copy of this software and associated documentation files (the 6 # "Software"), to deal in the Software without restriction, including 7 # without limitation the rights to use, copy, modify, merge, publish, 8 # distribute, sublicense, and/or sell copies of the Software, and to 9 # permit persons to whom the Software is furnished to do so, subject to 10 # the following conditions: 11 # 12 # The above copyright notice and this permission notice shall be 13 # included in all copies or substantial portions of the Software. 14 # 15 # THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 16 # EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 17 # MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. 18 # IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY 19 # CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, 20 # TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE 21 # SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 22 23 __version__ = 'SPARK-0.6.1' 24 25 import re 26 import sys 27 import string 28

29 -def _namelist(instance):

30 namelist, namedict, classlist = [], {}, [instance.__class__] 31 for c in classlist: 32 for b in c.__bases__: 33 classlist.append(b) 34 for name in dir(c): 35 if not namedict.has_key(name): 36 namelist.append(name) 37 namedict[name] = 1 38 return namelist

39

40 -class GenericScanner:

41 - def __init__(self):

42 pattern = self.reflect() 43 self.re = re.compile(pattern, re.VERBOSE) 44 45 self.index2func = {} 46 for name, number in self.re.groupindex.items(): 47 self.index2func[number-1] = getattr(self, 't_' + name)

48

49 - def makeRE(self, name):

50 doc = getattr(self, name).__doc__ 51 rv = '(?P<%s>%s)' % (name[2:], doc) 52 return rv

53

54 - def reflect(self):

55 rv = [] 56 for name in _namelist(self): 57 if name[:2] == 't_' and name != 't_default': 58 rv.append(self.makeRE(name)) 59 60 rv.append(self.makeRE('t_default')) 61 return string.join(rv, '|')

62

63 - def error(self, s, pos):

64 print "Lexical error at position %s" % pos 65 raise SystemExit

66

67 - def tokenize(self, s):

68 pos = 0 69 n = len(s) 70 while pos < n: 71 m = self.re.match(s, pos) 72 if m is None: 73 self.error(s, pos) 74 75 groups = m.groups() 76 for i in range(len(groups)): 77 if groups[i] and self.index2func.has_key(i): 78 self.index2func[i](groups[i]) 79 pos = m.end()

80

81 - def t_default(self, s):

82 r'( . | \n )+' 83 pass

84

85 -class GenericParser:

86 - def __init__(self, start):

87 self.rules = {} 88 self.rule2func = {} 89 self.rule2name = {} 90 self.collectRules() 91 self.startRule = self.augment(start) 92 self.ruleschanged = 1

93 94 _START = 'START' 95 _EOF = 'EOF' 96 97 # 98 # A hook for GenericASTBuilder and GenericASTMatcher. 99 #

100 - def preprocess(self, rule, func): return rule, func

101

102 - def addRule(self, doc, func):

103 rules = string.split(doc) 104 105 index = [] 106 for i in range(len(rules)): 107 if rules[i] == '::=': 108 index.append(i-1) 109 index.append(len(rules)) 110 111 for i in range(len(index)-1): 112 lhs = rules[index[i]] 113 rhs = rules[index[i]+2:index[i+1]] 114 rule = (lhs, tuple(rhs)) 115 116 rule, fn = self.preprocess(rule, func) 117 118 if self.rules.has_key(lhs): 119 self.rules[lhs].append(rule) 120 else: 121 self.rules[lhs] = [ rule ] 122 self.rule2func[rule] = fn 123 self.rule2name[rule] = func.__name__[2:] 124 self.ruleschanged = 1

125

126 - def collectRules(self):

127 for name in _namelist(self): 128 if name[:2] == 'p_': 129 func = getattr(self, name) 130 doc = func.__doc__ 131 self.addRule(doc, func)

132

133 - def augment(self, start):

134 # 135 # Tempting though it is, this isn't made into a call 136 # to self.addRule() because the start rule shouldn't 137 # be subject to preprocessing. 138 # 139 startRule = (self._START, ( start, self._EOF )) 140 self.rule2func[startRule] = lambda args: args[0] 141 self.rules[self._START] = [ startRule ] 142 self.rule2name[startRule] = '' 143 return startRule

144

145 - def makeFIRST(self):

146 union = {} 147 self.first = {} 148 149 for rulelist in self.rules.values(): 150 for lhs, rhs in rulelist: 151 if not self.first.has_key(lhs): 152 self.first[lhs] = {} 153 154 if len(rhs) == 0: 155 self.first[lhs][None] = 1 156 continue 157 158 sym = rhs[0] 159 if not self.rules.has_key(sym): 160 self.first[lhs][sym] = 1 161 else: 162 union[(sym, lhs)] = 1 163 changes = 1 164 while changes: 165 changes = 0 166 for src, dest in union.keys(): 167 destlen = len(self.first[dest]) 168 self.first[dest].update(self.first[src]) 169 if len(self.first[dest]) != destlen: 170 changes = 1

171 172 # 173 # An Earley parser, as per J. Earley, "An Efficient Context-Free 174 # Parsing Algorithm", CACM 13(2), pp. 94-102. Also J. C. Earley, 175 # "An Efficient Context-Free Parsing Algorithm", Ph.D. thesis, 176 # Carnegie-Mellon University, August 1968, p. 27. 177 # 178

179 - def typestring(self, token):

180 return None

181

182 - def error(self, token):

183 print "Syntax error at or near `%s' token" % token 184 raise ValueError("problem in the parsing phase")

185

186 - def parse(self, tokens):

187 tree = {} 188 tokens.append(self._EOF) 189 states = { 0: [ (self.startRule, 0, 0) ] } 190 191 if self.ruleschanged: 192 self.makeFIRST() 193 194 for i in xrange(len(tokens)): 195 states[i+1] = [] 196 197 if states[i] == []: 198 break 199 self.buildState(tokens[i], states, i, tree) 200 201 #_dump(tokens, states) 202 203 if i < len(tokens)-1 or states[i+1] != [(self.startRule, 2, 0)]: 204 del tokens[-1] 205 self.error(tokens[i-1]) 206 rv = self.buildTree(tokens, tree, ((self.startRule, 2, 0), i+1)) 207 del tokens[-1] 208 return rv

209

210 - def buildState(self, token, states, i, tree):

211 needsCompletion = {} 212 state = states[i] 213 predicted = {} 214 215 for item in state: 216 rule, pos, parent = item 217 lhs, rhs = rule 218 219 # 220 # A -> a . (completer) 221 # 222 if pos == len(rhs): 223 if len(rhs) == 0: 224 needsCompletion[lhs] = (item, i) 225 226 for pitem in states[parent]: 227 if pitem is item: 228 break 229 230 prule, ppos, pparent = pitem 231 plhs, prhs = prule 232 233 if prhs[ppos:ppos+1] == (lhs,): 234 new = (prule, 235 ppos+1, 236 pparent) 237 if new not in state: 238 state.append(new) 239 tree[(new, i)] = [(item, i)] 240 else: 241 tree[(new, i)].append((item, i)) 242 continue 243 244 nextSym = rhs[pos] 245 246 # 247 # A -> a . B (predictor) 248 # 249 if self.rules.has_key(nextSym): 250 # 251 # Work on completer step some more; for rules 252 # with empty RHS, the "parent state" is the 253 # current state we're adding Earley items to, 254 # so the Earley items the completer step needs 255 # may not all be present when it runs. 256 # 257 if needsCompletion.has_key(nextSym): 258 new = (rule, pos+1, parent) 259 olditem_i = needsCompletion[nextSym] 260 if new not in state: 261 state.append(new) 262 tree[(new, i)] = [olditem_i] 263 else: 264 tree[(new, i)].append(olditem_i) 265 266 # 267 # Has this been predicted already? 268 # 269 if predicted.has_key(nextSym): 270 continue 271 predicted[nextSym] = 1 272 273 ttype = token is not self._EOF and \ 274 self.typestring(token) or \ 275 None 276 if ttype is not None: 277 # 278 # Even smarter predictor, when the 279 # token's type is known. The code is 280 # grungy, but runs pretty fast. Three 281 # cases are looked for: rules with 282 # empty RHS; first symbol on RHS is a 283 # terminal; first symbol on RHS is a 284 # nonterminal (and isn't nullable). 285 # 286 for prule in self.rules[nextSym]: 287 new = (prule, 0, i) 288 prhs = prule[1] 289 if len(prhs) == 0: 290 state.append(new) 291 continue 292 prhs0 = prhs[0] 293 if not self.rules.has_key(prhs0): 294 if prhs0 != ttype: 295 continue 296 else: 297 state.append(new) 298 continue 299 first = self.first[prhs0] 300 if not first.has_key(None) and \ 301 not first.has_key(ttype): 302 continue 303 state.append(new) 304 continue 305 306 for prule in self.rules[nextSym]: 307 # 308 # Smarter predictor, as per Grune & 309 # Jacobs' _Parsing Techniques_. Not 310 # as good as FIRST sets though. 311 # 312 prhs = prule[1] 313 if len(prhs) > 0 and \ 314 not self.rules.has_key(prhs[0]) and \ 315 token != prhs[0]: 316 continue 317 state.append((prule, 0, i)) 318 319 # 320 # A -> a . c (scanner) 321 # 322 elif token == nextSym: 323 #assert new not in states[i+1] 324 states[i+1].append((rule, pos+1, parent))

325

326 - def buildTree(self, tokens, tree, root):

327 stack = [] 328 self.buildTree_r(stack, tokens, -1, tree, root) 329 return stack[0]

330

331 - def buildTree_r(self, stack, tokens, tokpos, tree, root):

332 (rule, pos, parent), state = root 333 334 while pos > 0: 335 want = ((rule, pos, parent), state) 336 if not tree.has_key(want): 337 # 338 # Since pos > 0, it didn't come from closure, 339 # and if it isn't in tree[], then there must 340 # be a terminal symbol to the left of the dot. 341 # (It must be from a "scanner" step.) 342 # 343 pos = pos - 1 344 state = state - 1 345 stack.insert(0, tokens[tokpos]) 346 tokpos = tokpos - 1 347 else: 348 # 349 # There's a NT to the left of the dot. 350 # Follow the tree pointer recursively (>1 351 # tree pointers from it indicates ambiguity). 352 # Since the item must have come about from a 353 # "completer" step, the state where the item 354 # came from must be the parent state of the 355 # item the tree pointer points to. 356 # 357 children = tree[want] 358 if len(children) > 1: 359 child = self.ambiguity(children) 360 else: 361 child = children[0] 362 363 tokpos = self.buildTree_r(stack, 364 tokens, tokpos, 365 tree, child) 366 pos = pos - 1 367 (crule, cpos, cparent), cstate = child 368 state = cparent 369 370 lhs, rhs = rule 371 result = self.rule2func[rule](stack[:len(rhs)]) 372 stack[:len(rhs)] = [result] 373 return tokpos

374

375 - def ambiguity(self, children):

376 # 377 # XXX - problem here and in collectRules() if the same 378 # rule appears in >1 method. But in that case the 379 # user probably gets what they deserve :-) Also 380 # undefined results if rules causing the ambiguity 381 # appear in the same method. 382 # 383 sortlist = [] 384 name2index = {} 385 for i in range(len(children)): 386 ((rule, pos, parent), index) = children[i] 387 lhs, rhs = rule 388 name = self.rule2name[rule] 389 sortlist.append((len(rhs), name)) 390 name2index[name] = i 391 sortlist.sort() 392 list = map(lambda (a,b): b, sortlist) 393 return children[name2index[self.resolve(list)]]

394

395 - def resolve(self, list):

396 # 397 # Resolve ambiguity in favor of the shortest RHS. 398 # Since we walk the tree from the top down, this 399 # should effectively resolve in favor of a "shift". 400 # 401 return list[0]

402 403 # 404 # GenericASTBuilder automagically constructs a concrete/abstract syntax tree 405 # for a given input. The extra argument is a class (not an instance!) 406 # which supports the "__setslice__" and "__len__" methods. 407 # 408 # XXX - silently overrides any user code in methods. 409 # 410

411 -class GenericASTBuilder(GenericParser):

412 - def __init__(self, AST, start):

413 GenericParser.__init__(self, start) 414 self.AST = AST

415

416 - def preprocess(self, rule, func):

417 rebind = lambda lhs, self=self: \ 418 lambda args, lhs=lhs, self=self: \ 419 self.buildASTNode(args, lhs) 420 lhs, rhs = rule 421 return rule, rebind(lhs)

422

423 - def buildASTNode(self, args, lhs):

424 children = [] 425 for arg in args: 426 if isinstance(arg, self.AST): 427 children.append(arg) 428 else: 429 children.append(self.terminal(arg)) 430 return self.nonterminal(lhs, children)

431

432 - def terminal(self, token): return token

433

434 - def nonterminal(self, type, args):

435 rv = self.AST(type) 436 rv[:len(args)] = args 437 return rv

438 439 # 440 # GenericASTTraversal is a Visitor pattern according to Design Patterns. For 441 # each node it attempts to invoke the method n_<node type>, falling 442 # back onto the default() method if the n_* can't be found. The preorder 443 # traversal also looks for an exit hook named n_<node type>_exit (no default 444 # routine is called if it's not found). To prematurely halt traversal 445 # of a subtree, call the prune() method -- this only makes sense for a 446 # preorder traversal. Node type is determined via the typestring() method. 447 # 448

449 -class GenericASTTraversalPruningException:

450 pass

451

452 -class GenericASTTraversal:

453 - def __init__(self, ast):

454 self.ast = ast

455

456 - def typestring(self, node):

457 return node.type

458

459 - def prune(self):

460 raise GenericASTTraversalPruningException

461

462 - def preorder(self, node=None):

463 if node is None: 464 node = self.ast 465 466 try: 467 name = 'n_' + self.typestring(node) 468 if hasattr(self, name): 469 func = getattr(self, name) 470 func(node) 471 else: 472 self.default(node) 473 except GenericASTTraversalPruningException: 474 return 475 476 for kid in node: 477 self.preorder(kid) 478 479 name = name + '_exit' 480 if hasattr(self, name): 481 func = getattr(self, name) 482 func(node)

483

484 - def postorder(self, node=None):

485 if node is None: 486 node = self.ast 487 488 for kid in node: 489 self.postorder(kid) 490 491 name = 'n_' + self.typestring(node) 492 if hasattr(self, name): 493 func = getattr(self, name) 494 func(node) 495 else: 496 self.default(node)

497 498

499 - def default(self, node):

500 pass

501 502 # 503 # GenericASTMatcher. AST nodes must have "__getitem__" and "__cmp__" 504 # implemented. 505 # 506 # XXX - makes assumptions about how GenericParser walks the parse tree. 507 # 508

509 -class GenericASTMatcher(GenericParser):

510 - def __init__(self, start, ast):

511 GenericParser.__init__(self, start) 512 self.ast = ast

513

514 - def preprocess(self, rule, func):

515 rebind = lambda func, self=self: \ 516 lambda args, func=func, self=self: \ 517 self.foundMatch(args, func) 518 lhs, rhs = rule 519 rhslist = list(rhs) 520 rhslist.reverse() 521 522 return (lhs, tuple(rhslist)), rebind(func)

523

524 - def foundMatch(self, args, func):

525 func(args[-1]) 526 return args[-1]

527

528 - def match_r(self, node):

529 self.input.insert(0, node) 530 children = 0 531 532 for child in node: 533 if children == 0: 534 self.input.insert(0, '(') 535 children = children + 1 536 self.match_r(child) 537 538 if children > 0: 539 self.input.insert(0, ')')

540

541 - def match(self, ast=None):

542 if ast is None: 543 ast = self.ast 544 self.input = [] 545 546 self.match_r(ast) 547 self.parse(self.input)

548

549 - def resolve(self, list):

550 # 551 # Resolve ambiguity in favor of the longest RHS. 552 # 553 return list[-1]

554

555 -def _dump(tokens, states):

556 for i in range(len(states)): 557 print 'state', i 558 for (lhs, rhs), pos, parent in states[i]: 559 print '\t', lhs, '::=', 560 print string.join(rhs[:pos]), 561 print '.', 562 print string.join(rhs[pos:]), 563 print ',', parent 564 if i < len(tokens): 565 print 566 print 'token', str(tokens[i]) 567 print

568

Source Code for Module pysynphot.spark