Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.8/site-packages/lark/parsers/earley_forest.py: 71%

459 statements  

« prev     ^ index     » next       coverage.py v7.3.1, created at 2023-09-25 06:30 +0000

1""""This module implements an SPPF implementation 

2 

3This is used as the primary output mechanism for the Earley parser 

4in order to store complex ambiguities. 

5 

6Full reference and more details is here: 

7https://web.archive.org/web/20190616123959/http://www.bramvandersanden.com/post/2014/06/shared-packed-parse-forest/ 

8""" 

9 

10from random import randint 

11from collections import deque 

12from operator import attrgetter 

13from importlib import import_module 

14from functools import partial 

15 

16from ..parse_tree_builder import AmbiguousIntermediateExpander 

17from ..visitors import Discard 

18from ..utils import logger 

19from ..tree import Tree 

20 

21class ForestNode: 

22 pass 

23 

24class SymbolNode(ForestNode): 

25 """ 

26 A Symbol Node represents a symbol (or Intermediate LR0). 

27 

28 Symbol nodes are keyed by the symbol (s). For intermediate nodes 

29 s will be an LR0, stored as a tuple of (rule, ptr). For completed symbol 

30 nodes, s will be a string representing the non-terminal origin (i.e. 

31 the left hand side of the rule). 

32 

33 The children of a Symbol or Intermediate Node will always be Packed Nodes; 

34 with each Packed Node child representing a single derivation of a production. 

35 

36 Hence a Symbol Node with a single child is unambiguous. 

37 

38 Parameters: 

39 s: A Symbol, or a tuple of (rule, ptr) for an intermediate node. 

40 start: The index of the start of the substring matched by this symbol (inclusive). 

41 end: The index of the end of the substring matched by this symbol (exclusive). 

42 

43 Properties: 

44 is_intermediate: True if this node is an intermediate node. 

45 priority: The priority of the node's symbol. 

46 """ 

47 __slots__ = ('s', 'start', 'end', '_children', 'paths', 'paths_loaded', 'priority', 'is_intermediate', '_hash') 

48 def __init__(self, s, start, end): 

49 self.s = s 

50 self.start = start 

51 self.end = end 

52 self._children = set() 

53 self.paths = set() 

54 self.paths_loaded = False 

55 

56 ### We use inf here as it can be safely negated without resorting to conditionals, 

57 # unlike None or float('NaN'), and sorts appropriately. 

58 self.priority = float('-inf') 

59 self.is_intermediate = isinstance(s, tuple) 

60 self._hash = hash((self.s, self.start, self.end)) 

61 

62 def add_family(self, lr0, rule, start, left, right): 

63 self._children.add(PackedNode(self, lr0, rule, start, left, right)) 

64 

65 def add_path(self, transitive, node): 

66 self.paths.add((transitive, node)) 

67 

68 def load_paths(self): 

69 for transitive, node in self.paths: 

70 if transitive.next_titem is not None: 

71 vn = SymbolNode(transitive.next_titem.s, transitive.next_titem.start, self.end) 

72 vn.add_path(transitive.next_titem, node) 

73 self.add_family(transitive.reduction.rule.origin, transitive.reduction.rule, transitive.reduction.start, transitive.reduction.node, vn) 

74 else: 

75 self.add_family(transitive.reduction.rule.origin, transitive.reduction.rule, transitive.reduction.start, transitive.reduction.node, node) 

76 self.paths_loaded = True 

77 

78 @property 

79 def is_ambiguous(self): 

80 """Returns True if this node is ambiguous.""" 

81 return len(self.children) > 1 

82 

83 @property 

84 def children(self): 

85 """Returns a list of this node's children sorted from greatest to 

86 least priority.""" 

87 if not self.paths_loaded: 

88 self.load_paths() 

89 return sorted(self._children, key=attrgetter('sort_key')) 

90 

91 def __iter__(self): 

92 return iter(self._children) 

93 

94 def __eq__(self, other): 

95 if not isinstance(other, SymbolNode): 

