Análisis
Sintáctico
Análisis Sintáctico.
El
análisis sintáctico es un análisis a nivel de sentencias, y es mucho más
complejo que el análisis léxico. Su función es tomar el programa fuente en
forma de tokens, que recibe del analizador léxico, y determinar la estructura
de las sentencias del programa. Este proceso es similar a determinar la estructura
de una frase en un idioma de habla humana, determinando quien es el sujeto,
predicado, el verbo y los complementos. (Sergio Gálvez Rojas, Traductores,
Compiladores e Intérpretes, 2009).
Manejo de errores sintácticos.
Si un compilador tuviera que
procesar sólo programas correctos, su diseño e implantación se simplificarían
mucho. Pero los programadores a menudo escriben programas incorrectos, y un
buen compilador debería ayudar al programador a identificar y localizar errores.
Es más, considerar desde el principio el manejo de errores puede simplificar la
estructura de un compilador y mejorar su respuesta a los errores.
Los
errores en la programación pueden ser de los siguientes tipos:
•
Léxicos, producidos al escribir mal un identificador, una palabra clave o un operador.
•
Sintácticos, por una expresión aritmética o paréntesis no equilibrados.
•
Semánticos, como un operador aplicado a un operando incompatible.
•
Lógicos, puede ser una llamada infinitamente recursiva.
El
manejo de errores de sintaxis es el más complicado desde el punto de vista de
la creación de compiladores. Nos interesa que cuando el compilador encuentre un
error, se recupere y siga buscando errores. Por lo tanto el manejador de
errores de un analizador sintáctico debe tener como objetivos:
•
Indicar los errores de forma clara y precisa. Aclarar el tipo de error y su localización.
•
Recuperarse del error, para poder seguir examinando la entrada.
•
No ralentizar significativamente la compilación.
Un
buen compilador debe hacerse siempre teniendo también en mente los errores que
se pueden producir; con ello se consigue:
•
Simplificar la estructura del compilador.
•
Mejorar la respuesta ante los errores.
(Sergio
Gálvez Rojas, Traductores, Compiladores e Intérpretes, 2009).
Gramáticas aceptadas por un analizador sintáctico.
Nosotros
nos centraremos en el análisis sintáctico para lenguajes basados en gramáticas formales,
ya que de otra forma se hace muy difícil la comprensión del compilador, y se pueden
corregir, quizás más fácilmente, errores de muy difícil localización, como es
la ambigüedad en el reconocimiento de ciertas sentencias.
La
gramática que acepta el analizador sintáctico es una gramática de contexto
libre, ya vista en el tema Jerarquía de Chomsky el cual nos define esta
gramática como una cuádrupla con elementos:
• G
(N, T, P, S)
N
= No terminales.
T
= Terminales.
P
= Reglas de Producción.
S
= Axioma Inicial
Ejemplo
: Se considera la gramática que reconoce las operaciones aritméticas.
E -> E + T
| T
T -> T * F
| F
F -> ID
| NUM
| ( E )
En el
que: N = {E, T, F} están a la izquierda de la regla.
T = {ID, NUM, ( ,) ,+ ,*}
P = Son las siete reglas de producción.
S = Axioma inicial. Podría ser cualquiera, en
este caso es E.
También
se incluyen la derivaciones por la izquierda vito en el tema anterior y las
asignaciones anteriores.
Árbol Sintáctico.
Es
una representación que se utiliza para describir el proceso de derivación de
una sentencia, recordemos las derivaciones son el proceso de descomposición y
resolución de los autómata de pila, es el intercambio del valor de la derecha
por el valor correspondiente, mejor explicado en la asignación Jerarquía de
Chomsky.
En cierto sentido un árbol
sintáctico es la representación de las derivaciones de modo gráfico y los pasos
para llegar a una respuesta específica o un valor deseado.
Proceso de Análisis Sintáctico.
El
proceso de análisis sintáctico parte justo después de realizar el análisis
léxico, es el paso siguiente y permite un análisis más apegado a un lenguaje
que el anterior, el proceso fundamental del análisis sintáctico parte de los
siguientes puntos.
·
Comprobar si la cadena de
componentes léxicos proporcionada por el analizador léxico puede ser generada
por la gramática que define el lenguaje fuente (Gramática libre de contexto).
·
Construir el árbol de análisis
sintáctico que define la estructura jerárquica de un programa y obtener la
serie de derivaciones para generar la cadena de componentes léxicos. El árbol
sintáctico se utilizara como representación intermedia en la generación de
código.
·
Informar de los errores
sintácticos de forma precisa y significativa y debería estar dotado de un
mecanismo de recuperación de errores para continuar con el análisis.
Analizador sintactico
Comprueba que las sentencias que componen
el texto fuente son correctas en el lenguaje, creando una representación
interna que corresponde a la sentencia analizada. De esta manera se garantiza
que solo serán procesadas las sentencias que pertenezcan al lenguaje fuente.
Durante el análisis sintáctico, así como en las demás etapas se irán mostrando
los errores que se encuentran. En otros términos se puede definir un analizador
sintáctico como el encargado del orden de los tokens que implica agrupar los
componentes léxicos del programa fuente en frases gramaticales que el
compilador utiliza para sintetizar la salida.
Nota: Ejemplo de Error Sintáctico, una expresión
aritmética con mayor número de paréntesis
de apertura que de cierre.
Ejemplo
#1: Arbol
de análisis sintáctico (Describe la estructura sintáctica de la ENTRADA).
posición:=
incial+velocidad*60
En la
expresión inicial+velocidad*60, la frase velocidad * 60 es una unidad lógica,
porque las convenciones usuales de las expresiones aritmeticas indican que la
multiplicación se hace antes que la suma. Puesto que la expresión inicial+
velocidad va seguida de un * , no se agrupa en una sola frase independiente.
Ejemplo
#2: Árbol
de análisis sintáctico (Representación interna más común de la estructura
sintáctica es la que da el árbol sintáctico de la siguiente figura).
Un
árbol sintáctico es una representación compacta del árbol de análisis
sintáctico en el que los operadores aparecen como nodos interiores y los
operando de un operador son los hijos del nodo para ese operador.
Función
del Analizador Sintáctico:
Analizar sintácticamente una cadena de tokens no es
más que encontrar para ella el árbol
sintáctico o de derivación que tiene como raíz
el axioma de la gramática, y como nodos terminales la sucesión ordenada
de símbolos que componen la cadena analizada. En caso de no existir este árbol
sintáctico, la cadena no pertenecerá al
lenguaje y el analizador sintáctico
habrá de emitir el correspondiente mensaje de error. Existen dos formas de
analizar sintácticamente una cadena:
• Análisis
Descendiente: Se
parte del axioma inicial de la gramática y se va descendiendo utilizando las
derivaciones izquierdas, hasta llegar a construir la cadena analizada. ANTLR genera árboles sintácticos descendientes,
escrito en java y genera código en java o c++. Tiene como
ventaja que es buena integración de los analizadores léxicos y sintácticos y
como desventaja, genera analizadores menos eficientes que los generadores YACC.
• Análisis Ascendente: Se va construyendo el árbol desde sus nodos terminales.
Es decir, se construye desde los símbolos de la cadena hasta llegar al axioma
de la gramática. Simultáneamente a la
fase de análisis sintáctico, además de reconocer las secuencias de tokens y
analizar su estructura, pueden realizarse una serie de tareas adicionales como:
Recopilar
información de los distintos tokens y almancenarla en la tabla de símbolos.
Realizar
algún tipo de análisis semántico, tal como la comprobación de tipos.
Generar
Código Intermedio.
Avisar
de los errores que se detecten.
JAVACC
inicialmente se llamó JACK
es similar al ANTLR y genera árboles ascendentes. Tiene como ventaja
que es buena integración en los analizadores léxicos y sintácticos. Genera
analizadores sintácticos y por lo siguiente árboles sintácticos y como desventaja,
analizadores menos eficientes.
Ejemplo: Construir una Calculadora. (Analizador
sintactico)
Especificaciones sintácticas:
El lenguaje a reconocer viene definido por la
siguiente gramática:
Calculadora:
id = Expresion ;
Expresión:
num |
Expresion +Expresion |
Expresion -Expresion |
Expresion * Expresion |
Expresion /Expresion |
(Expresion )| sen
(Expresion )| cos (Expresion)
Mostrar Código Ejemplo:
Para
una pequeña calculadora que permite trabajar con numeros enteros y reales con
las operaciones básicas de suma, resta, producto, division y trigonometricas
como el seno y el coseno.
Fichero lexico
#include <stdio.h>
#include
<stdlib.h>
int nlines=0;
%}
DIGITO [0-9]
ID [a-zA-Z][a-zA-Z0-9_]*
%%
{DIGITO}+
{printf("Encontrado
TKN_NUM_ENTERO:%d",atoi(yytext));}{DIGITO}+"."{DIGITO}+ {printf("Encontrado
TKN_NUM_REA%f",atof(yytext));}
"=" {printf("Encontrado
TKN_ASIGN: %s",yytext);}
";" {printf("Encontrado TKN_PTOCOMA:
%s",yytext);}
"*" {printf("Encontrado
TKN_MULT: %s",yytext);}
"/" {printf("Encontrado TKN_DIV:
%s",yytext);}
"+" {printf("Encontrado TKN_MAS:
%s",yytext);}
"-" {printf("Encontrado
TKN_MENOS: %s",yytext);}
"(" {printf("Encontrado TKN_PAA:
%s",yytext);}
")" {printf("Encontrado TKN_PAC:
%s",yytext);}
"cos" {printf("Encontrado TKN_COS:
%s",yytext);}
"sen" {printf("Encontrado TKN_SEN: %s",yytext);}
{ID} {printf("Encontrado TKN_ID:
%s",yytext);}
"\n" {nlines++;}
.
%%
void main(int argc,char
**argv)
{
if (argc>1)
yyin=fopen(argv[1],"rt");
else
yyin=stdin;
yylex();
printf("\nNumerolineas analizadas:
%d\n", nlines);
}
/* para compilar
flex lexico.l
cc lex.yy.c -o milex -lfl -lm
*/
Fichero lexico (Version a enlazar con Bison):
#include <stdio.h>
#include
<stdlib.h>
#include
"sintactico.tab.h"
int nlines=0;
%}
DIGITO [0-9]
ID [a-zA-Z][a-zA-Z0-9_]*
%%
{DIGITO}+("."{DIGITO}+)?
{//printf("Encontrado TKN_NUM: %f\n",atof(yytext));
yylval.real=atof(yytext);
return(TKN_NUM);}
"=" {//printf("Encontrado TKN_ASIGN:
%s\n",yytext);
return(TKN_ASIGN);}
";" {//printf("Encontrado TKN_PTOCOMA:
%s\n",yytext);
return(TKN_PTOCOMA);}
"*" {//printf("Encontrado TKN_MULT:
%s\n",yytext);
return(TKN_MULT);}
"/" {//printf("Encontrado TKN_DIV:
%s\n",yytext);
return(TKN_DIV);}
"+" {//printf("Encontrado TKN_MAS:
%s\n",yytext);
return(TKN_MAS);}
"-" {//printf("Encontrado TKN_MENOS:
%s\n",yytext);
return(TKN_MENOS);}
"(" {//printf("Encontrado TKN_PAA:
%s\n",yytext);
return(TKN_PAA);}
")" {//printf("Encontrado TKN_PAC:
%s\n",yytext);
return(TKN_PAC);}
"cos" {//printf("Encontrado TKN_COS:
%s\n",yytext);
return(TKN_COS);}
"sen" {//printf("Encontrado TKN_SEN:
%s\n",yytext);
return(TKN_SEN);}
{ID} {//printf("Encontrado TKN_ID:
%s\n",yytext);
return(TKN_ID);}
"\n" {nlines++;}
%
/********
Para el lexico solo
void main(int argc,char **argv)
{
if (argc>1)
yyin=fopen(argv[1],"rt");
else
yyin=stdin;
yylex();
printf("\nNumero
lineas analizadas: %d\n", nlines);
}
*******/
/* para compilar flex
lexico.lcc lex.yy.c -o milex -lfl -lm*/
Fichero Sintactico.y
(Bison)
#include <stdio.h>
#include
<stdlib.h>
#include <math.h>
extern int yylex(void);
extern char *yytext;
extern int nlines;
extern FILE *yyin;
void yyerror(char *s);
%}
%union
{
float real;
}
%start Calculadora
%token <real>
TKN_NUM
%token TKN_ASIGN
%token TKN_PTOCOMA
%token TKN_MULT
%token TKN_DIV
%token TKN_MAS
%token TKN_MENOS
%token TKN_PAA
%token TKN_PAC
%token TKN_COS
%token TKN_SEN
%token <real
> TKN_ID
%type Calculadora
%type <real> Expresion
%left TKN_MAS TKN_MENOS
%left TKN_MULT TKN_DIV
%%
Calculadora : TKN_ID { printf("El valor de
%s es: ", yytext);}
TKN_ASIGN Expresion TKN_PTOCOMA {
printf("%5.2f\n", $4); } ;
Expresion :
TKN_NUM {$$=$1;}|
Expresion TKN_MAS Expresion {$$=$1+$3;}|
Expresion TKN_MENOS Expresion {$$=$1-$3;}|
Expresion TKN_MULT Expresion {$$=$1*$3;}|
Expresion TKN_DIV Expresion {$$=$1/$3;} |
TKN_PAA
Expresion TKN_PAC {$$=$2;}|
TKN_COS TKN_PAA Expresion TKN_PAC {$$=cos($3);}|
TKN_SEN TKN_PAA
Expresion TKN_PAC {$$=sin($3);};
%%
void yyerror(char *s)
{
printf("Error
%s",s);
}
int main(int argc,char
**argv)
{
if (argc>1)
yyin=fopen(argv[1],"rt");
else
yyin=stdin;
yyparse();
printf("FIN del Analisis. Entrada
CORRECTA\n");
printf("Numero lineas analizadas:
%d\n", nlines);
return 0;
}
/* para compilar bison -d sintactico.yflex
lexico.lcc lex.yy.c sintactico.tab.c -o analizador -lfl -lm*/
Para el lenguaje creado simulador de
calculadora se toma las siguientes características o sintaxis:
X es
la variable que guardara el resultado
= es
el operador que asignara el resultado de la operación a la variable X
Luego
se procede a colocar 2 cifras a operar.
Y por
ultimo el operando +, -, *, /. De la operación que se desea realizar finalizado
por un ;
De lo
contrario el programa se cerrara.
Ejemplo 1: SUMA
Ejemplo 2: RESTA
Ejemplo 3: DIVISION
Ejemplo 4: MULTIPLICACION
Ejemplo 5: ASIGNACION DE VALOR
En el
caso de haber un error el programa se cerrara sin mostrar ningún detalle.
Referencia Bibliográfica
Vanegas,
C. A. (2013). Compiladores: un enfoque. Vínculos,
1(2), 59-66.
Palacios,
R. H., & González, D. H. (2014). Herramientas para el diseño de
compiladores. CIENCIA HUASTECA, 1(2).
Sethi, R., & Ullman, J. D. (1998). Compiladores:
principios, técnicas y herramientas. Pearson Educación.
0 comentarios:
Publicar un comentario