Syntax Analysis and Parsing Questions and Answers

Answer: C

Correct answer: from the root downward, expanding nonterminals as it goes

A top-down parser starts with the start symbol and works towards the input, choosing a production for each nonterminal and expanding it, so the tree is built from the root. A bottom-up parser does the reverse, combining tokens into larger structures until it reaches the start symbol.

Answer: D

Reductions replace a matched right side by its nonterminal, building the tree upward. The sequence of reductions traced backward gives a rightmost derivation of the input string. This correspondence is what justifies calling the method a rightmost parse.

Answer: A

Correct answer: one procedure per nonterminal, called as the grammar dictates

Recursive descent turns the grammar directly into code: each nonterminal becomes a procedure whose body follows its productions, calling the procedures for the nonterminals on the right side and matching the terminals. The call stack does the work a parse stack would otherwise do, which is what makes such parsers so readable.

Answer: B

Correct answer: without backtracking, the production chosen by lookahead alone

Predictive parsing is recursive descent with the guarantee that the lookahead always determines which production to use, so no alternative ever has to be abandoned and retried. The grammar must be LL(1) for that guarantee to hold, which is why left recursion is eliminated and left factoring applied first.

Answer: C

Correct answer: it can take exponential time and undoes semantic actions already run

Backtracking may explore many alternatives before finding the right one, and the cost can grow exponentially with the input. Worse for a practical compiler, any semantic action already executed - a symbol table entry, a line of output - must be undone, which is difficult to do correctly and is why predictive parsing is preferred.

Answer: D

Correct answer: grammar symbols still to be matched or expanded

The stack of a predictive parser holds what the parser still expects to see. A terminal on top is matched against the input and popped; a nonterminal is replaced by the right side of the production the table selects. It is a direct simulation of the recursive descent call stack without the recursion.

Answer: A

The table is indexed by nonterminal and lookahead terminal. Two productions in one cell is exactly the LL(1) conflict that makes the grammar unsuitable for predictive parsing. Such a conflict usually points at a common prefix or at left recursion.

Answer: B

The table is indexed by nonterminal and by terminal including the end marker, giving 6 times 10 which is 60 cells. Most cells are error entries and only a few hold productions. Sparse representations therefore save a great deal of space in practice.

Answer: C

Shifting moves a token from the input to the stack. Reduction is the complementary action, replacing the symbols of a matched right side by the nonterminal on its left. Shifting and reducing are the only two actions a bottom-up parser ever performs.

Answer: D

Correct answer: the substring matching a right side whose reduction is the correct step

A handle is not merely something that matches a right side but one whose reduction leads towards a successful parse, so identifying handles correctly is the whole problem of bottom-up parsing. LR parsing solves it by tracking, in its state, every production of which a prefix has been seen.