Parse tree¶

The parse-ebnf parse tree is represented using the PT class:

class parse_ebnf.PT¶

A parse tree for EBNF.

Contains the following variables:

root, the root node of the tree, an instance of Root;
count, the number of nodes in the tree;
height, the height of the tree;
maxDegree, the maximum number of children that a single node has in the tree.

And the following functions:

unparse, pass a write function(a function that works just like the write function for files) to write the text that the parse tree was created from.
write, use with a write function to dump a textual representation of the parse tree, mainly meant for debugging.

For parsing check the parsing section.

Each node in the parse tree inherits from the Node class:

class parse_ebnf.nodes.Node(startLine=0, startColumn=0, endLine=0, endColumn=0)¶

Base class of all PT nodes.

PT nodes differ only in what nodes are their parent and which nodes are their children, see the reference.

This node type, along with Leaf and Primary, are not instantiated in the PT, they serve as abstract base classes.

This class in particular is the base for all other node types. The intent is to use isinstance to resolve a node’s exact type.

All nodes contain the following variables:

parent – a Node instance that acts as the parent for this node. It is None only for Root.
children – a list of Node instances that act as this node’s children. Every node in this list has its parent set to this node. Empty only for instances of Leaf.
depth – an integer denoting how deep this node is in the tree. The root is defined as being at depth 0, it’s children at depth 1, their children at depth 2, etc.
startLine – the line where the text that this node is comprised of starts, inclusively. Counting starts from 1, and is incremented each time a newline is encountered in the input;
startColumn – the column where the text that this node is comprised of starts, inclusively. Counting starts at 1, and in incremented every character. Each newline resets the counter to 0;
endLine – like startLine except that this is where the text ends, exclusively;
endColumn – like startColumn except that this is where the text ends, exclusively.

The following statements are always true:

startLine >= 0
endLine >= 0
startColumn >= 0
startLine <= endLine
if startColumn > endColumn and startLine == endLine: str(node) == ‘’ else: endColumn >= 0

Note

The end coordinates also take into account child nodes. The children’s text is also counted as the parent’s text.

The Node class along with a few other node classes do not appear in the tree; they act as abstract base classes:

class parse_ebnf.nodes.Leaf(data='')¶

Base class of all leaf nodes.

This node is a base class for all leaf nodes, nodes whose children list is empty.

Note

Only leafs nodes contain text data in the tree.

This node has the following variables:

Variables inherited from Node;
data – the text content of the node, a string.

class parse_ebnf.nodes.Primary(startLine=0, startColumn=0, endLine=0, endColumn=0)¶

A node holding what a term parses.

This class is mainly meant to tag other nodes that may be primaries for a Term.

The current list of primaries is:

Terminal;
Repeat;
Option;
Group;
Special;
Identifier;
EmptyString.

Parse trees and all nodes implement the repr and str functions. Taking repr() of a node or parse tree gives a debug string that describes the structure of a parse tree or node. Taking str() of a node or parse tree gives the yield of said node or parse tree.

str() applied to a parse tree is equivalent to applying it to its root. On the other hand, repr() is not equivalent between a parse tree and its root, the parse tree adds an extra line.

Partial trees¶

If an error occurs during parsing, a partial tree is created. A partial tree is valid for the most part, with the exception of partial nodes. Partial nodes have valid parent and child links, however their coordinates, child specification and data are not guaranteed to be valid. This means that a partial parse tree as a whole is valid up to the point of failure, anything beyond that is undefined.

Partial trees and nodes operate under the following rules:

A partial tree has a partial root;
A partial node has a partial last child, all other children are valid;

See the example for how to get and handle partial trees.

Node types¶

This section contains a reference of all node types found in the PT.

Each node type contains:

A short description of what it represents;
A list of possible parent nodes;
A child node list specification.

The parent list and child node specification are taken directly from the tests. The child nodes specification uses functions whose meaning is described in the notation section.

The nodes are ordered in roughly the same way as they appear in the parse tree, going from the root to the leafs.

Notation¶

The types, order and count of child nodes for each node type is documented using a list of node types and functions called children. These functions enclose a node type and modify how many times, if it at all it appears. Some functions set what data a Leaf node may hold.

Child nodes appear in the same order as in the child node specification. For example say the node A had a child spec of:

children = [ Identifier, Space, Identifier ]

That means that any instance of A is guaranteed to have a child list of length 3 that first contains an Identifier as the first element, followed by a Space and finally another Identifier instance as the last element.

A number of functions modify the number of times a child node appears. For example the child specification of Product:

children = [ Identifier, maybe(Space), literal("="), maybe(Space), DefinitionList, maybe(Space), literal([";", "."]) ]

Means that any one Product instance may have between 4 and 7 child nodes. Of those, the first is always an Identifier. A single Space instance might follow, or it might not. Then a Literal with the data = always follows, with an optional Space. A single DefinitionList comes after and another optional Space follows. The last node is guaranteed to be a Literal that has its data set either to . or ;.

As another example, the child spec of Comment:

children = [ literal("(*"), zero_or_more(either(Comment, Text)), literal("*)") ]

All comments start with a Literal with the data (*, followed by any number, including zero, or either Comment or Text instances. Finally the last node is always a Literal with the data *). The length of the children list can be anywhere from 2 to any finite number.

As a final example, an empty child specification:

children = [ ]

This means that the node has no children, a unique characteristic of Leaf nodes.

The parents list gives the possible nodes types that may be a parent of a node. For example:

parents = [ Root, Product, Comment ]

Means that the node’s parent may either be a Root instance, a Product instance or a Comment instance.

Function reference¶

tests.tree_structure.literal(s)¶

A singe Literal instance is expected.

The data that the Literal holds is either one of the arguments.

tests.tree_structure.either(*args)¶

Only one of the arguments are expected.

The arguments may be node types or other functions. In any case, only one of them may follow in the child list.

tests.tree_structure.zero_or_more(*args)¶

Any finite number or zero of the arguments are expected.

Any number of node types and functions may be specified. In all cases, they are expected to follow in the child list in the order they are specified.

For example:

zero_or_more(either(Comment, Product), Space)

Means that either a Comment or Product followed by a Space are expected to occur any number of times in the child list.

tests.tree_structure.maybe(*args)¶

The arguments may or may not occur.

The arguments may be node types or other functions. In all cases, either all of the arguments occur in the child list in the specified order or they do not occur at all.

For example:

maybe(Space, zero_or_more(Term, Product), Space)

Means that a single sequence of a Space followed by any number of Term, Product pairs followed by a single Space may occur in the child list, or not at all.

Node reference¶

The PT always begins with the Root node:

class parse_ebnf.nodes.Root(startLine=0, startColumn=0, endLine=0, endColumn=0)¶

The root PT node.