Top Down Parsing Questions and Answers

Q: Which one of the following grammars is free from left recursion?

The grammar free from left recursion is S → Ab | Bb | c; A → Bd | ε; B → e.A grammar is left-recursive if some nonterminal can derive a string starting with itself. In this grammar, S begins with A, B or c; A begins with B or is empty; B begins with the terminal e. No chain returns to the nonterminal it started from, so there is no left recursion.The others are left-recursive. S → AB; A → Aa | b has direct left recursion in A → Aa. In S → Aa | B; A → Bb | Sc | ε, S ⇒ Aa ⇒ Sca, indirect left recursion through A. In S → Aa | Bb | c; A → Bd | ε; B → Ae | ε, A ⇒ Bd ⇒ Aed, indirect left recursion between A and B.

Q: Consider the following context-free grammar where the start symbol is $S$ and the set of terminals is $\{a,b,c,d\}$.$S \to AaAb \mid BbBa$$A \to cS \mid \epsilon$$B \to dS \mid \epsilon$The following is a partially-filled LL(1) parsing table.$a$$b$$c$$d$$$S$$S \to AaAb$$S \to BbBa$(1)(2)$A$$A \to \epsilon$(3)$A \to cS$$B$(4)$B \to \epsilon$$B \to dS$Which one of the following options represents the CORRECT combination for the numbered cells in the parsing table?Note: In the options, "blank" denotes that the corresponding cell is empty.

The correct combination is (1) $S \to AaAb$, (2) $S \to BbBa$, (3) $A \to \epsilon$, (4) $B \to \epsilon$.FIRST sets decide the S row. $AaAb$ can begin with c (from $A \to cS$) or, with A empty, with a, so FIRST$(AaAb) = \{a, c\}$; likewise FIRST$(BbBa) = \{b, d\}$. So cell (1), under c, holds $S \to AaAb$ and cell (2), under d, holds $S \to BbBa$.An $\epsilon$-production goes under every terminal in the FOLLOW set. In $S \to AaAb$, A is followed by a and by b, so FOLLOW$(A) = \{a, b\}$ and cell (3), under b, is $A \to \epsilon$. In $S \to BbBa$, B is followed by b and by a, so cell (4), under a, is $B \to \epsilon$.The options swapping (1) and (2) mix up the FIRST sets, and leaving (3) and (4) blank ignores the FOLLOW sets.

Q: Which of the following are correct statements in context of compiler ?(i) A grammar is Left Recursive if we can find some non-terminal ‘A’ which will eventually derive a sentential form with itself as a left symbol.(ii) Syntax analyzer groups the tokens produced by the scanner into syntactic structures by parsing the expressions and statements.(iii) A control flow statement is an instruction when executed can cause a change in the subsequent control flow to differ from the natural sequential order in which the instructions are listed.

All three statements are correct, so the answer is (i), (ii) and (iii) only.(i) A grammar is left recursive if some non-terminal A can derive, in one or more steps, a sentential form beginning with A itself (A ⇒+ Aα); such grammars must be rewritten before top-down parsing.(ii) The syntax analyser (parser) takes the tokens produced by the lexical analyser, the scanner, and groups them into syntactic structures such as expressions and statements, usually a parse tree.(iii) A control flow statement, such as a branch, loop or call, is one whose execution can make the next instruction executed differ from the next one listed.Since every statement is true, the options naming only two of them are incomplete.

Q: LL(1) parsing uses an explicit ............. rather than recursive calls to perform a parse.

LL(1) parsing uses an explicit Stack.A table-driven predictive (LL(1)) parser keeps the grammar symbols still to be matched on an explicit stack. At each step it looks at the top of the stack and the next input token, consults the parsing table, and either matches a terminal or replaces a nonterminal by the right side of a production.A recursive-descent parser does the same job using the program's own call stack through recursive procedures; the table-driven version makes that stack explicit. A deque, queue or linked list is not the structure it relies on.

Q: Consider the grammar G with productions S→ACB/CbB/Ba, A→da/BC, B→g/∈ C → h/∈Which of the following is correct set for FIRST (S) ?

FIRST(S) is {g, d, a, b, h, ∈}, with ∈ standing for the empty string.First the simple sets: FIRST(B) = {g, ∈} and FIRST(C) = {h, ∈}. For A → da | BC, FIRST(A) = {d} plus FIRST(BC) = {g, h, ∈}, since both B and C can vanish.S → ACB: FIRST(A) gives d, g, h; as A, C and B can all be empty, ∈ is also in.S → CbB: h from C, and since C can be empty, b.S → Ba: g from B, and since B can be empty, a.Together: {g, d, a, b, h, ∈}. Options A, B and C each leave out at least one of these symbols; A, for instance, misses d and ∈.

81.

Which one of the following grammars is free from left recursion?

A.S → AB; A → Aa | b; B → c
B.S → Ab | Bb | c; A → Bd | ε; B → e
C.S → Aa | B; A → Bb | Sc | ε; B → d
D.S → Aa | Bb | c; A → Bd | ε; B → Ae | ε

