Beefy Boxes and Bandwidth Generously Provided by pair Networks
Clear questions and runnable code
get the best and fastest answer
 
PerlMonks  

parser for evaluating arbitrarily complex boolean function in a string

by jce (Novice)
on Oct 14, 2004 at 20:24 UTC ( #399322=perlquestion: print w/ replies, xml ) Need Help??
jce has asked for the wisdom of the Perl Monks concerning the following question:

Knowledgeable monks,

I have a string which contains something like this (minus the quotes of course): $function = "((S0*B)|((!S0)*A))"; These functions are coming from some other parsing I have setup for some Verilog Library files. In this instance this equation describes a 2 input 1 ouput multiplexer. | being a Logical OR, ! being NOT, and * being AND, ^ being XOR etc. There will be an arbitrary number of boolean operands, operators, and parenthetical phrases. There is an order of operations, ! is highest precedence, (of course parantheses are evaluated first), AND is higher then OR, etc.

This is what i am looking to do. These libraries are megabytes in size, text files, with amoung other things these functional equations. I want to take the function that is in $string, and generate a truth table showing all possible combinations of inputs and then the corresponding result. I have written some parsing that counts the number of unique operands, the total number of operators (AND count, Or Count etc, and counts the number of parenthesized expressions, which is 4 in the MUX equation.

The problem is I am not sure how to proceed, given that the function might be as simple as (A*B*C), or more complex then the one given above. On a side note, we are only talking about no more then 4 unique boolean operands in a function (each may or may not be used more then 1 time). I want to use this method on each of the 1000 odd functions in this HDL code library, to make truth tables.

I am hoping someone may have done something like this, know of some code snippets that do something similar to this, or maybe just have some pointers or tips as to how they would do this. Im not a Regex expert, but have dabbled in some easy to moderate pattern matching before.

Cheers

Comment on parser for evaluating arbitrarily complex boolean function in a string
Re: parser for evaluating arbitrarily complex boolean function in a string
by kvale (Monsignor) on Oct 14, 2004 at 20:34 UTC
    The simplest approach would be to use the Math::BooleanEval module to evaluate your expressions to generate the truth table. The operators are a little different between your setup files and the module, but it is a matter of single character substitutions. From the synopsis:
    use Math::BooleanEval; my $bool = Math::BooleanEval->new('yes|no'); # evaluate each defined item in the expression to 1 or 0 foreach my $item (@{$bool->{'arr'}}){ next unless defined $item; $item = ($item =~ m/^no|off|false|null$/i) ? 0 : 1; } # evaluate the expression print $bool->eval();

    -Mark

Re: parser for evaluating arbitrarily complex boolean function in a string
by blokhead (Monsignor) on Oct 15, 2004 at 00:57 UTC
    If you trust that the data you're getting is well-formed, you can just use eval. Perl's boolean operators and precedence just happens to be exactly what you've defined, so why not let perl do the work? Taking that approach, it's pretty trivial to suck out the variable names from that expression and then make a truth table ..
    my $bool_func = "((S0*B)|((!S0)*A))"; (my $perl_expr = $bool_func) =~ s/([a-zA-Z]\w*)/\$val{$1}/g; print "Using perl expression: $perl_expr\n"; my @vars = do { my %seen; grep !$seen{$_}++, $bool_func =~ /([a-zA-Z]\w*)/g; }; for my $assignment ( 0 .. (2**@vars)-1 ) { my %val; $val{$vars[$_]} = ( $assignment >> $_ ) & 1 for 0 .. $#vars; my $result = eval $perl_expr; print join(", ", map { "$_=$val{$_}" } keys %val), " ==> $bool_func=$result\n"; } __END__ Using perl expression: (($val{S0}*$val{B})|((!$val{S0})*$val{A})) A=0, S0=0, B=0 ==> ((S0*B)|((!S0)*A))=0 A=0, S0=1, B=0 ==> ((S0*B)|((!S0)*A))=0 A=0, S0=0, B=1 ==> ((S0*B)|((!S0)*A))=0 A=0, S0=1, B=1 ==> ((S0*B)|((!S0)*A))=1 A=1, S0=0, B=0 ==> ((S0*B)|((!S0)*A))=1 A=1, S0=1, B=0 ==> ((S0*B)|((!S0)*A))=0 A=1, S0=0, B=1 ==> ((S0*B)|((!S0)*A))=1 A=1, S0=1, B=1 ==> ((S0*B)|((!S0)*A))=1
    I hope it goes without saying that if you aren't this confident about the state of your input, your solution needs to involve parsing (and therefore validating) the input expression -- either explicitly, or by means of an existing modular solution.

    blokhead

      hi blokhead,

      i am new to perl and my requirement is also almost similar ! I was trying to understand the solution you posted.

      can you explain me the following pieces of your code pl. ??

      my @vars = do { my %seen; grep !$seen{$_}++, $bool_func =~ /([a-zA-Z]\w*)/g; };
      and also the following statements
      for my $assignment ( 0 .. (2**@vars)-1 ) { my %val; $val{$vars[$_]} = ( $assignment >> $_ ) & 1 for 0 .. $#vars; .........
Re: parser for evaluating arbitrarily complex boolean function in a string
by TedPride (Priest) on Oct 15, 2004 at 08:44 UTC
    I'm assuming all the functions are logically valid, and using eval:
    use strict; use warnings; my (@truth, $c1, $c2, $line, $logic, $v, $c, $cref); my $max = 4; ## Max number of vars $truth[0] = '0 1'; for (1..($max-1)) { ($c1 = $truth[$_-1]) =~ s/(\d+)/0$1/g; ($c2 = $truth[$_-1]) =~ s/(\d+)/1$1/g; $truth[$_] = "$c1 $c2"; } for (0..($max-1)) { my @comb = split(/ /, $truth[$_]); $truth[$_] = \@comb; } for (<DATA>) { my %vars; chomp($line = $_); @_ = $line =~ /(\w+)/g; $v = ''; $c = 0; for (sort @_) { ## Sort and retrieve if ($_ ne $v) { ## unique var names $vars{$v = $_} = $c++; } } print $line . "\n"; print join(' ', sort {$vars{$a} <=> $vars{$b}} keys %vars) . "\n"; $cref = $truth[scalar(keys %vars) - 1]; for (@$cref) { $logic = $line; ## Replace var names with $logic =~ s/(\w+)/substr($_, $vars{$1}, 1)/eg; print $_ . ' ' . eval($logic) . "\n"; } ## logic values and evaluate print "\n"; } __DATA__ ((S0*B)|((!S0)*A)) ((A*B)^C)

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://399322]
Approved by kvale
Front-paged by grinder
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others wandering the Monastery: (4)
As of 2014-09-16 02:34 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My favorite cookbook is:










    Results (155 votes), past polls