Archive

Archive for the ‘The How’ Category

Multi-level modeling: what, why and how

October 4, 2014 2 comments

One of the arguably-classical problems of language engineering is literal notation. Basically, as soon as you can refer to (/name) types, you’d also want to be able to instantiate those types. As it so often happens, the nomer “classical problem” does not imply that is has been solved to some degree of satisfaction. Just look at Java which still lacks a good literal syntax for object and collection instantiation, even with a library like Google Guava. Only fairly recently have more main stream GPLs emerged which happened to have syntactically nice object and collection literals.

But in this blog I only will talk about multi-level modeling, which can be informally defined as being able to model “things” and to then also be able to model instances of those “things”. The multi-level aspect comes from the fact that instances of “things” live one meta level down from the “things” themselves. I will only consider 2-level modeling, i.e. we only “descend” one meta level. Arbitrarily-deeply nested multi-level modeling is certainly possible but is also a magnitude more difficult and for the purposes of our exposé not that relevant.

As an example, consider the archetypical data modeling DSL in which you can model entities having named features: attributes with a data type or references to other entities. It’s often handy to be able to instantiate those entities, e.g. as initialisation or test data, alongside the definition. (Admittedly, this particular example will only really start to liven up when you start referencing those entities in business logic.) This is entirely analogous to the GPL case. For an actual example, consider the following grammar of an Xtext implementation of this DSL.

Entity: 'entity' name=ID '{'
          features+=Feature*
        '}';

Feature: Attribute | Reference;

Attribute: name=ID ':' dataType=DataType;
enum DataType: string | integer;

Reference: name=ID '->' entity=[Entity];

One way to do provide some multi-level modeling capabilities is to include a concept EntityInstance in the abstract syntax, pointing to an Entity and containing FeatureValues which allow the user to put in literals or instances for each of the features. For the given Xtext example, this looks as follows:

EntityInstance:
  'instance-of' entity=[Entity] '{'
    values+=FeatureValue*
  '}';

FeatureValue: feature=[Feature] '=' value=Literal;

Literal:          AttributeLiteral | EntityInstance;
AttributeLiteral: StringLiteral | IntegerLiteral;
StringLiteral:    string=STRING;
IntegerLiteral:   integer=INT;

The main drawbacks to this approach are:

  • It provides one generic (i.e., uncustomisable) concrete syntax for literals.
  • It requires quite some constraints to get this to work correctly.

In our simple case, this last point boils down to:

  1. feature must be one of parent(EntityInstance).entity.features

  2. type(value) must match type of feature

  3. every feature may only receive one value

The implementation of the scoping (constraint 1) and the validations (constraints 2 and 3) is not too problematic, but this language happens to be tiny. In general, an implementation of a type system, scoping, validations, content assist, etc. tends to be superlinear in the grammar’s size, so we can only expect this to get worse.

Wouldn’t it be nicer if each occurrence of Entity would automagically and dynamically be transformed into a concept in the abstract syntax? In our case, if we start with

entity MarkdownDialect {
  ^name : string
  ^author : string
}

then this would be expanded into

MarkdownDialect:
  'markdown-dialect' '{'
      ('name' '=' name=STRING)
    & ('author' '=' authorName=STRING)
  '}';

We see two challenges with this: both the abstract syntax/meta model as well as the concrete syntax have to be expanded on-the-fly. The concrete syntax is by far the biggest problem. For a textual (i.e., parsed) situation it is difficult as it would mean extending the grammar according to some user-defined scheme and re-generating the parser and other artefacts. It’s not impossible as e.g. SugarJ proves, but it’s not exactly mainstream. For projectional editing, it tends to be easier as the concrete syntax then is typically more fluid and described in terms of simple templates, instead of grammars.

