Which type of grammar is required for predictive (non-backtracking) top-down…
2025
Which type of grammar is required for predictive (non-backtracking) top-down parsing?
- A.
LL(1) grammar
- B.
Ambiguous grammar
- C.
LR(0) grammar
- D.
Left-recursive grammar
Attempted by 36 students.
Show answer & explanation
Correct answer: A
In compiler design, a predictive top-down parser constructs the parse tree from the root node (the start symbol) down to the leaf nodes (the terminals/tokens) without ever rolling back or changing its mind.
To construct a deterministic parsing table for such a parser, the context-free grammar must satisfy the LL(1) properties:
L: Left-to-right scanning of the input string.
L: Leftmost derivation is used to construct the parse tree.
(1): One token of lookahead is sufficient to make a non-backtracking decision.
For a grammar to be LL(1), it must not contain any Left-Recursion or Left-Factoring issues. When the parser looks at a non-terminal variable and the current lookahead token from the input, there must be exactly one valid production entry in the parsing table. If a grammar meets these mathematical conditions, the parser can predict the correct derivation path instantly, rendering backtracking completely unnecessary.