09:11
11
Temas Analizador Sintáctico: funciones y tipos Analizador Sintáctico Descendente Analizador Sintáctico Ascendente Generador de Analizadores Sintácticos - Yacc
Objetivo Que el estudiante logre: 1) Identificar las funciones y los tipos de Analizadores Sintácticos. 2) Aplicar los algoritmos de los analizadores sintácticos.
09:11
22
Programa fuente Analizador Léxico Flujo de tokens o componentes léxicos
Analizador Sintáctico Árbol sintáctico
Administrador de la Tabla de Símbolos
Analizador Semántico Árbol sintáctico
Manejador de errores
Generador de Código Intermedio Representación intermedia
Optimizador Representación intermedia
Generador de Código Programa Objeto 3
Todo lenguaje de programación tiene reglas que prescriben la estructura sintáctica de programas bien formados. Se puede describir la sintaxis de las construcciones de los lenguajes de programación por medio de gramáticas libres de contexto. Las gramáticas ofrecen ventajas significativas a los diseñadores de lenguajes y a los escritores de compiladores, que son:
Especificación precisa y fácil de entender de un lenguaje de programación. Construcción automática de analizadores sintácticos. Imparten una estructura al programa fuente útil para la traducción a código objeto y para la detección adecuada de errores. Fácil mantenimiento: evolución del lenguaje.
4
Funciones
Obtener una cadena de componentes léxicos del A.L. y comprobar si la cadena puede ser generada por la gramática del lenguaje fuente.
Informar los errores sintácticos en forma precisa y significativa. Deberá ser dotado de un mecanismo de recuperación de errores para continuar con el análisis.
5
TIPOS
Métodos Universales: Cocke-Younger-Kasami y Earley
Sirven para cualquier gramática.
Muy ineficientes.
Descendentes (top-down)
Construyen el árbol de análisis sintáctico desde arriba (raíz) hasta abajo (hojas, terminales).
Analizadores Descendentes Recursivos.
Analizadores LL(1) con tabla.
Ascendentes (bottom-up)
Construyen el árbol de análisis sintáctico desde abajo hacia arriba.
Analizadores de Precedencia de Operador.
Analizadores LR.
6
Se puede considerar el análisis sintáctico descendente como un intento de encontrar una derivación más a la izquierda para la cadena de entrada. También
puede considerarse como un intento por construir un árbol de análisis sintáctico para la entrada comenzando desde la raíz y creando los nodos del árbol en orden previo.
Análisis Sintáctico por descenso recursivo con retroceso Usa retroceso para resolver la incertidumbre. Sencillo de implementar. Muy ineficiente.
7
Debe retroceder para tomar otro camino
8
Para construir un A.S. predictivo no recursivo se debe calcular las funciones PRIMERO y SIGUIENTE. Conjunto PRIMERO (X) para todos los símbolos gramaticales X Reglas: 1.Si X es un terminal PRIMERO (X) es {X}.
2. Si X es una producción PRIMERO (X). 3.Si X es un no terminal y X Y1 Y2 ...YK es una producción entonces poner a en PRIMERO (X) , si para algún i a está en PRIMERO (Yi) y está en todos los PRIMERO(Y1), PRIMERO(Y2),..., PRIMERO(Yi-1) Si está en PRIMERO (Yj) para todo j=1,2,...k entonces poner en PRIMERO (X). Ejemplo: E TE’ E’ +TE’ / T FT’ T’ *FT’ / F (E) / id
PRIMERO (E) = { (, id} PRIMERO (E’) = { +, } PRIMERO (T) = { (, id} PRIMERO (T’) = { *, } PRIMERO (F) = { (, id} 9
Se puede calcular PRIMERO para cualquier cadena X1 X2 ...Xn de la siguiente forma: • Añadir a PRIMERO(X1 X2 ...Xn) todos los símbolos distintos de de PRIMERO (X1). Si PRIMERO(X1), añadir todos los símbolos distintos de de PRIMERO (X2) y así sucesivamente. • Por último, añadir a PRIMERO(X1 X2 ...Xn) si, para todo i, PRIMERO (Xi).
10
Conjunto SIGUIENTE(A) 1. 2. 3.
Hacer SIGUIENTE (S)={$}, donde S es el símbolo inicial. Si A B, entonces todo lo que está en PRIMERO ()- se pone en SIGUIENTE (B). Si A B o A B, donde PRIMERO () contenga , entonces todo lo que está en SIGUIENTE (A) se pone en SIGUIENTE (B).
Ejemplo: E TE’ E’ +TE’ / T FT’ T’ *FT’ / F (E) / id
PRIMERO (E) = { (, id} PRIMERO (E’) = { +, } PRIMERO (T) = { (, id} PRIMERO (T’) = { *, } PRIMERO (F) = { (, id}
SIGUIENTE(E) = { $, )} SIGUIENTE(E’) = { $, )} SIGUIENTE(T) = { +,), $} SIGUIENTE(T’) = { +,), $} SIGUIENTE(F) = { +,*,), $}
11
Construcción de Tablas de Análisis Sintáctico 1. Para cada producción A efectuar los pasos 2 y 3. 2. Para cada terminal a de PRIMERO (), añadir A a M [A,a]. 3. Si PRIMERO (), añadir A a M [A,b] para cada terminal b de SIGUIENTE(A). 1. Si PRIMERO () y $ SIGUIENTE (A), añadir A a M [A,$]. 4. Todas las entradas no definidas de M son error. Ejemplo
NO TERMINAL E E’ T T’ F
E TE’ E’ +TE’ / T FT’ T’ *FT’ / F (E) / id
SIGUIENTE(E) = { $, )} SIGUIENTE(E’) = { $, )} SIGUIENTE(T) = { +,), $} SIGUIENTE(T’) = { +,), $} SIGUIENTE(F) = { +,*,), $}
PRIMERO (E) = { (, id} PRIMERO (E’) = { +, } PRIMERO (T) = { (, id} PRIMERO (T’) = { *, } PRIMERO (F) = { (, id}
SÍMBOLO DE ENTRADA id
+
*
E → TE’
(
$
E’ →
E’ →
T’ →
T’ →
E → TE’ E’ → +TE’
T → FT’
T → FT’ T’ →
F → id
)
T’ → *FT’ F → (E)
12
ENTRADA
PILA
a
+
b
$
X
Programa para
Y
análisis sintáctico
Z
predictivo
Buffer de entrada que contiene la cadena que se va a analizar, seguida de $, que indica fin de la cadena de entrada.
SALIDA
$ Pila que contiene una secuencia de símbolos gramaticales con $ en la parte de abajo de la pila que indica la base de la pila.
Tabla de análisis
Sintáctico M
13
PROGRAMA PARA ANÁLISIS SINTÁCTICO PREDICTIVO NO RECURSIVO Los símbolos de la entrada actual “a” y cima de la pila “X” determinan la acción del analizador. Hay tres posibilidades: •
X=a=$, el analizador se detiene y anuncia el éxito del análisis.
•
X=a $, el analizador saca X de la pila y mueve el puntero de la entrada al siguiente símbolo de entrada.
•
X VN , el programa consulta la entrada M[X,a]. Si M[X,a] error, entonces se saca X del tope de pila y se coloca en la pila la parte derecha de la producción en orden inverso. O sea, si X UVW, se coloca WVU (U queda como cima de la pila)
•
Si M[X,a]= error, se llama a la rutina de recuperación de error 14
Ejemplo: id + id * id PILA $E $E’T $E’T’F $E’T’id $E’T’ $E’ $E’T+ $E’T $E’T’F $E’T’id $E’T’ $E’T’F* $E’T’F $E’T’id $E’T’ $E’ $
ENTRADA id + id * id $ id + id * id $ id + id * id $ id + id * id $ + id * id $ + id * id $ + id * id $ id * id $ id * id $ id * id $ * id $ * id $ id $ id $ $ $ $
SALIDA E → TE’ T → FT’ F → id
T’ → E’ → +TE’ T → FT’ F → id
T’ → *FT’ F → id T’ → E’ →
a= entrada actual X= cima de la pila 1. X=a=$, el analizador se detiene y anuncia el éxito del análisis. 2. X=a $, el analizador saca X de la pila y mueve el puntero de la entrada al siguiente símbolo de entrada. 3. X VN , el programa consulta la entrada M[X,a]. Si M[X,a] error, entonces se saca X del tope de pila y se coloca en la pila la parte derecha de la producción en orden inverso. 4. Si M[X,a]= error, se llama a la rutina de recuperación de error. SÍMBOLO DE ENTRADA
NO TER.
id las acciones + que realiza * este analizador ( ) de $ Se observa que son las buscar una derivación por la izquierda de la entrada E E → TE’ E → TE’o el intento de construir un árbol sintáctico para la entrada comenzando por E’ E’ → +TE’ E’ → E’ → la raíz y creando los nodos del árbol. T T’ F
T → FT’
T → FT’
T’ →
T’ →
T’ → *FT’
F → id
F → (E)
Derivación más a la izquierda
E TE’ FT’E’ idT’E’ idE’ id+TE’ id+FT’E’ id+idT’E’ id+ id*FT’ E’ id+id*idT’ E’ id+ id*id E’ id+ id*id
15
T’ →
• •
•
•
Si una gramática no cumple ciertas condiciones, la tabla de análisis sintáctica tendrá al menos una entrada con definición múltiple. Una gramática cuya Tabla de Análisis Sintáctico no tiene entradas con definiciones múltiples se define como LL(1). Para ser LL(1) debe cumplir las siguientes condiciones: – No ser recursiva a izquierda – No ser ambigua – Estar factorizada a izquierda – Cuando A → α / β se debe cumplir: • Sólo puede derivarse de α ó de β. • Si β deriva , α no deriva ninguna cadena que comience con un terminal de SIGUIENTE (A). Si la gramática no cumple la condición se debe transformarla aplicando los algoritmos para eliminar la recursividad a izquierda y factorizando a izquierda. Existen gramáticas a las que ninguna transformación convertirá en LL(1). 16
Ejemplo: P iEtP / iEtPeP / a Eb
Factorizada a izquierda P iEtPP´ / a
PRIMERO(P)={i,a}
SIGUIENTE(P)={$,e}
P´ eP /
PRIMERO(P´)={e, }
SIGUIENTE(P´)={$,e}
Eb
PRIMERO(E)={b}
SIGUIENTE(E)={t}
NO TERMINAL P
SÍMBOLO DE ENTRADA a P a
b
P’ E
Eb
e P´ eP P´
i P iEtPP´
t
$ P’ →
17
Análisis por desplazamiento y reducción •
Precedencia de operadores
•
LR
Construir un árbol de análisis sintáctico para una cadena de entrada que comienza por las hojas y avanza hacia la raíz.
Reducir una cadena de entrada w al símbolo inicial de la gramática.
En cada paso de reducción se sustituye una subcadena que concuerde con el lado derecho de una producción por el símbolo del lado izquierdo, se traza una derivación por la derecha en sentido inverso.
18
•
•
•
Un mango de una cadena es una subcadena que concuerda con el lado derecho de una producción y cuya reducción al no terminal del lado izquierdo de la regla de producción representa un paso a lo largo de la inversa de una derivación por la derecha. Formalmente, un mango de una forma de frase derecha es una regla A → β y una posición de donde la cadena β podría encontrarse y sustituirse por A para producir la forma de frase derecha previa en una derivación por la derecha de . Es decir, si S * Aw * βw, entonces A → β si la posición que sigue de es un mango de βw. La cadena w a la derecha del mango contiene sólo símbolos terminales. Ejemplo
abbcde
mango posición 2 (regla A → b)
S → aABe
aAb c d e
mango posición 2 (regla A → Abc)
A → Abc
aAd e
mango posición 3 (regla B → d)
A→ b
aAB e
mango posición 1 (regla S → aABe)
B→d
S 19
Se puede obtener una derivación por la derecha en orden inverso mediante la poda de mangos. Es decir, se comienza con una cadena w de terminales que se desea analizar sintácticamente. Si w es una frase de la gramática en cuestión obtener w= µn donde µn es la n-ésima forma de frase derecha de una, aún desconocida, derivación por la derecha. S= µo µ1 µ2 ..... µn-1 µn = w
Para reconstruir esta derivación en orden inversa, se coloca el mango n en µn se reemplaza n por el lado izquierdo de alguna producción An n para obtener la (n-1) ésima forma derecha µn-1. Después se repite este proceso, es decir se sitúa el mango n-1 en µn-1 y se reemplaza este mango para obtener la forma de frase derecha µn-2. Si al repetir este proceso se llega a S, entonces se anuncia la realización con éxito del análisis. FORMAS DE FRASE DERECHA
Ejemplo
MANGO
REGLA DE REDUCCIÓN
id1 + id2 * id3
id1
E → id
E→E+E
E + id2 * id3
id2
E → id
E→E*E
E + E * id3
id3
E → id
E→(E) E → id
E+E*E
E*E
E→E*E
E+E
E+E
E→E+E
E
20
•
Problemas de implantación del AS por desplazamiento y reducción – Situar la subcadena a reducir – Elegir la regla adecuada en caso de que haya más de una con esa subcadena en la parte derecha • Posible solución utilizar: – Una pila para manejar los símbolos gramaticales – Buffer de entrada para gestionar la cadena w a analizar Funcionamiento • Inicialmente: – En la pila se coloca el símbolo de fin de cadena ($) – En el buffer se coloca la cadena a analizar seguida de la marca de fin de línea (w$) • Repetir hasta que se detecte un error o en la pila sólo se encuentre el símbolo inicial (S$) y la entrada esté vacía ($) – Desplazar cero o más símbolos de la entrada a la pila hasta que en la cima se encuentre un mango β – Reducir β al lado izquierdo de la regla adecuada. 21
Operaciones • • • •
Desplazar: Mover el siguiente símbolo de entrada a la cima de la pila Reducir: (en este momento el extremo derecho del mango está en la cima de la pila), localizar el extremo izquierdo del mango dentro de la pila y decidir el no terminal con el que se debe sustituir el mango. Aceptar: Anunciar el fin con éxito del análisis Error: Llamar a la rutina de recuperación de errores. PILA $
ENTRADA
ACCIÓN
id1 + id2 * id3 $
desplazar
Ejemplo
$ id1
+ id2 * id3 $
reducir por E → id
E→E+E
$E
+ id2 * id3 $
desplazar
E→E*E
$E+
id2 * id3 $
desplazar
E→(E)
$ E + id2
* id3 $
reducir por E → id
E → id
$E+E
* id3 $
desplazar
id3 $
desplazar
$E+E* $ E + E * id3
$
reducir por E → id
$E+E*E
$
reducir por E → E * E
$E+E
$
reducir por E → E + E
$E
$
aceptar
22
• Existen gramáticas libres de contexto para las que no se pueden utilizar analizadores sintácticos por desplazamiento y reducción. • En esas gramáticas se puede llegar a una configuración en la que, conociendo el contenido de la pila y el siguiente símbolo de entrada, no se puede decidir si: – Desplazar o reducir (conflicto de desplazamiento/reducción) – Que tipo de reducción efectuar (conflicto de reducción/reducción)
23
Ejemplo: P → if E then P / if E then P else P / otro
PILA $
$ if $ if E $ if E then $ if E then P
$ if E then P else $P
ENTRADA
ACCIÓN
if E then P else P $
desplazar
E then P else P $
desplazar
then P else P $
desplazar
P else P $
desplazar
else P $
P$ $
En este momento no sabe si Desplazar o Reducir. El conflicto se resuelve a favor del desplazamiento.
Conflicto Desplazamiento / Reducción
desplazar Reducir P → if E then P
24
Ejemplo: A → id (B) / E = E B → B , C /C C → id E → id (D) / id D → D , E /E
El A.L. devuelve el componente léxico para todos los identificadores independientemente de su uso. Suponga que el lenguaje invoca procedimientos dando sus nombres con parámetros encerrados entre paréntesis y que con la mima sintaxis se hace referencia a las matrices. Dado que la traducción de índices en las referencias a matrices y la de los parámetros en las llamadas a procedimientos es distinta, se utilizan distintas producciones para generar lista de parámetros actuales e índices.
PILA $ $ id
ENTRADA id(id,id) $ (id,id) $
ACCIÓN desplazar Reducción/Reducción C → id E → id
Conflicto Reducción / Reducción
25
Una solución es cambiar el componente léxico id en la producción A → id (B) por A → idproc (B) usando un A.L. más complicado que devuelva el componente léxico idproc cuando reconozca un identificador que sea el nombre de un procedimiento, esto exigiría que el A.L. consulte a la tabla de símbolos antes de devolver un componente léxico.
PILA $
ENTRADA
ACCIÓN
idproc(id,id) $
desplazar
$ idproc
(id,id) $
Desplazar
$ idproc (
id,id)$
Desplazar
$ idproc (id
,id)$
Ejemplo: A → idproc (B) / E = E B → B , C /C C → id E → id (D) / id D → D , E /E
Reducción/Reducción C → id E → id
Conflicto Reducción / Reducción
26
Ventajas • Se pueden construir analizadores sintácticos LR para casi todos los lenguajes que se pueden describir con gramáticas libres de contexto. • Es el método de análisis por desplazamiento y reducción sin retroceso más general que se conoce. • Detectan los errores sintácticos tan pronto como sea posible en un examen de izquierda a derecha Inconveniente – Costoso de construir a mano Tipos • LR simple (SLR) – Fácil de implementar – Menos poderoso • LR canónico – Es muy costoso de implementar – El más potente • LALR (LR con examen por anticipado) – Intermedio entre los dos métodos anteriores
27
Gramática aumentada G’ Sea G una gramática cuyo símbolo inicial es S entonces G’ será una gramática aumentada con un nuevo símbolo inicial S´ y la regla de producciones S’S. Operaciones •Cerradura o Clausura (I) – Inicialmente todo elemento de I se añade a Clausura (I). – Si A α.Bβ Clausura (I) y BVN y B es una producción ENTONCES añadir el elemento B . a Clausura (I) si todavía no está ahí. Repetir esta regla hasta que no se pueda añadir más elementos a Clausura (I).
•IR-A (I,X): donde I es un conjunto de elementos y X es un símbolo de la gramática (terminal y no terminal) Se define IR-A (I,X) como la Clausura del conjunto de todos los elementos [A αX.β] tales que [A α.Xβ] esté en I. S´A
A(A)
Aa
I0
I1=(I0,A)
I2=(I0,a)
I3=(I0,( )
I4= (I3, A)
I5= (I3,( )
I5=(I3,a)
I5=(I4,) )
S´.A A.(A) A.a
S´A.
A a.
A (.A) A.(A) A.a
A (A.)
A (.A) A.(A) A.a = I3
A a. = I2
A (A).
28
I0
I1=(I0,A)
I2=(I0,a)
I3=(I0,( )
I4= (I3, A)
I5= (I3,( )
I5=(I3,a)
I5=(I4,) )
S´.A A.(A) A.a
S´A.
A a.
A (.A) A.(A) A.a
A (A.)
A (.A) A.(A) A.a = I3
A a. = I2
A (A).
29
Tabla de Análisis Sintáctico SLR A partir de la colección canónica de conjuntos de elementos para G´ se construye la tabla de análisis sintáctico que consta de dos partes: 1. 2.
Acción ir-a
Acción • Si [A α.aβ] está en Ii e IR-A (Ii,a)=Ij entonces Acción [i,a]=“desplazar j”. (a es un símbolo terminal). • Si [A α.] está en Ii entonces Acción [i,a]=“reducir A α” para todo a SIGUIENTE (A). • Si [S´ S.] está en Ii entonces Acción [i,$]=“aceptar”. ir-a Si IR-A (Ii,A)=Ij entonces ir-a (i,A)=j
30
EJEMPLO 0) S´A 1) A(A) 2) A.a
I0
I1=(I0,A)
I2=(I0,a)
I3=(I0,( )
I4= (I3, A)
I5= (I3,( )
I5=(I3,a)
I5=(I4,) )
S´.A A.(A) A.a
S´A.
A a.
A (.A) A.(A) A.a
A (A.)
A (.A) A.(A) A.a = I3
A a. = I2
A (A).
PRIMERO(S´) = { (, a} PRIMERO(A) = { (, a} SIGUIENTE(S´) = {$} SIGUIENTE(A) = { ), $}
Acción Estado
(
a
0
D3
D2
)
$
A 1
1
acepta
2 3
ir-a
R2 D3
R2
D2
4
4
D5
5
R1
Acción • Si [Aα.aβ] está en Ii e IR-A (Ii,a)=Ij entonces Acción [i,a] = “d.j”. • Si [Aα.] está en Ii entonces Acción [i,a]=“reducir Aα” para todo a SIGUIENTE (A). • Si [S´S.] está en Ii entonces Acción [i,$]=“aceptar”. Ir-a Si IR-A (Ii,A)=Ij entonces ir-a (i,A)=j
R1
31
El programa conductor es el mismo para todos los analizadores sintácticos LR, sólo cambia las tablas de un analizador a otro.
32
Algoritmo para reconocimiento de una hilera: Sea S el estado de la cima de la pila y a el símbolo de la entrada. Entonces: Si Acción [S,a] = desplazar S´, entonces introducir a y S´en la cima de la pila y avanzar el puntero de entrada al siguiente símbolo. Si Acción [S,a] = Reducir A , entonces sacar 2 * || símbolos de la pila, introducir A y después ir-a [S´, A] en la cima de la pila. Emitir la producción A . Si Acción [S,a] = Acepta, entonces aceptar y terminar. Si Acción [S,a] = error, entonces convocar a una rutina de recuperación de error. PILA Acción Estado
(
a
D3
D2
)
ir-a
$
A
0 $ 0(3
0
((a)) $
D3
(a)) $
D3
$0(3(3
a)) $
D2
acepta
2
R2 D3
ACCIÓN
1
1
3
ENTRADA
R2
D2
4
4
D5
5
R1
R1
$0(3(3a2
)) $
Reducir A a
$0(3(3A4
)) $
D5
$0(3(3A4)5
)$
Reducir A (a)
$0(3A4
)$
D5
$0(3A4)5
$
Reducir A (a)
$0A1
$
Acepta
33
Se comienza con una gramática aumentada S’→.S, $ Clausura (I)
Para cada elemento [A α.Bβ,a] I y BVN y B es una producción y cada terminal b en PRIMERO (βa) ENTONCES añadir el elemento [B .,b] a Clausura (I) si todavía no está ahí. Repetir esta regla hasta que no se pueda añadir más elementos a Clausura (I). IR-A (I,X): donde I es un conjunto de elementos y X es un símbolo de la gramática (terminal y no terminal) – Se define IR-A (I,X) como la Clausura del conjunto de todos los elementos [A αX.β,a] tales que [A α.Xβ,a ] esté en I.
09:11
34 34
I0
I1=(I0,S)
I2=(I0,C)
I3=(I0, c)
I4= (I0, d)
I5= (I2, C)
S´.S, $ S.CC, $ C.cC, c/d C .d, c/d
S´S. , $
SC.C, $ C.cC,$ C .d, $
Cc.C, c/d C.cC, c/d C .d, c/d
C d., c/d
S CC.,$
I6=(I2,c)
I7=(I2,d)
I8=(I3,C)
I9=(I3, c)
I9= (I3, d)
I9= (I6, C)
Cc.C, $ C.cC, $ C .d, $
C d., $
CcC., c/d
Cc.C, c/d C.cC, c/d C .d, c/d = I3
C d., c/d = I4
CcC., $
I10= (I6, C)
I10= (I6, d)
Cc.C, $ C.cC, $ C .d, $ = I6
C d., $ = I7
S´S SCC CcC C d
PRIMERO(S´) = { c, d} PRIMERO(S) = { c, d} PRIMERO(C) = { c, d} 09:11
Se comienza con una gramática aumentada S’→.S, $ Clausura (I) Para cada elemento [A α.Bβ,a] I y BVN y B es una producción y cada terminal b en PRIMERO (βa) ENTONCES añadir el elemento [B .,b] a Clausura (I) si todavía no está ahí. Repetir esta regla hasta que no se pueda añadir más elementos a Clausura (I). IR-A (I,X): donde I es un conjunto de elementos y X es un símbolo de la gramática (terminal y no terminal) Se define IR-A (I,X) como la Clausura del conjunto de todos los elementos [A αX.β,a] tales que [A α.Xβ,a ] esté en I.
35 35
Tabla de Análisis Sintáctico LR(1) A partir de la colección canónica de conjuntos de elementos para G´se construye la tabla de análisis sintáctico que consta de dos partes: Acción ir-a Tabla Accion • Si [A α.aβ,b] ∈ Ii e IR-A(Ii, a) = Ij ⇒ Accion(i, a) = “Desplazar j”. En este caso a debe ser un terminal. • Si [A → α.,a] ∈ Ii ⇒Accion(i, a) = “Reducir A → α” • Si [S′ → S., $] ∈ Ii ⇒ Accion(i, $) = “Aceptar” Tabla ir a Si IR-A(Ii, A)=Ij ⇒ ir-a (i, A) = j Todas las entradas no definidas son error.
09:11
36 36
0) S´S 1) SCC 2) CcC 3) C d
Acción Estado
I0
I1=(I0,S)
I2=(I0,C)
I3=(I0, c)
I4= (I0, d)
I5= (I2, C)
S´.S, $ S.CC, $ C.cC, c/d C .d, c/d
S´S. , $
SC.C, $ C.cC,$ C .d, $
Cc.C, c/d C.cC, c/d C .d, c/d
C d., c/d
S CC.,$
I6=(I2,c)
I7=(I2,d)
I8=(I3,C)
I9=(I3, c)
I9= (I3, d)
I9= (I6, C)
Cc.C, $ C.cC, $ C .d, $
C d., $
CcC., c/d
Cc.C, c/d C.cC, c/d C .d, c/d = I3
C d., c/d = I4
CcC., $
I10= (I6, C)
I10= (I6,d)
Cc.C, $ C.cC, $ C .d, $ = I6
C d., $ = I7
09:11
0
c
d
D3
D4
1
$
S
C
1
2
acepta
2
D6
D7
5
3
D3
D4
8
4
R3
R3
5 6
R1 D6
D7
7 Tabla Accion Si [A α.aβ,b] ∈ Ii e IR A(Ii, a) = Ij ⇒ Accion(i, a) = “Desplazar j”. En este caso a debe ser un terminal. Si [A → α.,a] ∈ Ii ⇒Accion(i, a) = “Reducir A → α” Si [S′ → S., $] ∈ Ii ⇒ Accion(i, $) = “Aceptar” Tabla ir a Si IR A(Ii, A)=Ij ⇒ ir-a (i, A) = j Todas las entradas no definidas son error.
ir-a
8 9
9 R3
R2
R2 R2
37 37
Algoritmo para reconocimiento de una hilera: Sea S el estado de la cima de la pila y a el símbolo de la entrada. Entonces: Si Acción [S,a] = desplazar S´, entonces introducir a y S´en la cima de la pila y avanzar el puntero de entrada al siguiente símbolo. Si Acción [S,a] = Reducir A , entonces sacar 2 * || símbolos de la pila, introducir A y después ir-a [S´, A] en la cima de la pila. Emitir la producción A . Si Acción [S,a] = Acepta, entonces aceptar y terminar. Si Acción [S,a] = error, entonces convocar a una rutina de recuperación de error. Acción Estado 0
c
d
D3
D4
1
PILA
ir-a $
S
C
0
1
2
$ 0c3
acepta
$0c3c3
2
D6
D7
5
3
D3
D4
8
4
R3
R3
5
6
R1
D6
D7
7 8 9 09:11
9 R3
R2
R2 R2
ENTRADA
ACCIÓN
ccdd $
D3
cdd $
D3
dd $
D4
$0c3c3d4
d$
R3 C d
$ 0c3c3C8
d$
R2 C cC
$ 0c3C8
d$
R2 C cC
$0C2
d$
D7
$0C2d7
$
R3 C d
$ 0C2C5
$
R1 S CC
$0S1
$
Acepta
0) S´S 1) SCC 2) CcC 3) C d
38 38
Las tablas que se obtienen con LALR son más compacto que LR(1) LALR es menos potente que LR(1) canónico Propuesto por DeRemer en 1969 La idea general del algoritmo es construir los conjuntos de elementos LR(1) y fusionar los conjuntos con corazones comunes. Después se construye la tabla a partir de la serie de conjuntos de elementos fusionados.
Algoritmo 1)Construir C={I0, I1,…,In} la colección de conjuntos de elementos LR(1). 2)Para cada corazón presente entre el conjunto de elementos LR(1) encontrar todos los conjuntos que tengan dicho corazón y sustituir estos conjuntos por su unión. 3)Sea C´={Y0, Y1,…,Ym} los conjuntos de elementos LR(1) obtenidos de la unión. Se construye la tabla acción para el estado i del mismo modo que se hizo con el LR(1). 4)La tabla ir-a se construye de la siguiente manera: Si Y es la unión de uno o más conjuntos de elementos LR(1), es decir, Y=I1 I2 Ik, entonces todos los corazones de ir-a(I1,X), ir-a(I2,X),…., ir-a(Ik,X) son el mismo, puesto que I1, I2,…, Ik tienen todos el mismo corazón. Sea k la unión de todos los conjuntos de elementos que tienen el mismo corazón que ir-a(I1,X) entonces ir-a(Y,X) = k.
09:11
39 39
0) S´S 1) SCC 2) CcC 3) C d
Colección de elementos LR(1) I0
I1=(I0,S)
I2=(I0,C)
I3=(I0, c)
I4= (I0, d)
I5= (I2, C)
S´.S, $ S.CC, $ C.cC, c/d C .d, c/d
S´S. , $
SC.C, $ C.cC,$ C .d, $
Cc.C, c/d C.cC, c/d C .d, c/d
C d., c/d
S CC.,$
I6=(I2,c)
I7=(I2,d)
I8=(I3,C)
I9=(I3, c)
I9= (I3, d)
I9= (I6, C)
Estado
c
d
Cc.C, $ C.cC, $ C .d, $
C d., $
CcC., c/d
Cc.C, c/d C.cC, c/d C .d, c/d = I3
C d., c/d = I4
CcC., $
0
D36
D47
Acción
I10= (I6, C)
I10= (I6,d)
Cc.C, $ C.cC, $ C .d, $ = I6
C d., $ = I7
09:11
1
ir-a $
S
C
1
2
acepta
2
D36
D47
5
36
D36
D47
89
47
R3
R3
5 89
R3 R1
R2
R2
R2
40 40
0) S´S 1) SCC 2) CcC 3) C d Acción Estado
c
d
D36
D47
PILA
ir-a $
S
C
1
2
0 $ 0c36
0
1
acepta
$0c36c36
ENTRADA
ACCIÓN
ccdd $
D36
cdd $
D36
dd $
D47
$0c36c36d47
d$
R3 C d
2
D36
D47
5
$ 0c36c36C89
d$
R2 C cC
36
D36
D47
89
$ 0c36C89
d$
R2 C cC
47
R3
R3
$0C2
d$
D47
5 89
09:11
R3 R1
R2
R2
R2
$0C2d47
$
R3 C d
$ 0C2C5
$
R1 S CC
$0S1
$
Acepta
41 41
• Yacc - Yet Another Compiler-Compiler • ¿Qué es YACC ? – Herramienta que genera automáticamente un parser (analizador sintáctico/semántico) para una gramática dada en especificación YACC (fichero .y). – YACC es un programa diseñado para compilar una gramática LALR(1) y producir el código fuente del analizador sintáctico del lenguaje producido por esta gramática. 42
¿Cómo trabaja YACC?
gram.y
yacc
y.tab.c
cc o gcc
a.out
Fichero que contiene la gramática en formato de yacc
software yacc
Programa fuente C creado por yacc
Compilador C
Analizador sintáctico/semántico. Correspondiente a la gramática dada en gram.y 43
Formato de fichero YACC %{ Declaraciones C %} Declaraciones yacc %% Reglas de gramática %% Código C adicional Comentarios encerrados entre /* y */ pueden aparecer en cualquiera de las secciones.
44
%{ < Variables globales C, prototipos, comentarios >
Esta parte será embebida en el fichero *.c
%}
[SECCIÓN DE DEFINICIONES YACC]
Contiene declaraciones de tokens. Los tokens serán reconocidos por el analizador léxico.
%% [SECCIÓN DE REGLAS DE PRODUCCIÓN] %% < Subrutinas auxiliares C>
Definición de como se estructura el lenguaje de entrada, y qué acciones realizar para cada sentencia. Código de usuario. P. ej., main con llamada al analizador yyparse() 45
Sección de definiciones
%{ #include #include %} %token ID NUM %start expr
Símbolos terminales (tokens) Símbolo inicial de la gramática 46
Sección de reglas %% produccion1 : simbolo1 simbolo2 …{accion} | simbolo3 simbolo4 …{accion} | … produccion2: simbolo1 simbolo2…{accion} %% Ejemplo: expr : expr '+' term | term; term : term '*' factor | factor; factor : '(' expr ')' | ID | NUM;
47
Sección de reglas
$1
Los símbolos terminales van encerrados entre ´´. Las cadenas sin comillas de letras y dígitos no declaradas como componentes léxicos se los considera no terminales. Una acción semántica es una secuencia de proposiciones en C.
expr : expr '+' term { $$ = $1 + $3; } Los símbolos $$ se refiere al valor del | term { $$ = $1; } atributo asociado con el no terminal del lado ; izquierdo. term : term '*' factor { $$ = $1 * $3; } | factor { $$ = $1; } $i se refiere al valor asociado con el i-ésimo ; símbolo gramatical (terminal o no terminal) factor : '(' expr ')' { $$ = $2; } del lado derecho. La acción semántica se | ID realiza siempre que se reduzca por la | NUM producción asociada. Generalmente, la ; acción semántica calcula un valor para $$ en función de $i. Si se omite la acción semántica entonces por defecto: $$ = $1; 48
Valores semánticos %% statement : expression { printf (“ = %g\n”, $1); } expression : expression ‘+’ expression { $$ = $1 + $3; } | expression ‘-’ expression { $$ = $1 - $3; } | NUMBER { $$ = $1; } %%
statement expression
Según estas dos producciones, 5 + 4 – 3 + 2 se transforma en:
expression
expression
number
expression
expression
number
5
+
4
-
expression
expression
number
number
3
+
2
49
Gramática libre de contexto
G = (VN, VT, P , S)
Lenguajes Libre de contexto Obtén siguiente token
Analizador Sintáctico
Autómata de Pila token
A =(Q, , , q0, F)
Obtener una cadena de componentes léxicos del A.L. y comprobar si la cadena puede ser generada por la gramática del lenguaje fuente.
Árbol de análisis sintáctico Herramientas para la construcción automática de analizadores sintáctico como [Yacc] [Bison]. Se basan en la definición de una gramática libre de contexto
50
![ID o]](https://d.documentop.com/img/300x300/id-o_59dfd3511723ddc1f43ebf34.jpg)
