El analizador LR ( eng. LR parser ) es un analizador para los códigos fuente de los programas escritos en algún lenguaje de programación que lee el flujo de entrada de izquierda (izquierda ) a derecha y produce la producción más a la derecha (derecha ) de una gramática libre de contexto . También se utiliza el término analizador LR( k ) , donde k expresa el número de caracteres de vista previa no leídos en el flujo de entrada, sobre la base de los cuales se toman decisiones durante el análisis. Por lo general , k es 1 y, a menudo, se omite.
La sintaxis de muchos lenguajes de programación se puede definir mediante una gramática que es LR(1) o similar, y por esta razón los compiladores suelen utilizar analizadores LR para realizar el análisis del código fuente.
Por lo general, se hace referencia a un analizador en relación con el nombre del idioma cuyo código fuente analiza, por ejemplo, "analizador de C++" analiza el código fuente de C++ .
Un analizador LR puede generarse a partir de una gramática libre de contexto mediante un programa llamado generador de analizador , o puede ser escrito a mano por un programador. Una gramática libre de contexto se clasifica como LR( k ) si hay un analizador LR( k ) para ella, según lo determine el generador del analizador.
Se dice que el analizador LR analiza sintácticamente de abajo hacia arriba porque trata de inferir la producción de nivel superior de la gramática construyéndola a partir de hojas .
Un lenguaje determinista libre de contexto es un lenguaje para el cual existe algún tipo de gramática LR( k ). Cada gramática LR( k ) se puede convertir automáticamente en una gramática LR( 1 ) para el mismo idioma, mientras que las gramáticas LR( 0 ) para algunos idiomas pueden no existir. Los lenguajes LR( 0 ) son su propio subconjunto de los deterministas.
Un analizador LR se basa en un algoritmo controlado por una tabla de análisis , una estructura de datos que contiene la sintaxis del lenguaje analizado. Entonces, el término analizador LR en realidad se refiere a una clase de analizadores que pueden analizar casi cualquier lenguaje de programación para el que se proporciona una tabla de análisis. La tabla de análisis es generada por el generador del analizador.
El análisis LR se puede generalizar como análisis arbitrario de un lenguaje sin contexto sin pérdida de rendimiento, incluso para gramáticas LR(k). Esto se debe a que la mayoría de los lenguajes de programación se pueden expresar con una gramática LR( k ), donde k es una pequeña constante (generalmente 1). Tenga en cuenta que el análisis de gramáticas que no son LR(k) es un orden de magnitud más lento (cúbico en lugar de cuadrático en términos del tamaño del flujo de entrada).
El análisis LR se puede aplicar a más idiomas que el análisis LL y también es mejor en el informe de errores, lo que significa que detecta errores de sintaxis donde la entrada no coincide con la gramática lo antes posible. Por el contrario, los analizadores LL(k) (o peor, incluso LL(*)) pueden retrasar la detección de un error en otra rama de la gramática debido a la reversión, lo que a menudo dificulta la localización de un error en lugares de prefijos largos comunes.
Los analizadores LR son difíciles de crear a mano y normalmente los crea un generador de analizadores o un compilador compilador . Dependiendo de cómo se creó la tabla de análisis, estos analizadores pueden llamarse analizadores LR simples (SLR), analizadores LR anticipados (LALR) o analizadores LR canónicos . Los analizadores LALR tienen un poder de reconocimiento significativamente mayor que los analizadores SLR . Al mismo tiempo, las tablas para el análisis SLR tienen el mismo tamaño que para el análisis LALR, por lo que ya no se utiliza el análisis SLR. Los analizadores LR canónicos tienen un poco más de poder de reconocimiento que los analizadores LALR, pero requieren mucha más memoria de tabla, por lo que rara vez se usan. .
| Lenguajes formales y gramáticas formales | |
|---|---|
| Conceptos generales | |
| tipo 0 | |
| Tipo 1 |
|
| Tipo 2 | |
| Tipo 3 |
|
| analizando | |