"Left recursion detected" when translating from BNF

[Bertram]

Hello,

I am new to Javacc, so there might be a very obvious solution to this.
This is a left recursion problem (Left recursion detected:).

Here the 1:1 translation of the related BNF description:

void searchExp():
{}
{
    relExp()
    |  searchExp() logOp() searchExp()  // this line is the problem
    | "(" searchExp() ")"
       
}  

void logOp():
{}
{
         <T_OR>
         | <T_AND>
}


All solutions I found so far, do not cover all scenarios.

Any help much appreciated !!

Bertram

[Artur Rataj]

Decide on the associativity of the operator. If you want the operator to have a left associativity:

void searchExp():
{}
{
  
     relExp() ( logOp() relExp() )*
   | "(" searchExp() ")"

}

If you'd like to search more for this, the problem is generally called resolving left recursion.

On Tue, Mar 24, 2009 at 10:03 AM, Bertram <bertram@...> wrote:

Hello,

I am new to Javacc, so there might be a very obvious solution to this.
This is a left recursion problem (Left recursion detected:).

Here the 1:1 translation of the related BNF description:

void searchExp():
{}
{
   relExp()
   |  searchExp() logOp() searchExp()  // this line is the problem
   | "(" searchExp() ")"

}

void logOp():
{}
{
        <T_OR>
        | <T_AND>
}

[Bertram]

left associativity is what I need.

But:
Lets say: relExp can just be one of "ABC"
with the original expression I'm able to recognize:

A OR (B AND C)

I don't see how this works with <relExp() ( logOp() relExp() )* | "(" searchExp() ")"> ?

So I tried:

<relExp() (logOp() searchExp())* | "(" searchExp() ")">

But here I get "Warning: Choice conflict in (...)*". With the suggested solution (LOOKAHEAD(some_number)) I can't solve this.

Is the warning in this case to be ignored, or is there a different way ?
thanx

Artur Rataj wrote:

Decide on the associativity of the operator. If you want the operator to
have a left associativity:

void searchExp():
{}
{

     relExp() ( logOp() relExp() )*
   | "(" searchExp() ")"

}

If you'd like to search more for this, the problem is generally called
resolving left recursion.



On Tue, Mar 24, 2009 at 10:03 AM, Bertram <[e-mail]> wrote:

>
>
> Hello,
>
> I am new to Javacc, so there might be a very obvious solution to this.
> This is a left recursion problem (Left recursion detected:).
>
> Here the 1:1 translation of the related BNF description:
>
> void searchExp():
> {}
> {
>    relExp()
>    |  searchExp() logOp() searchExp()  // this line is the problem
>    | "(" searchExp() ")"
>
> }
>
> void logOp():
> {}
> {
>         <T_OR>
>         | <T_AND>
> }
>
>

[Artur Rataj]

I am sorry I have overlooked that you have put the parenthesized expression under searchExp.

Expression in parentheses is usually at the very bottom of the expression tree, "(" searchExp() ")" should be one of the choices of relExp.

[Bertram]

That did it, thanx a lot.

Artur Rataj wrote:

I am sorry I have overlooked that you have put the parenthesized expression
under searchExp.

Expression in parentheses is usually at the very bottom of the expression
tree, "(" searchExp() ")" should be one of the choices of relExp.