Syntax Analysis and Parsing Questions and Answers

Answer: A

Correct answer: 2 - 4 - 1 - 3

Remove ambiguity first, since neither of the other transformations helps with it and the grammar must be unambiguous before either is worth doing. Then eliminate left recursion, which a top-down parser cannot tolerate at all. Then left factor, which removes the remaining need for lookahead beyond one token. Only then compute FIRST and FOLLOW, on the grammar that will actually be used.

Answer: B

Correct answer: the set of terminals that can begin a string derived from it

FIRST tells the parser what it may expect to see if it chooses a given production, so comparing the FIRST sets of the alternatives is how the choice is made. Epsilon is included when the string can derive nothing at all, and it is that case which brings FOLLOW into the calculation.

Answer: C

FOLLOW is needed to decide when to apply an epsilon production, since the parser must then look at what comes after A. The end marker is in FOLLOW of the start symbol by definition. Computing the sets is an iterative process repeated until nothing more changes.

Answer: D

Correct answer: 1 and 2 only

Statements 1 and 2 are correct: epsilon belongs to the FIRST set of anything that can derive the empty string, and the end of input marker belongs to the FOLLOW set of the start symbol. Statement 3 is wrong - a FOLLOW set contains terminals and the end marker, and epsilon is not something that can follow a symbol.

Answer: A

Correct answer: one token of lookahead suffices to choose the correct production

The two Ls mean scanning left to right and producing a leftmost derivation, and the 1 is the tokens of lookahead. The condition is that for each nonterminal the FIRST sets of its alternatives are disjoint, and where an alternative can be empty, that its FIRST set is disjoint from the nonterminal’s FOLLOW set.

Answer: B

Correct answer: LL(1) or LR(1), since both require a unique parsing action

Both methods build a table with one entry per state and lookahead, and ambiguity means two different actions are needed in one place, which appears as a conflict. The grammar may still be written down and may describe a real construct perfectly well - it simply cannot be parsed deterministically without being rewritten or a conflict resolution rule supplied.

Answer: C

Correct answer: LL(1), since the predictive parser would not terminate

A predictive parser expanding a left recursive nonterminal would call itself without consuming a token and never return. Left recursion is therefore fatal to LL parsing and must be eliminated first; LR parsing handles it without difficulty, and in fact prefers it. Nothing about left recursion makes a grammar ambiguous.

Answer: D

Each defect blocks a different aspect of parsing. Recognising which transformation applies is the routine first step in preparing any grammar for a parser generator. Most generators report the defect precisely enough to identify the offending rule.

Answer: A

Correct answer: derives no terminal string or is unreachable from the start symbol

Either fault makes the nonterminal contribute nothing to the language: one that derives no terminal string can never complete a derivation, and one unreachable from the start symbol can never begin one. Both are removed before parsing, since they only complicate the tables and can mask genuine errors in the grammar.

Answer: B

Top-down builds the tree from the root toward the leaves, bottom-up from the leaves toward the root. Every practical parsing algorithm belongs to one family or the other. The choice determines both the grammars accepted and the shape of the code written.