4
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • $\begingroup$ "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. $\endgroup$ – Raphael♦ Feb 28 '13 at 10:14
3
$\begingroup$

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

Improve this answer
$\endgroup$
2
$\begingroup$

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

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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