Exam Year(s)

GATE CS - 2016,

Answer: B

The grammar free from left recursion is S → Ab | Bb | c; A → Bd | ε; B → e.

A grammar is left-recursive if some nonterminal can derive a string starting with itself. In this grammar, S begins with A, B or c; A begins with B or is empty; B begins with the terminal e. No chain returns to the nonterminal it started from, so there is no left recursion.

Discuss in Forum

82.

Consider the following context-free grammar where the start symbol is $S$ and the set of terminals is $\{a,b,c,d\}$.

$S \to AaAb \mid BbBa$
$A \to cS \mid \epsilon$
$B \to dS \mid \epsilon$

The following is a partially-filled LL(1) parsing table.

	$a$	$b$	$c$	$d$
$S$	$S \to AaAb$	$S \to BbBa$	(1)	(2)
$A$	$A \to \epsilon$	(3)	$A \to cS$
$B$	(4)	$B \to \epsilon$		$B \to dS$

Which one of the following options represents the CORRECT combination for the numbered cells in the parsing table?

Note: In the options, "blank" denotes that the corresponding cell is empty.

A.(1) $S \to AaAb$ (2) $S \to BbBa$ (3) $A \to \epsilon$ (4) $B \to \epsilon$
B.(1) $S \to BbBa$ (2) $S \to AaAb$ (3) $A \to \epsilon$ (4) $B \to \epsilon$
C.(1) $S \to AaAb$ (2) $S \to BbBa$ (3) blank (4) blank
D.(1) $S \to BbBa$ (2) $S \to AaAb$ (3) blank (4) blank

Exam Year(s)

GATE CS - 2024,

Answer: A

The correct combination is (1) $S \to AaAb$, (2) $S \to BbBa$, (3) $A \to \epsilon$, (4) $B \to \epsilon$.

FIRST sets decide the S row. $AaAb$ can begin with c (from $A \to cS$) or, with A empty, with a, so FIRST$(AaAb) = \{a, c\}$; likewise FIRST$(BbBa) = \{b, d\}$. So cell (1), under c, holds $S \to AaAb$ and cell (2), under d, holds $S \to BbBa$.

An $\epsilon$-production goes under every terminal in the FOLLOW set. In $S \to AaAb$, A is followed by a and by b, so FOLLOW$(A) = \{a, b\}$ and cell (3), under b, is $A \to \epsilon$. In $S \to BbBa$, B is followed by b and by a, so cell (4), under a, is $B \to \epsilon$.

The options swapping (1) and (2) mix up the FIRST sets, and leaving (3) and (4) blank ignores the FOLLOW sets.

Discuss in Forum

83.

Which of the following are correct statements in context of compiler ?

(i) A grammar is Left Recursive if we can find some non-terminal ‘A’ which will eventually derive a sentential form with itself as a left symbol.
(ii) Syntax analyzer groups the tokens produced by the scanner into syntactic structures by parsing the expressions and statements.
(iii) A control flow statement is an instruction when executed can cause a change in the subsequent control flow to differ from the natural sequential order in which the instructions are listed.

A.(i) and (ii) only
B.(ii) and (iii) only
C.(i), (ii) and (iii) only
D.(i) and (iii) only

Exam Year(s)

MH SET - 2019, SET Exam - 2019,

Answer: C

All three statements are correct, so the answer is (i), (ii) and (iii) only.

(i) A grammar is left recursive if some non-terminal A can derive, in one or more steps, a sentential form beginning with A itself (A ⇒+ Aα); such grammars must be rewritten before top-down parsing.

(ii) The syntax analyser (parser) takes the tokens produced by the lexical analyser, the scanner, and groups them into syntactic structures such as expressions and statements, usually a parse tree.

(iii) A control flow statement, such as a branch, loop or call, is one whose execution can make the next instruction executed differ from the next one listed.

Since every statement is true, the options naming only two of them are incomplete.

Discuss in Forum

84.

LL(1) parsing uses an explicit ............. rather than recursive calls to perform a parse.

A.Deque
B.Stack
C.Queue
D.Linked List

Exam Year(s)

MH SET - 2021, SET Exam - 2021,

Answer: B

LL(1) parsing uses an explicit Stack.

A table-driven predictive (LL(1)) parser keeps the grammar symbols still to be matched on an explicit stack. At each step it looks at the top of the stack and the next input token, consults the parsing table, and either matches a terminal or replaces a nonterminal by the right side of a production.

A recursive-descent parser does the same job using the program's own call stack through recursive procedures; the table-driven version makes that stack explicit. A deque, queue or linked list is not the structure it relies on.

Discuss in Forum

85.

Consider the grammar G with productions S→ACB/CbB/Ba, A→da/BC, B→g/∈ C → h/∈

Which of the following is correct set for FIRST (S) ?

A.{a, b, h, g}
B.{a, d, g, ∈}
C.{g, d, b, h, ∈}
D.{g, d, a, b, h, ∈}

Exam Year(s)

MH SET - 2023, SET Exam - 2023,

Answer: D

FIRST(S) is {g, d, a, b, h, ∈}, with ∈ standing for the empty string.