96 return False 

97 return self is other or (type(self.s) == type(other.s) and self.s == other.s and self.start == other.start and self.end is other.end) 

98 

99 def __hash__(self): 

100 return self._hash 

101 

102 def __repr__(self): 

103 if self.is_intermediate: 

104 rule = self.s[0] 

105 ptr = self.s[1] 

106 before = ( expansion.name for expansion in rule.expansion[:ptr] ) 

107 after = ( expansion.name for expansion in rule.expansion[ptr:] ) 

108 symbol = "{} ::= {}* {}".format(rule.origin.name, ' '.join(before), ' '.join(after)) 

109 else: 

110 symbol = self.s.name 

111 return "({}, {}, {}, {})".format(symbol, self.start, self.end, self.priority) 

112 

113class PackedNode(ForestNode): 

114 """ 

115 A Packed Node represents a single derivation in a symbol node. 

116 

117 Parameters: 

118 rule: The rule associated with this node. 

119 parent: The parent of this node. 

120 left: The left child of this node. ``None`` if one does not exist. 

121 right: The right child of this node. ``None`` if one does not exist. 

122 priority: The priority of this node. 

123 """ 

124 __slots__ = ('parent', 's', 'rule', 'start', 'left', 'right', 'priority', '_hash') 

125 def __init__(self, parent, s, rule, start, left, right): 

126 self.parent = parent 

127 self.s = s 

128 self.start = start 

129 self.rule = rule 

130 self.left = left 

131 self.right = right 

132 self.priority = float('-inf') 

133 self._hash = hash((self.left, self.right)) 

134 

135 @property 

136 def is_empty(self): 

137 return self.left is None and self.right is None 

138 

139 @property 

140 def sort_key(self): 

141 """ 

142 Used to sort PackedNode children of SymbolNodes. 

143 A SymbolNode has multiple PackedNodes if it matched 

144 ambiguously. Hence, we use the sort order to identify 

145 the order in which ambiguous children should be considered. 

146 """ 

147 return self.is_empty, -self.priority, self.rule.order 

148 

149 @property 

150 def children(self): 

151 """Returns a list of this node's children.""" 

152 return [x for x in [self.left, self.right] if x is not None] 

153 

154 def __iter__(self): 

155 yield self.left 

156 yield self.right 

157 

158 def __eq__(self, other): 

159 if not isinstance(other, PackedNode): 

160 return False 

161 return self is other or (self.left == other.left and self.right == other.right) 

162 

163 def __hash__(self): 

164 return self._hash 

165 

166 def __repr__(self): 

167 if isinstance(self.s, tuple): 

168 rule = self.s[0] 

169 ptr = self.s[1] 

170 before = ( expansion.name for expansion in rule.expansion[:ptr] ) 

171 after = ( expansion.name for expansion in rule.expansion[ptr:] ) 

172 symbol = "{} ::= {}* {}".format(rule.origin.name, ' '.join(before), ' '.join(after)) 

173 else: 

174 symbol = self.s.name 

175 return "({}, {}, {}, {})".format(symbol, self.start, self.priority, self.rule.order) 

176 

177class TokenNode(ForestNode): 

178 """ 

179 A Token Node represents a matched terminal and is always a leaf node. 

180 

181 Parameters: 

182 token: The Token associated with this node. 

183 term: The TerminalDef matched by the token. 

184 priority: The priority of this node. 

185 """ 

186 __slots__ = ('token', 'term', 'priority', '_hash') 

187 def __init__(self, token, term, priority=None): 

188 self.token = token 

189 self.term = term 

190 if priority is not None: 

191 self.priority = priority 

192 else: 

193 self.priority = term.priority if term is not None else 0 

194 self._hash = hash(token) 

195 

196 def __eq__(self, other): 

197 if not isinstance(other, TokenNode): 

198 return False 

199 return self is other or (self.token == other.token) 

200 

201 def __hash__(self): 

202 return self._hash 

203 

204 def __repr__(self): 

