JavaCC中的左迴歸（直接和間接）消除

我在清除JavaCC中的左遞歸時遇到了問題。我找到了一個解決方案Epsilon tokens，但似乎JavaCC無法與Epsilon令牌一起工作得很好（如TOKEN : <eps : "">）。下面我準備一個我的問題的例子：JavaCC中的左迴歸（直接和間接）消除

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

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

在這裏，我們看到直接和不連續的左遞歸。這是我真正語法的一個簡化例子（我的JavaCC語法基於現有的BNF語法，因此我被迫以這種形式使用它）。

來源

2017-03-16 Pavel Sozonov

第二種選擇用於'prod2'只是'prod2'。我懷疑是一個錯字。 –

謝謝！我修復了這個錯字 –

有必要改變語法（不改變語言）。在許多情況下，您可以使用迭代（'{...}'）來解決遞歸。 – Henry

我找到了一個解決方案，它似乎適合我。

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.將Prod2的內部的PROD1

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

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

步驟3.消除左遞歸與小量生產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_小量製作（）（這裏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_()] 
}

來源

2017-03-17 05:41:51

我不確定第三步。我認爲prod2_中prod2的調用不應該在那裏。即你需要'void prod2_（）：{} { prod2_（）| prod2（）_ | {}}。（另外，請注意在JavaCC中爲epsilon使用'{}'。） –

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

展開選項

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

在Prod2的替換PROD1

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

分發

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

重新排列和因子

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

消除左遞歸

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

來源

2017-03-18 16:24:10

JavaCC中的左迴歸（直接和間接）消除

回答

相關問題