Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl: the Markov chain saw
 
PerlMonks  

Parsing Boolean expressions

by Anonymous Monk
on Apr 23, 2017 at 02:22 UTC ( [id://1188650]=perlquestion: print w/replies, xml ) Need Help??

Anonymous Monk has asked for the wisdom of the Perl Monks concerning the following question:

Hi,

Is there a readily usable library to parse Boolean expressions like below:

Y = A + (B*C) Y = A + (B' + (C*D)') Y = A*(B*(C'+D)')

Thanks in advance.

Matt

Replies are listed 'Best First'.
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.

    Bill
      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

      Cheers Rolf
      (addicted to the Perl Programming Language and ☆☆☆☆ :)
      Je suis Charlie!

Re: Parsing Boolean expressions
by tybalt89 (Monsignor) on Apr 23, 2017 at 16:08 UTC

    Lacking adequate specs :)

    #!/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
Re: Parsing Boolean expressions
by tybalt89 (Monsignor) on Apr 23, 2017 at 03:13 UTC

    What does your input and output look like ?

    Do you have test cases (sets of input and output) ?

      The OP is asking for a module. I think whatever output format that module uses will probably be fine.
        > I think whatever output format that module uses will probably be fine.

        well then ... taking output from Re: Parsing Boolean expressions (hack)

        $ 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.

        Cheers Rolf
        (addicted to the Perl Programming Language and ☆☆☆☆ :)
        Je suis Charlie!

Re: Parsing Boolean expressions
by choroba (Cardinal) on Apr 23, 2017 at 21:13 UTC
    I like Marpa::R2 for building grammars:
    #!/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,
Re: Parsing Boolean expressions
by Anonymous Monk on Apr 23, 2017 at 03:00 UTC
Re: Parsing Boolean expressions (hack)
by LanX (Saint) on Apr 23, 2017 at 15:06 UTC
    Just for fun :)

    no guarantees whatsoever...

    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

    Cheers Rolf
    (addicted to the Perl Programming Language and ☆☆☆☆ :)
    Je suis Charlie!

    update

  • wait there is a precedence problem ... = before and
  • Solved
      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"], "'"]]
        > 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)

        Cheers Rolf
        (addicted to the Perl Programming Language and ☆☆☆☆ :)
        Je suis Charlie!

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.

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlquestion [id://1188650]
Approved by beech
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others chilling in the Monastery: (3)
As of 2024-04-25 05:37 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found