205 return repr(self.token) 

206 

207class ForestVisitor: 

208 """ 

209 An abstract base class for building forest visitors. 

210 

211 This class performs a controllable depth-first walk of an SPPF. 

212 The visitor will not enter cycles and will backtrack if one is encountered. 

213 Subclasses are notified of cycles through the ``on_cycle`` method. 

214 

215 Behavior for visit events is defined by overriding the 

216 ``visit*node*`` functions. 

217 

218 The walk is controlled by the return values of the ``visit*node_in`` 

219 methods. Returning a node(s) will schedule them to be visited. The visitor 

220 will begin to backtrack if no nodes are returned. 

221 

222 Parameters: 

223 single_visit: If ``True``, non-Token nodes will only be visited once. 

224 """ 

225 

226 def __init__(self, single_visit=False): 

227 self.single_visit = single_visit 

228 

229 def visit_token_node(self, node): 

230 """Called when a ``Token`` is visited. ``Token`` nodes are always leaves.""" 

231 pass 

232 

233 def visit_symbol_node_in(self, node): 

234 """Called when a symbol node is visited. Nodes that are returned 

235 will be scheduled to be visited. If ``visit_intermediate_node_in`` 

236 is not implemented, this function will be called for intermediate 

237 nodes as well.""" 

238 pass 

239 

240 def visit_symbol_node_out(self, node): 

241 """Called after all nodes returned from a corresponding ``visit_symbol_node_in`` 

242 call have been visited. If ``visit_intermediate_node_out`` 

243 is not implemented, this function will be called for intermediate 

244 nodes as well.""" 

245 pass 

246 

247 def visit_packed_node_in(self, node): 

248 """Called when a packed node is visited. Nodes that are returned 

249 will be scheduled to be visited. """ 

250 pass 

251 

252 def visit_packed_node_out(self, node): 

253 """Called after all nodes returned from a corresponding ``visit_packed_node_in`` 

254 call have been visited.""" 

255 pass 

256 

257 def on_cycle(self, node, path): 

258 """Called when a cycle is encountered. 

259 

260 Parameters: 

261 node: The node that causes a cycle. 

262 path: The list of nodes being visited: nodes that have been 

263 entered but not exited. The first element is the root in a forest 

264 visit, and the last element is the node visited most recently. 

265 ``path`` should be treated as read-only. 

266 """ 

267 pass 

268 

269 def get_cycle_in_path(self, node, path): 

270 """A utility function for use in ``on_cycle`` to obtain a slice of 

271 ``path`` that only contains the nodes that make up the cycle.""" 

272 index = len(path) - 1 

273 while id(path[index]) != id(node): 

274 index -= 1 

275 return path[index:] 

276 

277 def visit(self, root): 

278 # Visiting is a list of IDs of all symbol/intermediate nodes currently in 

279 # the stack. It serves two purposes: to detect when we 'recurse' in and out 

280 # of a symbol/intermediate so that we can process both up and down. Also, 

281 # since the SPPF can have cycles it allows us to detect if we're trying 

282 # to recurse into a node that's already on the stack (infinite recursion). 

283 visiting = set() 

284 

285 # set of all nodes that have been visited 

286 visited = set() 

287 

288 # a list of nodes that are currently being visited 

289 # used for the `on_cycle` callback 

290 path = [] 

291 

292 # We do not use recursion here to walk the Forest due to the limited 

293 # stack size in python. Therefore input_stack is essentially our stack. 

294 input_stack = deque([root]) 

295 

296 # It is much faster to cache these as locals since they are called 

297 # many times in large parses. 

298 vpno = getattr(self, 'visit_packed_node_out') 

299 vpni = getattr(self, 'visit_packed_node_in') 

300 vsno = getattr(self, 'visit_symbol_node_out') 

301 vsni = getattr(self, 'visit_symbol_node_in') 

302 vino = getattr(self, 'visit_intermediate_node_out', vsno) 

303 vini = getattr(self, 'visit_intermediate_node_in', vsni) 

