%token CONST
%token VAR
%token IMP
%token FUN
%token LPAREN
%token RPAREN
%token APP

%nonassoc FUN
%nonassoc VAR CONST LPAREN
%left APP

%%

expr: CONST { my $litval = $_[1]; sub { $litval } }
    | VAR { my $varname = $_[1]; sub { my %args_ = @_; $args_{$varname
+} } }
    | FUN VAR IMP expr { my ($param, $term) = ($_[2], $_[4]); sub { my
+ %args = @_; sub { $args{$param} = shift; $term->(%args) } } }
    | LPAREN expr RPAREN { $_[2] }
    | expr expr %prec APP { my ($op, $arg) = ($_[1], $_[2]); sub { my 
+%args_ = @_; $op->(%args_)->($arg->(%args_)) } }
;

%%
[download]

Constants are compiled to functions with trivial return values. Variables, abstraction terms and application terms are handled with some trick, which is similar to lambda lifting (http://en.wikipedia.org/wiki/Lambda_lifting). All bound variables are saved in a hash context and passed to any term in the current scope. Thus, a bound variable is accessed by getting the value of the hash entry with its variable name as the key. Abstraction and application terms are quoted in a function to separate the passing of context and arguments.

Here is a test case, with lexical analysis utilities:

#!/usr/bin/perl

# These are only decoration. The superiors hardly understand this.

use strict;
use warnings;

use Parse::Lex;
use utlc;

my @tokens = (
    qw (
        LPAREN      [\(]
        RPAREN      [\)]
        FUN         [\\\\]
        IMP         [.]
        VAR         [A-Za-z_][A-Za-z_0-9]*
        CONST       [1-9][0-9]*
    )
);

our $lexer = Parse::Lex->new(@tokens);
$lexer->skip('\s+');

sub lexana {
    my $token = $lexer->next;
    if (not $lexer->eoi) {
        return ($token->name, $token->text);
    } else {
        return ('', undef);
    }
}

# $lexer->from(\*STDIN);
$lexer->from('\f.(\x.(f (\y.x x y))) (\x.(f (\y.x x y)))');

my $parser = utlc->new();
my $expr = $parser->YYParse(yylex => \&lexana);

#print $expr->(), "\n";

# \f.\x.(=0 x) 1 (* x (f (- x 1)))
sub fac {
    my $f = shift;
    sub {
        my $x = shift;
        ($x) ? ($x * $f->($x - 1)) : (1)
    }
}

# \f.(\x.(f (\y.x x y))) (\x.(f (\y.x x y)))
print $expr->()->(\&fac)->(5), "\n";
[download]

The test is a factorial function, implemented by using a typical call-by-value Y combinator (for references on Y combinator, see http://en.wikipedia.org/wiki/Fixed-point_combinator#Strict_fixed_point_combinator).