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

parsing compiler-construction ll lr
Ahmed Elbannan picture Ahmed Elbannan · Apr 15, 2016 · Viewed 10k times · Source

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

Answer

templatetypedef picture templatetypedef · Jul 7, 2016

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.

Related questions

Why are there LR(0) parsers but not LL(0) parsers?

I've been reading on both in Wikipedia, and noticed that although LR(0) parsers exist, there's no such thing as LL(0) parser. From what I read, I understand that the k in LL(k)/LR(k) means how many characters the …

Read More
Algorithm for computing FIRST and FOLLOW sets for context-free grammars

I need an algorithm to computing FIRST and FOLLOW sets for a grammar. Is there a simple algorithm or simple code for computing these?

Read More
Difference between Left Factoring and Left Recursion

What is the difference between Left Factoring and Left Recursion ? I understand that Left factoring is a predictive top down parsing technique. But I get confused when I hear these two terms.

Read More