|
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 |
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.
| [reply]
[d/l] |
|
|
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;
.........
| [reply]
[d/l]
[select] |
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();
| [reply]
[d/l] |
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)
| [reply]
[d/l] |
|
|
