BNF-Grammatik und Operatorassoziativität

Question

(Zu allererst ist dies nicht HW, ich habe alle Antworten)

Ich habe eine einfache BNF-Grammatik

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

and Operator links assoziativ (linke rekursiv) or Operator ist recht assoziative (diesmal ist es rechte rekursiv)

Bei Ausdruck c and b or not a and ( not b or c ), warum die meisten rechts „und“ höher in dem Parsing-Baum?
Die Art und Weise, wie ich sehe c **and** b or not a and ( not b or c ) am weitesten links stehenden sollte in dem Parsing-Baum höher sein.

Unser Professor bereitgestellt diese Antwort:

Hier ist der Parsing-Baum in einer 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')))))
')' ))))

Answer 1

Die gegebene BNF-Grammatik scheint mit dem Parsing-Baum im Einklang und im Einklang mit der Behauptung, dass „und“ sollte gelassen werden assoziativ. Wenn Sie „a und b und c“ mit dieser Grammatik, beginnend mit „Klausel“ produzieren möchten, starten Sie auf diese Weise:

1. Klausel
2. Klausel und Satz

An diesem Punkt, Phrase kann nicht „b und c“ werden (ohne Klammern), weil nur Klauseln produzieren „und“ können. Phrase hat in „c“ und die Klausel in der zweiten Zeile werden kann entwickeln „a und b“. Dies wird die äußerste rechte Gewalt „und“ in dem Parsing-Baum höher sein.

Da höhere Elemente in dem Parsing-Baum sind zuletzt zu bewerten, dies steht im Einklang mit der Behauptung, dass der Operator „und“ links assoziativ ist.