1

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

我有一个简单的 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 )，为什么最正确的“和”在解析树中更高？
方式，我看到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')))))
')' ))))
4

1 回答 1

1

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

  1. 条款
  2. 从句和短语

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

由于解析树中较高的元素最后被评估，这与运算符“and”是左结合的说法一致。

于 2010-11-02T18:19:55.870 回答