Top Down Parsing Questions and Answers

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.

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.

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.

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.

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.