如何在语法中实现运算符优先级，修复表达式解析BIDMAS顺序错误

语法修改方案 #

你的现有语法问题是把所有运算符放在同一层级定义，没有做优先级分层，递归下降解析的运算符优先级完全靠语法规则的层级拆分实现，优先级越高的运算符需要定义在越深层的语法规则中。

如果需要实现优先级从高到低为：括号/数字 > 除法 > 乘法 > 加减法，修改后的语法如下：

exp     ::= mul ( ( "+" | "-" ) mul )*
mul     ::= div ( "*" div )*
div     ::= term ( "/" term )*
term    ::= number | "(" exp ")"

规则说明 #

• 用*表示对应片段可重复0次或多次，是为了避免左递归导致递归下降解析器死循环
• 上层规则会优先调用下层规则完成解析，所以越靠近底层的规则对应的运算符优先级越高：
  • 解析加减运算前，会先完成所有乘法、除法、括号和数字的计算
  • 解析乘法运算前，会先完成所有除法、括号和数字的计算
  • 最底层的term规则对应最高优先级的括号和数字，括号内会重新从最高层的exp开始解析，保证括号内的运算优先执行

你提供的测试用例1 + 2 * 3 + 4按该语法解析时，会先计算乘法2 * 3 = 6，再依次计算加减1 + 6 + 4 = 11，结果符合预期。

如果是常规的乘除同优先级、加减同优先级的需求，可简化为两层运算符拆分：

exp     ::= term ( ( "+" | "-" ) term )*
term    ::= factor ( ( "*" | "/" ) factor )*
factor  ::= number | "(" exp ")"

对应递归下降代码只要按规则实现对应层级的解析函数，每个函数消费对应层级的Token返回计算结果即可。

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