Teoretyczne porównanie gramatyk LL i LR

Ludzie często mówią, że parsery LR (k) są silniejsze niż parsery LL (k) . Te stwierdzenia są przez większość czasu niejasne; w szczególności, czy powinniśmy porównać klasy dla ustalonego $k$ lub unii dla całego $k$ ? Jak więc naprawdę wygląda sytuacja? W szczególności jestem zainteresowany tym, jak pasuje LL (*).

O ile mi wiadomo, odpowiednie zestawy gramatyk, które akceptują parsery LL i LR, są ortogonalne, więc porozmawiajmy o językach generowanych przez odpowiednie zestawy gramatyk. Niech oznacza klasę języków generowanych przez gramatykę, które mogą być analizowane przez parser L R ( k ) i podobne dla innych klas.$LR(k)$$LR(k)$

Interesują mnie następujące relacje:

• $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)$

Niektóre z nich są prawdopodobnie łatwe; moim celem jest zebranie „kompletnego” porównania. Referencje są mile widziane.

Istnieje wiele znanych pojemników. Niech oznacza ograniczenie i ⊂ właściwe ograniczenie. Niech × oznacza nieporównywalność.$\subseteq$$\subset$$\times$

Niech , L R = ⋃ k L R ( k ) .$LL = \bigcup_k LL(k)$$LR = \bigcup_k LR(k)$

Poziom gramatyki

Dla 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)$

$SLL(k+1) \times LL(k)$$LL(*)$$LL \subset LLR$$LL \subset LL(*)$

Dla 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$

To są wszystkie proste ćwiczenia.

LL kontra LR

• $LL(k) \subset LR(k)$
• $LL(k) \times SLR(k), LALR(k), LR(k-1)$
• $LL \subset LR$
• $LL(*) \times LR$

Poziom języka

Dla LL

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

$LL(k) \subset LL(*)$$LL \subset LLR$$LL \subset LL(*)$

Dla LR

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

Niektóre z nich zostały udowodnione przez Knutha w jego artykule na temat tłumaczenia języków od lewej do prawej, w którym wprowadził LR (k), pozostałe zostały udowodnione w Transformacji gramatyki LR (k) do LR (1), SLR (1), oraz (1,1) Ograniczone gramatyki prawego kontekstu autorstwa Mickunas i in.

LL kontra LR

• $LL \subset LR(1)$$\{ a^i b^j | i \geq j \}$
• $LL(*) \times LR$$\{ a^i b^j | i \geq j \}$
• $LR(1) = DCFL$