Informatica

Análisis LR (1)

Descripción intuitiva LR(k), k>0: se llamará conjunto de símbolos de adelanto a los símbolos que, en un estado concreto del diagrama, se espera encontrar en cada una de susconfiguraciones. En este nuevo tipo de análisis se añadirá a cada configuración de los símbolos de adelanto correspondiente.
Introducción al cálculo de símbolos de adelanto. Vamos a construir eldiagrama de estados de análisis LR(1) de la gramática Gaxb. Se mantendrá el mismo algoritmo básico, al que se incorpora el calculo de los conjuntos de símbolos de adelanto de cada configuración de cadaestado.
Empezaremos con un mecanismo para calcular el conjunto de símbolos de adelanto:
º De la configuración inicial del estado inicial (A´::=.A$).
º De las configuraciones del cierre de unaconfiguración.
º De las configuraciones resultado de ir a otro conjunto de configuraciones mediante un símbolo.

Autómata asociado a un analizador LR(1): definiciones formales
A continuación sedescribirán las diferencias entre los análisis LR(0) y LR(1).
< Gramática aumentada. La interpretación del símbolo de adelanto para la regla añadida a la gramática de partida origina algunas diferenciasen el análisis LR(1).
Dada cualquier gramática independiente del contexto G=<Et, En, A, P>, la gramática extendida para LR(1) se define así, donde A`&En y $&Et:
G`=<Et, EnU{A`}, A`,PU{A`::A}>
Es fácil comprobar que el lenguaje generado por G` es el mismo que el generado por G. obsérvese que el símbolo ´$´ no aparece de forma explicita en G`. sin embargo, la restricciónimpuesta sobre él es necesaria, porque en la construcción del autómata de análisis LR(1) el símbolo ´$´ se utilizara como el único símbolo de adelanto para la configuración del estado inicial.
<Construcción de los conjuntos de símbolos de adelanto. El único cambio de lso conceptos descritos formalmente en la sección Autómata asociado a un analizador LR(0): definiciones formales es la...