Bottom Up Parsing Questions and Answers

Answer: A

Natural language grammars and a few awkward programming language constructs defeat a single deterministic table. The generalised mode explores the alternatives and discards those that fail, at the cost of the linear time guarantee the ordinary table provides.

Answer: B

Actions run at reduction time, when the values of the right side symbols are available on the value stack. Mid-rule actions are possible but split the production internally. Splitting can introduce conflicts that were absent before the action was added.

Answer: C

Correct answer: the dollar sign written twice

The value of the whole production - that is, of the left hand side - is written $$, while $1, $2 and so on refer to the symbols of the right side in order. The typical action for a binary operator assigns to $$ a value computed from $1 and $3, with $2 being the operator token itself.

Answer: D

Correct answer: introducing an anonymous nonterminal deriving epsilon

An action in the middle of a rule needs a reduction to trigger it, so the generator invents a nonterminal deriving nothing, places it at that point, and attaches the action to its reduction. The cost is that this extra nonterminal can introduce conflicts into a grammar that was otherwise clean.

Answer: A

Every push onto the parsing stack has a corresponding value. A reduction combines the values of the right side into a value for the left side, which is how attributes flow upward. The value stack is popped and pushed in step with the parsing stack.

Answer: B

Correct answer: the value of a left side is computed from those of its right side

A synthesised attribute flows upward, and a bottom up parser reduces a right side only once all its symbols are complete - so their values are already on the value stack when the action runs. The fit is exact, which is why Yacc-style tools support synthesised attributes with no machinery beyond the value stack.

Answer: C

Correct answer: the parent is not created until after its children are complete

An inherited attribute passes information from a parent or a left sibling down into a subtree, but a bottom up parser reduces the children first and creates the parent only afterwards. There is nothing to inherit from at the time it would be needed, so such attributes require marker nonterminals or values reached at known depths in the stack.

Answer: D

Correct answer: force a reduction at a chosen point so an action can run there

Because actions run only on reductions, an action needed part way through a production has nowhere to attach. A marker deriving epsilon supplies a reduction at exactly that point, which is both how mid-rule actions are implemented and how inherited attributes can be made available part way along a rule.

Answer: A

Correct answer: True

Every LL(1) grammar is LR(1) and in fact LALR(1), so the LR family strictly contains what recursive descent with one token of lookahead can handle. The converse fails badly: LR grammars may be left recursive and need no left factoring, which is the practical reason generated bottom up parsers accept grammars written the natural way.

Answer: B

Deciding after the whole right side has been seen is a weaker requirement than deciding at the start. Error messages and hand implementation are generally worse, not better. Coverage is what settles the choice for most parser generator users.