Which of the following is FALSE ?
2016
Which of the following is FALSE ?
- A.
The grammar S → a Sb |bSa|SS|∈, where S is the only non-terminal symbol and ∈ is the null string, is ambiguous.
- B.
SLR is powerful than LALR.
- C.
An LL(1) parser is a top-down parser.
- D.
YACC tool is an LALR(1) parser generator.
Attempted by 55 students.
Show answer & explanation
Correct answer: B
Correct answer: SLR is powerful than LALR. is false.
The grammar S → a S b | b S a | S S | ε is ambiguous. Reason: the production S → SS allows multiple ways to split a balanced string, yielding different parse trees. Example: the string "ab" can be derived as S → a S b → a ε b, or as S → S S with left S → a S b → a ε b and right S → ε; these are different parse trees for the same string.
The statement "SLR is powerful than LALR" is false. Reason: LALR(1) parsers retain more lookahead information (derived from LR(1) states, then merged) and can resolve some conflicts that SLR(1) cannot. SLR uses FOLLOW sets for reductions which can cause spurious conflicts; therefore LALR is at least as powerful and often strictly more powerful than SLR.
An LL(1) parser is a top-down parser. Reason: LL(1) is a predictive parser that reads input left-to-right and constructs a leftmost derivation using one-token lookahead, so this statement is true.
YACC tool is an LALR(1) parser generator. Reason: Traditional YACC constructs LALR(1) parse tables, so this statement is true.
Summary: The false statement is that SLR is more powerful than LALR; in fact, LALR is at least as powerful and typically more capable than SLR.