Configuration Tree

This page was moved from my old website.

Expanding on a footnote in the post Top-Down Parsing as Graph Search: if each configuration has not only an index, but a full analysis stack, our graph is a tree, as one node cannot have exactly one analysis stack and more than one parent:

Tree of configurations with full analysis stack.

With this definition we get more configurations, meaning that the parser has to perform more steps for the same result. For example, 4:aB and its descendants appear twice in the tree above, but only once in the directed acyclic graph presented in the post.