Editing LL parser (section)

== Parser ==

The LL(''k'') parser is a [[deterministic pushdown automaton]] with the ability to peek on the next ''k'' input symbols without reading. This peek capability can be emulated by storing the lookahead buffer contents in the finite state space, since both buffer and input alphabet are finite in size. As a result, this does not make the automaton more powerful, but is a convenient abstraction.

The stack alphabet is <math>\Gamma = N \cup \Sigma</math>, where:
* <math>N</math> is the set of non-terminals;
* <math>\Sigma</math> the set of terminal (input) symbols with a special end-of-input (EOI) symbol '''$'''.
The parser stack initially contains the starting symbol above the EOI: {{nowrap|[ S '''$''' ]}}. During operation, the parser repeatedly replaces the symbol <math>X</math> on top of the stack:
* with some <math>\alpha</math>, if <math>X \in N</math> and there is a rule <math>X \to \alpha</math>;
* with <math>\epsilon</math> (in some notations <math>\lambda</math>), i.e. <math>X</math> is popped off the stack, if <math>X \in \Sigma</math>. In this case, an input symbol <math>x</math> is read and if <math>x \neq X</math>, the parser rejects the input.
If the last symbol to be removed from the stack is the EOI, the parsing is successful; the automaton accepts via an empty stack.

The states and the transition function are not explicitly given; they are specified (generated) using a more convenient ''parse table'' instead. The table provides the following mapping:
* row: top-of-stack symbol <math>X</math>
* column: {{abs|''w''}} ≤ ''k'' lookahead buffer contents
* cell: rule number for <math>X \to \alpha</math> or <math>\epsilon</math>
If the parser cannot perform a valid transition, the input is rejected (empty cells). To make the table more compact, only the non-terminal rows are commonly displayed, since the action is the same for terminals.