[Solved]: Priority in formal grammar

Problem Detail: 

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?

Asked By : URL87

Answered By : yatima2975

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/10142

3.2K people like this

 Download Related Notes/Documents