If a recursive descent parser encounters a construct nested a hundred thousand levels deep, the likely outcome is
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.
Please log in or register to report this question.
Consider the following statements about predictive parsing.
1. It runs in time linear in the length of the input.
2. It requires the grammar to be free of left recursion.
3. It can parse any unambiguous context free grammar.
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.
Please log in or register to report this question.
An LL(1) grammar for arithmetic expressions typically expresses repetition of the plus operator with
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.
Please log in or register to report this question.
Left associativity of the plus operator in an LL grammar is recovered by
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.
Please log in or register to report this question.
A top down parser that reads the input strictly left to right and never backs up is
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.
Please log in or register to report this question.
The chief limitation of top down parsing as a family is that
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.
Please log in or register to report this question.
Converting a grammar so that a top down parser can use it may
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.
Please log in or register to report this question.
Assertion (A): Grammar transformations for LL parsing preserve the language but not the parse trees.
Reason (R): Left recursion elimination replaces left recursion with right recursion, which leans the tree the other way.
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.
Please log in or register to report this question.
A top down parser is a natural fit for a language whose constructs are
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.
Please log in or register to report this question.
A common reason to prefer recursive descent in a production compiler is
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.
Please log in or register to report this question.
