如何消除这个左递归
How to eliminate this left recursion
我正在编译器构造中进行赋值,但在左递归方面遇到了问题。对于 expression() 和 condition(),JavaCC 给我一个错误“检测到左递归”,如下所示。每个第二行都是一样的,所以我认为是问题所在。
A → Aα|β
A → βA'
A' → ε|αA'
这是用来说明如何消除左递归的公式。我已经在讲座以及在线视频和解释中理解了这个概念,但我不知道如何在这里应用它。谁能告诉我如何消除左递归?
void expression() :
{ }
{
fragment() binary_arith_op() fragment()
| <OPAREN> expression() <CPAREN>
| <ID> <OPAREN> arg_list() <CPAREN>
| fragment()
}
void fragment() :
{ }
{ (<MINUS_SIGN>)? <ID> | <NUM> | <TRUE> | <FALSE> | expression() }
void condition() :
{ }
{ <TILDE> condition()
| <OPAREN> condition() <CPAREN>
| expression() comp_op() expression()
| condition() (<OR> | <AND>) condition()
}
类似的例子几乎可以在任何一本关于编译的书中找到。你也可以看看我的教程Parsing Expressions by Recursive Descent。或任何其他免费教程。
这是一个解决方案。首先我要像这样重写表达式
void expression() :
{ }
{
expression() binary_arith_op() expression()
|
simpleExpression() :
}
void simpleExpression() :
{ }
{ (<MINUS_SIGN>)? <ID> | <NUM> | <TRUE> | <FALSE>
| <OPAREN> expression() <CPAREN>
| <ID> <OPAREN> arg_list() <CPAREN> }
现在清楚什么是 alpha 和 beta 了。所以我们得到
void expression() :
{ }
{
simpleExpression() expressionPrime()
}
void expressionPrime() :
{ }
{
binary_arith_op() expression()
|
{}
}
但是在JavaCC中,我们还不如使用循环(即Kleene star)。
void expression() :
{ }
{
simpleExpression() (binary_arith_op() simpleExpression())*
}
void simpleExpression() :
{ }
{ (<MINUS_SIGN>)? <ID> | <NUM> | <TRUE> | <FALSE>
| <OPAREN> expression() <CPAREN>
| <ID> <OPAREN> arg_list() <CPAREN> }
条件类似
void condition() :
{ }
{
simpleCondition() ((<OR> | <AND>) simpleCondition())*
}
void simpleCondition() :
{ }
{
<TILDE> condition()
| <OPAREN> condition() <CPAREN>
| expression() comp_op() expression()
}
这消除了左递归。
它仍然给你留下了一些选择冲突。这些可以使用句法前瞻来消除。您还需要处理运算符优先级,但这很简单。请参阅我的教程中的 "classic" 解决方案。
我正在编译器构造中进行赋值,但在左递归方面遇到了问题。对于 expression() 和 condition(),JavaCC 给我一个错误“检测到左递归”,如下所示。每个第二行都是一样的,所以我认为是问题所在。
A → Aα|β
A → βA'
A' → ε|αA'
这是用来说明如何消除左递归的公式。我已经在讲座以及在线视频和解释中理解了这个概念,但我不知道如何在这里应用它。谁能告诉我如何消除左递归?
void expression() :
{ }
{
fragment() binary_arith_op() fragment()
| <OPAREN> expression() <CPAREN>
| <ID> <OPAREN> arg_list() <CPAREN>
| fragment()
}
void fragment() :
{ }
{ (<MINUS_SIGN>)? <ID> | <NUM> | <TRUE> | <FALSE> | expression() }
void condition() :
{ }
{ <TILDE> condition()
| <OPAREN> condition() <CPAREN>
| expression() comp_op() expression()
| condition() (<OR> | <AND>) condition()
}
类似的例子几乎可以在任何一本关于编译的书中找到。你也可以看看我的教程Parsing Expressions by Recursive Descent。或任何其他免费教程。
这是一个解决方案。首先我要像这样重写表达式
void expression() :
{ }
{
expression() binary_arith_op() expression()
|
simpleExpression() :
}
void simpleExpression() :
{ }
{ (<MINUS_SIGN>)? <ID> | <NUM> | <TRUE> | <FALSE>
| <OPAREN> expression() <CPAREN>
| <ID> <OPAREN> arg_list() <CPAREN> }
现在清楚什么是 alpha 和 beta 了。所以我们得到
void expression() :
{ }
{
simpleExpression() expressionPrime()
}
void expressionPrime() :
{ }
{
binary_arith_op() expression()
|
{}
}
但是在JavaCC中,我们还不如使用循环(即Kleene star)。
void expression() :
{ }
{
simpleExpression() (binary_arith_op() simpleExpression())*
}
void simpleExpression() :
{ }
{ (<MINUS_SIGN>)? <ID> | <NUM> | <TRUE> | <FALSE>
| <OPAREN> expression() <CPAREN>
| <ID> <OPAREN> arg_list() <CPAREN> }
条件类似
void condition() :
{ }
{
simpleCondition() ((<OR> | <AND>) simpleCondition())*
}
void simpleCondition() :
{ }
{
<TILDE> condition()
| <OPAREN> condition() <CPAREN>
| expression() comp_op() expression()
}
这消除了左递归。
它仍然给你留下了一些选择冲突。这些可以使用句法前瞻来消除。您还需要处理运算符优先级,但这很简单。请参阅我的教程中的 "classic" 解决方案。