HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

How does one make an unambiguous context-free grammar for arithmetic expressions?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
freemakeexpressionsunambiguousonegrammarfordoeshowcontext

Problem

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 \\
$$

Solution

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:

 ::=  |  "+" 
       ::=  |  "*" 
     ::=  |  | "("  ")"


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

Code Snippets

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

Context

StackExchange Computer Science Q#7443, answer score: 3

Revisions (0)

No revisions yet.