Home > DSLs, The How, Xtext > More on pre- and postfix operators in Xtext

More on pre- and postfix operators in Xtext

In the previous blog, I entirely glossed over the aspect of associativity of operators. I turns out that the unitary minus operator we constructed is right-associative and the signum operator is non-associative. In general, prefix operators can either be right-associative, meaning the operations are grouped from right to left, or non-associative, meaning that the operator can’t bind with operators of the same precedence (including itself). Postfix operators can either be left-associative (exemplified by “x++–“) or non-associative.

We already ascertained the right-associativity of the unitary minus by means of the last line in the unit test in the previous post: if unitary minus were non-associative, then “- -2” would trigger a parse error and not be equal to 2. We can check the non-associativity of the signum operator with the following test (still as part of the CalculatorTest class), which asserts that parsing “-2s s” yields a parse error:

    public void test_associativity_of_signum() throws Exception {
		getResourceAndExpect(new StringInputStream("module test  -2s s;"), 1);

(I’ll explain about the extra space in the expression string “-2s s” in a minute.)

It’s not difficult to make our prefix operator non-associative: we simply call the grammar rule UnitaryMinus call the rule for the next precedence level instead of calling itself.

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

We can test this by trying to parse “–2” and expecting a (1) parse error.

Making the postfix operator left-associative is equally simple: we replace the ?-cardinality with a *-cardinality.

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

We can test this by checking whether “2s s” is parsed (and equals 1).
(The following “obvious” solution “obviously” introduces left-recursion:

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

As usual with implementing left-recursive grammars with LL parser technology, this is circumvented with tree writing, in the case of Xtext using actions.)

The only problem with this grammar is that it doesn’t parse something like “-2ss”. The reason for that is that the sub string “ss” is lexed as an ID token instead of a sequence of ‘s’ terminals. By introducing an extra hidden token (whitespace or comments) in between, we force the lexer to produce a sequence of ‘s’ terminals, but that means we’re bothering the DSLs users with it. A better solution would be to choose a character for the postfix operator that doesn’t clash with the ID terminal rule (the σ character would’ve been a rather obvious choice, in this case) or rewrite the ID terminal rule to not match the regexp /s+/.

Categories: DSLs, The How, Xtext

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 )

Connecting to %s

%d bloggers like this: