Analizador léxico sintáctico C

En las universidades es una practica común para todos los estudiantes del área de computación el hacer un analizador léxico sintáctico, que son los pasos previos para realizar un compilador.Empecemos con las definiciones de ambos.

Analizador Léxico: Un analizador léxico o analizador lexicográfico (en inglés scanner) es la primera fase de un compilador consistente en un programa que recibe como entrada el código fuente de otro programa (secuencia de caracteres) y produce una salida compuesta de tokens (componentes léxicos) o símbolos. Estos tokens sirven para una posterior etapa del proceso de traducción, siendo la entrada para el analizador sintáctico (en inglés parser).

La especificación de un lenguaje de programación a menudo incluye un conjunto de reglas que definen el léxico. Estas reglas consisten comúnmente en expresiones regulares que indican el conjunto de posibles secuencias de caracteres que definen un token o lexema.

En algunos lenguajes de programación es necesario establecer patrones para caracteres especiales (como el espacio en blanco) que la gramática pueda reconocer sin que constituya un token en sí.

Analizador sintactico: Un analizador sintáctico (o parser) es un programa informático que analiza una cadena de símbolos de acuerdo a las reglas de una gramática formal. El término proviene del Latín pars, que significa parte (del discurso). Usualmente hace parte de un compilador, en cuyo caso, transforma una entrada en un árbol sintáctico de derivación.¹​²​

El análisis sintáctico convierte el texto de entrada en otras estructuras (comúnmente árboles), que son más útiles para el posterior análisis y capturan la jerarquía implícita de la entrada. Un analizador léxico crea tokens de una secuencia de caracteres de entrada y son estos tokens los que son procesados por el analizador sintáctico para construir la estructura de datos, por ejemplo un árbol de análisis o árboles de sintaxis abstracta.

El análisis sintáctico también es un estado inicial del análisis de frases de lenguaje natural. Es usado para generar diagramas de lenguajes que usan flexión gramatical, como los idiomas romances o el latín. Los lenguajes habitualmente reconocidos por los analizadores sintácticos son los lenguajes libres de contexto. Cabe notar que existe una justificación formal que establece que los lenguajes libres de contexto son aquellos reconocibles por un autómata de pila, de modo que todo analizador sintáctico que reconozca un lenguaje libre de contexto es equivalente en capacidad computacional a un autómata de pila.

Los analizadores sintácticos fueron extensivamente estudiados durante los años 1970, detectándose numerosos patrones de funcionamiento en ellos, cosa que permitió la creación de programas generadores de analizadores sintácticos a partir de una especificación de la sintaxis del lenguaje en forma Backus-Naur por ejemplo, tales como yacc, GNU bison y javaCC.

En los años 50's fue un tema muy estudiado, por lo que se realizaron herramientas para generarlos, donde uno de los mas óptimos es flex de GNU y bison de GNU tambien, estas herramientas son distribuidas de forma libre debido a que pertenecen a los proyectos de software libre. Si decides investigar mas a detalle la historia de estas herramientas, te sorprenderás al descubrir que miembros muy importantes en mundo de la computación estan implicados, tales como Richard Stallman y el CEO de google. Mientras tanto solo nos acomoda entender flex como una herramienta para generar un analizador lexico y a bison como una herramienta para generar analizador sintáctico.

Se dara por supuesto que ya cuentas con ambas herramientas instaladas, debido a que para poder  ejecutar el ejemplo, necesitaras instalar apropiadamente flex y bison. 

1.-Generar el archivo c.l

El archivo se compone de tres partes

definiciones

%%

reglas

%%

código del usuario

El contenido del archivo es el siguiente:

%{

#include "c.tab.h" 
int lineno=1;
int num_caracteres=1;
void yyerror(char *s);
%}



