Package lepl :: Package core :: Module rewriters

Module rewriters

Rewriters modify the graph of matchers before it is used to generate a parser.

Classes

Rewriter
base class for rewriters, supporting a fixed ordering.

Flatten
A rewriter that flattens And and Or lists.

ComposeTransforms
A rewriter that joins adjacent transformations into a single operation, avoiding trampolining in some cases.

TraceVariables
A rewriter needed for TraceVariables which adds the trace_variables attribute to untransformable matchers that need a transform.

RightMemoize
A rewriter that adds RMemo to all nodes in the matcher graph.

LeftMemoize
A rewriter that adds LMemo to all nodes in the matcher graph.

AutoMemoize
Apply two different memoizers, one to left recursive loops and the other elsewhere (either can be omitted).

OptimizeOr
A rewriter that re-arranges Or matcher contents for left--recursive loops.

SetArguments
Add/replace named arguments while cloning.

DirectEvaluation
Replace given matchers if all Matcher arguments are subclasses of NoTrampolineWrapper

FullFirstMatch
If the parser fails, raise an error at the maxiumum depth.

NodeStats
Provide statistics and access by type to nodes.

NodeStats2
Avoid using graph code (so we can check that...)

Functions

[hide private]

clone(i, j, node, args, kargs)
Clone a single node, including matcher-specific attributes.

source code

copy_standard_attributes(node, copy)
Handle the additional attributes that matchers may have.

source code

linearise_matcher(node)
Return [(head, reversed), ...] where each tuple describes a tree of matchers without loops. source code

clone_tree(i, head, reversed, mapping, delayed, clone, duplicate=False)
Clone a tree of matchers.

source code

clone_matcher(node, clone=clone, duplicate=False)
This used to be implemented using the graph support classes (ConstructorWalker() etc).

source code

post_clone(function)
Generate a clone function that applies the given function to the newly constructed node, except for Delayed instances (which are effectively proxies and so have no functionality of their own) (so, when used with DelayedClone, effectively performs a map on the graph). source code

left_loops(node)
Return (an estimate of) all left-recursive loops from the given node.

source code

either_loops(node, conservative)
Select between the conservative and liberal loop detection algorithms.

source code

Function Details

[hide private]

linearise_matcher(node)

source code

Return [(head, reversed), ...] where each tuple describes a tree of matchers without loops. The first head is the root node. The reversed list contains nodes ordered children-first (except for Delayed() instances, whose children are other head elements).

This allows us to clone a DAG of matchers in the same way as it was first created - by creating linear trees and then connecting the Delayed() instances.

The postorder ordering is used to match the ordering in the more general iteration over matchers based on the graph support classes and helps keep things consistent (there was a strange issue where the .tree() display of a cloned graph differed from the original that, I think, was due to a different ordering).

clone_tree(i, head, reversed, mapping, delayed, clone, duplicate=False)

source code

Clone a tree of matchers. This clones all the matchers in a linearised set, except for the Delayed() instances, which are re-created without their contents (these are set later, to connect the trees into the final matcher DAG).

i is the index of the tree (0 for the first tree, which cannot be part of a loop itself). It is passed to the clone function.

head is the root of the tree.

reversed are the tree nodes in postorder

mapping is a map from old to new node of all the nodes created. For Delayed() instances, if duplicate=True, then the new node is just one of possibly many copies.

clone is the function used to create a new node instance.

duplicate controls how Delayed() instances are handled. If true then a new instance is created for each one. This does not preserve the graph, but is used by memoisation.

clone_matcher(node, clone=clone, duplicate=False)

source code

This used to be implemented using the graph support classes (ConstructorWalker() etc). But the left-recursive handling was unreliable and that was too opaque to debug easily. It's possible this code could now be moved back to that approach, as not everything here is used (the j index turned out not to be useful, for example). But this approach is easier to understand and I am not 100% sure that the code is correct, so I may need to continue working on this.

node is the root of the matcher graph.

clone is a function used to create new instances.

duplicate controls how Delayed() instances are handled. If true then a new instance is created for each one. This does not preserve the graph, but is used by memoisation.

left_loops(node)

source code

Return (an estimate of) all left-recursive loops from the given node.

We cannot know for certain whether a loop is left recursive because we don't know exactly which parsers will consume data. But we can estimate by assuming that all matchers eventually (ie via their children) consume something. We can also improve that slightly by ignoring Lookahead.

So we estimate left-recursive loops as paths that start and end at the given node, and which are first children of intermediate nodes unless the node is Or, or the preceding matcher is a Lookahead.

Each loop is a list that starts and ends with the given node.