¿Cuáles son las principales ventajas y desventajas del análisis LL y LR?

Al construir un analizador sintáctico para un lenguaje de programación, ¿qué gano y qué pierdo al elegir uno u otro?

Contrastaré el análisis de LL y LR para varios criterios:

Complejidad

LL gana aquí, sin duda. Puede escribir a mano fácilmente un analizador LL. De hecho, esto se hace comúnmente: el compilador de Microsoft C # es un analizador de descenso recursivo escrito a mano (fuente aquí , busque un comentario hecho por Patrick Kristiansen - la publicación del blog también es muy interesante).

El análisis LR utiliza un método bastante intuitivo para analizar un texto. Funciona, pero me llevó algo de tiempo entender cómo funciona exactamente. Por lo tanto, escribir tal analizador a mano es difícil: estaría más o menos implementando un generador de analizador LR.

Generalidad

LR gana aquí: todos los idiomas LL son idiomas LR, pero hay más idiomas LR que idiomas LL (un idioma es un lenguaje LL si se puede analizar con un analizador LL, y un idioma es un idioma LR si se puede analizar con un analizador LR).

LL tiene bastantes molestias que lo molestarán cuando implemente casi cualquier lenguaje de programación. Consulte aquí para obtener una descripción general.

Hay idiomas inequívocos que no son idiomas LR, pero son bastante raros. Casi nunca te encuentras con esos idiomas. Sin embargo, LALR tiene algunos problemas.

LALR es más o menos un truco para que los analizadores LR reduzcan las tablas. Las tablas para un analizador LR generalmente pueden crecer enormemente. Los analizadores LALR renuncian a la capacidad de analizar todos los idiomas LR a cambio de tablas más pequeñas. La mayoría de los analizadores LR en realidad usan LALR (aunque no en secreto, generalmente puedes encontrar exactamente lo que implementa).

LALR puede quejarse de conflictos de reducción de turnos y reducción de reducción. Esto es causado por el hack de la tabla: 'pliega' entradas similares juntas, lo que funciona porque la mayoría de las entradas están vacías, pero cuando no están vacías genera un conflicto. Este tipo de errores no son naturales, difíciles de entender y las soluciones suelen ser bastante extrañas.

Errores del compilador y recuperación de errores

LL gana aquí. En un análisis LL, generalmente es bastante fácil emitir errores útiles del compilador, en particular en analizadores escritos a mano. Usted sabe lo que espera después, por lo que si no aparece, generalmente sabe qué salió mal y cuál sería el error más sensato.

Además, en el análisis LL, la recuperación de errores es mucho más fácil. Si una entrada no se analiza correctamente, puede intentar saltar un poco hacia adelante y averiguar si el resto de la entrada se analiza correctamente. Si, por ejemplo, alguna declaración de programación tiene un formato incorrecto, puede omitir y analizar la siguiente declaración, para que pueda detectar más de un error.

Usar un analizador LR es mucho más difícil. Puede intentar aumentar su gramática para que acepte entradas erróneas e imprima errores en las áreas donde las cosas salieron mal, pero esto generalmente es bastante difícil de hacer. La posibilidad de que termines con una gramática no LR (o no LALR) también aumenta.

Velocidad

La velocidad no es realmente un problema con la forma en que analiza su entrada (LL o LR), sino más bien con la calidad del código resultante y el uso de tablas (puede usar tablas para LL y LR). LL y LR son por lo tanto comparables a este respecto.

Campo de golf

Aquí hay un enlace a un sitio que también contrasta LL y LR. Busque la sección cerca de la parte inferior.

Aquí puedes encontrar una conversación sobre las diferencias. Sin embargo, no es una mala idea mirar críticamente las opiniones expresadas allí, hay un poco de guerra santa allí.

Para obtener más información, aquí y aquí hay dos de mis propias publicaciones sobre analizadores, aunque no se trata estrictamente del contraste entre LL y LR.