A match procedure in a recursive descent parser
Answer: C
Correct answer: checks the lookahead against an expected terminal and advances
The match procedure is the single point at which input is consumed: it compares the current token with the terminal the grammar requires, advances if they agree, and reports an error if they do not. Every terminal in every right side becomes a call to it.
Please log in or register to report this question.
Optional constructs in a grammar are handled in recursive descent by
Answer: D
A simple conditional on the lookahead decides whether to parse the optional part. This is the direct code equivalent of an epsilon production in the grammar. Optional constructs are therefore among the easiest cases to write by hand.
Please log in or register to report this question.
Repetition such as a list of statements is handled in recursive descent by
Answer: A
A while loop on the FIRST set is both clearer and shallower than recursion. It is also why extended notation with explicit repetition maps so naturally onto recursive descent. Many language definitions are published in that notation for exactly this reason.
Please log in or register to report this question.
Extended BNF notation with repetition and option operators is convenient for recursive descent because
Answer: B
Braces become loops and brackets become conditionals almost mechanically. The notation also avoids the auxiliary nonterminals that left recursion removal would otherwise introduce. The grammar stays readable and the code stays close to it.
Please log in or register to report this question.
State whether the following is true or false.
A predictive parser can be built for any unambiguous context free grammar.
Answer: C
Unambiguity is necessary but not sufficient. Many unambiguous grammars are not LL(1), and some languages have no LL(1) grammar at all, which is why the LR family exists. Testing a grammar for the property is mechanical once the sets are computed.
Please log in or register to report this question.
A language for which no LL(1) grammar exists can still be parsed by
Answer: D
LR methods postpone the decision until the end of a construct and so cover a strictly larger class. This is the main practical reason bottom up generators dominate. Language designers rarely constrain their syntax to fit the smaller class.
Please log in or register to report this question.
The relationship between the LL(1) and LR(1) grammar classes is that
Answer: A
Deciding early is a stronger requirement than deciding late, so LL(1) is the smaller class. Any grammar an LL(1) parser handles can also be handled by an LR(1) parser. The converse fails for many perfectly ordinary language grammars.
Please log in or register to report this question.
A parser that must choose between a declaration and an expression on seeing an identifier illustrates
Answer: B
Correct answer: a construct requiring more than one token of lookahead
Seeing an identifier, the parser cannot tell a declaration from an expression statement until it has looked further ahead. This is a genuine LL(1) failure and is resolved either by more lookahead, by backtracking, or by consulting the symbol table - the difficulty being real rather than an artefact of the grammar.
Please log in or register to report this question.
Consulting the symbol table during parsing to decide between two productions is
Answer: C
Correct answer: a pragmatic departure from pure context free parsing
Using the symbol table means the parser’s decisions depend on what has been declared, which is context-sensitive information a context free grammar cannot express. It is nonetheless standard practice in C and C++ compilers, where a name’s being a typedef changes how the following text parses.
Please log in or register to report this question.
A single token of lookahead is insufficient for a grammar in which
Answer: D
Left factoring fixes this when the shared prefix is a fixed string of symbols. When the shared prefix can be arbitrarily long, no amount of factoring makes the grammar LL(1). Such constructs are exactly where the top down approach reaches its limit.
Please log in or register to report this question.