%%
"main" {return MAIN;}
"return" {return RETURN;}
"printf" {return PRINTF;}
"if" |
"while" |
"do" |
"for" {return CONDITIONAL;}
";" {return PCOMA;}
"=" |
"<=" |
">=" |
"<" |
">" |
"==" |
"!=" {return COMPARISION;}
"int" |
"double" |
"float" |
"long" |
"void" |
"char" {return DECLARACION;}  
"{" |
"}" |
"(" |
")" |
"[" |
"]" {return DELIMITADORES;}
"+" {return SUMA;}
"-" {return RESTA;}
"*" {return MULTIPLICACION;}
"/" {return DIVISION;} 
"++" {return INCREMENTO;}
"--" {return DECREMENTO;}
\x22 {return COMILLA;}
"," {return COMA;}
"%s" |
"%c" |
"%d" |
"%f" {return VAL;}
[0-9]+ |
[0-9]+". "[0-9]* |
"."[0-9]* { return NUMERO; }
[ \t] ; /* ignore whitespace */
[a-zA-Z_][a-zA-Z_0-9-]* {return NOMBRE;}
\n lineno++;
. ;
%%

int yywrap() { return 1; }

void yyerror(char *s) {
printf ("%d: %s at %s\n", lineno, s, yytext) ;
}

El analizador léxico contendrá todas las palabras reservadas, operadores y delimitadores que se usaran para la gramática que se definirá en el archivo c.y el cual es un archivo bison, la función  yyerror solo se encargara de imprimir el numero de linea donde se detecta el error y el carácter que lo ocasiona. El archivo c.y queda de la siguiente forma:

%{
/*
* A lexer for the basic gramar to use for recognizing mlish sentences.
*/
#include <stdio.h>
extern int lineno;
%}

%token MAIN DESCONOCIDO NOMBRE NUMERO PCOMA PRINTF VAL RETURN
%token CONDITIONAL DELIMITADORES COMPARISION COMILLA COMA MAIN
%token DECLARACION OPERACIONES INCREMENTO DECREMENTO SUMA RESTA MULTIPLICACION DIVISION

%%

sentence : input
| input principal {printf("No hay errores de sintaxis");}
;

input: /* vacío */
| input line
;

line:     '\n'
        | sencondicion
| declaraciones
| sencondicion '\n'  
| declaraciones '\n'
| operaciones
| operaciones '\n'
| imprimir
| imprimir '\n'
| retornar
| retornar '\n'
;





sencondicion: condicion delimitador variable comparacion variable delimitador delimitador input delimitador {if($4=='=')
{ yyerror("no se permite asignacion"); exit(1);}
else{if(($2!='(') || ($6!=')')) yyerror("falta parentecis"); exit(1);}}
| condicion delimitador variable comparacion numero delimitador delimitador input delimitador
| condicion delimitador variable comparacion numero delimitador input
| condicion delimitador variable comparacion variable delimitador input
;


declaraciones : tipo variable comparacion numero pcoma {/*if($5==';')   {yyerror("falta ;");exit(1);}*/}
   | tipo variable comparacion variable pcoma {/*if($5==';')  {yyerror("falta ;");exit(1);}*/}
   | tipo variable pcoma {if($3!=';') yyerror("falta ;");exit(1);}
   | tipo variable delimitador numero delimitador comparacion numero pcoma { if(($3!='[') && ($5!=']')) yyerror("falta '[' o '] '");exit(1);}
   | tipo variable delimitador numero delimitador pcoma { if(($3!='[') && ($5!=']')) yyerror("falta '[' o '] '");exit(1);}
   | tipo variable comparacion {if($3!='=') yyerror("Solo se permite asignacion");exit(1);}
   ;