But to do this, we will need to be able to transform relevant parts of the DSL prose into “dynamic parts” of the abstract + concrete syntax. This is a matter of a fairly simple transformations -one for abstract, one for concrete- provided we don’t introduce the chance of infinite recursion. However, there’s a bit of a challenge with regards to the dynamic nature of the syntaxes: if entities are changed/removed, the corresponding instances become invalid. This means that the editor must be aware -at least to some extent- of the fact that this might happen and consequently shouldn’t break.

Advertisements

Ambiguitiy in Xtext grammars – part 2

September 11, 2014 Leave a comment

In this continuation of the previous instalment, we’re going to take an ambiguous grammar and resolve its ambiguity.

As an example, consider the situation that we have a (arguably slightly stupid) language involving expressions and statements, two of which are variable declaration and assignment. (Let’s assume that all other statements start off by consuming an appropriate keyword token.) So, the following is valid, Java-like syntax (SomeClass is the identifier of a class thingy defined elsewhere):

SomeClass.SomeInnerClass localVar := ...
localVar.intField := 42

Now, let’s implement a “naive” Xtext grammar fragment for this:

Variable: name=ID;

Statement: VariableDeclaration | Assignment;

VariableDeclaration: typeRef=ClassRef variable=Variable (':=' value=Expression)?;
ClassRef:            type=[Class] tail=FeatureRefTail?;

Assignment:     lhs=AssignableSite ':=' value=Expression;
AssignableSite: var=[VariableDeclaration] tail=FeatureRefTail?;

FeatureRefTail: '.' feature=[Feature] tail=FeatureRefTail?;

Here, Class and Feature are quite standard types that both have String-valued ‘name’ features and have corresponding syntax elsewhere. Expression references an expression sub language which is at least able to do integer literals. Note that a Variable is contained by a VariableDeclaration so you can refer to a variable without needing to refer to its declaration. (You can find this grammar on GitHub.)

Now, let’s run this through the Xtext generator:

error(211): ../nl.dslmeinte.xtext.ambiguity/src-gen/nl/dslmeinte/xtext/ambiguity/parser/antlr/internal/InternalMyPL.g:415:1: [fatal] rule ruleStatement has non-LL(*) decision due to recursive rule invocations reachable from alts 1,2.  Resolve by left-factoring or using syntactic predicates or using backtrack=true option.
error(211): ../nl.dslmeinte.xtext.ambiguity.ui/src-gen/nl/dslmeinte/xtext/ambiguity/ui/contentassist/antlr/internal/InternalMyPL.g:472:1: [fatal] rule rule__Statement__Alternatives has non-LL(*) decision due to recursive rule invocations reachable from alts 1,2.  Resolve by left-factoring or using syntactic predicates or using backtrack=true option.

Even though Xtext itself doesn’t warn us about any problem (upfront), ANTLR spits out two errors back at us, and flat-out refuses to generate a parser after which the Xtext generation process crashes completely. The problem is best illustrated with the example DSL proza: its first line corresponds to a token stream ID-Keyword(‘.’)-ID-Keyword(‘:=’)-… while the second line corresponds to a stream ID-Keyword(‘.’)-ID-Keyword(‘:=’)-INT(42). (Note that whitespace is usually irrelevant and therefore, typically hidden which is Xtext’s default anyway.) Both lines start with consuming an ID token and because of the k=1 lookahead, the parser doesn’t stand a chance of distinguishing the variable declaration parser rule from the assignment one: only the fourth token reveals the distinction ID vs. Keyword(‘:=’). Note that since the nesting can be arbitrarily deep, any finite lookahead wouldn’t suffice meaning that we’d have to switch on the backtracking – one could think of this as setting k=∞.

To recap the situation with the token streams in comments:

SomeClass.SomeInnerClass localVar := ...  // ID-Keyword('.')-ID-[WS]-ID-[WS]-Keyword(':=')-[WS]-...
localVar.intField := 42                   // ID-Keyword('.')-ID-[WS]-Keyword(':=')-INT(42)

