Nel precedente listato abbiamo visto la grammatica, che è in un formato conforme al linguaggio accettato da Yacc. Adesso che abbiamo idea di come funziona l'analizzatore lessicale e le grammatiche, possiamo procedere a descrivere il seguente listato, che genera il parser, completo delle azioni semantiche.

%{

#define VERSION "v0.1"

#include <stdlib.h>
#include <stdio.h>
#include <ctype.h>

int line_nr;
void yyerror(char *s);
int yywrap(void);
char* make_var(char*);

%}

/*** TERMINAL TOKENS */

%token SEP
%token GE
%token LE
%token NE
%token AND
%token OR
%token NOT
%token LET
%token FOR
%token TO
%token NEXT
%token WHILE
%token WEND
%token IF
%token THEN
%token ELSE
%token ENDIF
%token PRINT
%token INPUT
%token INTEGER
%token VARIABLE
%token STRING

/*** VALUE STACK TYPE DEFINITION */

%union {
char* str;
}

%type <str> INTEGER
%type <str> VARIABLE
%type <str> STRING
%type <str> primary.expression
%type <str> unary.expression
%type <str> multiplicative.expression
%type <str> additive.expression
%type <str> relational.expression
%type <str> equality.expression
%type <str> AND.expression
%type <str> OR.expression
%type <str> expression

/*** STARTING RULE */

%start program

%%

/*** EXPRESSIONS */

primary.expression:
VARIABLE
{ printf("%s", make_var($1)); free($1); } 
| INTEGER
{ printf("%s", $1); free($1); }
| '(' 
{ printf("( "); } 
expression ')'
{ printf(" )"); } 
;

unary.expression:
primary.expression 
| '+' { printf("+ "); } primary.expression 
| '-' { printf("- "); } primary.expression 
| NOT { printf("! "); } primary.expression 
;

multiplicative.expression:
unary.expression
| multiplicative.expression '*' 
{ printf(" * "); } 
unary.expression
| multiplicative.expression '/' 
{ printf(" / "); } 
unary.expression
;

additive.expression:
multiplicative.expression
| additive.expression '+' 
{ printf(" + "); } 
multiplicative.expression
| additive.expression '-' 
{ printf(" - "); } 
multiplicative.expression
;

relational.expression:
additive.expression
| relational.expression '<' 
{ printf(" < "); } 
additive.expression
| relational.expression '>'
{ printf(" > "); } 
additive.expression 
| relational.expression LE 
{ printf(" <= "); } 
additive.expression
| relational.expression GE 
{ printf(" >= "); } 
additive.expression 
;

equality.expression:
relational.expression
| equality.expression '=' 
{ printf(" == "); } 
relational.expression
| equality.expression NE 
{ printf(" != "); } 
relational.expression
;

AND.expression:
equality.expression
| AND.expression AND 
{ printf(" && "); } 
equality.expression
;

OR.expression:
AND.expression
| OR.expression OR 
{ printf(" || "); } 
AND.expression
;

expression:
OR.expression
;

/*** STATEMENTS */

sep.list: 
SEP
| sep.list SEP 
;

sep.list.opt : | sep.list ;

statement.list:
statement
| statement.list sep.list statement 
;


statement:
assignment.statement
| for.statement
| while.statement
| if.statement
| print.statement
| input.statement
;

assignment.statement:
LET VARIABLE '=' 
{ printf("%s = ", make_var($2)); free($2); } 
expression
{ printf(";\n"); } 
| VARIABLE '=' 
{ printf("%s = ", make_var($1)); free($1); } 
expression
{ printf(";\n"); } 
;

for.statement:
FOR VARIABLE '=' 
{ printf("for(%s = ", make_var($2)); } 
expression TO 
{ printf("; %s <= ", make_var($2)); } 
expression sep.list
{ printf("; ++%s) {\n", make_var($2)); } 
statement.list sep.list NEXT
{ printf("}\n"); free($2); }
;

while.statement:
WHILE 
{ printf("while("); }
expression sep.list
{ printf(") {\n"); }
statement.list sep.list WEND
{ printf("}\n"); }
;


if.statement:
IF
{ printf("if("); }
expression THEN 
{ printf(") {\n"); } 
sep.list.opt statement.list sep.list.opt else.statement.opt
{ printf("}\n"); } 
;

else.statement.opt:
ENDIF
| ELSE
{ printf("} else {\n"); } 
sep.list.opt statement.list sep.list.opt ENDIF
print.statement:
PRINT
{ printf("printf(\"\\n\");\n"); } 
| PRINT VARIABLE
{ printf("printf(\"%%d\\n\", %s);\n", make_var($2)); free($2); } 
| PRINT VARIABLE ';'
{ printf("printf(\"%%d\", %s);\n", make_var($2)); free($2); } 
| PRINT STRING
{ printf("printf(%s \"\\n\");\n", $2); free($2); }
| PRINT STRING ';'
{ printf("printf(%s);\n", $2); free($2); }
;

input.statement:
INPUT VARIABLE
{ printf("scanf(\"%%d\", &%s);\n", make_var($2)); free($2); }
;
program: 
sep.list.opt statement.list sep.list.opt
;


%%

#include "lex.yy.c"

/* error function */
void yyerror(char *s)
{
fprintf(stderr, "syntax error in line %ld: %s\n", line_nr, yytext);
exit(1);
}


