Analizador LARL
En informática , un analizador LALR o un analizador Look-Ahead LR es una versión simplificada de un analizador LR canónico , para analizar un texto de acuerdo con un conjunto de reglas de producción especificadas por una gramática formal para un lenguaje informático . ("LR" significa derivación de izquierda a derecha, más a la derecha ).
El analizador LALR fue inventado por Frank DeRemer en su tesis doctoral de 1969, Traductores prácticos para lenguajes LR(k) , en su tratamiento de las dificultades prácticas en ese momento para implementar analizadores LR(1). Demostró que el analizador LALR tiene más poder de reconocimiento de idioma que el analizador LR(0), mientras que requiere la misma cantidad de estados que el analizador LR(0) para un idioma que ambos analizadores puedan reconocer. Esto hace que el analizador LALR sea una alternativa eficiente en memoria al analizador LR(1) para lenguajes que son LALR. También se comprobó que existen lenguajes LR(1) que no son LALR. A pesar de esta debilidad, el poder del analizador LALR es suficiente para muchos lenguajes informáticos principales, incluido Java, aunque las gramáticas de referencia para muchos idiomas no son LALR debido a que son ambiguas.[1]
La disertación original no proporcionó ningún algoritmo para construir dicho analizador dada una gramática formal. Los primeros algoritmos para la generación de analizadores sintácticos LALR se publicaron en 1973. En 1982, DeRemer y Tom Pennello publicaron un algoritmo que generaba analizadores sintácticos LALR altamente eficientes en memoria. Los analizadores sintácticos LALR pueden generarse automáticamente a partir de una gramática mediante un generador de analizadores sintácticos LALR como Yacc o GNU Bison . El código generado automáticamente se puede aumentar con código escrito a mano para aumentar la potencia del analizador resultante.
Historia editar
En 1965, Donald Knuth inventó el Analizador sintáctico LR ( derivación de izquierda a derecha, más a la derecha ). El analizador LR puede reconocer cualquier lenguaje determinista libre de contexto en un tiempo lineal limitado. La derivación más a la derecha tiene requisitos de memoria muy grandes y la implementación de un analizador LR no era práctica debido a la memoria limitada de las computadoras en ese momento. Para abordar esta deficiencia, en 1969, Frank DeRemer propuso dos versiones simplificadas del analizador LR, a saber, Look-Ahead LR (LALR) y el analizador LR simple .que tenía requisitos de memoria mucho más bajos a costa de menos poder de reconocimiento de idioma, siendo el analizador LALR la alternativa más poderosa. En 1977, se inventaron las optimizaciones de memoria para el analizador LR pero aun así el analizador LR era menos eficiente en memoria que las alternativas simplificadas.
En 1979, Frank DeRemer y Tom Pennello anunciaron una serie de optimizaciones para el analizador LALR que mejorarían aún más la eficiencia de su memoria. Su trabajo fue publicado en 1982.
Resumen editar
Generalmente, el analizador LALR se refiere al analizador LALR(1), al igual que el analizador LR generalmente se refiere al analizador LR(1). El "(1)" denota una búsqueda anticipada de un token, para resolver las diferencias entre los patrones de reglas durante el análisis. De manera similar, hay un analizador LALR(2) con búsqueda anticipada de dos tokens, y analizadores LALR( k ) con búsqueda de k tokens, pero estos son raros en el uso real. El analizador LALR se basa en el analizador LR(0), por lo que también se puede denotar LALR(1) = LA(1)LR(0) (1 token de anticipación, LR(0)) o más generalmente LALR( k ) = LA( k )LR(0) (k tokens de anticipación, LR(0)). De hecho, existe una familia de dos parámetros de analizadores sintácticos LA( k )LR( j ) para todas las combinaciones de jy k , que se puede derivar del analizador LR( j + k ), pero estos no tienen un uso práctico.
Al igual que con otros tipos de analizadores LR, un analizador LALR es bastante eficiente para encontrar el único análisis de abajo hacia arriba correcto en un solo escaneo de izquierda a derecha sobre el flujo de entrada, porque no necesita usar backtracking . Al ser un analizador de búsqueda anticipada por definición, siempre utiliza una búsqueda anticipada, siendo LALR(1) el caso más común.
Relación con otros analizadores editar
Analizadores LR editar
El analizador LALR(1) es menos poderoso que el analizador LR(1) y más poderoso que el analizador SLR(1), aunque todos usan las mismas reglas de producción . La simplificación que introduce el analizador LALR consiste en fusionar reglas que tienen conjuntos de elementos del núcleo idénticos , porque durante el proceso de construcción del estado LR(0) no se conocen las búsquedas anticipadas. Esto reduce el poder del analizador porque no conocer los símbolos de anticipación puede confundir al analizador en cuanto a qué regla gramatical elegir a continuación, lo que genera conflictos de reducción/reducción . Todos los conflictos que surgen al aplicar un analizador LALR(1) a una gramática LR(1) inequívoca son conflictos de reducción/reducción. El analizador SLR(1) realiza más fusiones, lo que introduce conflictos adicionales.
El ejemplo estándar de una gramática LR(1) que no se puede analizar con el analizador LALR(1), mostrando un conflicto de reducción/reducción de este tipo, es:
S → a E c
→ a F d
→ b F c
→ b E d
E → e
F → e
En la construcción de la tabla LALR, dos estados se fusionarán en un solo estado y luego se encontrará que las búsquedas anticipadas son ambiguas. El único estado con anticipación es:
mi → e. {CD}
F → e. {CD}
Un analizador LR(1) creará dos estados diferentes (con anticipaciones no conflictivas), ninguno de los cuales es ambiguo. En un analizador LALR, este estado tiene acciones en conflicto (dada la anticipación c o d, reducir a E o F), un "conflicto de reducción/reducción"; la gramática anterior será declarada ambigua por un generador de analizador LALR y se informarán los conflictos.
Para recuperar, esta ambigüedad se resuelve eligiendo E, porque aparece antes de F en la gramática. Sin embargo, el analizador resultante no podrá reconocer la secuencia de entrada válida b e c, ya que la secuencia ambigua e cse reduce a (E → e) c, en lugar de la correcta (F → e) c, pero b E cno está en la gramática.
Analizadores LL editar
Los analizadores sintácticos LALR( j ) son incomparables con los analizadores sintácticos LL( k ) : para cualquier j y k mayores que 0, hay gramáticas LALR( j ) que no son gramáticas LL( k ) y viceversa. De hecho, es indecidible si una gramática LL(1) dada es LALR( k ) para cualquier k > 0
Dependiendo de la presencia de derivaciones vacías, una gramática LL(1) puede ser igual a una gramática SLR(1) o LALR(1). Si la gramática LL(1) no tiene derivaciones vacías, es SLR(1) y si todos los símbolos con derivaciones vacías tienen derivaciones no vacías, es LALR(1). Si existen símbolos que solo tienen una derivación vacía, la gramática puede o no ser LALR(1).
Véase también editar
Referencias editar
- ↑ Nigel P. Chapman (5 de julio de 2021). «Análisis de LR: teoría y práctica». Wikipedia (en inglés). Consultado el 24 de enero de 2022.
Datos: Q115799311