So, how do we deal with this ambiguity? One answer is to left-factor(ize) the grammar – as is already suggested by the ANTLR output. The trade-off is that our grammar becomes more complicated and we might have to do some heavy lifting outside of the grammar. But that is only to be expected since the grammar deals first and foremost with the syntax – what Xtext provides extra has everything to do with inference of the Ecore meta model (to which the EMF models conform) and only marginally so with semantics, by means of the default behavior for lazily-resolved cross-references.

Analogous to the left-factorized pattern for expression grammars, we’re going to implement the lookahead manually and rewrite nodes in the parsing tree to have the appropriate type. First note that our statements always begin with an ID token which either equals a variable name or a class name. After that any number of Keyword(‘.’)-ID sequences follow (we don’t care about whitespace, comments and such for now) until we either encounter an ID-Keyword(‘:=’) sequence or a Keyword(‘:=’) token, in both cases followed by an expression of sorts.

So, the idea is to first parse the ID-(Keyword(‘.’)-ID)* token sequence (which we’ll call the head) and then rewrite the tree according to whether we encounter an ID or the Keyword(‘:=’) token first. In Xtext, there’s a distinction between parser and type rules but only type rules give us code completion through scoping out-of-the-box, so we would like to use a type rule for the head. The head starts with either a reference to a Class or to a VariableDeclaration. Unfortunately, we can’t distinguish between these two at parse level so we have to have a common super type:

HeadTarget: Class | Variable;

However, due to the way that Xtext tries to “lift” or automatically Refactor identical features (having the same name, type, etc.), we need to introduce an additional type (that’s used nowhere) to suppress the corresponding errors:

Named: Class | Variable | Attribute;

Now we can make the Head grammar rule, reusing the FeatureRefTail rule we already had:

Head: target=[HeadTarget] tail=FeatureRefTail?;

And finally, the new grammar rule to handle both Assignment and VariableDeclaration:

AssignmentOrVariableDeclaration:
  Head (
    ({VariableDeclaration.assignableSite=current} name=ID ':=' (value=Expression)?) |
    ({Assignment.lhs=current} ':=' value=Expression)
  );

This works as follows:

  1. Try to parse and construct a Head model element without actually creating a model element containing that Head;
  2. When the first step is successful, determine whether we’re in a variable declaration or an assignment by looking at the next tokens;
  3. Create a model element of the corresponding type and assign the Head instance to the right feature.

This is commonly referred to a “tree rewriting” but in the case of Xtext that’s actually slightly misleading, as no trees are rewritten. (In fact, Xtext produces models which are only trees as long as there are no unresolved references.)

To complete the example, we have to implement the scoping (which can also be found on GitHub). I’ve already covered that (with slightly different type names) in a previous blog post, but I will rephrase that here. Essentially, scoping separates into two parts:

  1. Determining the features of the type of a variable. This type is specified by the typeRef feature (of type Head) of a VariableDeclaration. This is a actually a type system computation as the Head instance in the VariableDeclaration should already be completely resolved.
  2. Determining the features of the previous element of a Head instance as possible values of the current FeatureRefTail.feature. For this we only want the “direct features” since we’re actively computing a scope.

(The scoping implementation uses a type SpecElement which is defined as a super type of Head and FeatureRefTail, but this is merely for convenience and type-safety of said implementation.)

In conclusion, we’ve rewritten an ambiguous grammar as an unambiguous one so we didn’t need to use backtracking with all its associated disadvantages: less performance, ANTLR reports no warnings about unreachable alternatives, “magic”, etc. We also found that this didn’t really complicate the grammar: it expresses intent and mechanism quite clearly and doesn’t feel like as kluge.

 

Ambiguities in Xtext grammars – part 1

August 26, 2014 1 comment

In this blog in two instalments, I’ll discuss a few common sources of ambiguity in Xtext grammars in the hopes that it will allow the reader to recognise and fix these situations when they arise. This instalment constitutes the theoretical bit, while the next one will discuss a concrete example.

