Perhaps SQL::Parser might help you.

If you want to use regexes, you could try something like this:

my $op = qr/AND|OR|NOT/;
my $block = qr/($op?)\s*\((\w\s+$op\s+\w)\)/;
if ($str =~ m/^\(\s*(?:$block\s*)\)/){
    # access $1, $2, ... here
}
[download]