Friday Dec 05, 2008

See how your java source file is parsed

I've written a new visual tool showing how a Java file is parsed using the Java grammar from Compiler Grammar project.

For more details, see here .


Sunday Jun 15, 2008

Stack based vs Recursive descent

For expression like  "a && b || c == d", javac parses int a stack based way, with while loops, pushes and pops.

With the current antlr java grammar, this is parsed by making various sub-rules, which are reflected into varous method calls in the parser code:

AndExpression
    :   
        ID ( '&&' ID )\*
    ;

OrExpression
    :   
        AndExpression( '||' AndExpression)\*
    ;

relationalExpression
    :   
        OrExpression '==' OrExpression
    ;

This handles operator precedence very well and is easy to read and code, but with each expression (even a single identifier) being parsed by making many method calls, speed is going to be a problem.  


Optimization is possible by writing a grammar like
    expression :
            ID (('&&' | '||' | '==') ID)\*


This doesn't handle precedence very well, but this way it is possible to parse the expression with stacks, thus not that many method calls, with more space requirement though :)
And I'm also expecting the new antlr feature could help here, which gives operators precedence by the sequence they are listed.
Only I'm not sure if it is still been translated into many sub-rules, or if it is implemented in a stack based way?

About

Yang Jiang

Search

Categories
Archives
« April 2014
SunMonTueWedThuFriSat
  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
   
       
Today