JavaCC中如何消除Exp文法的左递归？已有尝试未成功

你的核心问题是错误地用递归调用Exp()处理左递归，导致循环依赖，根本没消除左递归。正确的做法是将左递归文法转换为基础表达式+迭代后缀的结构，JavaCC通过迭代（()*）替代左递归。

步骤1：拆分文法结构 #

原文法的左递归产生式是：

Exp ::= Exp op Exp
::= Exp [ Exp ]
::= Exp . length
::= Exp . id ( ExpList )

我们需要把Exp拆分为：

1. Primary（基础表达式）：所有无左递归的原子表达式，包括字面量、标识符、new表达式、括号表达式、一元!表达式等。
2. Exp：由Primary加上零个或多个后缀操作组成，后缀操作就是原左递归里的op Exp、[Exp]、.length、.id(ExpList)。

步骤2：修正后的JavaCC代码 #

// 基础表达式：无左递归的原子项
void Primary() :
{}
{
    <INTEGER> <LITERAL>  // 对应INTEGER LITERAL
    | <TRUE>
    | <FALSE>
    | <ID>
    | <THIS>
    | <NEW> <INT> <LBR> Exp() <RBR>  // new int [Exp]
    | <NEW> <ID> <LPAR> <RPAR>       // new id()
    | <NOT> Exp()                     // ! Exp，假设词法中!定义为NOT
    | <LPAR> Exp() <RPAR>             // (Exp)
}

// 消除左递归后的Exp：基础表达式 + 零个或多个后缀操作
void Exp() :
{}
{
    Primary()
    (
        // 后缀操作1：二元操作符 Exp
        <OP> Exp()
        // 后缀操作2：[Exp]
        | <LBR> Exp() <RBR>
        // 后缀操作3：.length 或 .id(ExpList)
        | <DOT>
        (
            <LEN>  // .length
            | <ID> <LPAR> ExpList() <RPAR>  // .id(ExpList)
        )
    )*
}

// 你已有的ExpList方法（假设已实现）
void ExpList() :
{}
{
    Exp() ( <COMMA> Exp() )*
}

关键说明 #

• 原ExpOp方案无效的原因：你之前的ExpOp方法递归调用Exp()，导致Exp()→ExpOp()→Exp()无限循环，完全没解决左递归，反而引入了循环依赖。
• 迭代替代左递归：用()*表示零个或多个后缀操作，完美替代原左递归的Exp ::= Exp 后缀结构，JavaCC能正确解析这种迭代模式。
• 可选优先级调整：如果需要处理表达式优先级（比如后缀操作[]/.length比二元操作符op优先级高），可以进一步拆分出PostfixExp：

  void PostfixExp() :
  {}
  {
      Primary()
      (
          <LBR> Exp() <RBR>
          | <DOT>
          (
              <LEN>
              | <ID> <LPAR> ExpList() <RPAR>
          )
      )*
  }
  
  void Exp() :
  {}
  {
      PostfixExp()
      ( <OP> PostfixExp() )*
  }
  

  这样能保证后缀操作先被解析，符合常规表达式优先级。

内容的提问来源于stack exchange，提问作者Severus