304 vtn = getattr(self, 'visit_token_node') 

305 oc = getattr(self, 'on_cycle') 

306 

307 while input_stack: 

308 current = next(reversed(input_stack)) 

309 try: 

310 next_node = next(current) 

311 except StopIteration: 

312 input_stack.pop() 

313 continue 

314 except TypeError: 

315 ### If the current object is not an iterator, pass through to Token/SymbolNode 

316 pass 

317 else: 

318 if next_node is None: 

319 continue 

320 

321 if id(next_node) in visiting: 

322 oc(next_node, path) 

323 continue 

324 

325 input_stack.append(next_node) 

326 continue 

327 

328 if isinstance(current, TokenNode): 

329 vtn(current.token) 

330 input_stack.pop() 

331 continue 

332 

333 current_id = id(current) 

334 if current_id in visiting: 

335 if isinstance(current, PackedNode): 

336 vpno(current) 

337 elif current.is_intermediate: 

338 vino(current) 

339 else: 

340 vsno(current) 

341 input_stack.pop() 

342 path.pop() 

343 visiting.remove(current_id) 

344 visited.add(current_id) 

345 elif self.single_visit and current_id in visited: 

346 input_stack.pop() 

347 else: 

348 visiting.add(current_id) 

349 path.append(current) 

350 if isinstance(current, PackedNode): 

351 next_node = vpni(current) 

352 elif current.is_intermediate: 

353 next_node = vini(current) 

354 else: 

355 next_node = vsni(current) 

356 if next_node is None: 

357 continue 

358 

359 if not isinstance(next_node, ForestNode): 

360 next_node = iter(next_node) 

361 elif id(next_node) in visiting: 

362 oc(next_node, path) 

363 continue 

364 

365 input_stack.append(next_node) 

366 

367class ForestTransformer(ForestVisitor): 

368 """The base class for a bottom-up forest transformation. Most users will 

369 want to use ``TreeForestTransformer`` instead as it has a friendlier 

370 interface and covers most use cases. 

371 

372 Transformations are applied via inheritance and overriding of the 

373 ``transform*node`` methods. 

374 

375 ``transform_token_node`` receives a ``Token`` as an argument. 

376 All other methods receive the node that is being transformed and 

377 a list of the results of the transformations of that node's children. 

378 The return value of these methods are the resulting transformations. 

379 

380 If ``Discard`` is raised in a node's transformation, no data from that node 

381 will be passed to its parent's transformation. 

382 """ 

383 

384 def __init__(self): 

385 super(ForestTransformer, self).__init__() 

386 # results of transformations 

387 self.data = dict() 

388 # used to track parent nodes 

389 self.node_stack = deque() 

390 

391 def transform(self, root): 

392 """Perform a transformation on an SPPF.""" 

393 self.node_stack.append('result') 

394 self.data['result'] = [] 

395 self.visit(root) 

396 assert len(self.data['result']) <= 1 

397 if self.data['result']: 

398 return self.data['result'][0] 

399 

400 def transform_symbol_node(self, node, data): 

401 """Transform a symbol node.""" 

402 return node 

403 

404 def transform_intermediate_node(self, node, data): 

405 """Transform an intermediate node.""" 

406 return node 

407 

408 def transform_packed_node(self, node, data): 

409 """Transform a packed node.""" 

410 return node 

411 

412 def transform_token_node(self, node): 

413 """Transform a ``Token``.""" 

414 return node 

415 

416 def visit_symbol_node_in(self, node): 

417 self.node_stack.append(id(node)) 

418 self.data[id(node)] = [] 

419 return node.children 

420 

421 def visit_packed_node_in(self, node): 

422 self.node_stack.append(id(node)) 

423 self.data[id(node)] = [] 

424 return node.children 

425 

426 def visit_token_node(self, node): 

427 transformed = self.transform_token_node(node) 

428 if transformed is not Discard: 

429 self.data[self.node_stack[-1]].append(transformed) 

