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 \eps…


This content originally appeared on DEV Community and was authored by Mujahida Joynab

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.


This content originally appeared on DEV Community and was authored by Mujahida Joynab


Print Share Comment Cite Upload Translate Updates
APA

Mujahida Joynab | Sciencx (2025-11-03T19:30:35+00:00) Top-Down and Bottom-Up Parsing. Retrieved from https://www.scien.cx/2025/11/03/top-down-and-bottom-up-parsing/

MLA
" » Top-Down and Bottom-Up Parsing." Mujahida Joynab | Sciencx - Monday November 3, 2025, https://www.scien.cx/2025/11/03/top-down-and-bottom-up-parsing/
HARVARD
Mujahida Joynab | Sciencx Monday November 3, 2025 » Top-Down and Bottom-Up Parsing., viewed ,<https://www.scien.cx/2025/11/03/top-down-and-bottom-up-parsing/>
VANCOUVER
Mujahida Joynab | Sciencx - » Top-Down and Bottom-Up Parsing. [Internet]. [Accessed ]. Available from: https://www.scien.cx/2025/11/03/top-down-and-bottom-up-parsing/
CHICAGO
" » Top-Down and Bottom-Up Parsing." Mujahida Joynab | Sciencx - Accessed . https://www.scien.cx/2025/11/03/top-down-and-bottom-up-parsing/
IEEE
" » Top-Down and Bottom-Up Parsing." Mujahida Joynab | Sciencx [Online]. Available: https://www.scien.cx/2025/11/03/top-down-and-bottom-up-parsing/. [Accessed: ]
rf:citation
» Top-Down and Bottom-Up Parsing | Mujahida Joynab | Sciencx | https://www.scien.cx/2025/11/03/top-down-and-bottom-up-parsing/ |

Please log in to upload a file.



There are no updates yet.
Click the Upload button above to add an update.

You must be logged in to translate posts. Please log in or register.

Related Posts