I played around with RecDescent a bit last night after posting. I think for the types of things I'm trying to express it may be more than I need (though it will definately do it) I have pretty strict control over how these things get added (adding clauses via a web form) so I don't need to deal with the vaugeries of human typed input. I came up with this which appears to be working for me. Just a fragment that's going to be inserted into a larger bit of code, no error handling/strict etc. Just a poc at this point.

#!/usr/bin/perl                                                       
+                                                                     
+                                                                 
use Data::Dumper;

my $clauses;

push(@$clauses, ["==","a","b"]);
push(@$clauses, "and");
push(@$clauses, ["==","c","d"]);
push(@$clauses, "or");
push(@$clauses, ["==","e","f"]);
push(@$clauses, "and");
push(@$clauses, ["==","g","h"]);

$Data::Dumper::Indent = 0;                                            
+                                                                     
+                                                                

my $list = BuildList($clauses);
print Dumper($list). "\n";


sub BuildList($)
{
    my $clauses = shift();
    my $list;

    while(my $clause = shift(@$clauses))
    {
        if($clause eq "and")
        {
            $list = ['AND',[$list], [shift(@$clauses)]];
        }
        elsif($clause eq "or")
        {
            $list = ["OR",[$list, BuildList($clauses)]];
        }
        else
        {
            $list = $clause
        }
    }
    return($list);
}
[download]

This gives me

['OR',[['AND',[['==','a','b']],[['==','c','d']]],['AND',[['==','e','f'
+]],[['==','g','h']]]]]
[download]

Thanks for all the input.
Update: It's also important to note, that I don't really care about what's in each clause. The clauses are going to be pretty tightly controlled by the creation mechanisim.