YACC - Yet another Compiler-Compiler

¿Qué es YACC?
Es una herramienta que genera automáticamente un parser ( nalizador 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) (ver analizadores LARL) y producir el código fuente del analizador sintáctico del lenguaje producido por esta gramática.
¿Cómo trabaja YACC?

Formato del fichero YACC

%{

Declaraciones en C

%}

Declaraciones YACC

%%

Reglas de Gramática

%%

Código C adicional

Comentarios entre /*  y  */ pueden aparecer en cualquiera de las secciones

%{ 
< Variables globales C, prototipos, comentarios >  Esta parte será enmbebida 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] Definición de cómo se estructura el lenguaje de entrada, y qué acciones realizar para cada sentencia.
%%
<Subrutinas auxiliares C> Código de usuario. Por ejemplo, main con llamada al analizador yyparse().


Sección de definiciones

%{
#include <stdio.h>
#include <stdlib.h>
%}
%token ID NUM  Símbolos terminales (tokens) 
%start expr   Símbolo inicial de la gramática


Sección de reglas


%%
producción1: simbolo1 simbolo2...{accion}
                  | simbolo 3 simbolo4...{accion}
                  | ...
produccion2: simbolo1 simbolo2...{accion}


Ejemplo:
expr: expr '+' term | term;
term: term '*' factor | factor;
factor: '('expr')' | ID | NUM;


Sección de reglas

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.
Los símbolos $$ se refiere al valor del atributo asociado con el no terminal del lado izquierdo.
$i se refiere al valor asociado con el i-ésimo símbolo gramatical (terminal o no terminal) del lado derecho. La acción semántica se realiza siempre que se reduzca por la 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


Valores semánticos


%%
statement: expression { printf("=%g\n",$1);}
expression : expression '+' expression { $$ = $1 + $3; }
                  | expression '-' expresion { $$ = $1 - $3; }
                  | NUMBER { $$ = $1; }


%%


Según estas dos producciones, 5 + 4 - 3 +2 se transforma en: