0

For a compilation project, my group and me are defining a grammar with Antlr. We have currently a problem with theses rules :

expr: ...
| lvalue expr3 expr2
|  ID '('exprList')' expr2
|... ;


lvalue: ID lvalue2;

lvalue2: '.' ID lvalue2
    | '[' expr ']' lvalue2
    | ;

As you can see, lvalue can result in ID, which lead to a non-LL() grammar. So my question is: how can we modify the grammar so as to make it LL() without permitting extra stuff.

Thank you in advance !

Cédric Rémond
  • 954
  • 1
  • 8
  • 20

1 Answers1

0

Indeed you can refactor the rules, but on the other hand it's not a left recursive construct you use there, so your conclusion this would no longer be LL(k) is not correct. All you have are two alternatives that start with the same token. Factoring that out is, as said, one way to overcome that situation. Another one is to simply increase the lookahead, which allows the parser to also inspect following tokens to decide which alt to take.

You can either set the lookahead value in the grammar options:

options {
  k = 2;
}

or in specific rules to only increase the value for that rule:

expr options { k = 2; }: ...
| lvalue expr3 expr2
|  ID '('exprList')' expr2
|... ;

Note: ANTLR 4 doesn't have this kind of problem as it always has unlimited lookahead.

Mike Lischke
  • 48,925
  • 16
  • 119
  • 181
  • Thanks for your answer. Antlrworks displayed me a non-LL(*) error, so I guessed my grammar not to be LL(k). The major problem was that we had to make it LL(1), so I cannot use your solution. – Cédric Rémond Feb 19 '16 at 10:17