Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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"


share|cite|improve this question
"unequivocal" means "unambiguous"? I think the concept of "priority" here may be related with operator precedence. Meaning, when parsing using that grammar, resolve any ambiguity between alternatives three and four in favor of four. – Raphael Feb 28 '13 at 10:14
up vote 3 down vote accepted

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

share|cite|improve this answer
  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).

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.