Análisis Sintáctico
Teoría de Autómatas y Lenguajes Formales
Alma María Pisabarro, 2007
ANÁLISIS SINTÁCTICO
Función
• Entrada: sucesión de componentes
léxicos <clex, vlex>
• Salida: la entrada es o no correcta
sintácticamente
Además:
– si la entrada es correcta, árbol de derivación
– si no indicación de errores
Uso de gramáticas independientes de contexto
• Especificación precisa y fácil de entender
• Construcción automática de analizadores sintácticos
• Imparten una estructura al programa fuente, a la que se
asigna el significado. Detección adecuada de errores
• Fácil mantenimiento: evolución del lenguaje
<programa> → <cabecera> <bloque>
<cabecera> → program <identificador>;
<cabecera> → program <identificador> (<ids.archivos>);
<bloque> → <declaraciones y definiciones de entorno>
<def. de subprogramas> <sent. secuencial>.
<sent. secuencial> → begin <sentencias> end
...
TIPOS DE ANÁLISIS SINTÁCTICOS
• Universales (CYK, Earley, ...)
• Descendentes. Subclases de gramáticas adecuadas (LL)
• Ascendentes. Subclases de gramáticas adecuadas (LR)
<programa>
<cabecera>
...
<bloque>
<cabecera>
...
....
program
id
...
program
id
;
begin ...
ERRORES: TIPOS
• Léxicos
(a!b, begon)
• Sintácticos
(X := a *(b-(c+d);;)
• Semánticos
(3 div sqrt(2))
• Lógicos
(bucle infinito)
Consideraciones
• La mayoría de los errores son simples
• La mayoría son o se manifiesten en la fase de
análisis sintáctico
• La detección de errores lógicos es muy difícil o
imposible
• A veces el error está mucho antes de que se
pueda detectar
ERRORES: OBJETIVOS DEL GESTOR DE ERRORES
• Informar con claridad y exactitud
– línea, posición, mensajes (“falta un ;”)
• Recuperarse con rapidez
– No se abandona al primer error
– Introducción de errores espurios (sintácticos o
semánticos): inhibir mensajes de demasiado
cercanos
– Se abandona si hay “muchos” errores
• No retrasar significativamente la
traducción de programas correctos
– Mecanismos sencillos de recuperación
ERRORES: ESTRATEGIAS
• En modo pánico: descartar símbolos de
entrada (hasta que alguno permita la
recuperación: elementos de sincronización)
• A nivel de frase: corrección local según el error
concreto (borrar, sustituir, insertar: peligro de
bucle infinito)
• De producciones de error: prever errores
(frecuentes o probables) ampliando la gramática
con reglas específicas de error
• De corrección global: hallar el programa
correcto más cercano” al de entrada: costoso y
no necesariamente se encuentra el deseado
ANÁLISIS SINTÁCTICO DESCENDENTE
tipo
→
simple →
tipo
simple
tipo
^
simple
simple
simple
integer
char
simple
| ^ simple
| array [simple] of tipo
integer
| char
| num ptpt num
tipo
array [
simple ]
simple
num
ptpt
num
of
tipo
Análisis Sintáctico Predictivo
• Análisis Sintáctico Descendente Recursivo
– Conjunto de procedimientos recursivos
– Cada no terminal de la gramática tiene
asociado un procedimiento
– El símbolo de preanálisis determina sin
ambigüedad el procedimiento seleccionado
para cada no terminal
– Procedimiento adicional parea
procedimiento tipo: según que regla se aplique:
?: { <tipo> → <simple> }
simple
?: { <tipo> → ^ <simple> }
parea (‘^’); simple
?: { <tipo> → array [ <simple> ] of <tipo> }
parea (array); parea ( ‘[‘ ); simple; parea ( ‘]’ ); parea (of); tipo
procedimiento simple: según que regla se aplique:
?: { <simple> → integer }
parea (integer)
?: { <simple> → char }
parea (char)
?: { <simple> → num ptpt num }
parea (num); parea (ptpt); parea (num)
“parea (num); parea(ptpt); parea(num)”
procedure parea (t:TCompLex);
begin
if preanalisis = t then
preanalisis := SgteCompLex()
else error
end;
simple
simple
simple
?
num
ptpt
num
num
parea
ptpt
num
parea
parea
num ptpt num ... ...
num ptpt num ... ....
num ptpt num ... ...
“parea( ‘^’ ); simple”
tipo
tipo
tipo
?
^
simple
^
simple
?
parea
^ char
^ char
^ char
“parea (array); parea (‘[‘); simple; parea (‘]’); parea(of); tipo”
“parea(‘^’); simple”
tipo
tipo
tipo
?
array
[ simple ]
of
tipo
array
[ simple ]
of
tipo
?
array [num ptpt num] of char
array [ num ptpt num ] of char
tipo
array
[ simple ]
array [ num ptpt num ] of char
tipo
of
tipo
array
[ simple ]
of
tipo
?
array [ num ptpt num ] of char
array [ num ptpt num ] of char
Elección de regla a aplicar:
tipo
→ simple | ^ simple | array [ simple ] of tipo
simple → integer | char | num ptpt num
tipo:
• regla 1: preanalisis in [integer, char, num]
• regla 2: preanalisis = ‘^’
• regla 3: preanalisis = array
simple:
• regla 4: preanalisis = integer
• regla 5: preanalisis = char
• regla 6: preanalisis = num
const INTEGER = 257; CHAR = 258; ...
var preanalisis: TCompLex;
function StgteCompLex(): TCompLex;
procedure parea(...)...;
procedure simple;
begin
if preanalisis = INTEGER then
parea (INTEGER)
else if preanalisis = CHAR then
parea (CHAR)
else if preanalisis = NUM then
begin parea(NUM); parea(PTPT); parea(NUM); end
else
error
end;
procedure tipo;
begin
if preanalisis in [INTEGER, CHAR, NUM] then simple
else if preanalisis = ‘^’ then
begin parea(‘^’); simple end
else if preanalisis = ARRAY then
begin
parea(ARRAY); parea(‘[‘); simple;
parea (OF); tipo
end
else error
end;
begin
preanalisis := SgteCompLex(); tipo;
end.
Análisis Sintáctico Predictivo
no Recursivo
• Utilizan una pila en lugar de llamadas
recursivas
• Guiado por una tabla
• Las tablas se construyen directamente
sólo para ciertos tipos de gramáticas
ENTRADA
PILA
a
+
b
$
X
Programa para
Y
análisis sintáctico
Z
predictivo
$
Tabla de análisis
Sintáctico M
SALIDA
Inicialmente:
• Buffer: cadena de entrada finalizada con
el símbolo $
• Pila: símbolo $ y en la cima el símbolo
inicial de la gramática
• Tabla M: Si A es un no terminal y a un
terminal, M[A,a] contiene una regla de
producción de la gramática
• X: Cima de la pila
• A: símbolo de la entrada (preanalisis)
Análisis Sintáctico Predictivo no recursivo
• Si X terminal
– Si X <> a
• Llamar a la rutina de recuperación de error
– Si X = a
• Si X = a = $
– Fin con éxito
• Si X = a <> $
– Sacar X de la pila
– Obtener siguiente símbolo de la entrada
• Si X no terminal
– Si M [X, a] contiene una regla
• Sacar X de la pila
• Meter en la pila la parte derecha de la regla en orden inverso
– Si M [X, a] no contiene una regla
• Llamar a la rutina de recuperación de error
Símbolo de entrada
No terminal
E
E’
T
T’
F
id
+
*
E → TE’
(
$
E → TE
E’ → +TE’
T → FT’
E’ → ε
E’ → ε
T’ → ε
T’ → ε
T → FT’
T’ → ε
T’ → *FT’
F → id
F → (E)
PILA
Gramática:
E → TE’
E’ → +TE’ | ε
T → FT’
T’ → *FT’ | ε
F → (E) | id
)
$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’ → ε
Algoritmo de Análisis Sintáctico Predictivo no recursivo
apuntar ae al primer símbolo de w$
repetir
X  símbolo de la cima de la pila
a  símbolo apuntado por ae
si x es un terminal o $ entonces
si X = a entonces
extraer X de la pila
avanzar ae
si_no error fin_si
si_no
si M[x,a] = X → Y1Y2...Yk entonces
extraer X de la pila
meter Yk, Yk-1, ..., Y1 en la pila, con Y1 en la cima
emitir la producción X → Y1Y2...Yk
si_no error fin_si
fin_si
hasta_que X = $ /*la pila está vacia*/
Funciones PRIMERO y SIGUIENTE
• La función PRIMERO(a) devuelve el conjunto de
terminales que inician las cadenas derivadas de a
• La función SIGUIENTE(a) devuelve el conjunto de
terminales que pueden aparecer inmediatamente
a la derecha de a en alguna forma de frase
• Son funciones asociadas a una gramática G
• Permiten rellenar las entradas de una tabla de
ASP para G
• Los conjuntos de componentes léxicos devueltos
por la función SIGUIENTE se pueden utilizar
como elementos de sincronización durante la
recuperación de errores en modo pánico
FUNCIÓN PRIMERO (X)
Para todos los símbolos X de la gramática
Repetir hasta que no se puedan añadir más símbolos a ningún conjunto
1.
Si existe la regla x → ε
PRIMERO (X) = PRIMERO(X) U {ε}
2.
Si x es un símbolo terminal
PRIMERO (X) = {X}
3.
Si x es un símbolo no terminal
Para cada producción x → y1y2...yk
PRIMERO (X) = PRIMERO (X) U PRIMERO (Y1)
si existe la regla y1 → ε
PRIM (X) = PRIM (X) U PRIM (Y1) U PRIM (Y2)
si existen las reglas y1 → ε y y2 → ε
PRIM (X) = PRIM (X) U PRIM (Y1) U PRIM (Y2) U PRIM (Y3)
....
si existe la regla yn → ε ∀ n=1...k
PRIM (X) = PRIM (X) U PRIM (Y1) U PRIM (Y2) U .... U PRIM (Yk) U {ε}
FUNCIÓN SIGUIENTE (X)
Para todos los símbolos A no terminales de la gramática
Repetir hasta que no se puedan añadir más símbolos a
ningún conjunto
1. Si S es el símbolo inicial de la gramática
SIGUIENTE (S) = SIGUIENTE (S) U {$}
2. Si existe una regla A → αBβ
3.
4.
SIGUIENTE (B) = PRIMERO (β) - {ε}
Si existe una regla A → αB
SIGUIENTE (B) = SIGUIENTE (B) U SIGUIENTE (A)
Si existe una regla A → αBβ y ε ∈ PRIMERO (β)
SIGUIENTE (B) = SIGUIENTE (B) U SIGUIENTE (A)
Gramática:
E → TE’
E’ → +TE’ | ε
T → FT’
T’ → *FT’ | ε
F → (E) | id
SIGUIENTES
PRIMEROS
E E’ T T’ F + *
( + ( * ( + *
id ε id ε id
(
(
) id
) id
E E’ T T’
$ $ $ $
) ) + +
) )
F
$
+
*
)
ALGORITMO DE CONSTRUCCIÓN DE TASP
Entrada: Una gramática G
Salida: La tabla de análisis sintáctico M
Para cada regla X → α de G
1. Para terminal t de PRIMERO (α)
Añadir X → α a M[X, t]
2. Si ε ∈ PRIMERO (α)
Añadir X → α a M[X, b], ∀ b ∈ SIGUIENTE (x)
Si ε ∈ PRIMERO (α) y $ ∈ SIGUIENTE (X)
Añadir X → α a M[X, $]
3. Poner error en todas las entradas no definidas
de M
regla E → TE’
regla E’ → +TE’
regla E’ → ε
regla T → FT’
regla T’ → *FT’
regla T’ → ε
regla F → (E)
regla F → id
PRIMERO (TE’) = PRIMERO (T) = {(, id}
M [ E, ( ] = E → TE’
M [ E, id ] = E → TE’
PRIMERO (+TE’) = PRIMERO (+) = { + }
M [ E’, + ] = E’ → +TE’
SIGUIENTE (E’) = { ), $ }
M [ E’, ) ] = E’ → ε
M [ E’, $ ] = E’ → ε
PRIMERO (FT’) = PRIMERO (F) = {(, id}
M [ T, ( ] = T → FT’
M [ T, id ] = T → FT’
PRIMERO (*FT’) = PRIMERO (*) = { * }
M [ T’, * ] = T’ → *FT’
SIGUIENTE (T’) = { ), +, $ }
M [ T’, ) ] = T’ → ε
M [ T’, + ] = T’ → ε
M [ T’, $ ] = T’ → ε
PRIMERO ((E)) = PRIMERO (() = { ( }
M [ F, ( ] = F → (E)
PRIMERO (id) = { id }
M [ F, id ] = F → id
Símbolo de entrada
No
terminal
id
+
*
E
E → TE’
error
error
E’
error
E’ → +TE’
error
error
T
T → FT’
error
error
T → FT’
T’
error
T’ → *FT’
F
F → id
T’ → ε
error
error
(
E → TE
)
$
error
error
E’ → ε
E’ → ε
error
error
error
T’ → ε
T’ → ε
F → (E)
error
error
GRAMÁTICAS LL(1)
• Si una gramática es recursiva por la izquierda o
ambigua la TASP tendrá al menos una entrada
con definición múltiple. Recurso: Transformar la
gramática
• Una gramática cuya TASP no tiene entradas con
definiciones múltiples se define como LL(1)
– Ninguna gramática ambigua o recursiva por la
izquierda puede ser LL(1)
– G es LL(1), si y solo si, cuando A → α|β siendo dos
reglas distintas de G se cumple:
• PRIMERO (α) ∩ PRIMERO (β) = Ф
• Solo puede derivarse ε de α o de β
• Si β deriva ε, α no deriva ninguna cadena que
comience con un terminal de SIGUIENTE (A)
ANÁLISIS ASCENDENTE
• Estilo general: Análisis sintáctico por
desplazamiento y reducción
– Por precedencia de operadores (gramáticas muy
específicas)
– LR (generadores automáticos de AS)
• Se construye el árbol de AS para una cadena w
a partir de las hojas y se avanza hacia la raíz
– Proceso: reducir w al símbolo inicial de la gramática
– Cada reducción sustituye una subcadena (asidero o
mango) que concuerde con el lado derecho de un
regla de producción por el símbolo no terminal del
lado izquierdo de esa regla
ASIDEROS O MANGOS
• Un asidero 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 es un paso de una
derivación por la derecha
• Ejemplo
S → aABe
A → Abc
A→b
B→d
abbcde
asidero posición 2 (regla A → b)
aAbcde
asidero posición 2 (regla A → Abc)
aAde
asidero posición 3 (regla B → d)
aABe
asidero posición 1 (regla S → aABe)
S
ASIDEROS O MANGOS
• La producción situada más a la izquierda de β
que concuerda con el lado derecho de una
producción A → β no es un asidero si la
reducción por esa regla genera una cadena no
reducible al símbolo inicial
• Ejemplo
S → aABe
A → Abc
A→b
B→d
aAbcde
aunque b es la subcadena situada
más a la izquierda que concuerda
con una parte derecha (regla A → b)
no es un asidero
a A A c d e No se puede reducir a S
ASIDEROS O MANGOS
• Formalmente, un asidero 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 µ
• Ejemplo
E→E+E
E→E*E
E→(E)
E → id
Formas de Frase
Derecha
Asidero
Regla de
Reducción
id1 + id2 * id3
id1
E → id
E + id2 * id3
id2
E → id
E + E * id3
id3
E → id
E+E*E
E*E
E→E*E
E+E
E+E
E→E+E
E
USO DE UNA PILA EN AS POR
DESPLAZAMIENTO Y REDUCCIÓN
• 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 DEL
ANALIZADOR
• Inicialmente:
– En la pila el símbolo de fin de cadena ($)
– En el buffer 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 solo haya el símbolo inicial (E$) y la entrada
está vacía ($)
– Desplazar cero o más símbolos de la entrada a la pila
hasta que en la cima haya un asidero β
– Reducir β al lado izquierdo de la regla adecuada
OPERACIONES DEL ANALIZADOR
• Desplazar: Mover el siguiente símbolo de
entrada a la cima de la pila
• Reducir: (En este momento el extremo derecho
del asidero está en la cima de la pila) Localizar
el extremo izquierdo del asidero dentro de la pila
y decidir el no terminal con el que se debe
sustituir el asidero.
• Aceptar: Anunciar el fin con éxito del análisis
• Error: Llamar a la rutina de recuperación de
errores
pila
$
$ id1
$E
$E+
$ E + id2
$E+E
$E+E*
$ E + E * id3
$E+E*E
$E+E
$E
entrada
acción
id1 + id2 * id3 $ desplazar
+ id2 * id3 $ reducir por E → id
+ id2 * id3 $ desplazar
id2 * id3 $ desplazar
* id3 $ reducir por E → id
* id3 $ desplazar
id3 $ desplazar
$
$
$
$
reducir por E → id
reducir por E → E * E
reducir por E → E + E
aceptar
PREFIJOS VIABLES
• Este método de análisis garantiza que el asidero
siempre aparecerá en la cima de la pila, nunca
dentro
• Los prefijos de las formas de frase derecha que
pueden aparecer en la pila se denominan
prefijos viables
• Un prefijo viable es un prefijo de una forma de
frase derecha que no continua más allá del
extremo derecho del asidero situado más a la
derecha de esta forma de frase
CONFLICTOS
• Existen gramáticas independientes de contexto
para las que no se pueden utilizar analizadores
sintácticos por desplazamiento y reducción
(gramáticas no LR)
• 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)
ANALIZADORES SINTÁCTICOS LR
• Se pueden construir AS LR para casi todos los
lenguajes que se pueden describir con GLC
• Es el método de análisis por desplazamiento y
reducción sin retroceso más general pero
eficiente
• La clase de gramáticas aplicables es un
supraconjunto de las que se pueden analizar con
ASP
• Detectan los errores sintácticos tan pronto como
sea posible en un examen de izquierda a
derecha
• Inconveniente: costosos de construir a mano
ALGORITMO DE ANÁLISIS SINTÁCTICO LR
a1
...
ai
...
an
$
Sm
Xm
S m-1
Programa para análisis
sintáctico LR
X m-1
...
S0
acción
ir_a
SALIDA
ALGORITMO DE ANÁLISIS SINTÁCTICO LR
• Entrada
– Cadena de entrada w
– Tabla de AS LR con las funciones acción e ir_a para
la gramática G
• Salida
– Si w está en L(G) una derivación ascendente
– Si no indicación de error
• Método
– Inicialmente:
• La pila contiene S0 (estado inicial)
• El buffer de entrada contiene w$ (la cadena de entrada
seguida de la marca de fin de cadena)
– Ejecución del programa de análisis hasta encontrar
una acción de aceptación o de error
PROGRAMA DE ANÁLISIS
apuntar ae al primer símbolo de w$
repetir
sea S el estado en la cima de la pila y
a el símbolo apuntado por ae
si accion [S,a]= desplazar S’ entonces
meter a y después S’ en la cima de la pila
avanzar ae al siguiente símbolo de entrada
si_no
si acción [S, a] = reducir A → β entonces
sacar 2 * |β| símbolos de la pila
sea S’ el estado que hay ahora en la cima de la pila
meter en la cima de la pila A y después ir_a [S’, A]
emitir la producción A → β
si_no
si acción [S, a] = aceptar entonces
fin con éxito
si_no error
fin_repetir
EJEMPLO
Gramática
(1) E → E + T
(2) E → T
(3) T → T * F
(4) T → F
(5) F → (E)
(6) F → id
Códigos de las acciones
1. di significa desplazar y
meter en la pila el estado i
2. rj significa reducir por la
regla de número j
3. Acep significa aceptar
4. El espacio en blanco
significa error
TABLA DE ANÁLISIS SINTÁCTICO LR
(para la gramática del ejemplo)
acción
Estado
id
0
d5
+
*
(
ir_a
)
$
d4
1
d6
2
r2
d7
r2
r2
3
r4
r4
r4
r4
4
d4
r6
T
F
1
2
3
8
2
3
9
3
acep
d5
5
E
r6
r6
6
d5
d4
7
d5
d4
r6
10
8
d6
d11
9
r1
d7
r1
r1
10
r3
r3
r3
r3
11
r5
r5
r5
r5
MOVIMIENTOS DEL ANALIZADOR SINTÁCTICO LR DEL EJEMPLO
(para la entrada id * id + id)
PILA
(1) 0
ENTRADA
ACCION
id * id + id $ desplazar
(2) 0 id 5
* id + id $ reducir por F → id
(3) 0 F 3
* id + id $ reducir por T → F
(4) 0 T 2
* id + id $ desplazar
(5) 0 T 2 * 7
id + id $ desplazar
(6) 0 T 2 * 7 id 5
+ id $ reducir por F → id
(7) 0 T 2 * 7 F 10
+ id $ reducir por T → T * F
(8) 0 T 2
+ id $ reducir por E → T
(9) 0 E 1
+ id $ desplazar
(10) 0 E 1 + 6
id $ desplazar
(11) 0 E 1 + 6 id 5
$ reducir por F → id
(12) 0 E 1 + 6 F 3
$ reducir por T → F
(13) 0 E 1 + 6 T 9
$ reducir por E → E + T
(14) 0 E 1
$ aceptar
GENERADORES DE AS: YACC
• Yacc es un generador de analizadores sintácticos LALR
• Resolución de conflictos en Yacc
– Un conflicto reducción/reducción se resuelve eligiendo la regla
en conflicto que se haya listado primero en la especificación en
Yacc
– Un conflicto de desplazamiento/reducción se resuelve a favor
del desplazamiento
• Invocando a Yacc con la opción –v se genera el archivo
y.output que contiene
– Los núcleos de los conjuntos de elementos encontrados por el
analizador sintáctico
– Una descripción de los conflictos en las acciones del análisis
generados por el algoritmo LALR
– Una representación legible de la tabla de análisis sintáctico LR
que muestra como se resolvieron los conflictos de las acciones
del análisis sintáctico
Descargar

Análisis Sintáctico Predictivo