Your own dsl: a primer on operators

When writing your own domain specific language (dsl), a full fledged parser generator like antlr can be very helpful with the nitty gritty. You may come to a point where you want to use (infix) operators in your language. But beware! A naive solution might look like:

expr: number '+' expr | number '-' expr | number '*' expr | number '/' expr | …;

If you want to support mathematical like operators this solution misses two important traits: operator precedence and associativity.
Precendence can be easily achieved:

expr: term '+' expr |  term '-' expr | …;
term: number '*' term | number '/' term | …;

The operators with the lowest precedence come first, then the next and so on. Unfortunately this has one side effect: the operators are now right associative.
Which means an expression like 5 – 4 + 3 would evaluate to -2 and not 4. Because of right associativity it is the same as 5 – (4 + 3). So another refinement does the trick:

expr: term (('+'  |  '-' | …) term)*;
term: number (('*' | '/' | …) number)* | …;

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s