Compilador. Análisis Predictivo

Alumna: Jessica Cecibel Correa Campoverde

Paralelo: Decimo “A”

Docente: Edison Coronel.

Completar las siguientes gramáticas:

If – else

Ciclos repetitivos

For

While

Operaciones básicas

UNIVERSIDAD NACIONAL DE LOJA

FACULTAD DE ENERGÍA, LAS INDUSTRIAS Y LOS RECURSOS NATURALES NO RENOVABLES

CARRERA DE INGENIERÍA EN SISTEMAS

CARRERA DE INGENIERIA EN SISTEMAS

TAREA-CIS-2019

Nombre: Diego Eduardo Murquincho Puma Fecha: 31 de julio

Modulo: Decimo “A” Asignatura: Compiladores.

Docente: Ing. Edison Coronel. Tema: Análisis Predictivo.

Dada la siguiente gramática

E → TE'

E' → +TE' |ε

T → FT'

T' → ∗FT' |ε

F → (E )|id

Generar el análisis predictivo para las siguientes entradas

id + id * id

(id + id) * id

Generar el análisis sintáctico

Recordemos que el analizador sintáctico o parser es el corazón del compilador o intérprete y gobierna todo el proceso. Su objetivo es realizar el resto del análisis (continuando el trabajo iniciado por el analizador morfológico) para comprobar que la sintaxis de la instrucción en cuestión es correcta. Para ello, el analizador sintáctico considera como símbolos terminales las unidades sintácticas devueltas por el analizador morfológico. Existen dos tipos principales de análisis:

Descendente o de arriba abajo (top-down, en inglés). Se parte del axioma S y se va realizando la derivación S→*x. La cadena x (que normalmente corresponde a una instrucción o un conjunto de instrucciones) se llama meta u objetivo del análisis. La primera fase del análisis consiste en encontrar, entre las reglas cuya parte izquierda es el axioma, la que conduce a x. De esta manera, el árbol sintáctico se va construyendo de arriba abajo, tal como indica el nombre de este tipo de análisis.

Ascendente o de abajo arriba (bottom-up, en inglés). Se parte de la cadena objetivo x y se va reconstruyendo en sentido inverso la derivación S→*x. En este caso, la primera fase del análisis consiste en encontrar, en la cadena x, el asidero, que es la parte derecha de la última regla que habría que aplicar para reducir S a x. De esta manera, el árbol sintáctico se va construyendo de abajo arriba, tal como indica el nombre de este tipo de análisis.

Conjuntos importantes en una gramática

Sea una gramática limpia G=(ΣT, ΣN, S, P). Sea Σ = ΣT ∪ ΣN. Sea ∈Σ un símbolo de esta gramática (terminal o no terminal). Se definen los siguientes conjuntos asociados a estas gramáticas y a este símbolo:

Si X∈ΣN, primero(X) = {V | X →+ Vx, V∈ΣT, x∈Σ*}

Si X∈ΣT, primero(X) = {X}

Es decir, si X es terminal, primero(X) contiene sólo a X; en caso contrario, primero(X) es el conjunto de símbolos terminales que pueden aparecer al principio de alguna forma sentencial derivada a partir de X.

siguiente(X) = {V | S →+ xXVy, X∈ΣN, V∈ΣT, x,y∈Σ*}, donde S es el axioma de la gramática.

Es decir, si X es un símbolo no terminal de la gramática, siguiente(X) es el conjunto de símbolos terminales que pueden aparecer inmediatamente a la derecha de X en alguna forma sentencial. Si X puede aparecer en el extremo derecho de alguna forma sentencial, entonces el símbolo de fin de cadena $ ∈ siguiente(X).

Para calcular el conjunto primero(X) ∀X ∈ ΣN ∪ ΣT, se aplicarán las siguientes reglas, hasta que no se puedan añadir más símbolos terminales ni λ a dicho conjunto.

(R1) Si X ∈ ΣT, se hace primero(X)={X}.

(R2) Si X ::= λ ∈ P, se añade λ a primero(X).

(R3) Si X ::= Y1 Y2 ... Yk ∈ P, se añade primero(Yi)–{λ} a primero(X) para i=1,2,…,j, donde j es el primer subíndice tal que Yj no genera la cadena vacía (Yj es terminal, o siendo no terminal no ocurre que Yj → λ).

(R4) Si X ::= Y1 Y2 ... Yk ∈ P y Yj →λ∀j ∈ {1,2,...,k}, se añade λ a primero(X)

Consideremos la gramática siguiente, en la que E es el axioma:

Figura 6. Ejemplo de una gramática

En esta gramática, el conjunto primero(E) resulta ser igual al conjunto primero(T) aplicando la regla (R3) a la regla (1). Para calcular el conjunto primero(T) se aplica la regla (R3) a la regla (4), de la que se obtiene que primero(T) es igual a primero(F).

Para calcular primero(F) se aplica la regla (R3) a la regla (7), añadiendo el conjunto primero((), que es igual a {(} por la regla (R1). Al aplicar la regla (R3) a la regla (8), se añade también el conjunto primero(id), que es igual a {id} por la regla (R1).

Por tanto: primero(E)=primero(T)=primero(F)={(, id}

A continuación

...