How do I enforce correct associativity of binary operators in a CFG?
Generally, if we say a binary operator is associative, we mean that ∀ a b c. a ⊗ (b ⊗ c) = (a ⊗ b) ⊗ c However, when dealing with CFGs, the term is used with a slightly different meaning. We describe a binary operator as associating in a certain direction, based on the structure of the derivation for bracketless expressions involving multiple uses of that operator. This is best seen by example. Consider the expression a ⊗ b ⊗ c We say that ⊗ associates to the left if we want to consider the expression to have the structure (a ⊗ b) ⊗ c and that ⊗ associates to the right if we want to consider the expression to have the structure a ⊗ (b ⊗ c) We can also describe binary operators as non-associative if we desire bracketless expressions involving multiple uses of the operator to be invalid. For example, a ≤ b ≤ c When it comes to writing a grammar to enforce these associativity directions, they generally have the following forms: • For non-associative binary operators: R → E ≤ E | E • For b
