Advanced string searching

Question

I need some help with doing some advanced string searching.  I'm writing a program that will allow the user to input text to search for, then the program scans files and returns a list of the files containing the text.  I want it to work similar to how indexing works, but I will be searching non-indexed locations and doing some things that indexing can't.  The user might enter in a complex string like 'fred barney "frog lake"', which would only match files containing "fred" and "barney" and the exact string "frog lake" (case insensitive for all).  I'd like to be able to accept AND and OR keywords but could live without that if it's too tough.  I think that some sort of conversion to a regular expression is what I need, but I'm not comfortable enough with them to know what I'm doing.
Can you help me with ideas for how to do this, and regular expressions if that's the best way?  Thanks!