By default (at least: the default for the Itemis distro) Xtext relies on ANTLR to produce a so-called LL(k) parser, where LL(k) stands for “Left-to-right Leftmost-derivation with lookahead k“, where k is a positive integer or * = ∞ – see the Wikipedia article for more information (with a definite “academic” feel, so be warned). This means that grammars which are not LL(k) yield ANTLR errors during the Xtext generation stating that certain alternatives of a decision have been switched off. These are actual errors: the generated parser quite probably does not accept the full language as implied by the grammar (disregarding the fact that it’s not actually LL(k)) because the parser doesn’t follow certain decision paths to try and parse the input. We say that this grammar is ambiguous.

Xtext and “LL(1) conflicts”

Remember that first of all that the parser tokenizes its input into a linear stream of tokens (by default: keywords, IDs, STRINGs and all kinds of white space and comments) before it parses it into an EMF model (in the case of Xtext, but into an AST for general parsers). The problem is that an Xtext grammar specifies more than just the tokenizing and parsing behavior: it also specifies cross-references whose syntax often introduce an ambiguity on the parsing level by consuming the same token (ID, by default). The second parsing phase (still completely generated by ANTLR from an ANTLR grammar) only uses information on the token type, but doesn’t use additional information, such as a symbol table it may have built up. Such a strategy wouldn’t work with forward references anyway as the parser is essentially one-pass: references are resolved lazily only after parsing. This means that we have to beware especially of language constructs which start off by consuming the same token types (such as IDs) left-to-right but whose following syntax are totally different. This is a typical example of the FIRST/FIRST conflict type for a grammar; see also the Wikipedia article. The other non-recursive conflict type is FIRST/FOLLOW and is a tad more subtle, but it can be dealt with in the same way as the FIRST/FIRST conflict: by left-factorization.

Left-recursion

A grammar is left-recursive if (and only if) it contains a parser rule which can recursively call itself without first consuming a token. A left-recursive grammar is incompatible with LL(k) tech and Xtext or ANTLR will warn you about your grammar being left-recursive: Xtext detects left-recursion at the parser rule level while ANTLR detects left-recursion at the token level. Expression languages provide excellent examples of left-recursive grammars when trying to implement them in Xtext naively. For expression languages there’s a special pattern (ultimately also based on left-factorization) to deal both with the left-recursion, the precedence levels and creating a useable expression tree at the same time: see Sven’s oft-referenced blog and two of my blogs.

Backtracking

There are several ways to deal with ambiguities, one of which is enabling backtracking in the ANTLR parser generator. To understand what backtracking does, have a look at the documentation: essentially, it introduces a recovery strategy to try other alternatives from a parser rule, even if the input already matched with one alternative based on the specified lookahead. (See also this blog for some examples of the backtracking semantics and the difference with the grammar being LL(*).) I’m not enamored of backtracking because ANTLR analysis doesn’t report any errors anymore during analysis, so while it may resolve some ambiguities, it will not warn you about other/new ones. (It also tends to cause a bit of a performance hit, unless memoization is switched on using the memoize option.) In case you do really need backtracking, you should have a good language testing strategy in place with both positive and negative tests to check whether the parser accepts the intended language.

It’s my experience that very few DSLs actually require backtracking. In fact, if your DSL does really need it, chances are that you’re actually implementing something of a GPL which you should think about twice anyway. A quite common case requiring backtracking is when your language uses the same delimiter pair for two different semantics, e.g. expression grouping and type casting in most of the C-derived languages. Using different delimiters is an obvious strategy, but you might as well think hard about why you actually need to push something as unsafe as type casting on your DSL users.

Configuring the lookahead

To manually configure the lookahead used in the ANTLR grammar generated Xtext fragment (instead of relying on ANTLR’s defaults), you’ll have to do a bit of hacking: you have to create a suitable custom implementation of such a fragment, because MWE2 doesn’t have syntax for integer literals or revert to using MWE(1) to configure that. I’ll present a good illustration of this in the worked example in the next instalment which contains nested type specifications (or “path expressions”, as I called them in an earlier blog) which can have an arbitrary nesting depth. Using left-factorization we can rewrite the grammar to be LL(1), at the cost of some extra indirection structure in the meta model and some extra effort in implementing scoping and validation.