430 

431 def _visit_node_out_helper(self, node, method): 

432 self.node_stack.pop() 

433 transformed = method(node, self.data[id(node)]) 

434 if transformed is not Discard: 

435 self.data[self.node_stack[-1]].append(transformed) 

436 del self.data[id(node)] 

437 

438 def visit_symbol_node_out(self, node): 

439 self._visit_node_out_helper(node, self.transform_symbol_node) 

440 

441 def visit_intermediate_node_out(self, node): 

442 self._visit_node_out_helper(node, self.transform_intermediate_node) 

443 

444 def visit_packed_node_out(self, node): 

445 self._visit_node_out_helper(node, self.transform_packed_node) 

446 

447 

448class ForestSumVisitor(ForestVisitor): 

449 """ 

450 A visitor for prioritizing ambiguous parts of the Forest. 

451 

452 This visitor is used when support for explicit priorities on 

453 rules is requested (whether normal, or invert). It walks the 

454 forest (or subsets thereof) and cascades properties upwards 

455 from the leaves. 

456 

457 It would be ideal to do this during parsing, however this would 

458 require processing each Earley item multiple times. That's 

459 a big performance drawback; so running a forest walk is the 

460 lesser of two evils: there can be significantly more Earley 

461 items created during parsing than there are SPPF nodes in the 

462 final tree. 

463 """ 

464 def __init__(self): 

465 super(ForestSumVisitor, self).__init__(single_visit=True) 

466 

467 def visit_packed_node_in(self, node): 

468 yield node.left 

469 yield node.right 

470 

471 def visit_symbol_node_in(self, node): 

472 return iter(node.children) 

473 

474 def visit_packed_node_out(self, node): 

475 priority = node.rule.options.priority if not node.parent.is_intermediate and node.rule.options.priority else 0 

476 priority += getattr(node.right, 'priority', 0) 

477 priority += getattr(node.left, 'priority', 0) 

478 node.priority = priority 

479 

480 def visit_symbol_node_out(self, node): 

481 node.priority = max(child.priority for child in node.children) 

482 

483class PackedData(): 

484 """Used in transformationss of packed nodes to distinguish the data 

485 that comes from the left child and the right child. 

486 """ 

487 

488 class _NoData(): 

489 pass 

490 

491 NO_DATA = _NoData() 

492 

493 def __init__(self, node, data): 

494 self.left = self.NO_DATA 

495 self.right = self.NO_DATA 

496 if data: 

497 if node.left is not None: 

498 self.left = data[0] 

499 if len(data) > 1: 

500 self.right = data[1] 

501 else: 

502 self.right = data[0] 

503 

504class ForestToParseTree(ForestTransformer): 

505 """Used by the earley parser when ambiguity equals 'resolve' or 

506 'explicit'. Transforms an SPPF into an (ambiguous) parse tree. 

507 

508 Parameters: 

509 tree_class: The tree class to use for construction 

510 callbacks: A dictionary of rules to functions that output a tree 

511 prioritizer: A ``ForestVisitor`` that manipulates the priorities of ForestNodes 

512 resolve_ambiguity: If True, ambiguities will be resolved based on 

513 priorities. Otherwise, `_ambig` nodes will be in the resulting tree. 

514 use_cache: If True, the results of packed node transformations will be cached. 

515 """ 

516 

517 def __init__(self, tree_class=Tree, callbacks=dict(), prioritizer=ForestSumVisitor(), resolve_ambiguity=True, use_cache=True): 

518 super(ForestToParseTree, self).__init__() 

519 self.tree_class = tree_class 

520 self.callbacks = callbacks 

521 self.prioritizer = prioritizer 

522 self.resolve_ambiguity = resolve_ambiguity 

523 self._use_cache = use_cache 

524 self._cache = {} 

525 self._on_cycle_retreat = False 

526 self._cycle_node = None 

527 self._successful_visits = set() 

528 

529 def visit(self, root): 

530 if self.prioritizer: 

