dmitry_vk's notes

Normalizing mixed-order tree traversal into pre-order traversal

Intro

While working on some parsing problems, I encountered an interesting problem that I haven't seen elsewhere and want to share it (with its solution).

When parsing, we often deal with parse tree traversals. Normally, the pre-order traversal is most convenient for processing, but parsers often don't produce parse results in that order.

Let's define a mixed traversal as a sequence of the following kinds of steps (one might also call them events):

  • StartNode(payload): marks the start of a new node
  • EndNode: marks the end of a previously started node (in LIFO order)
  • WrapSiblings(payload, n): denotes the start of a new node, which has actually started before, specifically before the n-th last node

payload is an information necessary to create a node, e.g. its type.

The sequence is processed left-to-right, and the tree is built incrementally, using a stack of nodes:

  • StartNode(payload) pushes a new empty node into the stack
  • EndNode pops a node from the stack and appends it into parent's children
  • WrapSiblings(payload, n) creates and pushes a new node (just as StartNode), but “steals” n nodes from the current parent node and inserts them into a new node.
    • This a similar to the “reduce” operation in LR parsing (except that “reduce” completes the node, while WrapSiblings leaves the node open for further modifications).

The “mixed” traversal is a superset of how different kinds of parsing algorithms construct a parse tree:

  • LL parsers only use StartNode and EndNode;
  • LR parsers only use WrapSiblings and EndNode;
  • Pratt parsers emit all kinds of steps.

The problem is as follows: Given a sequence of steps corresponding to a mixed traversal, produce a sequence of steps corresponding to an equivalent pre-order traversal.

Example

Let's consider the following syntax tree that corresponds to a * b + c:

The pre-order traversal (top-down, left-to-right; which is what we want to ideally have) of this tree would be:

Start "+"
Start "*"
Start "a"
End
Start "b"
End
Start "c"
End
End

The bottom-up, left-to-right traversal would be (e.g., how an LR parser would process the string):

Start "a"
End
Start "b"
End
WrapSiblings "*" 2
End
Start "c"
End
WrapSiblings "+" 2
End

The other option for the traversal is (e.g., how a Pratt parser would process the string):

Start "a"
End
WrapSiblings "*" 1
Start "b"
End
End
WrapSiblings "+" 1
Start "c"
End
End

Naive baseline algorithm

The simplest algorithm is as follows:

  • Allocate a stack S of active nodes. Initially, S contains a sentinel virtual root. Each node in S has id and children, where children is a vector of nodes.
  • Iterate over the input sequence of steps and check each step:
    • If it is StartNode: create a new node and push it into S.
    • If it is EndNode: pop a node from S, and push it into children of the new top node of the stack S.
    • If it is WrapSiblings(n): take last n items from children of the top node of S, create a new node with those n items, and push it into S.
  • At the end, serialize the resulting R into events by a pre-order traversal of trees in R.

This algorithm is fine. It has a run time O(|input|), but it performs dynamic memory-allocations for individual nodes and has to allocate the whole tree.

A more efficient algorithm

Some observations

  • When observing traversal left-to-right, we don't know if WrapSiblings comes in later and changes the tree structure. On the other hand, when processing it right-to-left, the structure we already emitted can'be affected by not-yet-processed events.
  • When processing steps right-to-left, WrapSiblings(n) means “after emitting n nodes, emit StartNode”.
  • All active StartNode and WrapSiblings (i.e., for which the corresponding EndNode was not yet observed in left-to-right order) belong to different tree levels.
  • Consecutive WrapSiblings steps may stack within each other, and their emit order may be reversed to their observation order.
  • Each node produced by a (StartNode, EndNode) pair may be wrapped by multiple WrapSiblings events, i.e. one node can count towards siblings counts of multiple WrapSiblings events.

Algorithm, v0

