Top Down Parsing Questions and Answers

Answer: A

Each production contributes entries only for the terminals in its FIRST set. The sparsity is what makes compressed representations attractive for large grammars. A grammar with many terminals produces a table that is almost entirely empty.

Answer: B

The dependencies can be cyclic, so a single pass may miss contributions. Repeating until a fixed point is reached is the standard way to solve such a system of set equations. The same fixed point technique reappears later in data flow analysis.

Answer: C

Whatever follows a nonterminal contributes its FIRST set to that nonterminal's FOLLOW. The dependency runs one way only, which fixes the order in which the two must be computed. Attempting the reverse order produces sets that are silently incomplete.

Answer: D

Correct answer: add FOLLOW of the left side nonterminal to the FOLLOW of that symbol

If everything after a symbol in a right side can vanish, then whatever may follow the left side may follow that symbol too. This propagation rule is what makes FOLLOW computation iterative, since adding to one FOLLOW set may require additions to others until nothing changes.

Answer: A

The first three all build the tree from the root down. Shift reduce parsing constructs the tree from the leaves upward and belongs to the bottom up family. The direction of construction is the defining difference between the families.

Answer: B

Correct answer: the correspondence between the grammar and the code is direct

A recursive descent parser can be read alongside its grammar, so the mechanics of parsing are visible rather than hidden in a table. That transparency makes it the natural first method, and it prepares the ground for tables by making clear what a table is doing.

Answer: C

Correct answer: an abstract syntax tree returned by each parsing procedure

Each procedure recognises one construct, so it is the natural place to build the node for that construct from the nodes its callees return. The tree is assembled bottom up as the recursion unwinds, and no separate tree-building pass is needed.

Answer: D

Correct answer: directly in the code of the parsing procedures

Actions sit in the procedure at the point where the corresponding part of the construct has been recognised, so there is no separate mechanism at all - the parser and the translator are the same code. This freedom is one of the practical attractions of writing the parser by hand.

Answer: A

Host stacks are finite, so deeply nested input can exhaust them. Table driven parsers use a heap allocated stack and are limited only by available memory. Compilers therefore often impose a documented limit on nesting depth.

Answer: B

Linear time and freedom from left recursion both hold. The third overstates the power of the method, since many unambiguous grammars need more lookahead or a bottom up approach. Unambiguity is a property of the language description, not of parsing difficulty.