Priority in formal grammar

Question

From my recitation class, I have the following exercise:

$\mathrm{EXP} = 0 \mid 1 \mid b \mathrm{EXP} \mid \mathrm{EXP} a \mid \mathrm{EXP} m \mathrm{EXP}$

The above grammar is ambiguous.

Make an unambiguous grammar which produce same language as the above.

In the new grammar, $a$ has priority over $b$ and $b$ has priority over $m$. Also $m$ is associative.

Can you explain what the phrases

• "has priority over" and
• "$m$ is associative"

mean?

Answer 1

b0a has two subtly different productions (Note: I always expand the leftmost non-terminal):

• EXP --> bEXP --> bEXPa --> b0a and
• EXP --> EXPa --> bEXPa --> b0a,

so that's an example of an ambiguous string.

To give a priority over b means that if you have b0a it will always be parsed as b(0a) (i.e. the first production I showed).

---

For the bit involving b and m, can you find two different productions for b0m0?

---

1m1m0 also has two subtly different productions:

• EXP -> EXPmEXP --> 1mEXP --> 1mEXPmEXP --> 1m1mEXP --> 1m1m0 and
• EXP -> EXPmEXP --> EXPmEXPmEXP --> 1mEXPmEXP --> 1m1mEXP --> 1m1m0.

To make m associative is to remove this ambiguity, so that only one of these parses is possible (from the question, it doesn't seem to matter which one exactly, as long as you choose one and stick to it!)

Answer 2

1. I'm going to guess that, in the case of your example grammar, that "$a$ has priority over $b$, and $b$ has priority over $m$" means that once a $b$ is generated, no more $a$s can be generated, and likewise, once an $m$ is generated, no more $b$s can be generated in any derivation using this grammar.

2. The general property of associativity for a (binary) operator $+$:

   $\forall a,b,c\in U: (a +b)+c = a+(b+c)$

   But, in the context of formal grammars, binary operators are generally declared to be either left-associative, meaning the string $a+b+c$ always has the meaning $(a+b)+c$, or right-associative, meaning the string $a+b+c$ always has the meaning $a+(b+c)$, or non-associative, meaning the string $a+b+c$ has no meaning (it is not a valid string in the language).