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

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