I think you should try splitting this into two problems.

The first is to parse the user input, getting some kind of parse tree with logical operations in the interior nodes and search words at the leaves. You may want to do this systematically with a parser generator module.

The second is to translate the parse tree into whatever mechanism your search uses, whether a bunch of greppy file scans or a database query.