基于ANTLR4的中缀转后缀翻译器语义动作修正问询

当前使用ANTLR4的g4语法实现中缀表达式转后缀表达式时，输入a + b * c得到错误输出a b + c *，正确结果应为a b c * +，问题仅在包含*//运算符时出现。

问题根源 #

现有语法通过expr → term rest的结构统一处理所有运算符，虽然规则顺序能实现语法层面的优先级，但语义动作的拼接逻辑错误：

• 对于*//的处理，错误地将当前操作数放在前，再拼接后续结果和运算符，导致高优先级运算的运算符被后置到低优先级运算之后。
• 运算符前后的空格处理不一致，导致输出格式混乱。

修正方案 #

重构语法结构，通过分层规则明确运算符优先级（*//高于+/-），并为每个层级编写正确的语义动作，确保后缀表达式的运算符顺序符合优先级要求：

1. 将表达式分为三层：
   • expr：处理加减运算（低优先级）
   • term：处理乘除运算（高优先级）
   • factor：处理原子项（标识符、数字、括号表达式）
2. 每个层级的语义动作遵循后缀表达式规则：操作数在前，运算符在后，且高优先级运算的运算符先于低优先级运算输出。

修正后的完整g4语法 #

start returns [String node]: e=expr <EOF> {$node = $e.node;};

// 处理加减运算，优先级低于乘除
expr returns [String node]
    : e=expr '+' t=term       {$node = $e.node + " " + $t.node + " +";}
    | e=expr '-' t=term       {$node = $e.node + " " + $t.node + " -";}
    | t=term                  {$node = $t.node;}
    ;

// 处理乘除运算，优先级高于加减
term returns [String node]
    : t=term '*' f=factor     {$node = $t.node + " " + $f.node + " *";}
    | t=term '/' f=factor     {$node = $t.node + " " + $f.node + " /";}
    | f=factor                {$node = $f.node;}
    ;

// 处理原子表达式
factor returns [String node]
    : Id                      {$node = $Id.text;}
    | Num                     {$node = $Num.text;}
    | '(' e=expr ')'          {$node = $e.node;}
    ;

// 词法规则
Id  : [a-z]+ ;
Num : [0-9]+ ;
WS  : [ \t\r\n]+ -> skip;

测试验证 #

输入a + b * c时，解析过程如下：

1. expr匹配term + term，其中第一个term是a，第二个term是term * factor
2. 第二个term匹配factor * factor，即b * c，生成后缀b c *
3. 最终expr生成a b c * +，与预期结果一致。

其他测试用例：

• 输入a * b + c * d → 输出a b * c d * +
• 输入(a + b) * c → 输出a b + c *

原Java主类无需修改 #

原SimpleMain类代码保持不变，即可正确运行并输出修正后的后缀表达式。

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