LL(1) Parsing - Oya-Learning-Notes/Compilers GitHub Wiki

When using Top-Down Parsing, we usually generate a table, then pass this table to a LL(1) Table-driven Parser.

Parse Table

For top down parse table:

  • Row: List of NonTerminal
  • Column: List of Terminal
  • Elements: Possible RHS (Derivations) of the NonTerminal

This table actually contains info that in what specific lookahead we should use a specific derivation.

Following is an example of a LL(1) Parse Table.

LL1 Parse Table Example

Parser

LL(1) Parser only use one stack called Analyze Stack. This stack record currently parsed sentence, including Terminal and NonTerminal, in a reverse order.

LL(1) Parser Working Procedure Example

Note:

  • When stack top is a NonTerminal, using Parse Table to perform production.
  • When stack top is a Terminal*, try match input string. Failed if not match.