An important issue in the asm2tcsm transformation is that the abstract syntax model by its nature describes a graph, whereas instances of the concrete syntax model should be trees (see Background on Graphs and Trees on p. 50). We must therefore find a way to transform some of the relationships between classes in the abstract syntax model to a representation in the concrete syntax model that basically holds the same information.

From past experience with textual languages, we already know how to handle references in BNF rules. To refer to the other element, you simply use a name or a name combined with something else. For example, when you write ClassA var1 in Java, you use the name ClassA to refer to the definition of ClassA, which is probably in another file. You do not use a direct link; you use a name-based reference.

In our situation, the occurrence of a name in a parse tree must be an instance of a class in the concrete syntax model. So, the names that are references should be instances of one or more special classes. For this purpose for each class to which a reference exists, the toolkit generates in the concrete syntax model a special reference class. For instance, in Alan, the abstract syntax model holds a class called Type, and the concrete syntax model contains a class called TypeREF.

To decide which associations in the abstract syntax model represent references and should therefore be handled like this, we make use of the composite/reference distinction in associations in the abstract syntax model. Our formal definition of metamodel in Section 5.1.5 ensures that in any instance of the abstract syntax model, the composite associations build a subgraph that is a tree or a set of unrelated trees (a forest). Thus, the composite relationships in the abstract syntax model are the perfect start for creating a concrete syntax model. If the subgraph formed by the composite associations is not a tree but rather a forest, the algorithm will produce a set of unrelated sets of grammar rules. It is up to the language engineer to decide whether this is desired.

Note that for each of the classes for which a reference class is created (step 3 of the algorithm), the language engineer must indicate which attribute of String type is used as identifier. This knowledge is used in the static semantic analyzer to implement the binding phase.

Figure 8-3 shows a small part of the abstract syntax model in Alan. Since this model does not contain any attributes with nonprimitive types, I have, for the sake of argument, regarded the relationship between an operation and its parameters as represented by an attribute in the class OperDecl. (In Figure 6-1, this relationship is shown as an association between the class OperDecl and the class VarDecl.)

Figure 8-3. Example abstract syntax model (part of Alan’s ASM)

Figure 8-4 shows the concrete syntax model that is automatically generated from this part of the abstract syntax model. The differences are marked by the gray color of the classes and the font of the role names. You can see that VarCallExp and OperCallExp are no longer associated with VarDecl and OperDecl, respectively. Instead, they have an acyclic (see Section 5.1.3) constraint on their relationships with VarDeclREF and OperDeclREF, respectively. The same holds for the relationships of VarDecl and OperDecl with Type. Furthermore, as expected, the params attribute in class OperDecl has been replaced by an acyclic relationship between OperDecl and VarDecl. The result of all this is that the concrete syntax model specifies a tree and not a graph.

Figure 8-4. Example textual concrete syntax model

The Grasland toolkit implements the algorithm in List 8-1 in a fully automatic way and is able to produce a concrete syntax model without any extra user effort. However, if the algorithm for the asm2tcsm transformation is executed as is, the differences between the abstract syntax model and the concrete syntax model are minimal; only the references are represented differently. Often, the language engineer wants a larger difference between the two, so there are two options to tune the asm2tcsm transformation. Because the static semantic analyzer must be able to inverse the asm2tcsm transformation on the instance level, these options are taken into account in the generation of the static semantic analyser as well.

The first option is to indicate that certain metaclasses in the abstract syntax model should not appear at all in the concrete syntax model. Examples are the classes PrimitiveType and NullType (you may want to have another look at Figure 6-1). These types are present in the abstract syntax model only to provide for a number of predefined elements in the language, the ones that are part of the standard library, but the language user is not meant to create new instances of these meta-classes. The language engineer can indicate that these classes are hidden to the concrete syntax.

The second option is to indicate that certain attributes and outgoing associations of a metaclass need not be present in the input text file; instead, their value will be determined based on the values of other elements that are present. In fact, these elements are what is known in OCL [Warmer and Kleppe 2003, OMG-OCL 2005] as derived elements. The language engineer may indicate that if an OCL derivation rule for this element in the abstract syntax model is provided, a certain element need not be taken into account in the concrete syntax model. An example of a derived value is the resultType of an Expression, which is shown in Figure 8-3 but is absent in Figure 8-4.

The generation of the BNFset from the concrete syntax model is implemented in a single algorithm. Yet the language engineer may choose between two different output formats: either BNF or a grammar that can directly be used as input to the JavaCC parser generator [JavaCC 2008]. The BNF grammar that is produced is an extension of EBNF that uses labeling of nonterminals in the right-hand side of a grammar rule. (Not to be confused with Labeled BNF [Forsberg and Ranta 2003], which uses labels on the nonterminals at the left-hand side of each rule.) The labels correspond to the names of the attributes and association roles in the concrete syntax model. List 8-3 shows an example in which the labels are called out in boldface.

