# Language theoretic comparison of LL and LR grammars

People often say that LR(k) parsers are more powerful than LL(k) parsers. These statements are vague most of the time; in particular, should we compare the classes for a fixed $k$ or the union over all $k$? So how is the situation really? In particular, I am interested in how LL(*) fits in.

As far as I know, the respective sets of grammars LL and LR parsers accept are orthogonal, so let us talk about the languages generated by the respective sets of grammars. Let $LR(k)$ denote the class of languages generated by grammars that can be parsed by an $LR(k)$ parser, and similar for other classes.

I am interested in the following relations:

• $LL(k) \overset{?}{\subseteq} LR(k)$
• $\bigcup_{i=1}^{\infty} LL(k) \overset{?}{\subseteq} \bigcup_{i=1}^{\infty} LR(k)$
• $\bigcup_{i=1}^{\infty} LL(k) \overset{?}{=} LL(*)$
• $LL(*) \overset{?}{\circ} \bigcup_{i=1}^{\infty} LR(k)$

Some of these are probably easy; my goal is to collect a "complete" comparison. References are appreciated.

-
Maybe this can help you! Grammar Hierarchy image – Andrea Tucci Jul 11 '12 at 15:32
@AndreaTucci: Yes, but that only covers the grammars, not the generated languages. – Raphael Jul 11 '12 at 18:06

There are numerous containments known. Let $\subseteq$ denote containment and $\subset$ proper containment. Let $\times$ denote incomparability.

Let $LL = \bigcup_k LL(k)$, $LR = \bigcup_k LR(k)$.

## Grammar level

### For LL

• $LL(0) \subset LL(1) \subset LL(2) \subset LL(2) \subset \cdots \subset LL(k) \subset \cdots \subset LL \subset LL(*)$
• $SLL(1) = LL(1), SLL(k) \subset LL(k), SLL(k+1) \times LL(k)$

Most of these are proven in Properties of deterministic top down grammars by Rosenkrantz and Stearns. $SLL(k+1) \times LL(k)$ is a rather trivial exercise. This presentation by Terence Parr places $LL(*)$ on slide 13. The paper LL-regular grammars by Jarzabek and Krawczyk show $LL \subset LLR$, and their proof trivially extends to $LL \subset LL(*)$

### For LR

• $LR(0) \subset SLR(1) \subset LALR(1) \subset LR(1)$
• $SLR(k) \subset LALR(k) \subset LR(k)$
• $SLR(1) \subset SLR(2) \subset \cdots \subset SLR(k)$
• $LALR(1) \subset LALR(2) \subset \cdots \subset LALR(k)$
• $LR(0) \subset LR(1) \subset LR(2) \subset \cdots \subset LR(k) \subset \cdots \subset LR$

These are all simple exercises.

### LL versus LR

• $LL(k) \subset LR(k)$ (Properties of deterministic top down grammars plus any left recursive grammar)
• $LL(k) \times SLR(k), LALR(k), LR(k-1)$ (simple exercise)
• $LL \subset LR$ (any left recursive grammar)
• $LL(*) \times LR$ (left recursion versus arbitrary lookahead)

## Language level

### For LL

• $LL(0) \subset LL(1) \subset LL(2) \subset \cdots \subset LL(k) \subset \cdots \subset LL \subset LL(*)$
• $SLL(k) = LL(k)$

Most of these are proven in Properties of deterministic top down grammars. The equivalence problem for LL- and LR-regular grammars by Nijholt makes references to papers showing $LL(k) \subset LL(*)$. The paper LL-regular grammars by Jarzabek and Krawczyk show $LL \subset LLR$, and their proof trivially extends to $LL \subset LL(*)$

### For LR

• $LR(0) \subset SLR(1) = LALR(1) = LR(1) = SLR(k) = LALR(k) = LR(k) = LR$

Some of these were proven by Knuth in his paper On the Translation of Languages from Left to Right in which he introduced LR(k), the rest are proven in Transforming LR(k) Grammars to LR(1), SLR(1), and (1,1) Bounded Right-Context Grammars by Mickunas et al.

### LL versus LR

• $LL \subset LR(1)$ (containment follows from the above, $\{ a^i b^j | i \geq j \}$ is the canonical example for strict containment)
• $LL(*) \times LR$ (the language $\{ a^i b^j | i \geq j \}$ shows half the claim, and the introduction of The equivalence problem for LL- and LR-regular grammars by Nijholt makes references to papers showing the other half)
-
 This is a great answer, thank you! – Raphael♦ Mar 7 '12 at 11:24 @Raphael: you're welcome. I think I covered everything you wanted to know - I could extend it to various other parsing algorithms, but it'd become quite long and I'm not sure what you'd be interested in. – Alex ten Brink Mar 7 '12 at 11:29 Jup, your answer is complete. The grammar level stuff would not have been necessary, but it is nice to have for reference. – Raphael♦ Mar 7 '12 at 11:45 The result you attribute to Knuth does not include LALR, which wasn't invented until four years later :-| – EJP Apr 11 '12 at 6:43 @EJP: correct. I noted this earlier, but didn't have the time to put in the proper reference. I've done so now. – Alex ten Brink Apr 11 '12 at 11:24