Suppression de gauche (directe et indirecte) dans JavaCC

Question

J'ai un problème avec l'élimination des récursions de gauche dans JavaCC. J'ai trouvé une solution avec Epsilon tokens, mais il semble que JavaCC ne fonctionne pas très bien avec les jetons Epsilon (comme TOKEN : <eps : "">). Ci-dessous je prépare un exemple de ma question:

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

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

Ici, nous voyons à la fois directe et undirect à gauche récursivité. C'est un exemple simplifié de ma vraie grammaire (Ma grammaire JavaCC est basée sur la grammaire BNF existante, donc je suis obligé de l'utiliser sous une telle forme).

Answer 1

J'ai trouvé une solution, et elle me semble convenir.

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

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

Étape 1. Développer (1)

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

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

Étape 2. Insérez le prod1 intérieur de la prod2

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

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

Étape 3. Éliminez récursion à gauche dans prod2 avec des productions epsilon (décrit ici 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> 
} 

Étape 4. Éliminer les productions epsilon de prod2_() (décrit ici 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_()] 
} 

Answer 2

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

Développer l'option

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

Remplacer prod1 dans prod2

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

Distribution

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

Réorganiser et facteur

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

récursion Éliminer les

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