Forum: Ruby parsing a boolean expression

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
Bd0203dc8478deb969d72f52e741bd4f?d=identicon&s=25 Daniel Baird (Guest)
on 2006-06-05 08:35
(Received via mailing list)
Hi all,

I need to take a string typed by dirty users' fingers, that should
contain a
boolean expression, like this:
  one and (two or three or (four and five) or six) and (seven or eight)
..and parse it into some kind of sensible data structure, like a tree or
something.   Or reject it if it's mal-formed.

I figure it might take me two or three days to write and debug from
scratch
(..hey, I'm fairly new to Ruby :\ ), but I'm sure there's a library
somewhere that will do the job.

I've tried searching for bool*, expr* and pars* in fxri but didn't get
anything, and Googling just tells me that my search terms are too
generic to
find what I want. Any suggestions?

Thanks in advance!

;Daniel
31af45939fec7e3c4ed8a798c0bd9b1a?d=identicon&s=25 Matthew Smillie (Guest)
on 2006-06-05 14:21
(Received via mailing list)
On Jun 5, 2006, at 7:32, Daniel Baird wrote:

> I figure it might take me two or three days to write and debug from
> scratch
> (..hey, I'm fairly new to Ruby :\ ), but I'm sure there's a library
> somewhere that will do the job.

Well, there is and there isn't.  If you know how to write grammars in
yacc, then there's racc:
http://i.loveruby.net/en/projects/racc/doc/

If your input is always going to be as simple as the above (space-
delimited tokens and parens), and you don't know anything about yacc,
then there's the distinct possibility that you'll lose more time
fiddling with it than you will writing your own parser.

Ferinstance, you could pretty easily add the 'missing' parens (after
each operator to the end of the expression) to make it explicit, then
change it to an s-expression by switching the order of the first
token and operator in each sub-expression.  And an s-expression is
basically a tree.  It would depend on what you want to do with it
when you're done.

matthew smillie.
Fc784eadb3b54531fdc3d2053db6f83f?d=identicon&s=25 Mat Schaffer (Guest)
on 2006-06-05 14:37
(Received via mailing list)
On Jun 5, 2006, at 2:32 AM, Daniel Baird wrote:
> I figure it might take me two or three days to write and debug from
>
> ;Daniel
>
> --
> Daniel Baird
> http://danielbaird.com (TiddlyW;nks! :: Whiteboard Koala :: Blog ::
> Things
> That Suck)

If you can force (or just add on) an exterior set of parenthesis, S-
Expressions could fill your parsing need as described here:
http://www.artima.com//rubycs/articles/patterns_se...

You'll have to work out the booleans yourself, but that shouldn't be
too tricky.

-Mat
Bd0203dc8478deb969d72f52e741bd4f?d=identicon&s=25 Daniel Baird (Guest)
on 2006-06-05 14:37
(Received via mailing list)
On 6/5/06, Matthew Smillie <M.B.Smillie@sms.ed.ac.uk> wrote:
> If your input is always going to be as simple as the above (space-
>
> matthew smillie.


Hmm.. I haven't done anything with yacc before, and my expressions _are_
going to be pretty simple, so I guess your advice is to write it myself
:)

I'd kinda fancied returning a tree made up of nodes that are either:

- a token
- a list of nodes with a common operator

eg "A and ( B or C or D) and E" would be:

node0: AND(A, node1, E)
node1: OR(B, C, D)

It's not a binary tree but it would be somewhat convenient for the
processing / storing / re-displaying I need to do.. I just hoped I'd
save a
day or two standing on someone else's shoulders.

Thanks Matthew.

;D
Cb48ca5059faf7409a5ab3745a964696?d=identicon&s=25 unknown (Guest)
on 2006-06-05 17:32
(Received via mailing list)
On Mon, 5 Jun 2006, Daniel Baird wrote:

> node0: AND(A, node1, E)
> node1: OR(B, C, D)
>
> It's not a binary tree but it would be somewhat convenient for the
> processing / storing / re-displaying I need to do.. I just hoped I'd save a
> day or two standing on someone else's shoulders.
>
> Thanks Matthew.
>
> ;D

this is extremely short and relatively secure, it may fit depending on
your use
case and leverages the fact that ruby knows how to parse ruby:

     harp:~ > cat a.rb
     class BoolExp
       attr 'exp'
       attr 'value'

       def initialize exp, context = {}
         @exp = exp.to_s

         tokens = context.keys.map{|k| k.to_s}.join '|'
         re = %r/^(?:\s*|#{ tokens }|[)(]|and|or|not)+$/i

         raise "bad exp <#{ @exp }>" unless @exp =~ re

         @value = Thread.new(exp, context) do |e, c|
           $SAFE = 4
           Module.new do
             sc =
               class << self
                 self
               end
             c.each do |k,v|
               case k.to_s
                 when %r/^[A-Z]/
                   const_set k, v
                 else
                   sc.module_eval{ attr_accessor k }
                   send "#{ k }=", v
               end
             end
             break module_eval(e)
           end
         end.value
       end
     end


     context = {:A => true, :B => false, :C => true, :D => false, :E =>
true}

     be = BoolExp.new "A and ( B or C or D) and E", context
     p be.value

     be = BoolExp.new "fork", context
     p be.value



     harp:~ > ruby a.rb
     true
     a.rb:11:in `initialize': bad exp <fork> (RuntimeError)
             from a.rb:41



regards.

-a
This topic is locked and can not be replied to.