[antlr-interest] Logical Expression parser

[John B. Brodie]

Greetings!

On Mon, 2010-02-15 at 22:57 +0000, Nazim Oztahtaci wrote:
> Hi,
> I want to write a parser using ANTLR grammar. I would like to translate the logical expression to Sum of Product form. I give you the example below.
> 

I am not sure that the following will be of any help.

Having the negation as a post-fix modifier, is rather ... unusual to me.
I have never seen that. Is that common practice for you? Can you provide
a reference to any Common Practice using this Form?

So anyway, attached please find a .g file that attempts to construct an
AST for an input in the form that you specify:

> Steps for expression: ((a AND b)
> OR (c AND d))' ->de morgan: (a' OR b') AND (c' OR
> d')->distribution: (a' AND c') OR (a' AND d'.....). So I will have
> DNF form in the result. I plan to use Antlr. I will write the grammar
> and then create the necessary files on the C#. First it would be great
> if you confirm me about it. I will just have AND OR operators and NOT.
> For instance (a OR NOT b) means actually (a or b)not. Also (a NOT OR b
> NOT) means a' OR b'. Do you have any example grammar for this task? I
> found one in codeproject but doesnt explain in bried detailly. Or at least someone can guide me little bit.

As stated above, I have no experience with negation as a post-fix
modifier; which means I have no intuition for how an AST might be best
formulated under this system.

I tried.

I hope it helps.

See attached.

You will need to add tree manipulation pass(s) to this in order to
transform the input AST into your requisite DNF AST.

This is just the first step.

Hope this helps...
   -jbb

-------------- next part --------------
grammar Boolean;

options {
   output = AST;
   ASTLabelType = CommonTree;
}

@members {
   private static final String [] x = new String[]{
      "(a & b) | (c & d)",
      "a & b | c & d",
      "a~ & b | c & d",
      "a~|b~",
      "a |~ b",
      "a | b | c | d",
      "a | b |~ c |~ d",
      "a |~ b~ |~ c | d~ &~ e & f~ | g"
   };

   public static void main(String [] args) {
      for( int i = 0; i < x.length; ++i ) {
         try {
            System.out.println("about to parse:`"+x[i]+"`");
            BooleanLexer lexer = new BooleanLexer(new ANTLRStringStream(x[i]));
            CommonTokenStream tokens = new CommonTokenStream(lexer);

            BooleanParser parser = new BooleanParser(tokens);
            BooleanParser.start_return p_result = parser.start();

            CommonTree ast = p_result.tree;
            if( ast == null ) {
               System.out.println("resultant tree: is NULL");
            } else {
               System.out.println("resultant tree: " + ast.toStringTree());
            }
            System.out.println();
         } catch(Exception e) {
            e.printStackTrace();
         }
      }
   }
}

start : expression EOF!;

expression : ior ;

ior : (a=and -> $a)
      ( ( x='|' i=ior -> ^($x $a $i) )
      | ( x='|' y='~' i=ior -> ^($y ^($x $a $i)) )
      )? ;

and : (n=neg -> $n)
      ( ( x='&' a=and -> ^($x $n $a) )
      | ( x='&' y='~' a=and -> ^($y ^($x $n $a)) )
      )? ;

neg : primary '~'^? ;

primary : VAR | '(' expression ')' ; 

VAR : ('a'..'z'|'A'..'Z'|'0'..'9'|'_')+ ;

// Whitespace -- ignored
WS : ( ' ' | '\t' | '\f' | '\r' | '\n' )+ { $channel=HIDDEN; } ;

// single-line comments
SL_COMMENT :
      '//' ( options { greedy=false; } : . )* ( '\r' | '\r\n' | '\n' )
      { $channel=HIDDEN; }
   ;

// multiple-line comments
ML_COMMENT : NESTED_COMMENTARY { $channel=HIDDEN; } ;

fragment NESTED_COMMENTARY :
      '/*'
      ( options {greedy=false;} : . )*
      ( NESTED_COMMENTARY ( options {greedy=false;} : . )* )*
      '*/'
   ;