What is the difference between top-down and bottom-up parsing?
2024
What is the difference between top-down and bottom-up parsing?
- A.
Top-down parsing starts from the start symbol/root, while bottom-up parsing starts from the input symbols/leaves.
- B.
Top-down verifies rules against previous tokens, bottom-up constructs the parse tree
- C.
Top-down is more efficient for smaller grammars, bottom-up for larger ones
- D.
All of the above.
Attempted by 30 students.
Show answer & explanation
Correct answer: A
Top-down and bottom-up parsing differ mainly in the direction in which the parse tree is constructed.
In top-down parsing, the parser starts from the start symbol/root of the grammar and expands productions until it matches the input string. It builds the parse tree from root to leaves.
In bottom-up parsing, the parser starts from the input symbols/leaves and repeatedly reduces substrings to non-terminals until it reaches the start symbol. It builds the parse tree from leaves to root.
Hence, the correct answer is: Top-down parsing starts from the start symbol/root, while bottom-up parsing starts from the input symbols/leaves.