/* make_var: build a new variable;
this uses a very simple scheme: 
all variables are members of the "var" array and indexed 
using the first character 
*/
char* make_var(char* s) {
static char buf[]="var['X'-'A']";
buf[5]=toupper(s[0]); /* 5: position of the X in buf */
return buf;
}

/* main */
int main(int argc, char** argv) {

#ifdef YYDEBUG
yydebug=1;
#endif

fprintf(stderr, 
"b2c " VERSION " (c) 1996 Michele Sciabarra'"
"\nPrototype of a BASIC-to-C compiler"
"\nWritten for Computer Programming\n\n"); 

if(argc!=2) {
fprintf(stderr, "usage: b2c <filename>\n");
exit(0);
} else if(strcmp(argv[1], "-")==0) {
fprintf(stderr, "\nreading STDOUT - press ^D to end\n");
} else if(freopen(argv[1], "rt", stdin)==NULL) {
fprintf(stderr, "cannot open %s\n", argv[1]);
exit(0);
}

line_nr=1;
printf("#include <stdio.h>\nint main(void) {\nint
var[26];\n");
yyparse();
printf("\nreturn(0);\n}\n");
exit(0);
}

Analogamente al Lex, anche l'input di Yacc è diviso in tre parti, separate da %%. La prima parte è dedicata alle dichiarazioni, la seconda alla grammatica e la terza al codice di supporto. Anche in questo caso è possibile incorporare codice C direttamente nella prima parte includendolo tra %{ e %}, è possibile associare codice ad ogni regola grammaticale nella seconda parte includendolo tra { e }, mentre la terza parte è soltanto codice C.

Tra le cose che è possibile dichiarare nella prima parte, abbiamo innanzitutto i token, utilizzando %token. La funzione yylex() ritorna sempre un intero, e infatti Yacc i token devono essere codificati come interi. Siccome i valori da 1 a 255 sono riservati per token corrispondenti a singoli caratteri, una dichiarazione come

%token SEP 
%token GE
viene espansa in qualcosa come 
#define SEP 258
#define GE 259

I valori assegnati variano in dipendenza della particolare implementazione di Yacc. La dichiarazione %union riguarda il tipo dei valori associati a token e non-terminali della grammatica. Consideriamo una regola grammaticale:

primary.expression: 
INTEGER 
{ printf("%s", $1); }
| '(' expression ')'
{ $$ = $2; }
;

Si tratta di una versione semplificata di una regola tratta dal precedente. In questo esempio, primary.expression ed expression sono non-terminali, mentre '(', INTEGER e ')' sono token. Sia token (o terminali) che non-terminali vengono chiamati simboli.

Il parser, secondo un algoritmo che non descriveremo (lo considereremo un dettaglio implementativo, vedere [2] per maggiori informazioni), riconosce le regole grammaticali da cui sono derivati i costrutti del linguaggio che sta analizzando. Il parser generato da Yacc fornisce supporto anche l'implementazione di azioni semantiche: ad ogni simbolo sono associati dei dati, che possono essere manipolati contestualmente al riconoscimento delle regole grammaticali dal codice delle azioni semantiche. Ogni azione semantica utilizza i dati associati a ogni simbolo utilizzando la notazione $$ per il simbolo in testa alla regola, e $1, $2, ... $i per riferirsi all’i-esimo simbolo nel corpo di una alternativa della regola.

Per esempio l'azione semantica { $$=$2; } assegna il valore associato al simbolo expression (che è il secondo simbolo nel secondo ramo della regola) al simbolo primary.expression che è la testa della regola. Le azioni semantiche possono essere inserite in qualunque punto in una regola, dove può essere inserito un simbolo, purché questo non renda la grammatica ambigua. Notare che una azione semantica conta come un simbolo e può perfino avere associato un valore. Nello scrivere una azione semantica occorre tenere presente che essa non può utilizzare un valore che non è stato ancora calcolato. Per esempio:

head : sym1 { $$ = $1 + $3; } sym3

è sbagliata. Infatti $1 si riferisce a sym1, ma $3 si riferisce a sym3 che non è stato ancora calcolato dal parser e quindi il suo valore è indefinito.

Infine notiamo che i valori associati ai simboli possono essere tipizzati. L'insieme di tutti i possibili tipi per i simboli deve essere dichiarato con la direttiva %union, mentre il tipo di ogni simbolo va specificato con la direttiva %type. Nell'esempio del listato l'unico tipo associato a tutti i simboli è char*, ma consideriamo un altro esempio:

%union {
int i;
char* s;
}
%type <i> int 
%type <s> str
%%
prog: int str { printf("%d %s", $1, $2); }

In questo caso abbiamo tipizzato il non-terminale int con un valore intero e il non-terminale str come un puntatore a carattere. Quindi abbiamo dichiarato con la %union due campi, uno chiamato i in corrispondenza dell'intero e uno chiamato s in corrispondenza del puntatore a carattere. Per tipizzare un simbolo usiamo la %type per associarvi il campo della %union del tipo che vogliamo. Il codice generato sarà tale che al posto di $1 ci sarà una espressione di tipo int e al posto di $2 una espressione di tipo char*. Non solo: eventuali errori di tipo saranno rilevati. Se scrivessimo nell'esempio, al posto della printf, { $1 = $2; }, Yacc genererebbe un messaggio di avvertimento per il fatto che sono stati assegnati tipi incompatibili. Questa caratteristica è molto utile per rilevare errori quando si hanno molte regole con molti tipi diversi.