Top-Down and Bottom-Up Parsing

Top-Down Parsing (Leftmost Derivation)

• The process starts with the starting symbol $$ S $$ and expands the leftmost non-terminal at each step.
• Given:
  • $$ S \rightarrow AB $$
  • $$ A \rightarrow aA \mid \epsilon $$
  • $$ B \rightarrow b \mid \epsilon $$
• Target: $$ aaab $$

Step-by-step derivation:

1. $$ S \rightarrow AB $$
2. $$ AB \rightarrow aAB $$
3. $$ aAB \rightarrow aaAB $$
4. $$ aaAB \rightarrow aaaAB $$
5. $$ aaaAB \rightarrow aaa\epsilon B $$
6. $$ aaa\epsilon B \rightarrow aaab $$

This is a top-down parsing approach because it expands from the start symbol $$ S $$ and works downward, always expanding the leftmost non-terminal.

Bottom-Up Parsing (Rightmost Derivation in Reverse)

• The process starts with the string of terminals $$ aaab $$ and works backward, reducing strings to non-terminals until you reach $$ S $$.
• Working backward:
  1. $$ aaab $$
  2. $$ aaaB $$ (replace $$ b $$ with $$ B $$)
  3. $$ aaaAB $$ (replace $$ \epsilon $$ with $$ A $$)
  4. $$ aaAB $$ (replace $$ aA $$ with $$ A $$)
  5. $$ aAB $$ (replace $$ aA $$ with $$ A $$)
  6. $$ AB $$ (replace $$ aA $$ with $$ A $$)

This is a bottom-up parsing approach because it starts from the terminal string and works upward, reducing substrings to non-terminals.

Summary

• Top-down parsing starts from the root ($$ S $$) and expands leftmost non-terminals.
• Bottom-up parsing starts from the target string and works backward, reducing substrings to non-terminals until reaching the root.