CODEWITHSUNDEEP
parsingcompiler-constructionll-grammarlr-grammar
Ahmed Elbannan
Ahmed Elbannan

Reputation: 111

Relationship between LR(0), LL(0), LALR(1), etc?

I'm really struggling to unterstand the relationship between:

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

Upvotes: 9

Views: 12583

Answers (1)

templatetypedef
templatetypedef

Reputation: 373082

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.

Upvotes: 14

Related Questions