531 self.prioritizer.visit(root) 

532 super(ForestToParseTree, self).visit(root) 

533 self._cache = {} 

534 

535 def on_cycle(self, node, path): 

536 logger.debug("Cycle encountered in the SPPF at node: %s. " 

537 "As infinite ambiguities cannot be represented in a tree, " 

538 "this family of derivations will be discarded.", node) 

539 self._cycle_node = node 

540 self._on_cycle_retreat = True 

541 

542 def _check_cycle(self, node): 

543 if self._on_cycle_retreat: 

544 if id(node) == id(self._cycle_node) or id(node) in self._successful_visits: 

545 self._cycle_node = None 

546 self._on_cycle_retreat = False 

547 else: 

548 return Discard 

549 

550 def _collapse_ambig(self, children): 

551 new_children = [] 

552 for child in children: 

553 if hasattr(child, 'data') and child.data == '_ambig': 

554 new_children += child.children 

555 else: 

556 new_children.append(child) 

557 return new_children 

558 

559 def _call_rule_func(self, node, data): 

560 # called when transforming children of symbol nodes 

561 # data is a list of trees or tokens that correspond to the 

562 # symbol's rule expansion 

563 return self.callbacks[node.rule](data) 

564 

565 def _call_ambig_func(self, node, data): 

566 # called when transforming a symbol node 

567 # data is a list of trees where each tree's data is 

568 # equal to the name of the symbol or one of its aliases. 

569 if len(data) > 1: 

570 return self.tree_class('_ambig', data) 

571 elif data: 

572 return data[0] 

573 return Discard 

574 

575 def transform_symbol_node(self, node, data): 

576 if id(node) not in self._successful_visits: 

577 return Discard 

578 r = self._check_cycle(node) 

579 if r is Discard: 

580 return r 

581 self._successful_visits.remove(id(node)) 

582 data = self._collapse_ambig(data) 

583 return self._call_ambig_func(node, data) 

584 

585 def transform_intermediate_node(self, node, data): 

586 if id(node) not in self._successful_visits: 

587 return Discard 

588 r = self._check_cycle(node) 

589 if r is Discard: 

590 return r 

591 self._successful_visits.remove(id(node)) 

592 if len(data) > 1: 

593 children = [self.tree_class('_inter', c) for c in data] 

594 return self.tree_class('_iambig', children) 

595 return data[0] 

596 

597 def transform_packed_node(self, node, data): 

598 r = self._check_cycle(node) 

599 if r is Discard: 

600 return r 

601 if self.resolve_ambiguity and id(node.parent) in self._successful_visits: 

602 return Discard 

603 if self._use_cache and id(node) in self._cache: 

604 return self._cache[id(node)] 

605 children = [] 

606 assert len(data) <= 2 

607 data = PackedData(node, data) 

608 if data.left is not PackedData.NO_DATA: 

609 if node.left.is_intermediate and isinstance(data.left, list): 

610 children += data.left 

611 else: 

612 children.append(data.left) 

613 if data.right is not PackedData.NO_DATA: 

614 children.append(data.right) 

615 if node.parent.is_intermediate: 

616 return self._cache.setdefault(id(node), children) 

617 return self._cache.setdefault(id(node), self._call_rule_func(node, children)) 

618 

619 def visit_symbol_node_in(self, node): 

620 super(ForestToParseTree, self).visit_symbol_node_in(node) 

621 if self._on_cycle_retreat: 

622 return 

623 return node.children 

624 

625 def visit_packed_node_in(self, node): 

626 self._on_cycle_retreat = False 

627 to_visit = super(ForestToParseTree, self).visit_packed_node_in(node) 

628 if not self.resolve_ambiguity or id(node.parent) not in self._successful_visits: 

629 if not self._use_cache or id(node) not in self._cache: 

630 return to_visit 

631 

632 def visit_packed_node_out(self, node): 

633 super(ForestToParseTree, self).visit_packed_node_out(node) 

634 if not self._on_cycle_retreat: 

