Logic expression parser

Question

I'm trying to create a logic expression parser for expressions like: ((VariableA -> VariableB) AND NOT VariableC) The parser should be able to return, wheather the result is true or false for given values of variables.

Basicly the expressions will only contain variables, logical operators (or, and, implication, equivalence, negation and parenthaises).

I would like to ask what is the best way to implement this kind of parser (using AST tree, or Reverse Polish Notation)? Or maybe there already exist some open source parsers that can do the job?

Answer 1

I would use RPN if I were you. That should save you some grief when parsing it, and the algorithm should be as simple as pushing and popping a stack of values as the operators come in. You won't have to fool with parentheses either, which should make life easier. The only real downside is that most people aren't familiar with postfix (AKA RPN) notation.

A stack will probably be easier to work with than a tree as well.

Just my 2¢ :)

Answer 2

What language are you targeting?

If you want to create a parser, maybe ANTLR will do the trick for you. It is originally java-based but it has generators for a variety of languages (I use it for generating a C# parser for example) and is no too difficult to pick-up. It has a nice editor (ANTLRWorks) that allows testing the grammar, which is a nice plus.

Answer 3

I'm sure there are already tools that do this (logic evaluation), but I couldn't find any. If you use a tool such as Bison (YACC, for C) or ANTLR (generates a number of languages, but uses Java) you won't have to worry much about parsing. Coco/R is another parser generator that can generate many different languages. If you want to do it yourself though, I would use RPN or prefix notation (which I think is simpler than RPN). This will make it much simpler to parse, but will annoy your users.

Answer 4

It sounds like a homework :-)

First you have to define your language recursively.

A variable is well formed form (WFF)

if X is a WFF then not X is a WFF

if X and Y are WFF then (X -> Y) is a WFF

if X and Y are WFF then (X AND Y is) a WFF

Once the grammar is defined use LEX or Flex or the equivalent for Java or your prefered language for writing a trivial scanner.

Use YACC or Bison or the equivalent for writing the descendent recursive parser.

Later add attributes to the grammar in order to get the evaluation of the expression you want to evaluate in a descendent recursive way.

Answer 5

If you are working in Python, try this expression parser/evaluator, written using pyparsing, as a starting point.