CODEWITHSUNDEEP
javaparsingrecursiongrammarjavacc
Pavel Sozonov
Pavel Sozonov

Reputation: 11

Left recurion (direct and indirect) eliminating in JavaCC

I have a problem with eliminating left recursions in JavaCC. I found a solution with Epsilon tokens, but it seems that JavaCC is not able to work very well with Epsilon tokens (like TOKEN : <eps : "">). Below I prepare an example of my issue:

void prod1() : 
{}
{
    <beta1>
    | prod2() <alpha1>
}

void prod2() : 
{}
{
    <beta2>
    | [prod2()] <alpha2>
    | prod1() <alpha3>
}

Here we see both direct and undirect left recursion. It is a simplified example of my real grammar (My JavaCC grammar is based on existing BNF grammar, hence I forced to use it in such form).

Upvotes: 0

Views: 332

Answers (2)

Theodore Norvell
Theodore Norvell

Reputation: 16241

prod1 --> beta1 | prod2 alpha1
prod2 --> beta2 | [prod2] alpha2 | prod1 alpha3

Expand the option

prod1 --> beta1 | prod2 alpha1
prod2 --> beta2 | alpha2 | prod2 alpha2 | prod1 alpha3

Replace prod1 in prod2

prod1 --> beta1 | prod2 alpha1
prod2 --> beta2 | alpha2 | prod2 alpha2 | (beta1 | prod2 alpha1) alpha3

Distribute

prod1 --> beta1 | prod2 alpha1
prod2 --> beta2 | alpha2 | prod2 alpha2 | beta1 alpha3 | prod2 alpha1 alpha3

Rearrange and factor

prod1 --> beta1 | prod2 alpha1
prod2 --> (beta2 | alpha2 | beta1 alpha3) | prod2 (alpha2 | alpha1 alpha3)

Eliminate left recursion

prod1 --> beta1 | prod2 alpha1
prod2 --> (beta2 | alpha2 | beta1 alpha3) (alpha2 | alpha1 alpha3)*

Upvotes: 0

Pavel Sozonov
Pavel Sozonov

Reputation: 11

I found a solution, and it seems to be fit for me.

void prod1() : 
{}
{
    <beta1>
    | prod2() <alpha1>
}

void prod2() : 
{}
{
    <beta2>
    | [prod2()] <alpha2> // (1)
    | prod1() <alpha3>
}

Step 1. Expand (1)

void prod1() : 
{}
{
    <beta1>
    | prod2() <alpha1>
}

void prod2() : 
{}
{
    <beta2>
    | <alpha2>
    | prod2() <alpha2>
    | prod1() <alpha3>
}

Step 2. Insert the prod1 inside of the prod2

void prod1() : 
{}
{
    <beta1>
    | prod2() <alpha1>
}

void prod2() : 
{}
{
    <beta2>
    | <alpha2>
    | prod2() <alpha2>
    | <beta1> <alpha3>
    | prod2() <alpha1> <alpha3>
}

Step 3. Eliminate left recursion in prod2 with epsilon productions (described here https://en.wikipedia.org/wiki/Left_recursion)

void prod1() : 
{}
{
    <beta1>
    | prod2() <alpha1>
}

void prod2() : 
{}
{
    <beta2> prod2_()
    | <alpha2> prod2_()
    | <beta1> <alpha3> prod2_()
}

void prod2_() :
{}
{
    prod2() <alpha2> prod2_()
    | prod2() <alpha1> <alpha3> prod2_()
    | <epsilon>
}

Step 4. Eliminate epsilon productions from prod2_() (described here http://www.d.umn.edu/~hudson/5641/l11m.pdf)

void prod1() : 
{}
{
    <beta1>
    | prod2() <alpha1>
}

void prod2() : 
{}
{
    <beta2> [prod2_()]
    | <alpha2> [prod2_()]
    | <beta1> <alpha3> [prod2_()]
}

void prod2_() :
{}
{
    prod2() <alpha2> [prod2_()]
    | prod2() <alpha1> <alpha3> [prod2_()]
}

Upvotes: 1

Related Questions