Top Down Parsing

Top-Down Parsing

The Parser Studio supports the LL(1) top-down predictive parsing algorithm.

"Top-Down" means the parser begins with the Start Symbol at the top of the tree, and tries to guess which production rules to apply to grow the tree downwards until its leaves match the input string.

1. LL(1) Mechanics

• L stands for reading the input from Left to right.
• L stands for producing a Leftmost derivation.
• 1 stands for using exactly 1 token of lookahead.

Because the parser only looks 1 token ahead, it must be completely certain which production rule to choose. If multiple rules are valid for the same lookahead token, a conflict occurs.

2. Generating the LL(1) Parse Table

When you select LL(1) from the dropdown, AutomataLab uses the FIRST and FOLLOW sets (calculated in the Grammar Lab) to generate the LL(1) Parse Table.

• Rows represent the Non-Terminals.
• Columns represent the input Terminals.
• Cells contain the production rule to apply.

How cells are populated

For every production rule $A \rightarrow \alpha$:

1. For every terminal $a$ in $\text{FIRST}(\alpha)$, place $A \rightarrow \alpha$ in the cell $[A, a]$.
2. If $\epsilon$ is in $\text{FIRST}(\alpha)$, then for every terminal $b$ in $\text{FOLLOW}(A)$, place $A \rightarrow \alpha$ in the cell $[A, b]$.

LL(1) Conflicts

If the algorithm tries to place two different production rules into the exact same cell, that cell is flagged Red. This means your grammar is not LL(1)-parseable. The two most common causes are:

1. Left Recursion: E.g., $E \rightarrow E + T \mid T$. Both rules share the same FIRST sets. You must mathematically eliminate left recursion for LL(1) to work.
2. Lack of Left Factoring: E.g., $S \rightarrow \text{if } E \text{ then } S \mid \text{if } E \text{ then } S \text{ else } S$. Both rules start with if. The parser cannot know which rule to pick just by looking 1 token ahead at if. You must factor out the common prefix.

3. Simulation & Execution

If your LL(1) Parse Table is conflict-free, you can simulate it!

1. Type a tokenized string in the Input Buffer (e.g., id + id * id).
2. Press Play or Step.

AutomataLab will initialize the Parse Stack with the Start Symbol. At every step:

• It looks at the symbol on top of the stack and the next token in the input.
• If the stack top is a terminal, it matches it against the input and pops it.
• If the stack top is a non-terminal, it looks up the rule in the Parse Table, pops the non-terminal, and pushes the RHS of the rule onto the stack in reverse order.
• The Syntax Tree automatically visualizes this expansion top-down in real time!

See Also

• Bottom-Up Parsing
• Mathematical Properties