First the simple sets: FIRST(B) = {g, ∈} and FIRST(C) = {h, ∈}. For A → da | BC, FIRST(A) = {d} plus FIRST(BC) = {g, h, ∈}, since both B and C can vanish.

S → ACB: FIRST(A) gives d, g, h; as A, C and B can all be empty, ∈ is also in.
S → CbB: h from C, and since C can be empty, b.
S → Ba: g from B, and since B can be empty, a.

Together: {g, d, a, b, h, ∈}. Options A, B and C each leave out at least one of these symbols; A, for instance, misses d and ∈.

Discuss in Forum

86.

Which of the following is true while converting CFG to LL(I) grammar ?

A.Remove left recursion alone
B.Factoring grammar alone
C.Both of the above
D.None of the above

Exam Year(s)

UGC NET - 2012,

Answer: C

To convert a context-free grammar to an LL(1) grammar both steps are needed: removing left recursion and factoring the grammar (left factoring). A left-recursive grammar makes a top-down parser loop for ever, and common prefixes in alternatives stop it from choosing a production with one symbol of look-ahead.

So 'Remove left recursion alone' and 'Factoring grammar alone' are each incomplete, and the key accepts 'Both of the above'. Even after both, the grammar must still be checked, because the conversion is not always possible.

Discuss in Forum

87.

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

A.Leftmost derivation
B.Leftmost derivation traced out in reverse
C.Rightmost derivation traced out in reverse
D.Rightmost derivation

Exam Year(s)

UGC NET - 2013,

Answer: A

A top-down parser builds the parse tree from the root and, scanning the input from left to right, uses a leftmost derivation. At each step it expands the leftmost non-terminal, which matches the input order.

Bottom-up (shift-reduce) parsers trace out a rightmost derivation in reverse. The options mentioning the reverse of a leftmost derivation or a plain rightmost derivation therefore describe other parsing approaches and do not suit a top-down parser.

Discuss in Forum

88.

The equivalent production rules corresponding to the production rules S → Sα1 |Sα2 | β1 | β2 is

A.S → β1 | β2, A → α1A | α2A | λ
B.S → β1| β2| β1A | β2A, A → α1A | α2A
C.S → β1 | β2, A → α1A | α2A
D.S → β1 | β2 | β1A | β2A, A → α1A | α2A | λ

Exam Year(s)

UGC NET - 2013,

Answer: D

Removing the immediate left recursion from S -> S a1 | S a2 | b1 | b2 gives S -> b1 | b2 | b1 A | b2 A with A -> a1 A | a2 A | lambda, option (D). Every string derived from the original begins with b1 or b2 followed by any number of a1 or a2, and the new rules produce the same: S gives b1 or b2 and may continue with A, and A produces a1 or a2 repeatedly and stops through lambda. Option (A) has no rule that reaches A from S, so it only gives b1 and b2. Options (B) and (C) have no way to stop the A-recursion, since A has no terminating alternative, so A derives nothing and only the b1 and b2 strings are generated. Only (D) is equivalent.

Discuss in Forum

89.

Which is the correct statement(s) for Non Recursive predictive parser ? S1 : First(α) = {t| α $\Rightarrow^{*}$ tβ for some string β} $\Rightarrow^{*}$ tβ S2 : Follow(X)={ a| S$\Rightarrow^{*}$αXaβ for some strings α and β}

A.Both statements S1 and S2 are incorrect.
B.S1 is incorrect and S2 is correct.
C.S1 is correct and S2 is incorrect.
D.Both statements S1 and S2 are correct.

Exam Year(s)

UGC NET - 2013,

Answer: D

Both statements are correct, option (D). For a non-recursive predictive parser, First(alpha) is the set of terminals t such that alpha derives a string beginning with t, that is alpha =>* t beta for some string beta, and this is S1. Follow(X) is the set of terminals a that can appear immediately to the right of X in some sentential form, that is S =>* alpha X a beta for some strings alpha and beta, and this is S2. Both are the standard definitions used to build the parsing table, so the options that call either statement incorrect, (A), (B) and (C), are wrong.

Discuss in Forum

Loading…

Topics

Other Subjects

Tags: Top Down Parsing Questions and Answers || Top Down Parsing MCQ Questions and Answers || Top Down Parsing GK Questions and Answers || Top Down Parsing GK MCQ Questions || Top Down Parsing Multiple Choice Questions and Answers || Top Down Parsing GK || GK on Top Down Parsing || Compiler Design Questions and Answers || Compiler Design MCQ Questions and Answers || Compiler Design GK Questions and Answers || GK on Compiler Design

	\(a\)	\(b\)	\(c\)	\(d\)
\(S\)	\(S \to AaAb\)	\(S \to BbBa\)	(1)	(2)
\(A\)	\(A \to \epsilon\)	(3)	\(A \to cS\)
\(B\)	(4)	\(B \to \epsilon\)		\(B \to dS\)

Top Down Parsing Questions and Answers

Topics

Other Subjects

About Us

Stay informed about all important Dates & Notifications