Early's Parser

Early describes his parser as a ``breadth-first top-down parser with bottom-up recognition'' (!) While we will regard it as a top-down parser it does in fact exhibit many similarities to LR parsing.

Note that any similarity with the LR algorithms is superficial however:

• The LR algorithm generates a set of states from the grammar; this machine can then be used to parse any input (Parser construction)
• Early's algorithm is executed for a particular string; each string will cause different state-sets to be generated (Parser operation)

At any stage in a top-down parse we have a ``current'' non-terminal symbol and a choice of rules to apply to it. If we cannot make a definite choice (eg. based on lookahead), we must adopt a search strategy.

Conventionally, this will be

1. Depth first, where we choose the first alternative and try it; if this doesn't work we must backtrack and try the next one. (this is how Prolog's DCGs¹work)
2. Breadth first, where we hive off one ``subprocess'' for each alternative, and proceed with trying each of them in parallel.

The major problem with breadth-first parsing is that it takes exponential time (relative to the input string length) in general. Early's approach seeks to limit the options chosen, resulting in an algorithm of order $n^3$, where $n$ is the length of the input string.