📘 Ch4. Abstract syntax

The abstract syntax is the most central part of a software language. It defines the concepts of the language and the relationships between these concepts. Moreover, it defines the valid structure of an AST of language, along with the valid types of the AST nodes.

In this chapter we will first learn how to design an abstract syntax using the MOF standard (which is a simplification of UML class diagrams), then we will learn to implement an abstract syntax in a Langium DSL.

1. Designing an abstract syntax

1.1. Object-oriented modeling

A common way to design the abstract syntax of a DSL is to rely on an object-oriented modeling language such as MOF, Ecore (from the EMF platform), or UML class diagrams.

Using an object-oriented modeling language as a metalanguage for designing an abstract syntax has several benefits:

each concept of the DSL can be represented using a class,
each node of an AST can be represented by an instance of once of such class (hence an AST can be represented as an object diagram),
important characteristics of a concept can be represented by properties in the corresponding class,
relationships between concepts can be represented using associations between classes,
when multiple concepts share some characteristics, abstract classes and inheritance can be used,
to make sure the nodes of an AST are organized into a tree, composite associations can be used to enforce parent-child relationships between concepts.

Metamodeling?

An abstract syntax represented by an object-oriented model, is usually called a metamodel. The process of creating a metamodel is called metamodeling.

A metamodel is a specific kind of software model that defines how to create models (here, the ASTs of the software language we are desining). When all objects of a model are instances of classes of a metamodel, we say that this model conforms to this metamodel.

1.2. MOF: a convenient subset of UML class diagrams

In this course we will use the MOF metalanguage to design abstract syntaxes. MOF (Meta-Object Facility) is a standardized subset of UML class diagrams tailored specifically for metamodeling.

MOF is a standard that was proposed because we do not need the entire expressivity of UML class diagrams for metamodeling. Hence, MOF removes significant parts of UML class diagrams, such as:

no interfaces, since we want to define concrete data structures,
no shared aggregations, since we prefer compositions to enforce a tree structure,
no visibilities (public/private/protected), since we do not need encapsulation.

In addition, in this course, we will use a metamodel as a pure data structure, hence we will never use operations:

no operations, since we are only interested in data and structure.

We can summarize the subset of MOF used in this course with the following figure:

Figure 1. Venn diagram that approximately shows the subset of MOF used in this course

Example 1. Forbidden UML constructs

Example 2. Allowed UML constructs (MOF without operations)

Example 3. MOF abstract syntax of a tiny programming language DSL

We design a tiny programming language DSL, to write simple programs with variables and basic arithmetic expressions. With a mockup concrete syntax, a program should look like this:

program hello

var x;
x = 12 + 3;
var y;
y = x - 10;

We design the abstract syntax of this DSL with the following MOF metamodel:

Using the classes of this abstract syntax, we can instantiate an AST representing the example program shown above:

Example 4. MOF abstract syntax of a Petri nets DSL

We would like a DSL that allows the modeling of Petri nets. A Petri net is a formal model used to study concurrent systems. It is composed of a set of places (represented as circles) and a set of transitions (represented as black rectangles). A place contains an amount of initial tokens. A transition has a set of input places, and a set of output places.

Here is an example of Petri net model represented using the traditional concrete syntax:

We design the abstract syntax of this DSL with the following MOF metamodel:

Using the classes of this abstract syntax, we can instantiate an AST representing the example model shown above:

1.3. How to design an abstract syntax?

1.3.1. Domain analysis

Where to start the design of a DSL, and especially of its abstract syntax? Since an abstract syntax is model of a specific domain of interest, a common approach is to borrow principes from domain analysis:

Q1: Purpose. What is the purpose of the language? What are the use cases?
Q2: Stakeholders. Who are the key stakeholders and the intended users ofthe language?
Q3: Concepts. What are the key domain concepts that users care about?
Q4: Relations. How are domain concepts related, and what are their relevant properties?
Q5: Examples. What examples of language instances are available or can be prototyped?

Since in a learning context are not able to discuss with real DSL stakeholders and users, we will consider Q1 and Q2 more sparsely, and focus mostly on Q3-Q5.

Example 5. Domain analysis of a States Machines DSL

