Re: Parsing Boolean expressions
by BillKSmith (Monsignor) on Apr 23, 2017 at 03:39 UTC
|
You could avoid confusion if you post a link to a definition of your symbols. You will need this yourself to tell if a proposed module does exactly what you need.
If your real objective is to evaluate the expression, you could consider translating it into perl.
| [reply] |
|
FWIW
> a definition of your symbols
it confused me too, till I remembered that some notations use a quote ' for boolean negation.
So
+ or
* and
' not
() grouping
= assignment
| [reply] [d/l] [select] |
Re: Parsing Boolean expressions
by tybalt89 (Monsignor) on Apr 23, 2017 at 16:08 UTC
|
#!/usr/bin/perl
# http://perlmonks.org/?node_id=1188650
# Parsing Boolean expressions
use strict;
use warnings;
use Data::Dump 'pp';
my @tests = grep /\S/, split /\n/, <<END;
Y = A + (B*C)
Y = A + (B' + (C*D)')
Y = A*(B*(C'+D)')
Y = A # wire
Y = (A')' # double negation
Y = A' # NOT gate
Y = (A + B)' # NOR gate
Y = (A * B)' # NAND gate
Y = (A' + B')' # AND gate by De Morgan
Y = (A' * B')' # OR gate by De Morgan
END
for ( @tests ) # for each test case
{
print "\nparsing: $_\n";
for my $input (glob join '', map "$_:\{0,1\}", # for each combinatio
+n
sort s/.*=|#.*//gr =~ /\w+/g) # of input values
{
my %dictionary = $input =~ /(\w+):(0|1)/g;
Parsing::Boolean::Expressions::parse( $_, \%dictionary );
pp \%dictionary;
}
}
package Parsing::Boolean::Expressions; ########################
my $vars; # variable dictionary hash ref
sub err { die s/\G/<* @_ *>/r, "\n" }
sub closeparen { /\G\)/gc ? shift : err "missing )" }
sub expr
{
my $p = shift; # precedence
/\G(?:\s+|#.*)+/gc; # skip whitespace
my $answer =
/\G(\w+)\s*/gc ? do { my $name = $1;
/\G=/gc ? $vars->{$name} = expr(0) : $vars->{$name} } :
/\G\(/gc ? closeparen expr(0) :
err "syntax error";
/\G(?:\s+|#.*)+/gc, # skip whitespace
$p <= 3 && /\G'/gc ? $answer ^= 1 : # highest precedence
$p <= 2 && /\G\*/gc ? $answer &= expr(3) :
$p <= 1 && /\G\+/gc ? $answer |= expr(2) : # lowest precedence
return $answer while 1;
}
sub parse # takes expression string and ref to dictionary hash
{
(local $_, $vars) = @_;
expr(0);
/\G\z/gc or err "incomplete parse";
}
# end of package Parsing::Boolean::Expressions
| [reply] [d/l] |
Re: Parsing Boolean expressions
by tybalt89 (Monsignor) on Apr 23, 2017 at 03:13 UTC
|
| [reply] |
|
The OP is asking for a module. I think whatever output format that module uses will probably be fine.
| [reply] |
|
$ perl -MO=Terse -e ' $Y = ( $A or ($B^1 or ($C and $D)^1) );'
LISTOP (0x8570520) leave [1]
OP (0x85a2968) enter
COP (0x856fff8) nextstate
BINOP (0x8570500) sassign
UNOP (0x85704e0) null
LOGOP (0x85704c0) or
UNOP (0x856ffb8) null [15]
PADOP (0x8570050) gvsv GV (0x856a758) *A
UNOP (0x85704a0) null
LOGOP (0x8659ee0) or
BINOP (0x856ff78) bit_xor [4]
UNOP (0x856ff58) null [15]
PADOP (0x856ff38) gvsv GV (0x856a7bc)
+ *B
SVOP (0x856ff08) const [8] IV (0x856a71c)
+1
BINOP (0x8659ec0) bit_xor [7]
UNOP (0x8659e80) null
LOGOP (0x8659e60) and
UNOP (0x8570180) null [15]
PADOP (0x85700c8) gvsv GV (0x
+856a7a8) *C
UNOP (0x8659e40) null [15]
PADOP (0x859fd50) gvsv GV (0x
+856a7e4) *D
SVOP (0x8659ea0) const [9] IV (0x856a7d0)
+1
UNOP (0x8570140) null [15]
PADOP (0x856edd8) gvsv GV (0x856a730) *Y
et voila! ;-P
And see B::Concise for even more formating options.
| [reply] [d/l] |
|
|
|
|
|
| [reply] |
|
Re: Parsing Boolean expressions
by choroba (Cardinal) on Apr 23, 2017 at 21:13 UTC
|
#!/usr/bin/perl
use warnings;
use strict;
use feature qw{ say };
use Marpa::R2;
my $dsl = << '__DSL__';
lexeme default = latm => 1
Assignment ::= var ('=') Expression action => ASSIGN
Expression ::= var action => VAR
| ('(') Expression (')') action => ::first assoc
+=> group
|| Expression (q) action => NOT
|| Expression ('*') Expression action => AND
|| Expression ('+') Expression action => OR
q ~ [']
var ~ [A-Z]+
:discard ~ whitespace
whitespace ~ [\s]+
__DSL__
my %var;
sub ASSIGN { $var{ $_[1] } = 0 + $_[2] }
sub NOT { ! $_[1] }
sub AND { $_[1] && $_[2] }
sub OR { $_[1] || $_[2] }
sub VAR { $var{ $_[1] } }
my @input = ('Y = A + (B*C)',
"Y = A + (B' + (C*D)')",
"Y = A*(B*(C'+D)')");
my $grammar = 'Marpa::R2::Scanless::G'->new({ source => \$dsl });
for my $line (@input) {
%var = map +( $_ => int rand 2 ), 'A' .. 'D';
my $result = $grammar->parse(\$line, { semantics_package => 'main'
+ });
say join ' ', %var;
}
($q=q:Sq=~/;[c](.)(.)/;chr(-||-|5+lengthSq)`"S|oS2"`map{chr |+ord
}map{substrSq`S_+|`|}3E|-|`7**2-3:)=~y+S|`+$1,++print+eval$q,q,a,
| [reply] [d/l] [select] |
Re: Parsing Boolean expressions
by Anonymous Monk on Apr 23, 2017 at 03:00 UTC
|
| [reply] |
Re: Parsing Boolean expressions (hack)
by LanX (Saint) on Apr 23, 2017 at 15:06 UTC
|
use strict;
use warnings;
my @equations;
while(<DATA>){
chomp;
next unless $_; # ignore empty
next if $_ =~ /^\s*#/; # ignore comment
s/(\w+)/\$$1/g; # variables
# ops by decending precedence
s/'/^1/g; # negation by xor 1
s/\*/ and /g; # and
s/\+/ or /g; # or
s/=(.*)$/= ( $1 )/; # assignment after ( RHS )
push @equations,"$_;\n";
}
my $format = "%s | %s %s %s %s\n";
$\="\n";
#print @equations;
for my $eq (@equations) {
print "\n $eq";
printf $format, qw/Y A B C D/;
for my $A (0,1) {
for my $B (0,1) {
for my $C (0,1) {
for my $D (0,1) {
my $Y=undef;
eval $eq;
printf $format, $Y, $A, $B, $C, $D;
}
}
}
}
}
__DATA__
#Y=A+B'
#Y=A*B'
#Y=A'
#Y=A*B
#Y=A+B
Y = A + (B*C)
Y = A + (B' + (C*D)')
Y = A*(B*(C'+D)')
$Y = ( $A or ($B and $C) );
Y | A B C D
0 | 0 0 0 0
0 | 0 0 0 1
0 | 0 0 1 0
0 | 0 0 1 1
0 | 0 1 0 0
0 | 0 1 0 1
1 | 0 1 1 0
1 | 0 1 1 1
1 | 1 0 0 0
1 | 1 0 0 1
1 | 1 0 1 0
1 | 1 0 1 1
1 | 1 1 0 0
1 | 1 1 0 1
1 | 1 1 1 0
1 | 1 1 1 1
$Y = ( $A or ($B^1 or ($C and $D)^1) );
Y | A B C D
1 | 0 0 0 0
1 | 0 0 0 1
1 | 0 0 1 0
1 | 0 0 1 1
1 | 0 1 0 0
1 | 0 1 0 1
1 | 0 1 1 0
0 | 0 1 1 1
1 | 1 0 0 0
1 | 1 0 0 1
1 | 1 0 1 0
1 | 1 0 1 1
1 | 1 1 0 0
1 | 1 1 0 1
1 | 1 1 1 0
1 | 1 1 1 1
$Y = ( $A and ($B and ($C^1 or $D)^1) );
Y | A B C D
0 | 0 0 0 0
0 | 0 0 0 1
0 | 0 0 1 0
0 | 0 0 1 1
0 | 0 1 0 0
0 | 0 1 0 1
0 | 0 1 1 0
0 | 0 1 1 1
0 | 1 0 0 0
0 | 1 0 0 1
0 | 1 0 1 0
0 | 1 0 1 1
0 | 1 1 0 0
0 | 1 1 0 1
1 | 1 1 1 0
0 | 1 1 1 1
update
wait there is a precedence problem ... = before and
Solved | [reply] [d/l] [select] |
|
Nice. You can almost parse the expression with the same technique.
use strict;
use warnings;
use Data::Dump;
my @exprs = (
"Y = A + (B*C)",
"Y = A + (B' + (C*D)')",
"Y = A*(B*(C'+D)')",
);
for my $expr (@exprs) {
print "$expr\n";
$expr =~ s/\(/[/g;
$expr =~ s/\)/],/g;
$expr =~ s/(\w+|[+*'=])/"$1",/g;
my @parse = eval $expr;
dd(\@parse);
print "\n";
}
__END__
Y = A + (B*C)
["Y", "=", "A", "+", ["B", "*", "C"]]
Y = A + (B' + (C*D)')
["Y", "=", "A", "+", ["B", "'", "+", ["C", "*", "D"], "'"]]
Y = A*(B*(C'+D)')
["Y", "=", "A", "*", ["B", "*", ["C", "'", "+", "D"], "'"]]
| [reply] [d/l] |
|
> You can almost parse the expression with the same technique.
not really, for a syntax tree you would need an [OP, arg1, arg2] format.
this
["B", "'", "+", ["C", "*", "D"], "'"]]
doesn't help without further parsing
because precedence is still not resolved.
Rather
[ "or",
[ "not" , "B" ] ,
[ "not",
[ "and", "C", "D"]
]
]
without recursive parsing hard to achieve, I just delegated the hard part to Perl, deliberately ignoring what the OP didn't tell us yet.
edit
For instance if the = is not an assignment but a condition, he would want solutions for this equation system...
(which I could produce at least by brute force for small variable sets, if we had a guarantied format)
| [reply] [d/l] [select] |
|
|
|
Re: Parsing Boolean expressions
by Anonymous Monk on Apr 23, 2017 at 14:40 UTC
|
The go-to module for expression parsing is Parse::RecDescent. It won't work right out of the box. You'll have to give it a grammar, but that's not hard to do. | [reply] |