Non-Recursive Predictive Parser: Architecture and Algorithm (LL(1))

A predictive parser is typically implemented either recursively (calling parsing routines per nonterminal) or non-recursively using an explicit stack and a parsing table. The non-recursive predictive parser (most often the table-driven LL(1) parser) has a clear architecture: it maintains a stack of grammar symbols, reads the next input token (lookahead), and consults a parsing table to decide whether to expand a nonterminal or match a terminal, until it reaches an accepting configuration. This approach eliminates recursion by simulating what the call stack would do in a recursive descent parser.

Key components

• Parsing table $M$
• Lookahead $a$
• Parsing stack $S$
• Start symbol $S_0$
• [End marker]{def="A special token ($or$) appended to input to signal end"} $$$
• LL(1) grammar: determinism depends on FIRST/FOLLOW properties

Dataflow overview (architecture)

This architecture is commonly presented alongside the standard LL(1) table construction (using FIRST and FOLLOW). For a correct parsing table, the grammar must be LL(1), ensuring at most one production per table cell.

Important: If the parsing table cell is empty or conflicts, the parser must report an error (no valid derivation for the observed lookahead).

Core algorithm idea

The non-recursive parser repeatedly inspects:

1. the symbol on top of the stack, and
2. the current input lookahead token.

Then:

• If the top symbol is a terminal:
  • it must match the lookahead; otherwise error.
• If the top symbol is a nonterminal:
  • consult parsing table $M[\text{nonterminal}, \text{lookahead}]$:
    • if a production exists: replace the nonterminal on the stack with the RHS (pushed in reverse order),
    • else error.
• When the stack top is \$$ and the input lookahead is also $$, the parser accepts.

This procedure is the iterative counterpart of the recursive approach that would “call” the appropriate production based on lookahead.

Key design invariants

• The parser stack always contains a suffix of the right-sentential form that should correspond to the remaining portion of the input.
• Table-driven expansion preserves derivation consistency: if the grammar is LL(1) and the table is correct, each step mimics choosing the same production that a deterministic recursive descent parser would choose.

Table construction link (why FIRST/FOLLOW matter)

To make $M$ correct, a production $A \\to \\alpha$ must be placed into table cells that correspond to all possible lookahead tokens that can appear when $A$ is expanded. The standard LL(1) logic uses:

• For each terminal $t \\in \\text{FIRST}(\\alpha)$, add $A \\to \\alpha$ to $M[A,t]$.
• If $\\epsilon \\in \\text{FIRST}(\\alpha)$, then $A \\to \\alpha$ must also be placed for all terminals $b \\in \\text{FOLLOW}(A)$, i.e., add $A \\to \\alpha$ to $M[A,b]$.
• If $\\alpha$ derives $\\epsilon$, ensure the FOLLOW propagation handles lookaheads appropriately so the parser knows when to effectively “skip” the production.

Minimal architectural consequence

Because the runtime algorithm only consults $M[X,a]$, all correctness depends on whether $M$ is constructed to satisfy LL(1) determinism (no conflicting productions in any cell).

Operational complexity

Let $n$ be the number of input tokens (excluding $\\$`$). Each loop iteration either:

• matches and advances the input (consuming at least one token), or
• expands a nonterminal by pushing RHS symbols (which increases stack content but is bounded by the derivation steps for valid inputs).

For an LL(1) predictive parser, the number of expansions and matches is linear in the length of a valid derivation, so runtime is typically described as $O(n)$ for parsing (ignoring the cost of building $M$). Building FIRST/FOLLOW and $M$ is additional preprocessing.

Symbol handling guarantees

• Terminals: exactly matched or error.
• Nonterminals: expanded only when a table entry exists.
• Epsilon productions: represent “push nothing”, so the parser effectively performs a zero-length derivation step.