Priority in formal grammar

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?

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!)

StackExchange Computer Science Q#10142, answer score: 3