leftmostoutermost

The term "leftmost outermost" is primarily used in the context of parsing, particularly in compiler design and formal language theory. It refers to a specific strategy for constructing a parse tree for a given input string according to a formal grammar.

In a leftmost outermost derivation, the parser always chooses the leftmost non-terminal symbol in the current sentential form and applies a production rule to replace it. This process is repeated until the sentential form consists entirely of terminal symbols, forming the input string. The "outermost" aspect emphasizes that the chosen non-terminal is the one furthest to the left that can be expanded.

This parsing strategy is associated with top-down parsers, such as recursive descent parsers and LL parsers. LL(k) parsers, for instance, are designed to look ahead k symbols in the input to make parsing decisions. The leftmost outermost derivation ensures that the parse tree is constructed by always expanding the leftmost available non-terminal, building the tree from the root downwards.

The success of a leftmost outermost derivation depends on the grammar. If a grammar is ambiguous or if the parsing strategy cannot uniquely determine which production rule to apply at each step (without sufficient lookahead), the parser may fail to produce a correct parse or might enter an infinite loop. Grammars suitable for leftmost outermost parsing are often called LL(k) grammars.