A shift-reduce conflict occurs when the parser
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.
Please log in or register to report this question.
A reduce-reduce conflict occurs when
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.
Please log in or register to report this question.
Match each parsing method with its characteristic data structure.
List I
A. recursive descent
B. table driven LL(1)
C. LR parsing
D. operator precedence
List II
1. a stack of states with a table of actions
2. the call stack of the host language
3. a table of relations between terminals
4. an explicit stack of grammar symbols
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.
Please log in or register to report this question.
The class of grammars parsed by LR methods, compared with LL methods, is
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.
Please log in or register to report this question.
In the notation LR(1), the 1 refers to
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.
Please log in or register to report this question.
Operator precedence parsing is applicable to grammars in which
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.
Please log in or register to report this question.
The principal weakness of operator precedence parsing is that
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.
Please log in or register to report this question.
The Chomsky hierarchy places context free languages
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.
Please log in or register to report this question.
Match each grammar class with the machine that recognises it.
List I
A. regular
B. context free
C. context sensitive
D. unrestricted
List II
1. linear bounded automaton
2. finite automaton
3. Turing machine
4. pushdown automaton
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.
Please log in or register to report this question.
Programming language syntax needs a context free grammar rather than a regular expression because
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.
Please log in or register to report this question.