We would like to design the abstract syntax of a States Machines DSL, to be able to create state machine models. We perform the following domain analysis:

Q1: Purpose. To model the state-based behavior of simple systems, and to generate event-driven Java code that can be integrated in the broader implementation of said systems. State changes are trigered by input events provided by an external system. Each state has a list of output commands that are executed when the state is reached. Executing an output command eventually results in calling a concrete Java method implemented separately.
Q2: Stakeholders. Systems engineers (who design the system), software engineers (who implement the software part of said system).
Q3: Concepts. State machine, State, Transition, Event, Command.
Q4: Relations. States have names and are connected through transitions. A transition has a name, a trigering input event, and possibly an trigered output command. Events and commands have names.
Q5: Examples. The engineering team provides the following example, represented using a mockup graphical concrete syntax:

1.3.2. Guidelines for abstract syntax design

When designing an abstract syntax as a metamodel, the main goal is to capture each relevant concept as a class in a MOF metamodel, and connect these concepts using associations.

However there are many ways to organize a metamodel. The following guidelines can help you improve the quality and usefulness of your metamodel.

Ensure there is a single partonomy. A partonomy is the decomposition of a class diagram into "part-of" relationships, which are defined by compositions between classes. Since the purpose of an abstract syntax is to be able to instantiate ASTs, it is important to make sure instances will always lead to a tree structure. Hence, a metamodel should have a single partonomy: each instance of a class should always be contained by another object, through a hierarchy where a single root object stands at the top.
Be careful with generalization. Do not hesitate to use generalization to avoid redundancies, if multiple concepts share some common properties, but avoid genealizing two concepts that are have nothing to do with one another.
If relations between concepts carry information, reify them into classes. You may be tempted to represent each relation betwen two concepts as an association in your metamodel; however sometimes this relation itself carry some extra information. In this case, reify this relation as a dedicated class.
Name your classes, properties and roles appropriately. Use singular for class names, singular for properties and associations with single elements, and plural for properties and associations with multiple elements.
Don’t put your tools (interpreter, compiler, validator, etc.) in your metamodels. Metamodeling is not the same as traditional software modeling! You are not making an architectural diagram of a software application or tool. A class in metamodel is a domain concept, not an implementation concept.
Keep it as simple as possible. Remember that designing a language is about expressivity: only put in your language concepts that you will require to express a solution.
If your DSL will be used to describe complex systems, design for modularity. Provide concepts that allow modularization, such as modules, components, packages. Also provide concepts that can can be capitalized and instantiated multiple times, similar to classes and functions.

Example 6. Designing a MOF abstract syntax for a State Machines DSL

As started above with the domain analysis, we would like to design the abstract syntax of a States Machines DSL.

Going further in the design process, we go into more details and identify the following concepts, properties and relations:

A state machine has a name, and contains the following:
- A set of commands, each with a name, representing external actions that can be invoked by the state machine.
- A set of events, each with a name, representing external events that are received by the state machine, and that may trigger transitions.
- A set of states, each with a name and containing the following:
  - A set of commands that are invoked when we enter the state. These commands should first be declared at the root of the state machine.
- A set of transitions, each with a name and containing the following:
  - an event that triggers the transition when received while we are in the state
  - a target state that is reached when the transition is fired. This state should be already part of the state machine.

We start the process of making a MOF metamodel with all this information.

First, we transform each identified concept into a dedicated class:

Next, when a concept contains information, we add dedicated properties. Here, many concepts require a name property:

Next, a crucial step is to define the partonomy of our metamodel using compositions. The goal is to make sure that each object of an AST created using our metaodel is contained within anotion object.

We identify StateMachine as a logical root class for our partonomy, which means each AST will contains a single root StateMachine object at the top, which will transitively contain all objects of the AST.
Since a command or an event can be reused in different states and transitions, we choose to put them at the top-level of each AST, which means putting the classes Command and Event right below StateMachine.
Since nothing in particular can contain a state, we also put the State class at the top, right below StateMachine.
Regarding transitions, we observe that it must be connected both to an input state, and to an output state. To mark the difference between input and output relations, we decide that a state will own all of its output transitions. Therefore, we put a composition between State and Transition.

