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

Question

我正在为基于 bash 的迷你 shell 程序实现一个递归下降解析器，通常应用右递归。然而，对于逻辑运算符

&&

和

||

来说，这种做法似乎不太方便执行。

例如，当解析诸如

cmd1 && cmd2 || cmd3

之类的命令序列时，正确的递归解析器将生成如下树：

     &&
    /   \
cmd1    ||
        /  \
    cmd2   cmd3

但是，为了使执行正确遵循 bash 逻辑，更适合为

&&

和

||

运算符保留左关联性，从而产生如下所示的树：

    ||
   /  \
&&   cmd3
/ \
cmd1 cmd2

考虑到这种情况，修改解析器以专门处理 && 和 || 的左关联性的推荐方法是什么运算符同时保持其他运算符的正确关联性？是否会涉及解析算法的更改或解析后的后处理步骤？或者有没有办法根据 bash 执行具有右关联性的树？

Answer 1

在 POSIX shell 语法中，&& 和 ||运算符具有相同的优先级并从左到右关联。

使用 Bash 特定的大括号语法，我们可以将其理解为：

A op1 B op2 C      <-->    { A op1 B } op2 C

对于

op1

和

op2

来说，是

||

和

&&

运算符的任意组合。

（我们不能使用括号来显示这一点，因为它们引入了“子shell”进程中执行的语义动作。）

shell 从左到右执行由这些运算符分隔的命令。当分隔符为

&&

时，到目前为止的命令必须成功才能继续。当分隔符为

||

时，到目前为止的命令一定失败了。

解析它与处理

A + B - C ...

相同。递归下降解析标识为 LL(k)（通常 k = 1），而左关联更自然地与 LR 解析配对。语法结构如下：

E := E && E
  |  E || E

是 LL(1) 解析的“左分解”。您不必正式这样做。有一个处理这种情况的代码结构。基本结构是：

1. 解析表达式；就叫它

   E

   。

2. 当下一个标记是

   &&

   或

   ||

   :
   • 消耗代币，称之为

     operator

     。
   • 解析后面的表达式，称之为

     Enext

     。
   • 通过将现有表达式与新表达式组合来构建树节点：

     E := make_node(E, operator, Enext)

     。
   • 从 (2) 开始循环

3. 返回E