如何在bash风格迷你Shell的递归下降解析器中处理逻辑运算符左结合性？

问题背景 #

我正在实现一个基于Bash的迷你Shell递归下降解析器，目前采用右递归逻辑，但遇到了逻辑运算符&&和||的执行适配问题。例如解析cmd1 && cmd2 || cmd3时，右递归生成的语法树为：

&&
    /   
cmd1    ||
        /  
    cmd2   cmd3

但Bash的执行逻辑要求&&/||是左结合的，正确的语法树应该是：

||
   /  
&&   cmd3
/ 
cmd1 cmd2

解决方案 #

1. 修改递归下降解析算法（最优方案） #

递归下降默认的右递归写法天然支持右结合，但要实现&&/||的左结合，只需给这两个运算符单独实现迭代式的左递归模拟——这是处理左结合运算符的标准做法，完全不会影响其他右结合运算符（如管道|、重定向>）的原有逻辑。

具体实现逻辑：

• 先解析一个基础命令（如cmd1），作为当前的左节点
• 循环检查当前token是否为&&或||：
  • 若是，先记录运算符，再解析下一个基础命令（如cmd2）
  • 将之前的左节点与新解析的命令，用当前运算符组合成新的左节点（如cmd1 && cmd2）
  • 继续循环，直到遇到非&&/||的token
• 最终返回这个不断组合的左节点，自然生成左结合的语法树

简化伪代码示例：

parse_and_or() {
  node = parse_command()  # 解析基础命令/管道等右结合结构
  while current_token is "&&" or "||":
    op = current_token
    consume_token()
    right_node = parse_command()
    node = new_binary_node(op, node, right_node)
  return node
}

用这个方法解析cmd1 && cmd2 || cmd3时，会先生成cmd1 && cmd2节点，再将该节点与cmd3用||组合，直接得到符合Bash逻辑的左结合语法树。

2. 解析后处理语法树（备选方案） #

如果不想改动解析核心逻辑，可以在生成右递归语法树后，对&&/||节点做左折叠处理：

• 遍历语法树，找到所有以&&/||为根、且右子节点也是同类型运算符的节点
• 将当前节点的右子节点的左子节点替换为当前节点，再把原右子节点作为新的根节点
• 重复上述操作，直到所有&&/||节点都转为左结合结构

比如原右递归树&&(cmd1, ||(cmd2, cmd3))，处理后会变为||(&&(cmd1, cmd2), cmd3)。但这种方法需要额外的树遍历逻辑，效率不如直接修改解析算法。

3. 直接基于右递归语法树执行？不可行 #

右递归生成的树结构与Bash的执行逻辑完全冲突：

• 右递归树会先执行cmd1，随后直接解析并尝试执行cmd2 || cmd3——但Bash的逻辑是cmd1 && cmd2执行成功后，才会判断是否执行cmd3
• 若硬要基于右递归树执行，需要重新定义执行逻辑，把右子树的执行条件改为依赖左节点的结果，这不仅绕弯，还容易出现逻辑错误，完全不符合直觉

总结 #

优先选择修改递归下降解析算法，为&&/||单独实现迭代式左结合解析，既高效又直接匹配Bash的执行逻辑，同时不会影响其他右结合运算符的原有逻辑。

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