Syntax Analysis and Parsing Questions and Answers

Answer: A

The conflict means the table cell holds both a shift and a reduce action. The dangling else is the classic example, and generators usually resolve it by preferring the shift. The report should still be read, since a genuine grammar error looks the same.

Answer: B

Correct answer: two different productions could be reduced at the same point

A reduce-reduce conflict means the parser has a handle on the stack but cannot tell which production it belongs to, so the grammar is not LR for the lookahead available. It usually indicates a genuine defect in the grammar rather than something to be resolved by declaration - unlike a shift-reduce conflict, which precedence rules can settle.

Answer: C

The methods differ in where they keep the parsing state. Recognising the structure a method relies on makes its strengths and limits much easier to remember. Each structure also determines how error recovery has to be implemented.

Answer: D

LR parsers postpone the decision until a whole right side has been seen, so they cope with grammars LL parsers cannot. Every LL(1) grammar is LR(1) but not conversely. The extra power is why parser generators overwhelmingly favour the LR family.

Answer: A

The L is left to right scanning and the R is rightmost derivation in reverse. The number in parentheses is always the lookahead, in both the LL and the LR families. A parser with no lookahead at all would be written LR(0) by the same convention.

Answer: B

Correct answer: no production has two adjacent nonterminals on its right side

The method works by placing precedence relations between adjacent terminals, so two nonterminals side by side leave no terminal pair to relate and the method breaks down. The restriction is met by ordinary expression grammars, which is why the technique was practical for expressions and little else.

Answer: C

The class is small and the relation table can accept strings outside the language. Its historical appeal was that a table could be built by hand for an expression grammar. Modern generators removed that motivation almost entirely.

Answer: D

Type 3 is regular, type 2 context free, type 1 context sensitive and type 0 unrestricted. Each class strictly contains the one below it in recognition power. The hierarchy explains why a compiler needs both a scanner and a parser.

Answer: A

The correspondence between grammar classes and machine models is the backbone of formal language theory and explains why scanning uses finite automata while parsing needs a stack. The extra memory of the stack is exactly what nesting demands.

Answer: B

Balanced parentheses and nested blocks demand counting to an unbounded depth. A finite automaton has no such memory, whereas the stack of a pushdown automaton supplies exactly that. This is the single clearest reason the two phases use different formalisms.