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

67

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 (*).kk

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)?LR(k)
  • i=1LL(k)?i=1LR(k)
  • i=1LL(k)=?LL()
  • LL()?i=1LR(k)

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

Rafael
fuente
2
¡Tal vez esto pueda ayudarle! Imagen de la jerarquía gramatical
Andrea Tucci
1
@AndreaTucci: Sí, pero eso solo cubre las gramáticas, no los idiomas generados.
Raphael

Respuestas:

60

×

LL=kLL(k)LR=kLR(k)

Nivel de gramática

Para LL

  • LL(0)LL(1)LL(2)LL(2)LL(k)LLLL()
  • SLL(1)=LL(1),SLL(k)LL(k),SLL(k+1)×LL(k)

SLL(k+1)×LL(k)LL()LLLLRLLLL()

Para LR

  • LR(0)SLR(1)LALR(1)LR(1)
  • SLR(k)LALR(k)LR(k)
  • SLR(1)SLR(2)SLR(k)
  • LALR(1)LALR(2)LALR(k)
  • LR(0)LR(1)LR(2)LR(k)LR

Todos estos son ejercicios simples.

LL versus LR

  • LL(k)LR(k)
  • LL(k)×SLR(k),LALR(k),LR(k1)
  • LLLR
  • LL()×LR

Nivel de idioma

Para LL

  • LL(0)LL(1)LL(2)LL(k)LLLL()
  • SLL(k)=LL(k)

LL(k)LL()LLLLRLLLL()

Para LR

  • LR(0)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

  • LLLR(1){aibj|ij}
  • LL()×LR{aibj|ij}
  • LR(1)=DCFL
Alex ten Brink
fuente
Excelente respuesta, sin embargo, ya había votado. ¿Pensé que Frank deRemer demostró LALR <= LR en su artículo original de LALR? (1969?)
usuario207421
LALR(k)LR(k)LALRLR
1
@AlextenBrink Leí el periódico y me enseñó Frank de Remer, pero hace más de 30 años ;-) Gracias por todos los detalles.
user207421
Sería bueno recopilar ejemplos de gramáticas para cada desigualdad.
2015
1
@ o11c Creo que eso sobrecargaría una sola respuesta. Mi impresión es que Alex dio buenas referencias cuando fue necesario; él dice "ejercicio fácil" para algunos. Supongo que si un lector no puede llegar a una gramática, puede publicar una nueva pregunta para ese caso específico.
Raphael