Which of the following is true ?
2014
Which of the following is true ?
- A.
Canonical LR parser is LR (1) parser with single look ahead terminal
- B.
All LR(K) parsers with K > 1 can be transformed into LR(1) parsers.
- C.
Both (A) and (B)
- D.
None of the above
Attempted by 111 students.
Show answer & explanation
Correct answer: C
Answer: Both statements are true.
Explanation:
Canonical LR parser (CLR): A canonical LR parser is built from LR(1) items; each item carries a single lookahead terminal. The canonical collection of these LR(1) items forms the parser states, so the canonical LR parser is an LR(1) parser.
LR(k) versus LR(1): Any LR(k) grammar for a finite k can be recognized by a canonical LR(1) parser. Intuitively, the LR(1) construction can capture the needed multi-symbol lookahead information either by computing appropriate lookahead sets in LR(1) items or by simple grammar encodings, so LR(1) is as powerful as LR(k).
Brief note: Compact variants like LALR(1) merge some LR(1) states to reduce table size; this merging can reintroduce conflicts, so LALR(1) is not always as powerful as canonical LR(1).