Left factoring is required when two alternatives
Answer: C
A shared prefix makes the FIRST sets overlap, so one token of lookahead cannot choose. Factoring the prefix out lets the parser commit to it and postpone the choice. Several rounds of factoring may be needed when alternatives share nested prefixes.
Please log in or register to report this question.
Left factoring an if statement rule whose two alternatives differ only in a trailing else clause has the effect of
Answer: D
The shared prefix is parsed once and the optional else becomes a two way choice in the auxiliary nonterminal. Nothing is removed from the language and nothing about recursion changes; only the moment at which the parser must commit has been moved later, which is exactly what one token of lookahead requires.
Please log in or register to report this question.
State whether the following is true or false.
Left factoring and left recursion elimination together guarantee that a grammar becomes LL(1).
Answer: A
Correct answer: False
The two transformations remove two specific obstacles, but a grammar can fail the LL(1) conditions for other reasons - overlapping FIRST sets that no factoring reveals, or an inherent ambiguity. Some languages have no LL(1) grammar at all, so no sequence of transformations could produce one.
Please log in or register to report this question.
A grammar that is ambiguous can be LL(1)
Answer: B
Two parse trees for one sentence means two applicable productions at some point. That is precisely a table conflict, so ambiguity and the LL(1) property are incompatible. Removing the ambiguity is therefore the first task when a conflict appears.
Please log in or register to report this question.
The dangling else grammar is problematic for LL(1) parsing because
Answer: C
Both continuing the inner statement and returning to the outer one are possible when else is the lookahead. The usual convention attaches the else to the nearest unmatched if. Languages with an explicit end keyword sidestep the whole difficulty.
Please log in or register to report this question.
A recursive descent parser resolves the dangling else in practice by
Answer: D
Taking the else greedily in the procedure for the if statement realises the nearest if rule directly. This is one of the places where a hand written parser is simpler than a table. The greedy consumption is a single line of code in the if statement procedure.
Please log in or register to report this question.
The number of lookahead tokens used by an LL(k) parser is
Answer: A
Larger k accepts more grammars, but the table grows roughly exponentially in k. Most practical tools use one token, sometimes with special handling for a few awkward constructs. The special cases are usually documented alongside the grammar itself.
Please log in or register to report this question.
Assertion (A): LL(k) parsers for k greater than one are rare in practice.
Reason (R): The size of the parsing table grows sharply with the number of lookahead tokens.
Answer: B
Both are true and the reason gives the mechanism, and there is a further consideration. Most language constructs can be brought within one token of lookahead by modest grammar changes, so the extra machinery earns little.
Please log in or register to report this question.
ANTLR uses a parsing strategy best described as
Answer: C
Correct answer: adaptive LL with arbitrary lookahead decided at parse time
ANTLR uses ALL(*), which resolves a decision by simulating the alternatives against the actual remaining input, using as much lookahead as that particular decision needs. This accepts far more grammars than LL(1) while keeping the readability of a recursive descent parser, and it caches the decisions so the cost is paid once.
Please log in or register to report this question.
Packrat parsing achieves linear time by
Answer: D
Caching results means no position is ever parsed twice for the same rule. The linear time comes at the cost of memory proportional to input length times the number of rules. For large inputs that memory cost can be the deciding practical consideration.
Please log in or register to report this question.
