Grammar for following JAVA predicates

Question

I'm trying to write productions ( LL ) for the following code

a[i].b[a[p]].id.xyz.a[c].o = i;

Using ASTView in Eclipse, the productions are like

FieldAccess -> Exp NAME
Exp -> FieldAccess
FieldAccess -> ArrayAccess NAME
ArrayAccess -> ArrayAccess Exp
ArrayAccess -> FieldAccess 
Exp -> FieldAccess
.....

How can I define the above in Antlr? They are left recursive and as far as I know JAVA is LL.

Answer 1

It's not possible to create an ANTLR v3 grammar for the rules:

FieldAccess -> Exp NAME
Exp         -> FieldAccess

ANTLR v4 can handle left recursion, but only direct left recursive rules:

Exp -> Exp '*' Exp
     | Exp '/' Exp
     | Exp '+' Exp
     ...
     | Name
     ...

(pseudo grammar syntax!)

but v4 is also not able to cope with your indirect left recursive rules:

FieldAccess -> Exp NAME
Exp         -> FieldAccess

I'm pretty sure you can make ANTLR create an AST just as Eclipse does using some fancy AST rewrite rules, but then you'll have edit your question and "draw" (or post a picture) of the desired AST for the input a[i].b[a[p].x].id.xyz.a[c].o = i;, and I might have a stab at it.

EDIT

Here's a small demo of how to parse your example input in a similar AST as you posted:

grammar T;

options {
  output=AST;
}

tokens {
  ASSIGN;
  IND;
  FA;
}

parse
 : assign EOF -> assign
 ;

assign
 : lookup '=' expr ';' -> ^(ASSIGN lookup expr)
 ;

expr
 : lookup
 ;

lookup
 : (NAME -> NAME) ( array_index  -> ^(IND $lookup array_index)
                  | field_access -> ^(FA $lookup field_access)
                  )*
 ;

array_index
 : '[' expr ']' -> expr
 ;

field_access
 : '.' NAME -> NAME
 ;

NAME  : 'a'..'z'+;
SPACE : ' ' {skip();};

WHen I debug the parser in ANTLRWorks with the input a[i].b[a[p].x].id.xyz.a[c].o = i;, the following AST is being generated:

EDIT

The rule:

lookup
 : (NAME -> NAME) ( array_index  -> ^(IND $lookup array_index)
                  | field_access -> ^(FA $lookup field_access)
                  )*
 ;

is nothing more than this:

lookup
 : NAME ( array_index^
        | field_access^
        )*
 ;

except the first will, for the input "a[i].b", create an AST like this:

        FA
       /  \
     IND   B
     / \
    A   I

where the latter would create a "reversed" AST:

        FA
       /  \
      B   IND
          / \
         I   A

(of course, the FA and IND wouldn't be in the last AST because they're not in the array_index and field_access rules, but if you'd put them there, it would have that structure).