Analizador LR
En informática , los analizadores sintácticos LR son un tipo de analizador ascendente que analiza lenguajes deterministas libres de contexto en tiempo lineal. [1] Hay varias variantes de análisis de LR: SLR analizadores , LALR analizadores , Canonical LR (1) analizadores , LR Minimal (1) programas de análisis , GLR analizadores . Los analizadores sintácticos LR pueden ser generados por un generador de analizadores sintácticos a partir de una gramática formal que define la sintaxis del lenguaje que se va a analizar. Son muy utilizados para el procesamiento de lenguajes informáticos..
Un LR analizador ( L eft a derecha, R derivación ightmost a la inversa) lee el texto de entrada de izquierda a derecha sin realizar copias de seguridad (esto es cierto para la mayoría de programas de análisis), y produce una derivación por la derecha a la inversa: se hace un bottom-up analizar : no es un análisis LL de arriba hacia abajo o un análisis ad-hoc. El nombre LR suele ir seguido de un calificador numérico, como en LR (1) o, a veces, LR ( k ) . Para evitar retroceder o adivinar, el analizador LR puede mirar adelante a k símbolos de entrada de búsqueda anticipada antes de decidir cómo analizar los símbolos anteriores. Típicamentek es 1 y no se menciona. El nombre LR suele ir precedido de otros calificadores, como en SLR y LALR . La LR ( k ) condición para una gramática fue sugerido por Knuth para representar "traducible de izquierda a derecha con cota k ". [1]
Los analizadores sintácticos LR son deterministas; producen un solo análisis correcto sin conjeturas ni retrocesos, en tiempo lineal. Esto es ideal para lenguajes de computadora, pero los analizadores LR no son adecuados para lenguajes humanos que necesitan métodos más flexibles pero inevitablemente más lentos. Algunos métodos que pueden analizar lenguajes arbitrarios libres de contexto (p. Ej., Cocke-Younger-Kasami , Earley , GLR ) tienen el peor rendimiento de tiempo O ( n 3 ). Otros métodos que retroceden o producen múltiples análisis pueden incluso llevar un tiempo exponencial cuando adivinan mal. [2]
Las propiedades anteriores de L , R , y k son en realidad compartidos por todos los programas de análisis de reducción por desplazamiento , incluyendo los analizadores de precedencia . Pero por convención, el nombre LR representa la forma de análisis sintáctica inventada por Donald Knuth y excluye los métodos de precedencia anteriores menos poderosos (por ejemplo , analizador de precedencia de operador ). [1] Los analizadores sintácticos LR pueden manejar una gama más amplia de lenguajes y gramáticas que los analizadores sintácticos de precedencia o el análisis sintáctico LL descendente . [3]Esto se debe a que el analizador LR espera hasta que ha visto una instancia completa de algún patrón gramatical antes de comprometerse con lo que ha encontrado. Un analizador LL tiene que decidir o adivinar qué está viendo mucho antes, cuando solo ha visto el símbolo de entrada más a la izquierda de ese patrón.
Un analizador LR escanea y analiza el texto de entrada en una pasada hacia adelante sobre el texto. El analizador genera el árbol de análisis de forma incremental, de abajo hacia arriba y de izquierda a derecha, sin adivinar ni retroceder. En cada punto de esta pasada, el analizador ha acumulado una lista de subárboles o frases del texto de entrada que ya se han analizado. Esos subárboles aún no están unidos porque el analizador aún no ha alcanzado el extremo derecho del patrón de sintaxis que los combinará.
En el paso 6 de un análisis de ejemplo, sólo se ha analizado "A * 2", de forma incompleta. Solo existe la esquina inferior izquierda sombreada del árbol de análisis. Ninguno de los nodos del árbol de análisis con el número 7 o superior existe todavía. Los nodos 3, 4 y 6 son las raíces de subárboles aislados para la variable A, el operador * y el número 2, respectivamente. Estos tres nodos raíz se mantienen temporalmente en una pila de análisis. La parte restante sin analizar del flujo de entrada es "+ 1".
