Boolean query string conversion into functional logic

[Hamish Ogilvy]

I'm looking to turn a query string into functional logic that can be repeatedly applied, i.e. processing any inputted boolean query on multiple documents.

So for example take the input string: ((name != cindy AND haircolor:blonde) OR rating > 10) OR (job: engineer*) and dynamically turn that into logic that can be applied repeatedly.

It's easy for me to create and process individual filters, AND, OR them, etc, but i'm struggling to dynamically turn the query string into dynamic logic to put them together dynamically. It was suggested to look at the "ast" package, which makes sense, but i know what i'm looking to do has been done before, so i'd like to avoid reinventing the wheel. Closest i've seen is Vitess SQL query parsing, but it's very application specific.

Thanks,

Hamish

[Gyepi SAM]

On Thu, Feb 20, 2014 at 08:48:16PM -0800, Hamish Ogilvy wrote:
> I'm looking to turn a query string into functional logic that can be
> repeatedly applied, i.e. processing any inputted boolean query on multiple
> documents.
>

> So for example take the input string: *((name != cindy AND
> haircolor:blonde) OR rating > 10) OR (job: engineer*)* and dynamically turn

> that into logic that can be applied repeatedly.
>
> It's easy for me to create and process individual filters, AND, OR them,
> etc, but i'm struggling to dynamically turn the query string into dynamic
> logic to put them together dynamically. It was suggested to look at the
> "ast" package, which makes sense, but i know what i'm looking to do has
> been done before, so i'd like to avoid reinventing the wheel. Closest i've
> seen is Vitess SQL query parsing, but it's very application specific.

If the search queries are dynamic, then yes, you'll need to parse the query.

The terms form a tree, so if you build a corresponding tree of Expr nodes during the parse:

type Expr struct {
Op string
Left *Expr
Right *Expr
Val string
}

you should be able to walk it and evaluate the tree.

A fun project for yacc.

The syntax presented here is a bit odd with the infix expressions, ':' operator, and what looks like a '*' operator
so it's probably simplest to use a little hand rolled lexer here.


-Gyepi

[Hamish Ogilvy]

Thanks Gyepi. Had a look at yacc, but i can't find too much relevant to what i'm trying to do. This did also lead me to some comments pointing to:

http://golang.org/pkg/text/scanner/

I also found the following using bufio as a tokeniser, which is interesting:

http://jeremy.marzhillstudios.com/io/

[egon]

Essentially what you need to do is first tokenize the text and then transform that to a hierarchy of expressions.

Simplest way is to apply shunting yard algorithm and do the expression evaluation with RPN. This works very well if you only have binary operators.

Alternatively you can use some sort of simple parser... one that I experimented was was http://egonelbre.com/js/bigram/, and should suit your needs well enough (although it is written in javascript, it's fairly short and simple... but inefficient in speed).

There's also possibility to use ragel with go to generate a state machine that builds the hierarchy.

If you are not going to do very complex language, then yacc might be overkill.

egon

[Hamish Ogilvy]

Cool javascript, nice way to visualise! RPN was a useful tip, found one interesting one Go based:

https://github.com/zephyrtronium/rpn

Looks like i'll have to smash this out myself. Will post it once done.

Thanks again!

egon

--
You received this message because you are subscribed to a topic in the Google Groups "golang-nuts" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/golang-nuts/phpOipu03G0/unsubscribe.
To unsubscribe from this group and all its topics, send an email to golang-nuts...@googlegroups.com.

For more options, visit https://groups.google.com/groups/opt_out.

[Jose]

Hi Hamish,

Any updates on how to tackle this problem with current Go tools ?

Is it useful to use some of the Go parse tools or AST ?

Thanks

> You received this message because you are subscribed to the Google Groups
> "golang-nuts" group.
> To unsubscribe from this group and stop receiving emails from it, send an

[Hamish Ogilvy]

Hey Jose,

Yep, might be worth a look at: https://github.com/influxdata/influxql for a pretty advanced and open source version. Also look at Rob Pike's calculator talk: https://www.youtube.com/watch?v=PXoG0WX0r_E That helped me a lot. You basically need a tokeniser and you then scan the input into tokens and build a tree of functions to represent the input. 

It's really valuable to build your own from scratch if you can.

Best.

[Jose]

Thanks, really useful!

> For more options, visit https://groups.google.com/d/optout.