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