Bottom Up Parsing Questions and Answers

Answer: C

Correct answer: the tables are opaque and conflicts can be hard to diagnose

LR parsing is linear in the input and handles a wide class of grammars, so the objection is not to its power. It is that a conflict is reported against a state number and an item set rather than against the language construct the author was thinking about, which makes tracing the cause a skilled exercise.

Answer: D

An iterative construct written left recursively is reduced item by item, so the stack stays short. Written right recursively the whole list must be stacked before any reduction occurs. A long initialiser list makes the difference plainly visible.

Answer: A

Both are true and the reason gives the mechanism, and the difference is measurable on long lists. Left recursion reduces after each element and keeps the stack at constant depth, which matters for generated initialiser lists and similar input.

Answer: B

Absence of conflicts is a statement about the grammar, not about whether it describes the intended language. Testing remains necessary for everything the generator cannot check. A conflict free grammar can still accept a language nobody intended.

Answer: C

The items show what the parser had seen and what it expected, which usually identifies the pair of productions in conflict. Most generators produce such a report on request. Learning to read one is among the more useful practical skills in this area.

Answer: D

Branches that fail are discarded and surviving branches may be merged. The method accepts ambiguous grammars at the cost of the linear time guarantee. Where the grammar happens to be unambiguous the extra cost is negligible.

Answer: A

Correct answer: share the common parts of several simultaneous parses

GLR pursues every viable parse at once, and a naive implementation would need a separate stack for each. The graph structured stack merges the parts the parses have in common and branches only where they differ, which keeps the work proportional to the genuine ambiguity rather than exponential in the input.

Answer: B

Because the parse is driven entirely by relations tabulated between pairs of terminals, a pair of nonterminals standing side by side offers the table nothing to look up. Arithmetic expression grammars happen to obey the restriction, which is what made the method attractive before generators were widely available.

Answer: C

The relations hold between pairs of terminals and determine where the handle begins and ends. They are not symmetric, so both orderings of a pair must be tabulated. The table is therefore quadratic in the number of terminal symbols.

Answer: D

The first three all build the tree from the leaves upward. Predictive parsing expands nonterminals from the start symbol and belongs to the top down family instead. The direction of tree construction is the defining difference.