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

Quoting from wiki :https://en.wikipedia.org/wiki/LR_parser

 L means that the parser reads input text in one direction without backing up; that direction is typically Left to right within each line, and top to bottom across the lines of the full input file. (This is true for most parsers.) The R means that the parser produces a Rightmost derivation in reverse

Right most derivation in reverse,clearly B is not specifying this.

I think correct option is C.

@Arjun sir Please verify this./\

---

$LR(k)$ can be converted into $LR(1)$. $LR(1)$ is the same as $DCFL/DPDA$ . Here $CFL$ is given. so $LR(k)$ should be a subset of $CFL$ in terms of expressive power. 

reference 

The definition of LR(k) is Left to right scanning with Rightmost derivation in reverse with k lookaheads. 

---

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