Top Down Parsing Questions and Answers

Answer: C

The classic E goes to TE prime with E prime going to plus TE prime or epsilon is exactly the transformed form. Associativity must then be restored in the semantic actions. Forgetting that step yields an expression evaluator that groups the wrong way.

Answer: D

Correct answer: passing the partial result as an inherited attribute down the recursion

Removing left recursion leaves a right recursive grammar, which naturally groups to the right - wrong for subtraction and division. The remedy is to carry the result accumulated so far down into the recursive call as an inherited attribute, so the tree is built left-leaning even though the recursion runs the other way.

Answer: A

Never backing up is exactly the predictive discipline. It requires the grammar to be LL(1), which is what the transformations and the table construction are for. Every step of the preparation exists to make this single discipline possible.

Answer: B

Committing early is what restricts the grammar class. Bottom up methods gather the whole right side before deciding, which is why they accept strictly more grammars. Committing early is the price paid for the simplicity of the top down style.

Answer: C

Left recursion removal and factoring preserve the language but not the tree. Any actions written against the original productions must be rewritten for the transformed ones. This is one reason some authors prefer to write the parser by hand instead.

Answer: D

Correct answer: Both A and R are true, and R is the correct explanation of A

Both are true and the reason gives the mechanism. Eliminating left recursion produces a grammar deriving the same strings but building right-leaning trees where the original built left-leaning ones. The language is preserved and the structure is not, which is exactly why associativity has to be restored by other means.

Answer: A

A leading keyword makes the choice obvious from one token. Languages designed with such prefixes in mind are pleasant to parse top down, which is part of why the style is common. Expression syntax remains the awkward part and is usually handled specially.

Answer: B

Correct answer: the freedom to depart from pure context free parsing where needed

A hand-written parser can consult the symbol table, look ahead as far as it likes, and handle a construct specially when the grammar cannot. Real languages contain such constructs, and that flexibility - together with the ability to produce good error messages - is why several major compilers use recursive descent.

Answer: C

Correct answer: a tree or a sequence of semantic actions reflecting the structure

A parser establishes the structure of the input and reports it, either as a tree or as the sequence of actions a syntax-directed translation performs. The symbol table and the target code are produced by later phases working from that structure.

Answer: C

The true statement is For a grammar to be LL(1), it must be left-factored.

An LL(1) parser chooses a production by looking at one input symbol. If two alternatives of a non-terminal begin with the same prefix, their FIRST sets overlap and one symbol of lookahead cannot choose between them, so the grammar is not LL(1). Left factoring removes such common prefixes.

The other statements are false. An LL(1) parser is predictive and never backtracks. Left recursion is forbidden, not required, because it sends a top-down parser into an endless loop. And LL(1) parsers are not more powerful than SLR parsers: left-recursive grammars such as the usual expression grammar are SLR(1) but cannot be LL(1).