Bottom-up parsing

In computer science, parsing reveals the grammatical structure of linear input text, as a first step in working out its meaning.

A bottom-up parse discovers and processes that tree starting from the bottom left end, and incrementally works its way upwards and rightwards.

The opposite of this is top-down parsing, in which the input's overall structure is decided (or guessed at) first, before dealing with mid-level parts, leaving completion of all lowest-level details to last.

A top-down parser discovers and processes the hierarchical tree starting from the top, and incrementally works its way first downwards and then rightwards.

If a language grammar has multiple rules that may start with the same leftmost symbols but have different endings, then that grammar can be efficiently handled by a deterministic bottom-up parse but cannot be handled top-down without guesswork and backtracking.