# Building truth tables

Paul McGuire ptmcg at austin.rr.com
Sat Oct 25 19:37:33 CEST 2008

On Oct 24, 5:53 am, andrea <kerny... at gmail.com> wrote:
> On 26 Set, 20:01, "Aaron \"Castironpi\" Brady" <castiro... at gmail.com>
> wrote:
>
>
>
> > Good idea.  If you want prefixed operators: 'and( a, b )' instead of
> > 'a and b', you'll have to write your own.  ('operator.and_' is bitwise
> > only.)  It may be confusing to mix prefix with infix: 'impl( a and b,
> > c )', so you may want to keep everything prefix, but you can still use
> > table( f, n ) like Tim said.
>
> After a while I'm back, thanks a lot, the truth table creator works,
> now I just want to parse some strings to make it easier to use.
>
> Like
>
> (P \/ Q) -> S == S
>
> Must return a truth table 2^3 lines...
>
> I'm using pyparsing and this should be really simple, but it doesn't
> allow me to recurse and that makes mu stuck.
> The grammar BNF is:
>
> Var :: = [A..Z]
> Exp ::= Var | !Exp  | Exp \/ Exp | Exp -> Exp | Exp /\ Exp | Exp ==
> Exp
>
> I tried different ways but I don't find a smart way to get from the
> recursive bnf grammar to the implementation in pyparsing...
> Any hint?

Use Forward to create a recursive grammar.  Look at the examples page
on the pyparsing wiki, and there should be several samples of
recursive grammars.

Here is a very simple recursive grammar, with no precedence to your
operators:

from pyparsing import oneOf, alphas, Forward, ZeroOrMore, Group,
Optional
var = oneOf(list(alphas))
op = oneOf(r"\/ /\ -> ==")
expr = Forward()
expr << Optional('!') + ( var  | Group('(' + expr + ')') ) +
ZeroOrMore(op + expr)

test = "(P \/ Q) -> S == S"

print expr.parseString(test).asList()

prints:

[['(', 'P', '\\/', 'Q', ')'], '->', 'S', '==', 'S']

Since these kinds of expressions are common, pyparsing includes a
helper method for defining precedence of operations infix notation:

from pyparsing import operatorPrecedence, opAssoc

expr = operatorPrecedence(var,
[
(r'!', 1, opAssoc.RIGHT),
(r'\/', 2, opAssoc.LEFT),
(r'/\\', 2, opAssoc.LEFT),
(r'->', 2, opAssoc.LEFT),
(r'==', 2, opAssoc.LEFT),
])

print expr.parseString(test).asList()

prints:

[[[['P', '\\/', 'Q'], '->', 'S'], '==', 'S']]

HTH,
-- Paul