Syntax Analysis and Parsing Questions and Answers

Answer: A

Correct answer: decide whether the token stream fits the rules the language lays down

The parser takes the token stream from the scanner and determines whether it forms a sentence of the language, building a parse tree or its equivalent as it goes. Grouping characters into lexemes is the scanner’s job, type compatibility belongs to semantic analysis, and instruction selection to the back end.

Answer: B

Correct answer: terminals, nonterminals, a start symbol and a set of productions

These four are the whole definition. The terminals are the tokens the scanner supplies, the nonterminals name the syntactic categories, the productions say how each nonterminal may be expanded, and the start symbol names the category a whole program belongs to. Nothing else is needed to define the language.

Answer: C

Correct answer: a single nonterminal symbol

This restriction is what makes the grammar context free: a nonterminal may be replaced by its right side wherever it occurs, without regard to what surrounds it. Allowing a string on the left would give a context sensitive grammar, for which no efficient general parsing algorithm exists.

Answer: D

Correct answer: a sequence of replacements of nonterminals by production right sides

A derivation starts from the start symbol and repeatedly replaces some nonterminal by the right side of one of its productions until only terminals remain. It is a process; the parse tree is the structure that process produces, and many derivations differing only in the order of expansion give the same tree.

Answer: A

Correct answer: the leftmost nonterminal in the current sentential form

Fixing the order removes the freedom that makes derivations differ without meaning anything. A leftmost derivation always expands the leftmost nonterminal, a rightmost derivation the rightmost, and each corresponds one-to-one with a parse tree - which is why ambiguity is defined on trees rather than on derivations.

Answer: B

Both are true and the reason gives the mechanism, and this is why the handle is always the leftmost complete right side. Reversing the sequence of reductions yields a rightmost derivation of the input from the start symbol.

Answer: C

Correct answer: any string derivable from the start symbol of the grammar

A sentential form is any intermediate stage of a derivation, and so may contain both terminals and nonterminals. When it contains terminals only it is a sentence of the language. The distinction matters because parsing works through sentential forms, and each step must take one to another.

Answer: D

Correct answer: does not record the order in which the nonterminals were expanded

The parse tree captures the structure and discards the sequence, so the leftmost and rightmost derivations of one sentence produce the same tree. That is precisely what makes the tree the right object: the order of expansion is an artefact of the derivation process, while the structure is what the sentence means.

Answer: A

Correct answer: some sentence of its language has more than one parse tree

Ambiguity is a property of the grammar rather than of the language: it means one sentence can be given two different structures, so the grammar does not determine the meaning. Recursion and multi-symbol right sides are ordinary and harmless; it is the existence of a second tree for one sentence that is the fault.

Answer: B

Correct answer: an else can be attached to either of two enclosing if statements

With a grammar that allows an if without an else, the sentence with two ifs and one else has two parse trees: the else may belong to either. Languages resolve it by rule - the else matches the nearest unmatched if - and grammars encode that by splitting the statement nonterminal into matched and unmatched forms.