Comparación teórica del lenguaje de gramáticas LL y LR

La gente suele decir que los analizadores LR (k) son más potentes que los analizadores LL (k) . Estas declaraciones son vagas la mayor parte del tiempo; en particular, ¿deberíamos comparar las clases para una fija o la unión sobre todas las k ? Entonces, ¿cómo es realmente la situación? En particular, estoy interesado en cómo encaja LL (*).$k$$k$

Hasta donde sé, los respectivos conjuntos de gramáticas que aceptan los analizadores LL y LR son ortogonales, así que hablemos de los lenguajes generados por los respectivos conjuntos de gramáticas. Supongamos que denota la clase de lenguajes generados por las gramáticas que pueden ser analizadas por un analizador L R ( k ) y similares para otras clases.$LR(k)$$LR(k)$

Estoy interesado en las siguientes relaciones:

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

Algunos de estos son probablemente fáciles; mi objetivo es recopilar una comparación "completa". Las referencias son apreciadas.

$\subseteq$$\subset$$\times$

$LL = \bigcup_k LL(k)$$LR = \bigcup_k LR(k)$

Nivel de gramática

Para 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(*)$

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

Todos estos son ejercicios simples.

LL versus LR

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

Nivel de idioma

Para 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(*)$

Para LR

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

Knuth probó algunos de estos en su artículo Sobre la traducción de idiomas de izquierda a derecha en el que introdujo LR (k), el resto se prueba en Transformar las gramáticas LR (k) en LR (1), SLR (1), y (1,1) Gramáticas del contexto derecho delimitadas por Mickunas et al.

LL versus 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$