635 self._successful_visits.add(id(node.parent)) 

636 

637def handles_ambiguity(func): 

638 """Decorator for methods of subclasses of ``TreeForestTransformer``. 

639 Denotes that the method should receive a list of transformed derivations.""" 

640 func.handles_ambiguity = True 

641 return func 

642 

643class TreeForestTransformer(ForestToParseTree): 

644 """A ``ForestTransformer`` with a tree ``Transformer``-like interface. 

645 By default, it will construct a tree. 

646 

647 Methods provided via inheritance are called based on the rule/symbol 

648 names of nodes in the forest. 

649 

650 Methods that act on rules will receive a list of the results of the 

651 transformations of the rule's children. By default, trees and tokens. 

652 

653 Methods that act on tokens will receive a token. 

654 

655 Alternatively, methods that act on rules may be annotated with 

656 ``handles_ambiguity``. In this case, the function will receive a list 

657 of all the transformations of all the derivations of the rule. 

658 By default, a list of trees where each tree.data is equal to the 

659 rule name or one of its aliases. 

660 

661 Non-tree transformations are made possible by override of 

662 ``__default__``, ``__default_token__``, and ``__default_ambig__``. 

663 

664 Note: 

665 Tree shaping features such as inlined rules and token filtering are 

666 not built into the transformation. Positions are also not propagated. 

667 

668 Parameters: 

669 tree_class: The tree class to use for construction 

670 prioritizer: A ``ForestVisitor`` that manipulates the priorities of nodes in the SPPF. 

671 resolve_ambiguity: If True, ambiguities will be resolved based on priorities. 

672 use_cache (bool): If True, caches the results of some transformations, 

673 potentially improving performance when ``resolve_ambiguity==False``. 

674 Only use if you know what you are doing: i.e. All transformation 

675 functions are pure and referentially transparent. 

676 """ 

677 

678 def __init__(self, tree_class=Tree, prioritizer=ForestSumVisitor(), resolve_ambiguity=True, use_cache=False): 

679 super(TreeForestTransformer, self).__init__(tree_class, dict(), prioritizer, resolve_ambiguity, use_cache) 

680 

681 def __default__(self, name, data): 

682 """Default operation on tree (for override). 

683 

684 Returns a tree with name with data as children. 

685 """ 

686 return self.tree_class(name, data) 

687 

688 def __default_ambig__(self, name, data): 

689 """Default operation on ambiguous rule (for override). 

690 

691 Wraps data in an '_ambig_' node if it contains more than 

692 one element. 

693 """ 

694 if len(data) > 1: 

695 return self.tree_class('_ambig', data) 

696 elif data: 

697 return data[0] 

698 return Discard 

699 

700 def __default_token__(self, node): 

701 """Default operation on ``Token`` (for override). 

702 

703 Returns ``node``. 

704 """ 

705 return node 

706 

707 def transform_token_node(self, node): 

708 return getattr(self, node.type, self.__default_token__)(node) 

709 

710 def _call_rule_func(self, node, data): 

711 name = node.rule.alias or node.rule.options.template_source or node.rule.origin.name 

712 user_func = getattr(self, name, self.__default__) 

713 if user_func == self.__default__ or hasattr(user_func, 'handles_ambiguity'): 

714 user_func = partial(self.__default__, name) 

715 if not self.resolve_ambiguity: 

716 wrapper = partial(AmbiguousIntermediateExpander, self.tree_class) 

717 user_func = wrapper(user_func) 

718 return user_func(data) 

719 

720 def _call_ambig_func(self, node, data): 

721 name = node.s.name 

722 user_func = getattr(self, name, self.__default_ambig__) 

723 if user_func == self.__default_ambig__ or not hasattr(user_func, 'handles_ambiguity'): 

724 user_func = partial(self.__default_ambig__, name) 

725 return user_func(data) 

726 

727class ForestToPyDotVisitor(ForestVisitor): 

