edited by
7,668 views
22 votes
22 votes

Which of the following derivations does a top-down parser use while parsing an input string? The input is scanned from left to right.

  1. Leftmost derivation
  2. Leftmost derivation traced out in reverse
  3. Rightmost derivation 
  4. Rightmost derivation traced out in reverse
edited by

6 Answers

1 votes
1 votes
Ans: A Leftmost derivation
0 votes
0 votes

A top-down parser, during parsing, uses a leftmost derivation of the input string. The leftmost derivation is a derivation in which the leftmost non-terminal is replaced at each step.

Explanation:

  • Leftmost Derivation: In a leftmost derivation, at each step, the leftmost non-terminal in the current sentential form is chosen for expansion. This corresponds to scanning the input string from left to right.

  • Leftmost Derivation Traced Out in Reverse: Tracing out a leftmost derivation in reverse is not a common practice during parsing.

  • Rightmost Derivation: Rightmost derivation involves replacing the rightmost non-terminal at each step. This is commonly used in bottom-up parsing.

  • Rightmost Derivation Traced Out in Reverse: Tracing out a rightmost derivation in reverse is not a common practice during parsing.

Answer:

Related questions

45 votes
45 votes
4 answers
1
15 votes
15 votes
3 answers
2
Kathleen asked Sep 14, 2014
7,916 views
Consider the syntax directed translation scheme $\textsf{(SDTS)}$ given in the following. Assume attribute evaluation with bottom-up parsing, i.e., attributes are evaluat...