Another valid solution would be to put transitions at the same level as states, right below StateMachine, but it would require one extra association in the next (and last) step.

Finally, we add associations between classes when some objects are required to have a relationship with another existing object of the model.

A state must know all commands it should execute on entry, hence we add an association between State and Command.
A state machine should have an initial state, hence we add an association between StateMachine and State.
A transition should have an output state, hence we add an association between Transition and State.

Using this final metamodel as our abstract syntax for our State Machines DSL, we are able to use it to create an AST for the following example model:

which results in the following AST:

A complex AST is rapidly difficult to organize and read. But this is not a problem: it is not actually made to be shown! The goal of an AST is only to be an in-memory representation of a program.

2. Implementating an abstract syntax in Langium

In this section we will see how to implement an abstract syntax design into usable data types using Langium.

2.1. The Langium Grammar Language

A Langium grammar is written in the packages/language/src folder in the form of one or multiple .langium files written using the Langium Grammar Language. This language can be divided in two parts:

A subset of the Langium Grammar Language called "Declared Types" can be used to implement the abstract syntax of the developed language, in the form of simple object-oriented data types.
The rest of the Langium Grammar Language can be used to implement the concrete syntax of the developed language, in the form of grammar rules.

Quite confusingly, the Langium documentation uses the term Semantic Model to refer to the abstract syntax of the developed language. Be careful: while the word "semantic" is used, this has nothing to do with what we called earlier the semantics of the language!

The abstract and concrete syntaxes can either be defined in separate .langium files, or in the same .langium file.

In this course we do not cover all the many possibilities offered by the Langium Grammar Language. For more information, refer to the corresponding page in the official documentation.

2.2. Implementing the abstract syntax using Declared Types

Defining the data type for a concept of the abstract syntax is achieved using the interface keyword:

interface MyConcept {
    …
}

This is similar to a class in an object-oriented model or program, but without operations/methods.

A concept can contain properties, each with a name and a mandatory type using the : separator:

interface MyConcept {
    aPrimitiveProperty: string
    aContainmentProperty: OtherType
    aCrossReferenceProperty: @AnotherType
}

There are three main types of properties:

A primitive property is typed with one of the Langium primitive types: boolean, number, string, bigint or Date.
A containment property is typed with another existing concept of the abstract syntax. In an AST, when a node A is linked to a node B using a containment, the node B is said to be contained (or owned) by the node A. In an AST, a node can only be contained by a single container node at a time.
A cross-reference property is typed with another existing concept of the abstract syntax, using the character @ as prefix. In an AST, when a node A is linked to a node B using a cross-reference, the node B is said to be referenced (or known) by the node A.

A cross-reference from A to B is only possible if:

The concept B contains a primitive property called name and with type string. This is because the concrete syntax requires a way to encode how to identify another existing element.
An instance of B is always (transitively) contained in a container node of the instance A that possess this cross-reference. This means if B is contained deeper in a separate sub-tree of the AST, it won’t be accessible. This limitation can be solved by implementing a scope provider, see the Langium documentation on scoping.

Apart from the root node, each node of an AST must be contained in another node.

A property can also define a cardinality using either the optional suffix ? on the property identifier, or the array suffix [] on the type name.

interface MyConcept {
    anOptionalProperty?: string
    aArrayProperty: number[]
}

An optional property means that there can be zero or one value.
A array property means that there can be zero or multiple values.

It is of course possible to combine the different types of properties with the cardinality suffixes to define "optional containments", "arrays of primitives", "arrays of cross-references", etc.

Finally, a concept can be defined as an subtype of another existing concept using the extends keyword:

interface MyConcept extends OtherConcept {
    …
}

This gives the possibility to generalize different concepts by introducing a supertype, which is both useful to define a reference to multiple types, and to avoid redundant properties.

2.3. From MOF to Langium Declared Types

As mentioned above, Langium Declared Types are mostly similar to object-oriented classes. It is therefore possible to directly map a MOF metamodel into Langium as shown in this table:

MOF Langium

	MOF	Langium