The Dangling Else-problem

A(nother) common source of ambiguity is known as The Dangling Else-problem (see the article for a definition) which is a “true” ambiguity in the sense that it doesn’t fall in one of the LL(1) conflicts categories described above. The only way to deal with that type of ambiguity in Xtext 1.0.x is to have a language (unit) test to check whether the dangling else ends up in the correct place – “usually”, that’s as else-part for the innermost if. Note that Xtext 2.0 has (some) support for syntactic predicates which allow you to deal with this declaratively in the grammar.

Next time, a concrete, worked example!

A (slightly) better switch statement in JavaScript

September 8, 2012 2 comments

The switch statement in JavaScript suffers from the usual problems associated with C-style switch statements: fall through. This means that each case guard needs to be expressly closed with a break statement to avoid falling through to the first executable code after that – no matter which case that code belongs to. Fall through has been the source of very many bugs. Unfortunately, the static code analysis for JavaScript (JSLint, JSHint and Google’s Closure compiler) do not check for potential fall through (yet?).

Today I thought I could improve the switch statement slightly with the following code pattern:

var result = (function(it) {
switch(it) {
case 'x': return 1;
case 'y': return 2;
/* ... */
default: return 0;
}
})(my_it);

(Apologies for the lack of indentation: couldn’t get that to work…)

The advantage of using return statements is two-fold:

  1. it exits the switch statement immediately,
  2. it usually comes right after the case guard, making visual inspection and verification much easier than hunting for a break either in- or outside of a nice pair of curly braces.

This approach also has a definite functional programming flavor, as we’ve effectively turned the switch statement into an expression, since the switch statement is executed as part of a function invocation.

Postscript

Yes, I do write JavaScript from time to time. I usually don’t like the experience very much, mostly because of inadequate tool support and the lack of static typing (and the combination thereof: e.g. the JS plug-ins for Eclipse often have a hard time making sense of the code at all). But we do what we can to get by 😉

Polymorphic dispatch in Xtend

August 3, 2012 1 comment

