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

...and是一个右关联运算符，其格式如下：

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 --> a -> a+ +-> opL ->+ --> -> exp1 ->其他->b+ +-> opL -> "+“-> exp1 ->c
• 右结合性： A ** b*c -> a ** (b * c) exp0 -> exp1 +-> exp1 +-> opR -> " **“->exp1 +->其他->b +-> opR -> "**“-> exp1 ->其他->c
• 优先顺序： A+b ** c -> a+ (b * c) exp0 +-> exp0 +-> exp1 -> a+ +-> opL -> "+“-> exp1 +->其他->b +-> opR -> " **”exp1 ->->->exp1->其他->c