Properties		`interface ConceptA { name: string id: number }`
Composition		`interface ConceptA { b: ConceptB } interface ConceptB {}`
Associations		`interface ConceptA { b: @ConceptB } interface ConceptB {}`
Optional composition		`interface ConceptA { b?: ConceptB } interface ConceptB {}`
Array property		`interface ConceptA { b: ConceptB[] } interface ConceptB {}`
Generalization		`interface ConceptA {} interface ConceptB extends ConceptA {}`
Abstract classes		Unfortunately there are no abstract types in Langium: `interface ConceptA {}`
Enumerations		There are no enums in Langium, but we can use a union type: `type Color = 'Red' \| 'Blue'`

Properties

interface ConceptA {
    name: string
    id: number
}

Composition

interface ConceptA {
    b: ConceptB
}

interface ConceptB {}

Associations

interface ConceptA {
    b: @ConceptB
}

interface ConceptB {}

Optional composition

interface ConceptA {
    b?: ConceptB
}

interface ConceptB {}

Array property

interface ConceptA {
    b: ConceptB[]
}

interface ConceptB {}

Generalization

interface ConceptA {}

interface ConceptB extends ConceptA {}

Abstract classes

Unfortunately there are no abstract types in Langium:

interface ConceptA {}

Enumerations

There are no enums in Langium, but we can use a union type:

type Color = 'Red' | 'Blue'

Example 7. Langium abstract syntax of a State Machines DSL

We consider the abstract syntax we designed earlier for the State Machines DSL:

We implement this abstract syntax using Langium Declared Types :

interface StateMachine {
    name: string
    commands: Command[]
    states: State[]
    events: Event[]
    initialState: @State
}

interface Command {
    name: string
}

interface State {
    name: string
    transitions: Transition[]
    on_entry: @Command[]
}

interface Event {
    name: string
}

interface Transition {
    trigger: @Event
    target: @State
}

In our Langium project, we put this file in the following location:

packages/language/src/state-machines-dsl.abstractsyntax.langium

And in the main grammar file located in packages/language/src/state-machines-dsl.langium (where we will ultimately implement our concrete syntax), we add at the top the following line to import our abstract syntax:

import './state-machines-dsl.abstractsyntax'

3. Manually constructing an AST in Langium

In practice it is never required to manually create an AST, because the parser always does it for us. This part is therefore presented mostly for learning purposes.

Once an abstract syntax has been implemented, we may want to manually test it by programatically constructing an AST using the TypeScript data types that have been generated.

Unfortunately, the Typescript data types that have been generated only include interfaces but no classes with constructors that would allow easily creating proper Typescript objects. In fact, the only officially supported way to create an AST in Langium is by writing a program using the DSL concrete syntax, and then by asking the parser to parse said program into an AST. But at this stage, we have no parser since we have not yet designed nor implemented our concrete syntax!

There is however a way to circumvent this limitation of Langium using the possibiblity in TypeScript to create an object without a class.

In this section, we will use the following example abstract syntax to illustrate an AST construction:

We consider this abstract syntax is implemented in Langium as follows:

interface RootConcept {
    name: string
    children: ChildConcept[]
}

interface ChildConcept {
    id: number
    sibling?: @ChildConcept
}

And we consider we have already called the Langium generator (npm run langium:generate) which generated the TypeScript data types we can import.

3.1. Importing the required TypeScript types

Considering we are writing code within the packages/language/src folder, we first have to import the following types:

import { AstUtils } from "langium"
import { RootConcept, ChildConcept } from "./generated/ast.js"

The first line imports a utility class from Langium that we will need,
The second line imports the two concepts of the example abstract syntax shown just before.

3.2. Creating a root object

Consider the following AST:

We can create this AST with the following TypeScript program:

const root : RootConcept {
    $type: "RootConcept",
    name: "hello",
    children: []
}

Note that :

For all AST nodes, Langium requires us to store the name of the concept in the $type attribute,
Even if there are no children, we have to initialize an empty list.

3.3. Creating a composition with another object

Consider the following AST:

We can create this AST with the following TypeScript program:

const child1 : child1 = {
    $type: "ChildConcept",
    $container: undefined!,
    id: 1,
}

const root : RootConcept = {
    $type: "RootConcept",
    name: "hello",
    children: [ child1 ]
}

AstUtils.linkContentToContainer(root, {deep: true})