Polymorphic dispatch (or http://en.wikipedia.org/wiki/Multiple_dispatch or multimethods as its also called) is a programming language construct which chooses a code path based on runtime types instead of types that are inferred at compile. The poor man’s method of achieving such behavior would be to litter your code with prose like this:

if( x instanceof TypeA ) { (x as TypeA).exprA }
else if( x instanceof TypeB ) { (x as TypeB).exprB }
else ...

Xtend 2.x offers two much better constructs to do polymorphic dispatching:

  1. Through the use of the dispatch modifier for function defs – this construct is Xtend’s “official” polymorphic dispatch.
  2. Through the use of the switch statement and referring to types instead of cases.

These are better than the poor man’s method because they are declarative, i.e.: they express intent much more clearly and succinctly. Though both constructs have a lot in common, there are some marked differences and Best Practices for safe guarding type safety which I’ll discuss in the blog.

The example

Consider the following Xtend code – note that the syntax coloring is lacking a bit, but WordPress doesn’t fully understand Xtend – …yet…. Also note that since Xtend2.3 you can have more than one Xtend class in one file.

class CommonSuperType { ... }
class TypeA extends CommonSuperType { ... }
class TypeB extends CommonSuperType { ... }
class TypeC extends CommonSuperType { ... }
class UnrelatedType { ... }
class Handler {

  def dispatch foo(TypeA it) { it.exprA }
  def dispatch foo(TypeB it) { it.exprB }

  def bar(CommonSuperType it) {
    switch it {
      TypeA: it.exprA
      TypeB: it.exprB
    }
  }
}

For simplicity’s sake, let’s assume that exprA and exprB both return an int. The Xtend compiler generates two public methods in the Java class Handler – one for foo, one for bar. Both of these have the same signature: int f(CommonSuperType), where f = foo or bar. In addition, for each foo dispatch function, Xtend generates a public method with signature int _foo(t), where t=TypeA or TypeB – note the prefixed underscore. The actual polymorphic dispatch then happens in “combined” foo(CommonSuperType) method, actually through the previously demonstrated poor man’s method.

By the way: a user-friendly way to inspect the “combined” method is the Outline which will group the dispatch functions belonging together under the combined signature.

Note that the foo and bar method ends up with CommonSuperType as the type of its parameter. This is because CommonSuperType is the most specific common super type of TypeA and TypeB – deftly implied by the name – and Xtend infers that as the parameter’s type for the “combined” method. In general, Xtend will compute the most specific common super type across all dispatch functions, on a per-argument basis. In case of the bar method we declared ourselves what the parameter type is.

As demonstration, add the following code to the Handler class and see what happens:

  def dispatch foo(TypeC it) { it.exprC }

(Assume that exprC again returns an int.)

The generated foo and bar methods are functionally nearly identical, the difference being that foo explicitly throws an IllegalArgumentException mentioning the unhandled parameter type(s) in its message, in case you called it with something that is a CommonSuperType but neither of TypeA nor of TypeB. The bar method does no such thing and simply falls through the switch, returning the appropriate default value: typically null but 0 in our int-case. To remedy that, you’ll have to add a default case which throws a similar exception, like so:

  def bar(CommonSuperType it) {
    switch it {
      TypeA: it.exprA
      TypeB: it.exprB
      default:
        throw new IllegalArgumentException("don't how to handle sub type " + it.^class.simpleName)
    }
  }

In case you already have sensible default case, you’re basically out of luck.

Potential mistakes

Both approaches have their respective (dis-)advantages which I’ll list comprehensively below. In both cases, though, it’s relatively easy to make programmers’ mistakes. The most common and obvious ones are:

  1. The parameter type of the “combined” foo method is inferred, so if you add a dispatch function having a parameter type which does not extend CommonSuperType, then the foo method will wind up with a more general parameter type – potentially Object. This means that the foo method will accept a lot more types than usually intended and failing miserably (through a thrown IllegalArgumentException) on most of them. This is especially dangerous for public (which happens to be the default visibility!) function defs.
  2. Xtend will not warn you at editor/compile time about the “missing” case TypeC: it’s a sub type of CommonSuperType but not of TypeA nor of TypeB. At runtime, the bar method will simply fall through and return 0.
  3. The return type of the combined method is also inferred as the most specific common super type of the various return types – again, potentially Object. This is usually much less of a problem because that inferred type is checked against the parameter type of clients of the combined method.

This shows that these constructs require us to do a little extra to safe guard the type safety we so appreciate in Xtend.

Advantages and disadvantages of both constructs

We list some advantages and disadvantages of both constructs. Advantages of the dispatch construct:

  • Provides more visual code space. This is useful if the handling of the separate types typically needs more than 1 line of code.
  • Explicit handling of unhandled cases at runtime.

Disadvantages of the dispatch construct:

  • Automagically infers parameter types of the “combined” method as the most common super types. In case of a programmer error, this may be (much) too wide.
  • Takes up more visual code space/more syntactic noise.

Advantages of the switch construct:

  • Takes up less visual code space. This is useful if the handling of the separate types doesn’t need more than one line of code.
  • It’s a single expression, so you can use it as such inside the function it’s living in. Also, you can precompute “stuff” that’s useful for more than one case.

Disadvantages of the switch construct:

  • Fall-through of unhandled cases at runtime, resulting in an (often) non-sensical return value. You have to add an explicit default case to detect fall-through.

Mixing polymorphic and ordinary dispatch

Since Xtend version 2.3, you are warned about dispatch functions having a compatible signature as a non-dispatch function and vice versa. As an example, consider the following addition to the Handler class:

  def foo(TypeC it) { it.exprC  }
  def foo(UnrelatedType it) { it.someExpr }

Here, exprC again returns an int, but someExpr may return anything. Note that both functions are not of the dispatch persuasion.

The first line is flagged with the warning “Dispatch method has same name and number of parameters as non-dispatch method”, which is a just warning in my book. However, this warning is also given for the second line, as well as for the first two foo functions. (Note that the warnings are also given with only one of these extra functions present.) In that case, it’s not always a helpful warning but it does riddle your code file with warnings.

To get rid of the warnings, I frequently make use of the following technique:

  • “Hide” all dispatch functions by giving them (and only these) an alternate name. My personal preference is to postfix the name with an underscore, since the extra _ it’s visually inconspicuous enough to not dilute the intended meaning. Also, give them private visibility to prevent prying eyes.
  • Create an additional function with the same signature as the “combined” method for the dispatch functions, calling those.

The net result is that you get rid of the warnings, because there’s no more mixture of dispatch and non-dispatch functions with compatible signatures. Another upshot is that the signature of the “combined” method is now explicitly checked by the additional function calling it – more type safety, yeah! Of course, a disadvantage is that you need an extra function but that typically only is one line of code.

In the context of our example, the original two foo functions are replaced by the following code:

  def foo(CommonSuperType it) { foo_ }

  def private dispatch foo_(TypeA it) { it.exprA }
  def private dispatch foo_(TypeB it) { it.exprB }
Categories: The How, Xtend(2)

Xtext tip: “synthetic” parser rules

December 22, 2011 2 comments

This is a quick one to share a simple trick which may come in handy when creating an Xtext grammar.

Let’s say your grammar has a type rule T1 (i.e., a rule which corresponds to an EClass in the Ecore meta model). Let’s also say that some other type rule T2 composes that type somehow, i.e., it has a feature someT1 to which something of type T1 is assigned. Let’s say that you want to limit the syntactic possibilities for the composition of a T1 instance somewhat, e.g. in the case that T1 is a group of alternatives but a few alternatives are invalid when used inside T2.

This is a wholly legitimate situation because Xtext grammars usually have a number of responsibilities at the same time, amongst which are defining (1) a mapping to an Ecore meta model and defining (2) the syntax of the DSL.

Let’s sum this situation up in some grammar code:

T1: A1 | A2 | A3;

T2: 'a-t2' someT1=T1;

Let’s say that we would want to exclude A3 from the possible T1‘s in any T2. We could do this via a validation which simply checks the someT1 feature of any T2, reporting an error if it’s an A3. But that means that the parser itself still allows an A3 at that spot which could open up a whole can of smelly worms – e.g., left-recursion or some ambiguity. Also, the content assist that comes out-of-the-box will make syntax suggestions for A3.

Hence, we would like to inform the parser about the restricted syntax. One possibility would be:

T1: T1WithoutA3 | A3;

T1WithoutA3: A1 | A2;

T2: 'a-t2' someT1=T1WithoutA3;

This works perfectly, but it also ‘pollutes’ the meta model a bit. Since the meta model is mostly consumed by downstream clients like interpreters and code generators, this would only cause confusion. But more importantly: if we re-use an existing Ecore meta model (by means of the returns clause) this solution is not possible, since we would have to add a super type T1WithoutA3 to the A1 and A2 types which are sealed inside the re-used Ecore meta model – Xtext will issue an error as soon as we try it.

The clean solution consists of using something which I’ve termed a “synthetic parser rule” and has the following form:

T1:  A1 | A2 | A3;

T1WithoutA3 returns T1: A1 | A2;

T2: 'a-t2' someT1=T1WithoutA3;

Now there’s no pollution of the meta model, but the syntax will be restricted as we’d like it. Note that is very much something which is part of the standard Xtext repertoire but this trick works especially well in the face of type hierarchies and re-used Ecore meta model or inheriting Xtext grammars.

Using syntactic predicates in Xtext, part 2

December 20, 2011 2 comments

This blog is a continuation of the previous one about how to use syntactic predicates in Xtext. As promised, I’ll provide a few more examples, most of which come from the realm of GPL-like languages.

But first, a little summary is in order. As stated in the previous blog, a syntactic predicate is an annotation in an Xtext grammar which indicates to the ANTLR parser generator how a (potential) ambiguity should be resolved by picking the (first) one which is decorated with ‘=>‘. The annotation can be applied to:

  • a(n individual) keyword (such as ‘else‘),
  • a rule call (unassigned or as part of an assignment) and
  • a grouped parse expression, i.e. a parse expression between parentheses.

One thing to keep in mind -not only for syntactic predicates but in general- that an Xtext grammar has at least three and often four responsibilities:

  1. defining the lexing behavior through definition and inclusion of terminals;
  2. defining the parsing behavior through parser rules which determine how tokens are matched and consumed;
  3. defining how the model is populated;
  4. (when not using an existing Ecore model) defining the meta model.

Syntactic predicates influence the second of these but not the others. It is, after all, a syntactic predicate, not a semantic one – which Xtext doesn’t have in any case. Just as without using syntactic predicates, parsing behavior is not influenced by how the model is populated: instead, it is governed solely by the types of the tokens it receives from the lexer. This is easily forgotten when you’re trying to write grammars with cross-references like this:

SomeParserRule: Alternative1 | Alternative2;
Alternative1: ref1=[ReferencedType1|ID];
Alternative1: ref2=[ReferencedType2|ID];

In this case, the parser will always consume the ID token as part of Alternative1 even if its value is the (qualified) name of something of ReferencedType2. In fact, ANTLR will issue a warning about alternative 2 being unreachable so it is disabled. For a workaround this problem, see this older blog: it uses a slightly different use case as motivation but the details are the same. The only thing a syntactic predicate can do here is to explicitly favor one alternative over the other.

Some examples from Xbase

The Xtend and the Xbase languages that Xtext ships with both use plenty of syntactic predicates to avoid ambiguities in their grammars and to avoid having to use backtracking altogether. This already indicates that syntactic predicates are a necessary tool, especially when creating GPL-like or otherwise quite expressive DSLs. Note again that syntactic predicates are typically found near/inside optional parts of grammar rules since optionality automatically implies an alternative parsing route.

A good example can be found in the Xbase grammar in the form of the XReturnExpression rule: see GitHub. It uses a syntactic predicate on an assignment to force the optional XExpression following the ‘return‘ keyword to be parsed as part of the XReturnExpression rather than being an XExpression all on its own – which would have totally different semantics, but could be a viable interpretation considering Xtend doesn’t require separating/ending semi-colons.

The Xbase grammar also shows that syntactic predicates are an effective way to disambiguate the use of pairs of parentheses for denoting a list of arguments to a function call from that for grouping inside an expression: once again, see GitHub – here, the syntactic predicate applies to a grouped parse expression, i.e. everything between the parentheses pair starting just before the ‘=>‘.

Unforeseen consequences

Even if you don’t (have to) use syntactic predicates yourself, it’s important to know of their existence. As an example, the other day I was prototyping a DSL which used the JvmTypeReference type rule from Xbase followed by an angled bracket pair (‘<‘, ‘>’) which held ID tokens functioning as cross-references. I was momentarily surprised to see parse errors arise in my example along the lines of “Couldn't resolve reference to JvmType 'administrator'.” The stuff between the angled brackets was being interpreted as a generic type parameter!

It turns out that the  JvmTypeReference parser rule uses a syntactic predicate on an angled bracket pair surrounding generic type parameters. This explains both the behavior and the lack of warnings by ANTLR about grammar ambiguities. You’d probably have a hard time figuring out this behavior before finding an innocuous ‘=>here. In the end, I changed “my” angled brackets to square brackets to resolve this. This shows that syntactic predicates, just like backtracking, can be a double-edged sword: it can solve some of your problems but you have to really know how it works to be able to understand what’s going on.

I hope that this was useful for you: please let me know whether it is! I’m not planning on a third installment but you never know: a particular enticing use case might just do the trick.