operaciones : variable comparacion numero division numero pcoma {/*if($5 == 0){yyerror("no es posible division entre 0"); exit(1);}*/}
| variable comparacion variable division variable pcoma
| variable comparacion variable division numero pcoma
| variable comparacion numero division variable pcoma
| variable comparacion numero suma numero pcoma 
| variable comparacion variable suma variable pcoma
| variable comparacion variable suma numero pcoma 
| variable comparacion numero suma variable pcoma 
| decremento variable pcoma
| variable decremento pcoma
| variable incremento pcoma 
| incremento variable pcoma
| variable comparacion numero multiplicacion numero pcoma
| variable comparacion variable multiplicacion variable pcoma
| variable comparacion variable multiplicacion numero pcoma
| variable comparacion numero multiplicacion variable pcoma
| variable comparacion numero resta numero pcoma
| variable comparacion variable resta variable pcoma 
| variable comparacion variable resta numero pcoma
| variable comparacion numero resta variable pcoma
;
imprimir : printf delimitador comilla variable comilla delimitador pcoma
   | printf delimitador comilla val variable comilla coma variable delimitador pcoma
   | printf delimitador comilla variable val comilla coma variable delimitador pcoma
   ;
retornar : return variable pcoma
   | return numero pcoma
   ;

principal : main delimitador delimitador delimitador input delimitador
    | main delimitador tipo variable delimitador delimitador input delimitador
    | tipo main delimitador delimitador delimitador input delimitador
    | tipo main delimitador tipo variable delimitador delimitador input delimitador
    | tipo main delimitador tipo variable coma tipo variable delimitador delimitador input delimitador
    ;
main : MAIN
;
   
tipo : DECLARACION
;
pcoma : PCOMA
  ;
suma :    SUMA
;    
resta : RESTA
   ;
multiplicacion:  MULTIPLICACION
   ;
   
division : DIVISION
   ;
incremento : INCREMENTO
   ;
decremento :  DECREMENTO
;
;
variable : NOMBRE
   ;
numero : NUMERO
;    
condicion : CONDITIONAL
;
delimitador : DELIMITADORES

comparacion : COMPARISION
;    
printf : PRINTF
;
comilla : COMILLA
;
coma : COMA
;
val : VAL
;
return : RETURN
;
%%
extern FILE *yyin;

int main(argc,argv)
int argc;
char **argv;
{
char filename[40];
++argv, --argc; /* se salta el nombre del programa */
if (argc>0)
yyin = fopen(argv[0], "r");

else
{
printf("Introduzca el nombre del fichero de entrada: ");
scanf("%s", &filename);
yyin = fopen(filename, "r");
}
yyparse();

}

El archivo c.y tiene las mismas características que el archivo c.l , solo que en la sección de las reglas contendrá la gramática en formato simplificado BNF,  de la siguiente manera:

principal : main delimitador delimitador delimitador input delimitador
    | main delimitador tipo variable delimitador delimitador input delimitador
    | tipo main delimitador delimitador delimitador input delimitador
    | tipo main delimitador tipo variable delimitador delimitador input delimitador
    | tipo main delimitador tipo variable coma tipo variable delimitador delimitador input delimitador
    ;

La primera linea main delimitador delimitador delimitador input delimitador puede traducirse como

                           main() {  

                                        input // input tambien tiene una definición de gramática 

                            } 

Para compilarlo se hará de la siguiente manera:

bison -d c.y

Este comando va a generar los archivos c.tab.h y c.tab.c

flex c.l

Este comando generara el archivo lex.yy.c 

Una vez generados los archivos, el siguiente paso es compilar la aplicación para generar el analizador. La compilación se genera con el siguiente comando:

gcc c.tab.c lex.yy.c -L "C:\GnuWin32\lib" -lfl -o analizador

Este comando va a juntar los archivos generados por flex y bison en una compilación en c que sera el archivo analizador.exe


Una vez generado el ejecutable le podemos cargar al programa un archivo de código en c con el que hará el análisis léxico sintáctico.

Fuentes:

Analizador Léxico

Analizador Sintáctico

Unix Text Processing Tools flex and bison Editorial O'Relly
Compilers: Principles, Techniques, and Tools 1st Alfred V. Aho  (Author),‎ Ravi Sethi  (Author),‎ Jeffrey D. Ullman  (Author)

A continuación te dejo el enlace a github para ver el proyecto y un breve vídeo explicativo.