Note that:

When creating the ChildConcept object, we are required to set an attribute $container to undefined!, because at this stage the object is not yet contained in a parent node of the AST,
The last line calls the Langium linkContentToContainer utility function to automatically set all the $container attributes of the whole AST, once objects have been connected together. Here, the $container attribute of the ChildConcept element will be automatically changed to point to the RootConcept element.

While type-safe, the API we are using to manually create the AST does not ensure that the tree is "correct by construction". This means it is possible to create invalid ASTs, such as trees where the same node is simultaneously contained in two different parent nodes.

3.4. Creating a cross-reference from an object to another

Consider the following AST:

We can create this AST with the following TypeScript program:

const child1 : ChildConcept = {
    $type: "ChildConcept",
    $container: undefined!,
    id: 1,
}

const child2 : ChildConcept = {
    $type: "ChildConcept",
    $container: undefined!,
    id: 2,
}

child1.sibling = { $refText: undefined!, ref: child2 }

const root : RootConcept = {
    $type: "RootConcept",
    name: "hello",
    children: [ child1, child2 ]
}

AstUtils.linkContentToContainer(root, {deep: true})

Note that:

For the sibling link between the two ChildConcept objects, we have to set it through a dedicated object with a $refText attribute (that we don’t need because it is only used by the parser), and a ref attribute that contains the actual pointer to the other object being referenced.

Example 8. Manually creating an AST for the State Machines DSL

Consider the following AST that we previously shown for the State Machines DSL:

We can create this AST with the following TypeScript program:

import { AstUtils } from "langium"
import { StateMachine, Event, State, Transition, Command } from "./generated/ast.js"


const c1 : Command = {
    $type: "Command",
    $container: undefined!,
    name: "c1"
}

const c2 : Command = {
    $type: "Command",
    $container: undefined!,
    name: "c2"
}


const c3 : Command = {
    $type: "Command",
    $container: undefined!,
    name: "c3"
}

const e1 : Event = {
    $type: "Event",
    $container: undefined!,
    name: "e1"
}

const e2 : Event = {
    $type: "Event",
    $container: undefined!,
    name: "e2"
}

const e3 : Event = {
    $type: "Event",
    $container: undefined!,
    name: "e3"
}


const s1 : State = {
    $type: "State",
    $container: undefined!,
    name: "S1",
    on_entry: [{ $refText: undefined!, ref: c1}],
    transitions: []
}

const s2 : State = {
    $type: "State",
    $container: undefined!,
    name: "S2",
    on_entry: [{ $refText: undefined!, ref: c2}],
    transitions: []
}

const s3 : State = {
    $type: "State",
    $container: undefined!,
    name: "S3",
    on_entry: [{ $refText: undefined!, ref: c3}],
    transitions: []
}

const s1ToS2 : Transition = {
    $type: "Transition",
    $container: undefined!,
    target: { $refText: undefined!, ref: s2},
    trigger: { $refText: undefined!, ref: e1},
}

s1.transitions.push(s1ToS2)

const s2ToS3 : Transition = {
    $type: "Transition",
    $container: undefined!,
    target: { $refText: undefined!, ref: s3},
    trigger: { $refText: undefined!, ref: e2},
}

s2.transitions.push(s2ToS3)

const s3ToS1 : Transition = {
    $type: "Transition",
    $container: undefined!,
    target: { $refText: undefined!, ref: s1},
    trigger: { $refText: undefined!, ref: e3},
}

s3.transitions.push(s3ToS1)

const root : StateMachine = {
    $type: "StateMachine",
    name: "threestates",
    commands: [c1,c2,c3],
    events: [e1,e2],
    states: [s1,s2],
    initialState:  { $refText: undefined!, ref: s1},
}

AstUtils.linkContentToContainer(root, {deep: true})

The push operation is used to add an element to the list of transitions of each state.

We put this code in a file packages/language/src/ast-test.ts, then we build the project:

npm run build

And finally we can run the compiled file using node:

node packages/language/out/ast-test.js

But the code does nothing we can see! So we run it in a JavaScript Debug Terminal, we set a breakpoint after the creation of the AST, and we can browse our AST loaded in memory in the variable view of the debugger: