Bottom Up Parsing Questions and Answers

Answer: C

Correct answer: True

LR parsing is incremental: actions run as reductions occur, so a translator can emit code, build tree fragments or write output long before the end of the input is reached. This is what makes single-pass compilation possible and why an LR parser can be used on a stream.

Answer: D

The parser may shift several times in a row or reduce several times in a row. There is no required alternation, and the counts of the two actions are generally different. The shift count equals the token count while the reduction count does not.

Answer: A

Every token is shifted exactly once, so ten shifts occur. The number of reductions depends on the grammar and is unrelated to the token count in any simple way. A grammar full of unit productions performs many more reductions than shifts.

Answer: B

Correct answer: reduces the augmented start production with the input exhausted

The grammar is augmented with a production from a new start symbol to the original one precisely so that acceptance has a definite marker: reducing that production with the end-of-input marker as lookahead is the accept action. An empty stack or a merely exhausted input is not the test.

Answer: C

Nothing in the grammar constrains what may be combined with what. An expression joining a string to the name of a function reduces without any complaint at all, and only the type checker holds the information needed to object to it. Form and meaning are separate questions, settled by separate phases of the compiler.

Answer: D

Correct answer: less specific, since the table knows states rather than constructs

A recursive descent parser fails inside a procedure named for the construct it was parsing, so it can say what it expected in the language’s own terms. An LR parser knows only that state 147 had no action on this token, and turning that into a message about a missing semicolon requires deliberate extra work.

Answer: A

Coverage and table size together are what settled the matter. Diagnostics are a known weakness, addressed by error productions rather than by the parsing method itself. A carefully written set of error rules narrows the gap considerably.