El Generador de Analizadores byacc

Existe una version del yacc de Berkeley que permite producir código para Perl:

> byacc -V
byacc: Berkeley yacc version 1.8.2 (C or perl)

Se trata por tanto de un generador de analizadores LALR. Es bastante compatible con AT&T yacc. Puedes encontrar una versión en formato tar.gz en nuestro servidor http://nereida.deioc.ull.es/˜pl/pyacc-pack.tgz o también desde http://www.perl.com/CPAN/src/misc/.

El formato de llamada es:

byacc  [ -CPcdlrtv ] [ -b file_prefix ] [ -p symbol_prefix ] filename

Las opciones C o c permiten generar código C. Usando -P se genera código Perl. Las opciones d y v funcionan como es usual en yacc. Con t se incorpora código para la depuración de la gramática. Si se especifica l el código del usuario no es insertado. La opción r permite generar ficheros separados para el código y las tablas. No la use con Perl.

Fichero conteniendo la gramática:

%{
%}

%token INT EOL
%token LEFT_PAR RIGHT_PAR
%left PLUS MINUS
%left MULT DIV

%%
start:	|
		start input
	;

input:		expr EOL	{ print $1 . "\n"; }
	|	EOL
	;

expr:		INT		{ $p->mydebug("INT -> Expr!"); $$ = $1; }
	|	expr PLUS expr	{ $p->mydebug("PLUS -> Expr!"); $$ = $1 + $3; }
	|	expr MINUS expr	{ $p->mydebug("MINUS -> Expr!"); $$ = $1 - $3; }
	|	expr MULT expr	{ $p->mydebug("MULT -> Expr!"); $$ = $1 * $3; }
	|	expr DIV expr	{ $p->mydebug("DIV -> Expr!"); $$ = $1 / $3; }
	|	LEFT_PAR expr RIGHT_PAR { $p->mydebug("PARENS -> Expr!"); $$ = $2; }
	;
%%

sub yyerror {
    my ($msg, $s) = @_;
    my ($package, $filename, $line) = caller;
    
    die "$msg at <DATA> \n$package\n$filename\n$line\n";
}

sub mydebug {
    my $p = shift;
    my $msg = shift;
    if ($p->{'yydebug'})
    {
        print "$msg\n";
    }
}

La compilación con byacc del fichero calc.y conteniendo la descripción de la gramática produce el módulo Perl conteniendo el analizador.

> ls -l
total 12
-rw-r-----    1 pl       casiano        47 Dec 29  2002 Makefile
-rw-r-----    1 pl       casiano       823 Dec 29  2002 calc.y
-rwxr-x--x    1 pl       casiano       627 Nov 10 15:37 tokenizer.pl
> cat Makefile
MyParser.pm: calc.y
        byacc -d -P MyParser $<

> make
byacc -d -P MyParser calc.y
> ls -ltr
total 28
-rw-r-----    1 pl       casiano       823 Dec 29  2002 calc.y
-rw-r-----    1 pl       casiano        47 Dec 29  2002 Makefile
-rwxr-x--x    1 pl       casiano       627 Nov 10 15:37 tokenizer.pl
-rw-rw----    1 pl       users          95 Nov 16 12:49 y.tab.ph
-rw-rw----    1 pl       users        9790 Nov 16 12:49 MyParser.pm

Observe que la opción -P es la que permite producir código Perl. Anteriormente se usaba la opción -p. Esto se hizo para mantener la compatibilidad con otras versiones de yacc en las que la opción -p se usa para cambiar el prefijo por defecto (yy). Ese es el significado actual de la opción -p en perl-byacc.

El fichero y.tab.ph generado contiene las definiciones de los tokens:

 cat y.tab.ph
$INT=257;
$EOL=258;
$LEFT_PAR=259;
$RIGHT_PAR=260;
$PLUS=261;
$MINUS=262;
$MULT=263;
$DIV=264;

El programa tokenizer.pl contiene la llamada al analizador y la definición del analizador léxico:

> cat tokenizer.pl
#!/usr/local/bin/perl5.8.0

require 5.004;
use strict;
use Parse::YYLex;
use MyParser;

print STDERR "Version $Parse::ALex::VERSION\n";

my (@tokens) = ((LEFT_PAR => '\(',
                 RIGHT_PAR => '\)',
                 MINUS => '-',
                 PLUS => '\+',
                 MULT => '\*',
                 DIV => '/',
                 INT => '[1-9][0-9]*',
                 EOL => '\n',
                 ERROR => '.*'),
                sub { die "!can\'t analyze: \"$_[1]\"\n!"; });

my $lexer = Parse::YYLex->new(@tokens);

sub yyerror
{
    die "There was an error:" . join("\n", @_). "\n";
}

my $debug = 0;
my $parser = new MyParser($lexer->getyylex(), \&MyParser::yyerror , $debug);
$lexer->from(\*STDIN);
$parser->yyparse(\*STDIN);

El módulo Parse::YYLex contiene una versión de Parse::Lex que ha sido adaptada para funcionar con byacc. Todas las versiones de yacc esperan que el analizador léxico devuelva un token numérico, mientras que Parse::Lex devuelbe un objeto de la clase token. Veamos un ejemplo de ejecución:

> tokenizer.pl
Version 2.15
yydebug: state 0, reducing by rule 1 (start :)
yydebug: after reduction, shifting from state 0 to state 1
3*(5-9)
yydebug: state 1, reading 257 (INT)
yydebug: state 1, shifting to state 2
yydebug: state 2, reducing by rule 5 (expr : INT)
INT -> Expr!
yydebug: after reduction, shifting from state 1 to state 6
yydebug: state 6, reading 263 (MULT)
yydebug: state 6, shifting to state 11
yydebug: state 11, reading 259 (LEFT_PAR)
yydebug: state 11, shifting to state 4
yydebug: state 4, reading 257 (INT)
yydebug: state 4, shifting to state 2
yydebug: state 2, reducing by rule 5 (expr : INT)
INT -> Expr!
yydebug: after reduction, shifting from state 4 to state 7
yydebug: state 7, reading 262 (MINUS)
yydebug: state 7, shifting to state 10
yydebug: state 10, reading 257 (INT)
yydebug: state 10, shifting to state 2
yydebug: state 2, reducing by rule 5 (expr : INT)
INT -> Expr!
yydebug: after reduction, shifting from state 10 to state 15
yydebug: state 15, reading 260 (RIGHT_PAR)
yydebug: state 15, reducing by rule 7 (expr : expr MINUS expr)
MINUS -> Expr!
yydebug: after reduction, shifting from state 4 to state 7
yydebug: state 7, shifting to state 13
yydebug: state 13, reducing by rule 10 (expr : LEFT_PAR expr RIGHT_PAR)
PARENS -> Expr!
yydebug: after reduction, shifting from state 11 to state 16
yydebug: state 16, reducing by rule 8 (expr : expr MULT expr)
MULT -> Expr!
yydebug: after reduction, shifting from state 1 to state 6
yydebug: state 6, reading 258 (EOL)
yydebug: state 6, shifting to state 8
yydebug: state 8, reducing by rule 3 (input : expr EOL)
-12
yydebug: after reduction, shifting from state 1 to state 5
yydebug: state 5, reducing by rule 2 (start : start input)
yydebug: after reduction, shifting from state 0 to state 1
yydebug: state 1, reading 0 (end-of-file)