BNF 语法和运算符结合性
(首先这不是硬件,我有所有答案)
我有一个简单的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 或不是 a 和(不是 b 或 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')))))
')' ))))
(First of all this is not HW, I have all the answers)
I have a simple BNF grammar
<UNIT> ::= ( <CLAUSE> ) | a | b | c
<ITEM> ::= not <UNIT> | <UNIT>
<CLAUSE> ::= <CLAUSE> and <PHRASE> | <PHRASE>
<PHRASE> ::= <ITEM> | <ITEM> or <PHRASE>
and
operator is Left associative (left-hand recursive )or
operator is Right associative (this time, it is right-hand recursive )
Given expression c and b or not a and ( not b or c )
, why is most right "and" is higher in the parse tree ?
The way, I see c **and** b or not a and ( not b or c )
left most should be higher in the parse tree.
Our professor provided this answer:
Here is the parse tree in a lispy notation.
(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')))))
')' ))))
给出的 BNF 语法似乎与解析树一致,并且与“and”应该是左关联的主张一致。如果你想用这个语法产生“a and b and c”,从“Clause”开始,你可以这样开始:
此时,Phrase 不能变成“b and c” (不带括号)因为只有从句才能产生“and”。短语必须发展成“c”,第二行的从句可以发展成“a and b”。这将迫使最右边的“和”在解析树中位于更高的位置。
由于解析树中的较高元素是最后评估的,因此这与运算符“and”是左关联的声明是一致的。
The BNF grammar given seems consistent with the parse tree, and consistent with the claim that "and" is supposed to be left-associative. If you want to produce "a and b and c" using this grammar, starting with "Clause", you start this way:
At which point, Phrase cannot become "b and c" (without parentheses) because only clauses can produce "and". Phrase has to develop into "c", and the Clause on the second line can become "a and b". This will force the rightmost "and" to be higher in the parse tree.
Since higher elements in the parse tree are last to evaluate, this is consistent with the claim that the operator "and" is left associative.