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?

Comments:

It will be a stack based implementation, not relying on recursion.
On thing that has bothered us was that in order to match a constant, in most grammars you have to chase down the rules to the highest depth, making even simple input like `5 + 4` expensive to match.

Turns out that there are interesting approaches out there already, so we can piggyback :)

Check out http://www.antlr.org/wiki/display/~admin/2008/04/10/Still+more+about+expression+parsing for more details on what we have thought about.

Posted by Kay Röpke on June 24, 2008 at 08:45 PM PDT #

Post a Comment:
  • HTML Syntax: NOT allowed
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