Analizador LR

En este artículo, discutiremos el analizador LR, su descripción general y luego discutiremos el algoritmo. Además, discutiremos la tabla de análisis y el diagrama de trabajo del analizador LR. Discutámoslo uno por uno.

Analizador LR :
El analizador LR es un analizador de abajo hacia arriba para la gramática libre de contexto que generalmente es utilizado por el compilador de lenguaje de programación de computadoras y otras herramientas asociadas. El analizador LR lee su entrada de izquierda a derecha y produce una derivación más a la derecha. Se llama un analizador de abajo hacia arriba porque intenta reducir las producciones de gramática de nivel superior al construir a partir de las hojas. Los analizadores LR son los analizadores más poderosos de todos los analizadores deterministas en la práctica.

Descripción del analizador LR:
El término analizador analizador LR(k), aquí la L se refiere al escaneo de izquierda a derecha, R se refiere a la derivación más a la derecha en sentido inverso y k se refiere al número de símbolos de entrada de «anticipación» no consumidos que se utilizan para tomar decisiones del analizador. Por lo general, k es 1 y a menudo se omite. Una gramática libre de contexto se llama LR (k) si existe el analizador LR (k) para ella. Esto primero reduce la secuencia de fichas a la izquierda. Pero cuando leemos desde arriba, el orden de derivación primero se extiende a no terminal.

1. La pila está vacía y buscamos reducir la regla en S’→S$.
2. Usando un «.» en la regla representa cuántas de las reglas ya están en la pila.
3. Un elemento punteado, o simplemente, el elemento es una regla de producción con un punto que indica cuánto RHS se ha reconocido hasta ahora. El cierre de un artículo se usa para ver qué reglas de producción se pueden usar para expandir la estructura actual. Se calcula de la siguiente manera:

Reglas para el analizador LR:
Las reglas del analizador LR son las siguientes.

1. El primer elemento de las reglas gramaticales dadas se agrega como el primer conjunto cerrado.
2. Si un objeto está presente en el cierre de la forma A→ α. β. γ, donde el siguiente símbolo después del símbolo no es terminal, agregue las reglas de producción del símbolo donde el punto precede al primer elemento.
3. Repita los pasos (B) y (C) para los nuevos elementos agregados en (B).

Algoritmo del analizador LR: el algoritmo
de análisis LR es el mismo para todos los analizadores, pero la tabla de análisis es diferente para cada analizador. Consta de los siguientes componentes de la siguiente manera.

1. Búfer de entrada: 
   contiene la string dada y termina con un símbolo $.
    
2. Pila: 
   la combinación del símbolo de estado y el símbolo de entrada actual se utiliza para hacer referencia a la tabla de análisis para tomar las decisiones de análisis.

Tabla de análisis :  la
tabla de análisis se divide en dos partes: la tabla de acciones y la tabla Ir a. La tabla de acciones da una regla gramatical para implementar el estado actual dado y el terminal actual en el flujo de entrada. Hay cuatro casos utilizados en la tabla de acción de la siguiente manera.

1. Acción de cambio: en la acción de cambio, el terminal actual se elimina del flujo de entrada y el estado n se coloca en la pila, y se convierte en el nuevo estado actual.
2. Acción de reducción: el número m se escribe en el flujo de salida.
3. El símbolo m mencionado en el lado izquierdo de la regla m dice que el estado se elimina de la pila.
4. El símbolo m mencionado en el lado izquierdo de la regla m dice que se busca un nuevo estado en la tabla Goto y se crea el nuevo estado actual empujándolo a la pila.

An accept - the string is accepted
No action - a syntax error is reported

Nota:
la tabla de acceso indica qué estado debe continuar.

Diagrama del analizador LR: