Pre- and postfix operators in Xtext

While re-visiting some Xtext DSLs I made earlier, I came across one which some ambiguities (reported by ANTLR) due to the use of a prefix operator in an expressions sub language. Fixing that stymied me enough to warrant this blog. (It’s actually a sort of addendum to Sven Efftinge’s excellent blog on expression parsing. I’ll do a blog later on to recap everything.)

For the sake of minimizing effort for all parties involved, we’ll extend the Arithmetics example that’s shipped with Xtext with a unitary minus as prefix operator and the signum function (which returns -1, 0, or 1 depending on whether the operand is negative, zero or positive) as postfix operator. (I chose the signum function because it’s an instance method of the BigDecimal class which is used for the interpreter.)

If you’ve had a good, hard look at the grammar of the Arithmetics example or Sven’s blog, you might have realized that the patterns there amount exactly to implementing a classical recursive-descent parser, right in Xtext’s grammar definition language. The rules of the expression language form a (strictly-ordered) sequence, each of which start of calling the next rule in the sequence before trying to match anything else (and doing a tree rewrite with the result of the rule call). The net effect is that the sequence order equals the precedence order, with the first rule corresponding to the lowest precedence and the last rule in the sequence corresponding to the highest level, typically consisting of the ubiquitous parentheses and possibly other things like literals, variable references and such.

We’re going to extend that pattern to deal with pre- and postfix operators as well. The relevant section of the Arithmetics grammar consists of lines 46-52 of the Arithmetics.xtext file:

Multiplication returns Expression:
    PrimaryExpression (({Multi.left=current} '*' | {Div.left=current} '/') right=PrimaryExpression)*;

PrimaryExpression returns Expression:
    '(' Expression ')' |
    {NumberLiteral} value=NUMBER |
    {FunctionCall} func=[AbstractDefinition] ('(' args+=Expression (',' args+=Expression)* ')')?;

We’re going to add two rules, called UnitaryMinus and Signum, in between the Multiplication and PrimaryExpression rules, so we have to change the Multiplication rule:

Multiplication returns Expression:
    UnitaryMinus (({Multi.left=current} '*' | {Div.left=current} '/') right=UnitaryMinus)*;

Matching the unitary minus prefix operator is simple enough:

UnitaryMinus returns Expression:
    '-' expr=UnitaryMinus;

Since this rule always consumes at least one token, the ‘-‘ character, from the input, we can recursively call UnitaryMinus without causing left-recursion. The upshot of this is that ‘–37’ is parsed as -(-(37)). Unfortunately, the rule (as it is) would break the sequence of rules, so that we’d lose the higher levels of precedence altogether. To prevent that, we also call the next rule, Signum, as an alternative:

UnitaryMinus returns Expression:
    Signum | ({UnitaryMinus} '-' expr=UnitaryMinus);

(We need the {UnitaryMinus} action here to make sure the Xtext generator generates a corresponding type in the Ecore model which holds the parsed info.)

Implementing the postfix operator is a matter of calling the next rule (PrimaryExpression) and performing a tree rewrite in case the postfix operator can be matched:

Signum returns Expression:
    PrimaryExpression ({Signum.expr=current} 's')?;

This is all that’s required for the grammar. Now, we only have to fix the Calculator class and add a couple of test cases in the CalculatorTest class. The Calculator class uses the PolymorphicDispatcher class I wrote about earlier which means we just have to add methods corresponding to the new UnitaryMinus and Signum types:

	protected BigDecimal internalEvaluate(UnitaryMinus unitaryMinus, ImmutableMap<String,BigDecimal> values) {
		return evaluate(unitaryMinus.getExpr(),values).negate();
	}
	protected BigDecimal internalEvaluate(Signum signum, ImmutableMap<String,BigDecimal> values) {
		return new BigDecimal( evaluate(signum.getExpr(),values).signum() );
	}

We add a couple of test cases, specifically for the new operators:

    public void test_unitary_minus_and_signum() throws Exception {
        check(-1,	"1 + -2");	// == 1 + (-2)
        check(1,	"-1 + 2");	// == (-1) + 2, not -(1 + 2)
        check(-1,	"-3.7s");	// == -(3.7s) == -1
        check(0,	"1 + -7s");	// == 1 + -(7s) == 1 + -(1) == 0
        check(2,	"--2");		// == -(-2)
    }

Now go out and add your pre- and postfix operators to your DSL today! 🙂