Parsing a User's Query

Question

So here's what I'm looking to achieve. I would like to give my users a single google-like textbox where they can type their queries. And I would like them to be able to express semi-natural language such as

"view all between 1/1/2008 and 1/2/2008"

it's ok if the syntax has to be fairly structured and limited to this specific domain ... these are expert users who will be using this.

Ultimately, I think I'd like the parse results to be available as some sort of expression tree. But if you've got some other ideas about what data structure might be better.

This is in C# :-)

Answer 1

Trying to parse that stuff would be a disaster, and ultimatley very limiting to the user, thus frustrating them more then helping them. I would suggest using pre-defined Query clasues, with some kind of query builder tool that has all the available options in drop down form. You can have different boolean operators for different Data Types (greater than, less than for numeric, like not like for strings etc), however I think that would make a helluva lot more sense than actually trying to parse out what a user may type.

Answer 2

An expression tree is a good idea. There are many good general parsers and parser generators out there, open-source as well as commercial, which can transform correct query strings into expression trees.

Answer 3

I have been in this situation before. After much discussion, we decided that context-sensitive dropdowns were a better solution than just a textbox.

For instance, have 4 dropdowns, but the last 3 are disabled. Then, when the user selects an option from the first, it populates and enables the others. So they would select "view all" then "between", and then maybe pop a textbox or a calendar for the last two.

Here's an example that's kind of like what I am talking about

Answer 4

For a very simple language, I'd go with regexps. Main benefit there is you don't have to deal with any code generation. Debugging of the pattern matching is basically nil, though.

If your language is moderately complex (you wouldn't mind specifying the entire thing in a single grammar file), I'd go with Coco/R -- it's fast, easy to use, and makes extremely debuggable code.

For a more complex language, my current favorite is Antlr v3. Supports multi-file grammars (via the 'import' statement), which is very nice. The generated code is debuggable, but takes a bit of getting used to before debugging could be considered 'easy.'

Answer 5

You are describing a programming language. Granted it's a small language (often called a little language, or Domain Specific Language (DSL)). If you've never heard the term recursive descent parser, you are probably better off following Paul's advice and using drop down boxes of some description.

However, again, I would have to agree with him, that if you want to do it, Antlr is the way to go. There are tutorials on the site that might help you get started. Basically, you will need to describe how the syntax using Backus-Naur Form notation.

You will then run Antlr over your grammer, and it will generate your parser. You can then feed the input from your textbook into an Abstract Syntax Tree. You can then use that Tree to generate your query. It's not as difficult as it all sounds, but there's a bit to it.

If you're really into this and/or want to stretch your programming wings a bit, you could read more on the topic with the Dragon Book, AKA Compilers: Principles, Techniques and Tools.

Good luck my friend.

Answer 6

I dont know if this will help you , but what we did was : we gave the user pre-defined criterias like for date selection we gave them two calendar pop-ups so that they can select from and to date range... we did not make it compulsory.. so date filter use to apply only when user specifies the dates... similarly you can also give the users a pre-defined criteria selection... other then that expression tree seems to be a nice workaround for that.

Answer 7

Use Oslo, it's designed specifically for this...

Answer 8

The GOLD Parser Generator has a helpful UI for designing and testing your grammar, reasonably good tutorials and documentation, and is easy to use from C#.