Well, Perl regular expressions can do that, but not "regular regular expressions", as they don't have a general way of saying "not", nor have they a non-exponential way of addressing "all of a set, regardless of their order".

I don't know why you say using some sort of parse tree is going to be overkill. Boolean expressions are amongst the simplest non-trivial expressions to parse; it's a typical excercise for students during the first hours of a compiler course. It shouldn't be too hard to parse this using Perl, even if you don't use Parse::RecDescent.

The reason I don't include some code in this post is that the specification of your target syntax isn't complete: it doesn't explain grouping. How do you express

    (word1 AND word2) OR word3
[download]

in the target syntax? And how is

    word1 AND (word2 OR word3)
[download]

expressed?

Abigail