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

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

至于优先级，规则在语法中越靠后，其优先级越高。在下面的文法中，opL代表左结合运算符，opR代表右结合运算符，exp0的优先级低于exp1，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

BNF 文法结合律

BNF grammar associativity

grammar

bnf

associativity

ambiguous-grammar