java - JavaCC 中的左递归(直接和间接)消除

Question

我在消除 JavaCC 中的左递归时遇到问题。我找到了一个解决方案 Epsilon tokens ，但 JavaCC 似乎无法与 Epsilon token 很好地配合(如 TOKEN : <eps : ""> )。下面我准备了一个我的问题的示例:

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

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

这里我们看到直接左递归和非直接左递归。这是我的真实语法的简化示例(我的JavaCC语法是基于现有的BNF语法，因此我被迫以这种形式使用它)。

Answer 1

我找到了一个解决方案，它似乎适合我。

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

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

步骤 1. 展开 (1)

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

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

第 2 步. 将 prod1 插入 prod2

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

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

步骤 3. 使用 epsilon 产生式消除 prod2 中的左递归(此处描述 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>
}

第 4 步:从 prod2_() 中消除 epsilon 产生式(此处描述 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_()]
}