Parsing a boolean expression

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

On Jun 5, 2006, at 7:32, Daniel B. 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.

On Jun 5, 2006, at 2:32 AM, Daniel B. wrote:

I figure it might take me two or three days to write and debug from

;Daniel


Daniel B.
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_sexp_dsls3.html

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

-Mat

On Mon, 5 Jun 2006, Daniel B. 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

On 6/5/06, Matthew S. [email protected] 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
:slight_smile:

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