BNF 语法和运算符结合性

Question

（首先这不是硬件，我有所有答案）

我有一个简单的 BNF 语法

<UNIT> ::= ( <CLAUSE> ) | a | b | c
<ITEM> ::= not <UNIT> | <UNIT>
<CLAUSE> ::= <CLAUSE> and <PHRASE> | <PHRASE>
<PHRASE> ::= <ITEM> | <ITEM> or <PHRASE>

and 运算符是左关联（左手递归）or 运算符是右关联的（这次是右递归）

给定表达式 c and b or not a and ( not b or c ), ，为什么最右边的“and”在解析树中更高？
路，我看见了 c **and** b or not a and ( not b or c ) 最左边的应该在解析树中更高。

我们的教授给出了这样的答案：

这是用 lispy 表示法表示的解析树。

(clause (clause (clause (phrase (item (unit 'c'))))
'and'
(phrase (item (unit 'b'))
'or'
(phrase (item 'not'
(unit 'a')))))
**'and'** // is higher in parse tree
(phrase (item (unit '('
(clause (phrase (item 'not’(unit 'b'))
'or'
(phrase (item (unit 'c')))))
')' ))))

Answer 1

给出的 BNF 语法似乎与解析树一致，并且与“and”应该是左关联的主张一致。如果你想使用这个语法生成“a and b and c”，从“Clause”开始，你可以这样开始：

1. 条款
2. 条款 和 短语

此时，Phrase 不能变成“b and c”（没有括号），因为只有从句才能产生“and”。短语必须发展成“c”，第二行的从句可以发展成“a and b”。这将迫使最右边的“和”在解析树中位于更高的位置。

由于解析树中的较高元素是最后评估的，因此这与运算符“and”是左关联的声明是一致的。