TIFR CSE 2012 | Part B | Question: 17

Question

Which of the following correctly describes $\text{LR}(k)$ parsing?

• A. The input string is alternately scanned left to right and right to left with $k$ reversals.
• B. Input string is scanned once left to right with rightmost derivation and $k$ symbol look-ahead.
• C. $\text{LR}(k)$ grammers are expressively as powerful as context-free grammers.
• D. Parser makes $k$ left-to-right passes over input string.
• E. Input string is scanned from left to right once with $k$ symbol to the right as look-ahead to give left-most derivation.

Comments

For Option C

Any $LR(k)$ grammar is equivalent to $LR(1)$ grammar, which is equivalent to DCFG

Hence, $LR(k)$ is expressively as powerful as DCFG, and not CFG as a whole.

---

Or, simply you can disprove Option C by taking an ambiguous CFG. Any ambiguous grammar can't be parsed by a parser (except Operator Precedence Parser)

Answer 1

1. Does not make any sense. false.
2. This is definition of LR($k$) Parser. True
3. False. LR($k$) is subset of CFL.
4. False.
5. LR($k$) , bottom up parser . We have Right most derivation. This is False.

Answer :- B

Comments

LR(k) grammar is unambiguous grammar where context free grammar can be ambiguous or unambiguous .Therefore LR(k) is a subset of Context free grammar.

Is it right?

---

I think option b also not fully correct  as bottom up parser use reverse of right most derivation.

---

What is the logic for right mos derivation?

Answer 2

https://www.google.co.in/?gfe_rd=cr&ei=DQY4VuOPMe_I8Aenm4GIBw#q=lr(k)+parser

Ans will be b

Comments

@srestha

Could you explain how it is B. LR(k) is left to right with rightmost derivation in reverse