My own infix to prefix approach. What do you think?

[Les Bell]

(04-29-2014 04:40 AM)Matt Agajanian Wrote:  And Les, now that I know thar ANTLR book is a Kindle version, I can read it at my leisure (pun intended).

Matt, here's a basic ANTLR grammar that will parse simple algebraic expressions (e.g. it parses your '(2+3)*(4+5)' example perfectly. From this grammar, ANTLR will generate a lexical analyzer, parser and related classes such as a listener that can walk the resultant parse tree and perform operations on it.

Code:


grammar Expr;

options {
  language = Java;
}

fragment
NEWLINE
    : '\r'? '\n' -> skip
    ;

WS
  : ( ' '
    | '\t'
    | ( '\r\n'    // DOS/Windows
      | '\r'      // Mac
      | '\n'      // Unix
      )
    ) -> skip
  ;

fragment
LETTER
  : ('a'..'z' | 'A'..'Z')
  ;

ID
  :  LETTER (LETTER | '0'..'9' | '.')*
  ;

FLOAT
  :  '0'..'9'+ ('.' '0'..'9'+)? ( ('E'|'e')( '+' | '-')? '0'..'9'+)?
  ;

expression
  : term (( '+' | '-' ) term) *
  ;

term
  : unaryfactor (( '*' | '/' ) factor) *
  ;
  
 unaryfactor
  : '-' factor
  | factor
  ;

factor
 : ID
 | FLOAT
 | '(' expression ')'
 ;

And here's a simple Java program that will use the lexer and parser to parse an expression typed into it, and will then print the tree:

Code:


import java.io.IOException;

import org.antlr.v4.runtime.ANTLRInputStream;
import org.antlr.v4.runtime.CommonTokenStream;
import org.antlr.v4.runtime.tree.ParseTree;
import org.antlr.v4.runtime.tree.ParseTreeWalker;

/**
 * 
 */

/**
 * @author les
 *
 */
public class ExpressionParser {

    /**
     * @param args
     * @throws IOException 
     */
    public static void main(String[] args) throws IOException {
        ANTLRInputStream input = new ANTLRInputStream(System.in);
        
        ExprLexer lexer = new ExprLexer(input);
        
        CommonTokenStream tokens = new CommonTokenStream(lexer);
        
        ExprParser parser = new ExprParser(tokens);
        
        ParseTree tree = parser.expression();
        
        System.out.println(tree.toStringTree());


    }

}

I've only just started using ANTLR 4 myself (all my work previously was with ANTLR 3.3) so I haven't gone any further, but I'll probably play around with this example some more when I get time to learn ANTLR 4.

Anyway, there's the beginning of some actual code that can parse infix and emit prefix or postfix notation, if you want to play with it.