728 """ 

729 A Forest visitor which writes the SPPF to a PNG. 

730 

731 The SPPF can get really large, really quickly because 

732 of the amount of meta-data it stores, so this is probably 

733 only useful for trivial trees and learning how the SPPF 

734 is structured. 

735 """ 

736 def __init__(self, rankdir="TB"): 

737 super(ForestToPyDotVisitor, self).__init__(single_visit=True) 

738 self.pydot = import_module('pydot') 

739 self.graph = self.pydot.Dot(graph_type='digraph', rankdir=rankdir) 

740 

741 def visit(self, root, filename): 

742 super(ForestToPyDotVisitor, self).visit(root) 

743 try: 

744 self.graph.write_png(filename) 

745 except FileNotFoundError as e: 

746 logger.error("Could not write png: ", e) 

747 

748 def visit_token_node(self, node): 

749 graph_node_id = str(id(node)) 

750 graph_node_label = "\"{}\"".format(node.value.replace('"', '\\"')) 

751 graph_node_color = 0x808080 

752 graph_node_style = "\"filled,rounded\"" 

753 graph_node_shape = "diamond" 

754 graph_node = self.pydot.Node(graph_node_id, style=graph_node_style, fillcolor="#{:06x}".format(graph_node_color), shape=graph_node_shape, label=graph_node_label) 

755 self.graph.add_node(graph_node) 

756 

757 def visit_packed_node_in(self, node): 

758 graph_node_id = str(id(node)) 

759 graph_node_label = repr(node) 

760 graph_node_color = 0x808080 

761 graph_node_style = "filled" 

762 graph_node_shape = "diamond" 

763 graph_node = self.pydot.Node(graph_node_id, style=graph_node_style, fillcolor="#{:06x}".format(graph_node_color), shape=graph_node_shape, label=graph_node_label) 

764 self.graph.add_node(graph_node) 

765 yield node.left 

766 yield node.right 

767 

768 def visit_packed_node_out(self, node): 

769 graph_node_id = str(id(node)) 

770 graph_node = self.graph.get_node(graph_node_id)[0] 

771 for child in [node.left, node.right]: 

772 if child is not None: 

773 child_graph_node_id = str(id(child.token if isinstance(child, TokenNode) else child)) 

774 child_graph_node = self.graph.get_node(child_graph_node_id)[0] 

775 self.graph.add_edge(self.pydot.Edge(graph_node, child_graph_node)) 

776 else: 

777 #### Try and be above the Python object ID range; probably impl. specific, but maybe this is okay. 

778 child_graph_node_id = str(randint(100000000000000000000000000000,123456789012345678901234567890)) 

779 child_graph_node_style = "invis" 

780 child_graph_node = self.pydot.Node(child_graph_node_id, style=child_graph_node_style, label="None") 

781 child_edge_style = "invis" 

782 self.graph.add_node(child_graph_node) 

783 self.graph.add_edge(self.pydot.Edge(graph_node, child_graph_node, style=child_edge_style)) 

784 

785 def visit_symbol_node_in(self, node): 

786 graph_node_id = str(id(node)) 

787 graph_node_label = repr(node) 

788 graph_node_color = 0x808080 

789 graph_node_style = "\"filled\"" 

790 if node.is_intermediate: 

791 graph_node_shape = "ellipse" 

792 else: 

793 graph_node_shape = "rectangle" 

794 graph_node = self.pydot.Node(graph_node_id, style=graph_node_style, fillcolor="#{:06x}".format(graph_node_color), shape=graph_node_shape, label=graph_node_label) 

795 self.graph.add_node(graph_node) 

796 return iter(node.children) 

797 

798 def visit_symbol_node_out(self, node): 

799 graph_node_id = str(id(node)) 

800 graph_node = self.graph.get_node(graph_node_id)[0] 

801 for child in node.children: 

802 child_graph_node_id = str(id(child)) 

803 child_graph_node = self.graph.get_node(child_graph_node_id)[0] 

804 self.graph.add_edge(self.pydot.Edge(graph_node, child_graph_node))