8

I'm really struggling to unterstand the relationship between:

  • LR(0)
  • LL(0)
  • LALR(1)
  • SLR(1)
  • LR(1)
  • LL(1)

I'm pretty sure LALR(1) and SLR(1) are subsets of LR(1), but I'm lost about the others. Are they all exclusive? Is LL(0) a subset of LL(1)?

Thanks

Ahmed Elbannan
  • 101
  • 1
  • 1
  • 5
  • 1
    Please see this answer on the CompSci SE site (which is where this question should have been asked, except that it would have been marked as a duplicate): http://cs.stackexchange.com/a/48/4416 – rici Apr 15 '16 at 21:25
  • 1
    I'm voting to close this question as off-topic because it has already been answered on http://cs.stackexchange.com/ – rici Apr 15 '16 at 21:26
  • I'm voting to close this question as off-topic because it has already been answered on http://cs.stackexchange.com and because it asks for a well-documented result in parsing theory. – user207421 Jul 29 '17 at 06:18

1 Answers1

13

The containment rules are the following:

  • Every LR(0) grammar is also SLR(1), but not all SLR(1) grammars are LR(0).
  • Every SLR(1) grammar is also LALR(1), but not all LALR(1) grammars are SLR(1).
  • Every LALR(1) grammar is also LR(1), but not all LR(1) grammars are LALR(1).
  • Every LL(1) grammar is also LR(1), but not all LR(1) grammars are LL(1).
  • Every LL(0) grammar is also LR(0), SLR(1), LALR(1), LR(1), and LL(1). (LL(0) grammars are basically useless; see this question for details why).

It's also the case that every language that has an LR(1) grammar also has an LR(0) grammar provided that you endmark the grammar, though the grammar isn't guaranteed to be pretty.

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
  • sir thanks for your answer .please clear my doubt :Is LR(0) always LALR(1) ? – laura Jan 22 '18 at 17:30
  • 1
    @laura Yep, that follows from the first two inclusions. – templatetypedef Jan 22 '18 at 18:24
  • sir one last doubt ,just want to confirm that -:if there is An LALR(1) parser for a grammar G can have shift-reduce (S-R) conflicts if and only if -:option a)The LR(1) parser for G has S-R conflicts b)The LR(0) parser for G has S-R conflicts..so sir answer to this should be both ? sorry if i violated any protocol , i mean i know i have to make a new thread for this question ..but the question is indirectly related so i asked here ..sorry:) – laura Jan 22 '18 at 19:13