Take the 2-minute tour ×
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.

Say I have a context-free grammar defined by the following rule.

$$ \langle EXPR\rangle \rightarrow \langle EXPR\rangle + \langle EXPR\rangle~|~\langle EXPR\rangle \times \langle EXPR\rangle~|~(\langle EXPR \rangle)~|~x $$

This grammar is ambiguous since, for instance, I can generate the string $x + x \times x$ via more than 1 leftmost derivation.

How could I make this grammar unambiguous? Should I make sure that no $\langle EXPR\rangle + \langle EXPR\rangle$ is evaluated after a $\langle EXPR\rangle \times \langle EXPR\rangle$ as such:

$$ \langle EXPR\rangle \rightarrow \langle EXPR\rangle + \langle EXPR\rangle~|~\langle MUL\_EXPR\rangle \times \langle MUL\_EXPR\rangle~|~(\langle EXPR \rangle)~|~x \\ \langle MUL\_EXPR \rangle \rightarrow \langle EXPR\rangle \times \langle EXPR\rangle~|~(\langle EXPR \rangle)~|~x \\ $$

share|improve this question
    
So, do you mean in general or in this case? –  Raphael Jan 16 '13 at 10:19
add comment

2 Answers

Indeed you made a step to resolve ambiguity, but your solution does not give a fully unmabiguous grammar yet. The string $x+x+x$ can be parsed in two different ways, like $x + [x+x]$ or like $[x+x]+x$, where the brackets indicate parses. As far as I see your solution resolves semantical ambiguities (it fixes the relative order of + and x) but not the syntactical ambiguity. So obtaining an umambiguous grammar is not the only goal for an example like this: we want to respect meaning (here operator precedence). (Perhaps there is more official terminology for that)

Your example is a familiar one, and is used in wikipedia/Syntax diagram:

<expression> ::= <term> | <expression> "+" <term>
<term>       ::= <factor> | <term> "*" <factor>
<factor>     ::= <constant> | <variable> | "(" <expression> ")"

Probably you will know that not every grammar has an unambiguous equivalent, so no general approach is possible.

share|improve this answer
add comment

i don't think there is a fixed method of derivations to make a grammar unambiguous. you have to try by trail and error method by adding new non-terminals to the grammar without changing the definition of that grammar.

share|improve this answer
    
Indeed, no such method exists: see e.g. people.cis.ksu.edu/~rhowell/770s03/lectures/23-twoup.pdf –  reinierpost Jan 16 '13 at 14:45
    
BTW, I found this with google.com/search?q=ambiguity+undecidable which comes up with quite a few more useful links. –  reinierpost Jan 16 '13 at 14:46
add comment

Your Answer

 
discard

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.