Search code examples
programming-languagesgrammarbnfassociativity

BNF grammar and Operator Associativity

(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')))))
')' ))))
Solution

  • 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:

    1. Clause
    2. Clause and Phrase

    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.