The algorithm normalizes the sequence using a right-to-left scan of input sequence. It uses a stack as an auxiliary data structure to track information about active events at each tree level.

  • Given:
    • S[n] - an array of tree traversal steps (as defined previously)
  • Output:
    • O[n] - an array that holds elements of the same type as S (but only items of types StartNode and EndNode may appear).
  • Initialize:
    • L: array of Option<{ payload, num_nodes }> - growable array of that tracks for each tree depth level a currently active WrapSiblings (i.e., which was observed but which is still waiting for one or more nodes before it can be emitted); L is initially empty and may contain empty slots.
      • payload is the payload that should be emitted as a part of an equivalent StartNode(payload)
      • num_nodes is the counter of remaining nodes before WrapSiblings can be converted into StartNode
    • O = []
  • Steps:
    • for i starting from n - 1 down to 0:
      • match on S[i]:
        • EndNode:
          • push null into S
          • output EndNode into O
        • WrapSiblings { payload, num_nodes }:
          • find k - the index of the last null value in L. Such k should always exist for a valid input sequence. Use simple linear search to find k.
          • assign { payload = S[i].payload, num_nodes = S[i].num_nodes } into L[k]
        • StartNode { payload }:
          • output StartNode { payload } into O
          • assert that L is not empty and it last value is an empty slot. This holds true for all valid input sequences.
          • pop the empty slot from L
          • process pending WrapSiblings that have been completed after emitting StartNode:
            • initialize num_emitted = 1. This variable tracks the number of node we have emitted in this iteration.
            • for j from length(L) - 1 down to 0:
              • if L[j] is empty: break the for loop
              • assert that L[j].num_nodes >= num_emitted. This holds true for all valid input sequences.
              • if L[j].num_nodes = num_emitted:
                • output StartNode { payload = L[j].payload } into O
                • assert that j = length(L) - 1. This holds for all valid input sequences
                • pop L[j] from L
                • increment num_emitted
              • else:
                • decrement L[j].num_nodes by num_emitted
    • assert that L is empty. This holds true for all valid input sequences.
    • reverse O

The tricky part of the algorithm is the properly considering stacking of active WrapSiblings:

  • WrapSiblings are emitted in reverse order, therefore they are added to a stack of level in reverse order (i.e., by looking for a free slot) as well
  • a node could have been at some point a child of several consecutive WrapSiblings steps, and WrapSiblings could also be a child of another node produced by WrapSiblings. As a result of this, when processing events right-to-left, a completed StartNode (including the one produced by completing a WrapSiblings) leads to a decrement of num_nodes for all consecutive slots of L.

This algorithm runs in O(n * d) time and uses O(n + d) additional memory, where d is the depth of the tree. In the worst case, d is proportional N, and the runtime of this algorithm may degenerate to O(n^2).

This algorithm can be improved by several simple mechanical optimizations.

Optimization 1: pre-subtract L[j].num_nodes

Each consecutively stacked WrapSiblings must fully exhaust its num_nodes before the next one can be completed. Therefore we can decrement num_nodes of stacked WrapSiblings in advance, in which case each processed StartNode will only require a single decrement. At the same time we must also consider that completing a pending WrapSiblings produces StartNode event, which also result in further decrements of num_nodes on further levels. The overall result of this is that we need to pre-subtract num_nodes - 1 from each consecutiely-stacked WrapSiblings.

Optimization 2: in-place output

We may observe that the output of the algorithm fits into an already-visited part of the input array S. And since the structure of the output is the same, we can reuse the input as an output and modify it in-place.

This lets us avoid O(n) of additional memory allocation, but does not change the runtime.

Optimization 3: track unoccipied tree levels in L

Searching for k - a pointer to a free slot in L - is O(d), but it can be made O(1). The search can be optimized, if we consider that L operates in almost (but not quite) a stack-like fashion, as all reads and writes are happening at the end of L.

In addition to L, maintain F: array of { slot_idx, sum_num_nodes_sub_1 } - a stack of indices of all free slots in L. This data structure would let us quickly find the last free slot in L.

Each item of F contains 2 attributes:

  • slot_idx - index in L of the free slot;
  • sum_num_nodes_sub_1 - sum of (num_nodes - 1) of all occupied slots until the next free slot.

This stack is maintained and used in the following way:

  • When pushing a new free level into L, push { slot_idx: level_idx, sum_num_nodes_sub_1: 0} into F
  • When popping an empty slot from L:
    • pop the value from F
  • When popping a non-empty value from L:
    • assert that its num_nodes equals 1
    • do nothing, as subtracting num_nodes - 1 = 1 - 1 = 0 does not change the value of sum_num_nodes_sub_1
  • When writing a value v into an empty slot of L:
    • if F only has 1 value: pop the value
    • if F has 2 or more values: merge the last 2 values in F, taking into account v.num_nodes - 1. I.e.:
      • pop a from F
      • pop b from F
      • push { slot_idx: b.slot_idx, sum_num_nodes_sub_1 = a.sum_num_nodes_sub_1 + b.sum_num_nodes_sub_1 + v.num_nodes - 1 }
  • When searching for the last free slot in L:
    • inspect the last value of F; its slot_idx is the last free slot index (i.e., k in the base algorithm), and its sum_num_nodes_sub_1 is the sum of (num_nodes - 1) for the remaining non-empty slots (i.e., equals to r in the base algorithm)

With these optimizations, the algorithm runs in O(n) time with O(d) additional memory.

Source code

Source code is available at https://codeberg.org/dmitryvk/convert-mixed-order-traversal. It contains the algorithm, as well as benchmarks and tests.