如何消除这种左递归

Question

我正在编译器构造中做一个作业，我在左递归方面遇到了问题。JavaCC 为表达式 （） 和 condition（） 给我一个错误"检测到左递归"，如下所示。每个的第二行是相同的，所以我假设这就是问题所在。

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()
}

Answer 1

类似的例子几乎可以在任何关于编译的书中找到。 你也可以看看我的教程 通过递归下降解析表达式. 或任何其他免费教程中的任何一个。

这是一个解决方案。 首先，我要像这样重写表达式

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星）。

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()
}

这消除了左递归。

它仍然会给你留下一些选择冲突。这些可以通过语法前瞻来消除。 您还需要处理运算符优先级，但这很简单。 请参阅教程中的"经典"解决方案。