grammar - BNF 语法关联性

Question

我正在尝试了解左右关联语法的工作原理，我需要一些帮助。所以我决定举一个例子并要求澄清一下。基本上，我想为两个逻辑操作创建一个语法：and+ implication。我想让它成为and左联想和implication右联想。这是我到目前为止得到的。这个对吗？我觉得这可能是模棱两可的。（我还记住，and它的优先级高于implication）

<exp> := <and>
<and> := <impl> | <and> ^ <impl>
<impl> := <term> | <term> -> <impl>
<term> := (<exp>) | <bool>
<bool> := true | false

Answer 1

根据我有限的知识，在我看来，您的优先级颠倒了。

在语法级别，左结合运算符具有以下格式：

exp = exp op other | other

...并且右结合运算符将具有以下格式：

exp = other op exp | other

如您所见，这取决于您对递归的使用：左关联性将使用左递归规则，而右关联性将使用右递归规则。

至于优先级，语法中的规则越晚，其优先级越高。在下面的语法中， whereopL表示左结合运算符并opR表示右结合运算符，其exp0优先级低于exp1，其优先级低于other：

exp0 = exp0 opL exp1 | exp1
exp1 = other opR exp1 | other
other = ...

例如，如果opL是“+”并且opR是“**”并且other是一个字母，请查看如何构建一些表达式的解析树：

• 左结合性：

  a + b + c -> (a + b) + c
  exp0 -+-> exp0 +-> exp0 --> exp1 --> other --> a
        |        |
        |        +-> opL --> "+"
        |        |
        |        \-> exp1 --> other --> b
        |
        +-> opL --> "+"
        |
        \-> exp1 --> c        
  

• 右结合性：

    a ** b ** c -> a ** (b ** c)
    exp0 --> exp1 +-> other --> a
                  |
                  +-> opR --> "**"
                  |
                  \-> exp1 +-> other --> b
                           |
                           +-> opR --> "**"
                           |
                           \-> exp1 --> other --> c
  

• 优先级：

  a + b ** c -> a + (b ** c)
  exp0 +-> exp0 +-> exp1 --> other --> a
       |
       +-> opL --> "+"
       | 
       \-> exp1 +-> other --> b
                |
                +-> opR --> "**"
                |
                \-> exp1 --> other --> c