Sesión del Miércoles 21 de Septiembre

En la sesión de hoy les presenté la herramienta YACC (Yet Another Compiler Compiler), que es un generador de analizadores sintácticos en C.

Esta herramienta está diseñada para trabajar en conjunto con LEX (el generador de analizadores léxicos visto en clases pasadas).
Yacc genera analizadores sintácticos ascendentes. Para esto utiliza una pila y operaciones shift (corrimiento) y reduce (reducción).
En este tipo de analizadores puede haber conflictos shift-reduce y reduce-reduce.

Las opciones que Yacc implementa por omisión para resolver estos conflictos son:

• En un conflicto shift-reduce opta por shift.
• En un conflicto reduce-reduce opta por la regla de reducción definida primero en la lista reglas.

Finalmente presenté el ejemplo de una gramática de una caculadora simple que sólo acepta sumas y restas de términos.
A continuación muestro los programas de lex y yacc para este ejemplo.

Analizador léxico

/* calc.l */
%{
#include<stdlib.h>
#include"calc_tab.h"
void yyerror(char *);
%}

%%

[0-9]+  { yylval = atoi(yytext); return INTEGER; }
[-+\n]  return *yytext;
[ \t]   ; /* Elimina espacios */
.       yyerror("caracter invalido");

%%

int yywrap(void)
{
        return 1;
}

Analizador sintáctico

/* calc.y */
%{
  int yyylex(void);
  void yyerror(char *);
%}

%token INTEGER

%%

program: program expr '\n'      {printf("%d\n",$2); }
        |
        ;

expr: INTEGER                   { $$ = $1; }
        | expr '+' expr         { $$ = $1 + $3; }
        | expr '-' expr         { $$ = $1 - $3; }
        ;
%%

void yyerror (char *s)
{
        printf("%s\n",s);
        return;
}

int main(void)
{
        yyparse();
        return 0;
}

Proceso de compilación
El proceso de compilación de esta calculadora requiere los siguientes pasos:

1. Compilar el programa yacc con el comando

    yacc -d calc.y

   que genera los archivos calc_tab.c y calc_tab.h


2. Compilar el progama lex con el comando

   flex -ocalc.c calc.l

   que genera el archivo calc.c


3. Compilar los códigos fuente con un compilador de C. En caso de Turbo C el comando sería

   tcc -ecalc.exe calc_tab.c calc.c

   que genera el ejecutable calc.exe

Para reforzar estos conceptos les recomiendo esta referencia.