The input for the JavaCC parser generator is such that the generated parser produces instances of the Java implementations of the classes in the concrete syntax model. The algorithm that implements tcsm2bnf is given in List 8-2. List 8-3 shows the BNF rules generated from the concrete syntax model in Figure 8-4. Note that terminals in the right-hand side of the grammar rules are surrounded by angle brackets (< and >).

Like the algorithm for the asm2tcsm transformation, the Grasland toolkit implements the algorithm in List 8-2 in a fully automatic way. A grammar can be produced without any extra effort from the language engineer. However, there are a number of differences between the metamodel formalism used for the concrete syntax model and the BNF formalism, and the language engineer is able to influence how these differences appear in the generated grammar, thus tuning the tcsm2bnf generation.

The most apparent difference is the lack of ordering in navigation—attributes and outgoing association—from a metaclass versus the ordering of the elements in the right-hand side of a BNF rule for a nonterminal. To indicate a certain ordering in the BNF rules, the language engineer can associate an index to all navigations. This is done in a so-called properties file. An example can be found in List 8-4, where, among other things, the order of the navigations from the metaclass OperCallExp in Figure 8-3 is given. The first element to be included in the right-hand side of the corresponding BNF rule is the attribute called name, the second element is the list of actual parameters, and the third is the object on which to call the operation.^[1] Without directions from the language engineer, the Grasland toolkit will randomly assign an ordering.

Another difference between a metamodel and a grammar is that most grammar rules contain one or more keywords, whereas the metamodel does not. These keywords are relevant in the parser because they enable it to differentiate between language elements (rules). For instance, the difference between a class and an interface is indicated by either the keyword class or interface. Therefore, the Grasland toolkit provides the option for the language engineer to indicate which keywords should be used in the grammar rule corresponding to a metaclass instance. Without keyword directions, the Grasland toolkit will generate keywords based on the class and association role names.

For each metaclass that is used in the right-hand side of a BNF rule, there are two options to use a keyword: (1) before the occurrence of the metaclass, and (2) after the occurrence of the metaclass. An example is the keyword new, indicated by CREATEEXP_BEGIN, that should appear at the start of a CreateExp instance.

For each navigation—attributes and outgoing associations—that appears in the right-hand side of a BNF rule, there are three possibilities: (1) a keyword before the navigated element, (2) a keyword after the element, and (3) a keyword that separates the elements in a list. The last is sensible only when the multiplicity of the association is larger than 1. If the element is optional—that is, the lower bound of multiplicity is 0—the language engineer is able to indicate whether the keyword should still appear even if the element is not present. This is useful, for instance, to indicate that the opening and closing brackets of a parameter list should be present even if there are no parameters. In List 8-4, for example, the brackets are mandatory for the navigation OPERCALLEXP_ACTUALPARS. Note that a keyword in this approach can be any string, including brackets.

A third difference between a metamodel and a grammar is that the parsing algorithm used poses a number of requirements on the rules. For instance, the JavaCC parser generator creates LL(n) parsers, and its input should be an LL(n) grammar, where n indicates the number of look-ahead tokens used. If the language engineer decides to create a grammar with too few keywords, the parser generator will produce errors and/or warnings. As the Grasland toolkit is a prototype, resolving these issues is the responsibility of the language engineer. By adding more keywords or by adding (by hand) look-aheads to the generated grammar, the language engineer will always be able to generate a grammar that is correct. Even so, the Grasland toolkit provides a minimal support in the form of the generation of lookaheads in the rule for a class with subclasses, where choice conflicts are likely because the attributes and navigations of the superclass appear in the rules for each subclass.

Binding is the general term for the binding of names to their definitions. These names may refer to types—for instance, in a variable declaration—or to variables or operation/functions—for instance, in assignments or operation calls. Binding is often context sensitive in the sense that not all occurrences of the same name are bound to the same definition; depending on the context of the name, it may be bound to a different definition, sometimes even to a definition of a different kind of element. For instance, in one context, “message” may be bound to a variable, in another to a type, and in yet another to an operation. Such a context is usually called a namespace.

Because the concrete syntax model is generated, we can be sure that all elements that need to be bound are instances of reference metaclasses (see List 8-1, rule 3). For each reference metaclass, we know the metaclass from which it is derived. We call this metaclass the target metaclass.

An important observation about static checking is that the rules that are checked during this phase are easily specified by OCL invariants on the abstract syntax model. These are the so called well-formedness rules. For instance, in our (simple) example, the following rule provides enough information to perform type checking:

Static checking is therefore implemented in the generated static semantic checker as the checking of invariants on the abstract form of the mogram. Whenever an invariant is broken, an error message is given to the language user.

Even more complex forms of type checking involving type conformance can be handled in this manner. For instance, given the existence of an operation in the Type class that implements the type conformance rules, the following invariant allows for type checking with type conformance. The type-conformance operation itself is also specified using OCL.

The advantage of this approach is that the invariants can be used for all concrete syntaxes that may be defined for the abstract syntax model. Thus, checking becomes a common functionality instead of a functionality that needs to be implemented for each concrete syntax.