En informática , un analizador sintáctico LR canónico o un analizador sintáctico LR (1) es un analizador sintáctico LR (k) para k = 1 , es decir, con una única terminal de búsqueda anticipada . El atributo especial de este analizador es que cualquier gramática LR (k) con k> 1 se puede transformar en una gramática LR (1). [1] Sin embargo, se requieren sustituciones hacia atrás para reducir k y, a medida que aumentan las sustituciones hacia atrás, la gramática puede volverse rápidamente extensa, repetitiva y difícil de entender. LR (k) puede manejar todos los lenguajes deterministas libres de contexto . [1] En el pasado, este analizador LR (k) se ha evitado debido a sus enormes requisitos de memoria a favor de alternativas menos potentes como el analizador LALR y LL (1) . Recientemente, sin embargo, varios generadores de analizadores sintácticos ofrecen un "analizador sintáctico LR (1) mínimo" cuyos requisitos de espacio están cerca de los analizadores sintácticos LALR [ cita requerida ] .
Como la mayoría de los analizadores, el analizador LR (1) es generado automáticamente por compiladores-compiladores como GNU Bison , MSTA, Menhir, [2] HYACC ,. [3]
En 1965 Donald Knuth inventó el LR (k) analizador ( L eft a derecha, R ightmost derivación parser) un tipo de desplazamiento y reducción analizador , como una generalización de existentes analizadores de precedencia . Este analizador tiene el potencial de reconocer todos los lenguajes deterministas libres de contexto y puede producir derivaciones tanto a la izquierda como a la derecha de las declaraciones encontradas en el archivo de entrada. Knuth demostró que alcanza su máximo poder de reconocimiento de lenguaje para k = 1 y proporcionó un método para transformar las gramáticas LR (k), k> 1 en gramáticas LR (1). [1]
Los analizadores sintácticos Canonical LR (1) tienen la desventaja práctica de tener enormes requisitos de memoria para la representación interna de la tabla del analizador sintáctico. En 1969, Frank DeRemer sugirió dos versiones simplificadas del analizador LR llamadas LALR y SLR . Estos analizadores requieren mucha menos memoria que los analizadores Canonical LR (1), pero tienen una capacidad de reconocimiento de idioma ligeramente menor. [4] Los analizadores LALR (1) han sido las implementaciones más comunes del analizador LR.
Sin embargo, un nuevo tipo de analizador LR (1), algunas personas llaman "analizador mínimo LR (1)", fue introducido en 1977 por David Pager [5], quien demostró que se pueden crear analizadores sintácticos LR (1) cuyos requisitos de memoria compiten con los de analizadores sintácticos LALR (1). Recientemente [ ¿cuándo? ] , algunos generadores de analizadores sintácticos ofrecen analizadores sintácticos mínimos LR (1), que no solo resuelven el problema de los requisitos de memoria, sino también el misterioso problema de conflicto inherente a los generadores de analizadores sintácticos LALR (1). [ cita requerida ] Además, los analizadores minimal LR (1) pueden usar acciones de reducción de desplazamiento, lo que los hace más rápidos que los analizadores Canonical LR (1).
El analizador sintáctico LR (1) es un autómata determinista y, como tal, su funcionamiento se basa en tablas de transición de estado estático . Estos codifican la gramática del idioma que reconoce y normalmente se denominan "tablas de análisis".