04 Top Down Parsing

Top-Down Parsing¶

Recursive predictive parsing is a type of Recursive Descent, without backtracking
Non-recusive predictive parser is also known as LL(1) parser

I would recommend just drawing the tree, and finding the corresponding set of terminals.

The first symbol accessible;

Non-Terminal
Start Symbol $S$	Follow(S) $\supset \{\$\}$
$A \to \alpha B \beta$	Follow(B) $=$ First($\beta$) - $\{\epsilon\}$
$A \to \alpha B$ $A \to \alpha B \beta$, and $\epsilon \in$ First($\beta$)	Follow(B) $\supset$ Follow(A)

No multiple-defined entries in parsing table


Input Buffer	String to be parsed, ending with `$`
Output	Producting rule representing step of leftmost derivation sequence of string in input buffer
Stack	Contains grammar symbols `$` signifies bottom of stack Initially, stack contains `$S` Only `$` in stack signfies parsing complete
Parsing Table	2 dimensional array $M[A, a]$ Each row is a non-terminal symbol Each column is `$`/terminal symbol Each entry holds production rule

		Replace with
Elimination of left recursion	$A \to A \alpha	\beta$
Elimination of left factoring	$A \to \alpha \beta_1	\alpha \beta_2
Calculate FIRST & FOLLOW
Construction of parsing table For each $A \to \alpha$
For each terminal a in FIRST($\alpha$)

Check if input string is accepted/not

This part is Incomplete

Last updated: 2023-01-25 • Contributors: AhmedThahir

Non-Terminal
Start Symbol \(S\)	Follow(S) \(\supset \{\$\}\)
\(A \to \alpha B \beta\)	Follow(B) \(=\) First(\(\beta\)) - \(\{\epsilon\}\)
\(A \to \alpha B\) \(A \to \alpha B \beta\), and \(\epsilon \in\) First(\(\beta\))	Follow(B) \(\supset\) Follow(A)