BNF parsing rule for left associativity

parsingsyntax

Can someone please assist me with the following question.

Write a BNF rule to parse into

C -> E
C -> E && E
C -> E && E && E

so that C generates as many E && E as needed and enforces left association.

Is the following correct?

C -> C && E | E

It should force left association because of the left recursion and make as many && E's it wants to because of the recursion.

Best Answer

Apart from some formatting issues (-> doesn't exist in formal BNF), your rule is correct. Written in proper BNF syntax and using quotes around literals, it would be

C ::= C '&&' E | E

The left-recursion indeed creates a parse tree for a left-associative operator.

Related Topic