📘 Ch5. Textual concrete syntax

The concrete syntax is a mandatory part of a software language that defines how a user of the language (a programmer or a domain expert) will concretely read and write programs in said language. The concrete syntax can be seen as the user interface (UI) of a software language.

In this chapter we will first learn how to design a concrete syntax using annotated mockups, then we will learn to implement an abstract syntax in a Langium DSL.

This course only deals with textual syntaxes designed "from the ground up". Another possibility, not shown in the course, is to rely on standardized markup languages (such as YAML, TOML, JSON) to provide a textual concrete syntax for a DSL.

In such a case, a concrete syntax takes the form of a schema describing what is allowed or not in a program, of an existing parser for the chosen markup language, and of a transformation able to map the parser output to a proper AST.

1. Designing a textual concrete syntax

1.1. Mockups

In user interface (UI) design, a mockup is a purely graphical representation of what a UI should look like once implemented. It is essentially a drawing showing the expected layout and the expected appearance of the different parts of a UI. It is a very efficient example-driven way to design a graphical UI, and a way to unleash creativity without being constrained by technical aspects.

In SLE, since a concrete syntax is a sort of UI for a software language, mockups are also a great approach to design a concrete syntax. Given a description of an example program, or given an AST of an example program, we can create a mockup textual representation showing the concrete syntax we envision for this example.

A good mockup must show examples all concepts, properties and associations of the abstract syntax of the DSL!
Example 1. Mockup of a Tiny programming DSL program

We continue the design of a tiny programming language DSL, to write simple programs with variables and basic arithmetic expressions.

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

Diagram

And using the classes of this abstract syntax, we already instantiated the following example AST:

Diagram

We now would like to design a textual concrete syntax for this DSL. In that goal, we prepare a mockup concrete syntax representation of this AST, which looks like this:

program hello

var x;
x = 12 + 3;
var y;
y = x - 10;
In the chapter on abstract syntaxes, we acually did the opposite: the mockup concrete syntax representation was an example part of the requirements, which we used to test the abstract syntax.
Example 2. Mockup of a Petri nets DSL program

We continue the design of a DSL that allows the modeling of Petri nets.

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

Diagram

We already considered the following example of Petri net, represented with the traditional graphical syntax of the formalism:

petrinet model.drawio

And using the classes of this abstract syntax, we already instantiated the following example AST that corresponds to this model:

Diagram

We now would like to design a textual concrete syntax for this DSL (even though Petri nets are commonly represented graphically). In that goal, we prepare a mockup concrete syntax representation of this AST, which looks like this:

PLACE p1 WITH 1 TOKEN
PLACE p2
PLACE p3 WITH 1 TOKEN

TRANSITION t1
    IN [p1]
    OUT [p2]
END

TRANSITION t2
    IN [p2,p3]
END

1.2. Tokens and token types

A textual representation of a program or model is essentially a sequence of tokens (usually obtained by the lexer, at the implementation level). A token is a sequence of characters.

There are five main types of tokens:

  • Keyword: a reserved word of the language, usually in english, used to precisely declare specific concepts of the language (if, state, while, place, etc.), or to declare begining or end of a declaration (begin, end, done, etc.).

  • Punctuation: a special character (or a combination of special characters) used to unambiguously structure and separate the different elements of a program. There are three main types of punctuation:

    • operator: a symbol that marks an operation applied to one or multiple elements, or that mark some element as special ( +, -, *, /, !, =, etc.)

    • delimiters: a pair of characters that mark the beginning and end of an element or a set of elements (( and ), { and }, [ and ], etc.)

    • separator: a single character used to separate elements in a list of elements (examples: ,, ;)

  • Identifier : a word assigned by the programmer that uniquely designate a specific element of the AST, usually composed only of alphanumeric characters (x, main, MyClass, etc.)

  • Comments: a whole sequence of characters that should be ignored by the parser (/* a comment */, // another comment, # a third comment, etc.)

  • Literal: raw data value written by the programmer, such as strings, integers, booleans (12, true, "word", -8.5, etc.)

When desining a concrete syntax using mockups, a useful step is to identify precisely what token types are used in which parts of a given mockup. This information will be helpful in later stages when implementing a grammar.

Example 3. Tokens of a Tiny programming DSL program

We already prepared the following mockup for a concrete syntax design of the Tiny programming DSL:

program hello

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

In this mockup, we can distinguish the following types of tokens:

  • Keywords: program, var

  • Punctuation:

    • operators: =, +, -

    • delimiters: N/A

    • separators: ;

  • Identifiers: hello, x, y

  • Comments: N/A

  • Literals: 3, 10

Example 4. Tokens of a Petri nets DSL program

We already prepared the following mockup for a concrete syntax design of the Petri nets DSL:

PLACE p1 WITH 1 TOKEN
PLACE p2
PLACE p3 WITH 1 TOKEN

TRANSITION t1
    IN [p1]
    OUT [p2]
END

TRANSITION t2
    IN [p2,p3]
END

In this mockup, we can distinguish the following types of tokens:

  • Keywords: PLACE, WITH, TOKEN

  • Punctuation:

    • operators: =, +, -

    • delimiters: []

    • separators: N/A

  • Identifiers: p1, p2, p3, t1, t2

  • Comments: N/A

  • Literals: 1

1.3. Mapping a concrete syntax with an abstract syntax

Now that we are able to create mockups and to understand the tokens it contains, the next step is to map the concrete syntax with the abstract syntax of the language being made. This is important to associate precisely what concept of the language is being represented by a given piece of concrete syntax, and to prepare a blueprint of how our future parser should build an AST given a textual representation.

When mapping a concrete syntax with an abstract syntax, tokens are usually in the following way:

  • Keywords and operators explictly mark what concepts or properties of the abstract syntax are being instantiated (example: the keyword PLACE declares an instance of the concept Place)

  • Identifiers are used in two ways:

    • for string properties of the abstract syntax, when such a property is used to name the element (example: in PLACE pl, p1 is an identifier for the name property of the concept Node)

    • for navigable associations of the abstract syntax, to identify an existing element that is being pointed to (example: in in [p1], p1 is an identifier for the inputs association of the Transition concept)

  • Literals are used to represent properties of the abstract syntax (example: in WITH 1 TOKEN, 1 is a literal for the initialTokens property of the concept Place)

Representing navigable associations in a textual syntax

Consider the following abstract syntax:

Diagram

With this perfectly valid abstract syntax, we can create the following AST:

Diagram

From there we would like to create a mockup concrete syntax representation of this AST. Problem: how to textually represent that the A element points to the first B element, and not the second? Because both B elements are identical, there is no way to textually disambiguate which one is being referenced by the A element.

The only way to solve this problem is to make sure each B instance can be uniquely identified through a dedicated property. The most common way to achieve this is to modify the abstract syntax and simply add a name property to the concept that needs to be referenced, here B:

Diagram

Then in the AST we can give a different name to each B instance:

Diagram

And finally we can design a mockup concrete syntax representation, for instance:

B #b1
B #b2
A @b1

Here we invent the # operator to specify the name of a B element, and we invent the @ operator to specify the B element that the A element points to through the b navigable association of the abstract syntax.

While this is one example of situation where the abstract syntax must be changed to be compatible with a textual concrete syntax, we usually prefer to avoid changing too much the abstract syntax when designing the concrete syntax. The abstract syntax should stay close to the studied domain concepts, and should ideally not be influenced by the constraints of the concrete representation.

To capture the mapping from concrete syntax to abstract syntax in a graphical and intelligle way, one simple approach is to create annotated mockups where each mockup gives an example of concrete representation of a specific concrete concept, and where said mockup is annotated to highlight where the properties and navigable associations are managed.

It is not required to prepare an annotated mockup for an abstract concept of the abstract syntax: only concrete concepts can be instantiated in an AST, and hence only concrete concepts can have a textual representation.
Example 5. Annotated mockups of a Tiny programming DSL program

We designed in the previous chapter the abstract syntax of a Tiny programming DSL with the following MOF metamodel:

Diagram

And we already prepared the following mockup for a concrete syntax:

program hello

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

To map the proposed concrete syntax and the abstract syntax, we prepare one annotated mockup per concept of the abstract syntax:

tiny programming annotated mockup.drawio
Example 6. Annotated mockups of a Petri nets DSL program

We designed in the previous chapter the abstract syntax of a Petri nets DSL with the following MOF metamodel:

Diagram

And we already prepared the following mockup for a concrete syntax:

PLACE p1 WITH 1 TOKEN
PLACE p2
PLACE p3 WITH 1 TOKEN

TRANSITION t1
    IN [p1]
    OUT [p2]
END

TRANSITION t2
    IN [p2,p3]
END

To map the proposed concrete syntax and the abstract syntax, we prepare one annotated mockup per concept of the abstract syntax:

petrinet annotated mockup.drawio
If some concepts, properties or associations of the abstract syntax are not shown in the annotated mockups, it means the mockup was not complete enough and should be improved.

1.4. Good practices

Where to start the design of a concrete syntax of a DSL? How to decide what keywords to use, what punctuation, and what structure should be preferable? In this section we review a selection of advices and common good practices.

  • Consider carefully both context and stakeholders. Stakeholders includes both people who will write program/model using the DSL, and (possibly different) people who will read resulting programs/models. All this people come with a specific technical background, a specific culture, and an existing set of habits. Ideally, a concrete syntax should take all this into account, and should provide notations that are as intuitive and easy to understand as possible for the stakeholders.

    • If they are already using formal/informal notations used by the stakeholders, use them as inspiration. For example if they are used to certain abbreviations or are used to write mathematics, the DSL concrete syntax can resue some of them.

    • If they have a specific jargon for their domain, don’t hesitate to use them as keywords.

    • If they already use software languages that they like, have a look at the concrete syntax of these languages and use them as inspiration. For example if they are used to C or Java programming, use lowcase keywords and use braces {} as delimiters.

  • Avoid making a DSL just for you! (except if you are the main target user) You are a software engineer, hence you have all the preferences of a software engineer, which may differ greatly from those of a specific domain expert.

  • Have a consistent syntax. A program or model is made to be read, which is easier if everything looks balanced and homogenous. Try using a limited set of punctuation that you always use in the same way, and try to always declare things in a similar fashion. Make sure your keywords are styled similarly (lower vs upper case, abbreviations vs full words, etc.)

  • Use existing concrete syntaxes as inspirations. Many software languages have been made already, each with different stylistic choices regarding their concrete syntax. Don’t hesitate to draw inspiration or to mimic what already exists − if it does not contradict previous points!

One DSL, many possible concrete syntaxes

For a given abstract syntax and a given DSL, many possible concrete syntaxes can be invented. Consider for example the Petri nets DSL shown previously, where we designed the following abstract syntax:

Diagram

And using the classes of this abstract syntax, we already instantiated the following example AST that corresponds to this model:

Diagram

We previously proposed a first design using the following mockup, where we avoid braces {} because they look too programming oriented, and where we use uppercase keywords to very clearly distinguish identifiers from keywords:

PLACE p1 WITH 1 TOKEN
PLACE p2
PLACE p3 WITH 1 TOKEN

TRANSITION t1
    IN [p1]
    OUT [p2]
END

TRANSITION t2
    IN [p2,p3]
END

But another possible concrete syntax could be closer to programming languages and how variables and their attributes are assigned:

place p1, p2, p3;
p1.tokens = 1;
p3.tokens = 1;
tran t1, t2;
t1.in = {p1};
t1.out = {p2};
t2.in = {p2,p3};

Or another could use action keywords to explain how tokens move around:

place p1(1)
place p2
place p3(1)

transition t1 {
	take from p1
	give to p2
}

transition t2 {
	take from p2
    take from p3
}

Or another could provide an arrow notation to bind places and transitions together:

places [
    p1: 1
    p2: 0
    p3: 1
]
p1 -> t1 -> p2
p2,p3 -> t2

All these solutions can work, there is no bad answer per se! The "good choice" will depends on requirements, context and and user feedback.

Example 7. Designing a concrete syntax for a State Machines DSL using annotated mockups

We would like to design the textual concrete syntax of the States Machines DSL that we began in the previous chapter.

As a reminder, we designed the following abstract syntax:

Diagram

Using this metamodel, we are able to use it to create an AST for the following example model:

statemachines threestates model.drawio

which results in the following AST:

Diagram

What textual concrete syntax do we want for this DSL? After discussions with (imaginary) stakeholders, we gather the following useful information:

  • they prefer lowcase keywords,

  • they are not programmers and thus are not used to using braces {},

  • they are used to graphical notations such as symbols and arrows, but do not like abbreviations in words,

  • they would like too be able to write comments in the code.

We make the following choices: - use very clear, unabbreviated lowcase keywords to declare each part of a program: statemachine, events, state, transitions, etc. - use the keyword end as a delimiter when appropriate, to avoid braces, - use a rather visual arrow notation ⇒ for declaring transitions, - use the traditional // notation to declare single-line comments.

We end-up with the following mockup textual representation for the AST shown above:

statemachine threestates

events:
    e1, e2, e3

commands:
    c1, c2, c3

initial: S1

state S1:
    on_entry: c1
    e1 => S2
end

state S2:
    on_entry: c2
    e2 => S3
end

state S3:
    on_entry: c3
    e3 => S1
end

In this mockup, we distinguish the following tokens and types of tokens:

  • Keywords: statemachine, events, commands, initial, state, on_entry, end

  • Punctuation:

    • operators: =>

    • delimiters: N/A

    • separators: :

  • Identifiers: threestates, e1, e2, e3, c1, c2, c3, S1, S2, S3

  • Comments: //

  • Literals: N/A

Finally, we map this proposed concrete syntax with the abstract syntax by preparing the following annotated mockups:

statemachines example cs annotated.drawio

2. Implementing a textual concrete syntax in Langium

In this section we will see how to implement a concrete syntax design into a usable parser using Langium.

2.1. Implementing the concrete syntax using grammar rules

A Langium concrete syntax is implemented in the form of a grammar and grammar rules. When a grammar is "executed", it transforms the text of an input program (provided as a file) into a structured AST (in memory) of the same program .

First, a grammar is declared with the keyword grammar:

grammar MyDSL

Another .langium file can be imported using the import keyword, without writing the .langium extension of said file:

import './otherfile' // this imports the file 'otherfile.langium'
This can for instance be used to import the abstract syntax defined in a separate file.

A grammar rule can be understood as a function that transforms a specific piece of text of the input program into a node of the output AST. This node is an instance of a concept of the abstract syntax (specified using the returns keyword).

Abstract syntax
interface MyConcept { … }
Concrete syntax
// Parser rule that produces an instance of 'MyConcept'
MyConceptRule returns MyConcept:
    …
;

// Terminal rule that recognizes a valid identifier, and outputs it as a string
terminal ID returns string:
    /[_a-zA-Z][\w_]*/
;

There are three sorts of grammar rules:

  • A parser rule defines a sequence of tokens that is possible at this location of the input program. From an abstract syntax point of view, executing a parser rule generally produces an instance of a concept.

  • A terminal rule is declared with the terminal keyword, and contains a regular expression. It defines a possible kind of lexical token that can be parsed using the grammar, such as an identifier, an arbitrary string, an integer, etc. From an abstract syntax point of view, executing a terminal rule produces the value of a primitive property.

  • A hidden terminal rule is declared with the hidden terminal keywords, and also contains a regular expression. However, instead of defining lexical tokens, it defines which sequences of characters that must be be ignored during parsing. This is typically used to ignore whitespaces and comments.

Langium default terminal rules

By default, a Langium project comes with the following set of pre-defined terminal rules:

hidden terminal WS: /\s+/;
terminal ID: /[_a-zA-Z][\w_]*/;
terminal INT returns number: /[0-9]+/;
terminal STRING: /"(\\.|[^"\\])*"|'(\\.|[^'\\])*'/;

hidden terminal ML_COMMENT: /\/\*[\s\S]*?\*\//;
hidden terminal SL_COMMENT: /\/\/[^\n\r]*/;

Each of these terminal rules can be used to either match or ignore different sequences of characters:

  • WS is a hidden terminal rule that matches (and therefore ignore) whitespaces, including tabulations and newline characters. This means the grammar will ignore all whitespaces, which means any amounts of whitespaces are allowed between two tokens.

  • ID is a terminal rule that matches an identifier (examples: List, myVariable, _building5), and implicitly produces a _string_ primitive value. This rule is almost always used to parse the name attribute of a concept, and to define a cross-reference to an existing element.

  • INT is a terminal rule that matches an integer (examples: 15, 896, 0) and produces a number primitive value.

  • STRING is a terminal rule that matches a string enclosed either between quotations marks " or single quotations marks ' (examples: "Good morning", "hello", 'the car is red'), and implicitly produces a string primitive value. It allows whitespaces between characters.

Be careful not to mix ID and STRING! ID does not allow whitespaces and cannot contain quotation marks, while STRING can contain whitespaces and must be enclosed in quotation marks.

  • ML_COMMENT is a hidden terminal rule that matches (and therefore ignore) multi-line comments enclosed between /* and */.

  • SL_COMMENT is a hidden terminal rule that matches (and therefore ignore) single-line comments enclosed between // and a newline character.

You can customize the comments delimiters of your language by changing the ML_COMMENT and/or the SL_COMMENT rules. For example for Python-style comments (using #), you can rewrite SL_COMMENT this way:

hidden terminal SL_COMMENT: /#[^\n\r]*/;
Most of the time, we can simply reuse the default terminal rules generated in a new Langium project.

A token declared in a parser rule can be defined in two ways:

Abstract syntax
interface MyConcept {
    name: string
}
Concrete syntax
// Parser rule that produces an instance of 'MyConcept'
MyConceptRule returns MyConcept:
    'somekeyword' name=ID ';'
;

  • A token in single quotes means that this exact string should be found at this specific location in the program. This is mostly used for definin keywords and punctuation. For example, here somekeyword is a keyword and ; is punctuation, and mean that MyConceptRule always starts with somekeyword and ends with ;.

  • A call to an existing grammar rule, which means that this other grammar rule should apply at this location of the program. In addition, calling another grammar rule requires assigning (=) the output of the called rule into a containment property of the output instance. For example here the rule ID is expected after somekeyword, and the output of the rule ID is stored in the property name of the output MyConcept instance.

By default Langium considers that there can be an arbitrary amount of whites spaces between two tokens.

It is possible to define repeated tokens in a parser rule:

Abstract syntax
interface MyConcept {
    name: string
    children: OtherConcept[]
}

interface OtherConcept {}
Concrete syntax
MyConceptRule returns MyConcept:
    'somekeyword' name=ID (children+=OtherConceptRule)* ';'
;

OtherConceptRule returns OtherConcept: … ;

  • A repetition of a group of tokens is declared with parentheses () followed by either a star \* or a plus `. This means that, at this location of the program, the enclosed tokens must be found _zero, one or multiple times_ for a `*`, and _one or multiple times_ for a `.

  • An assignment in a repetition must be written as +=, and must mandatorily target an containment array property of the returned concept. For instance here children is a containment array property, therefore we can have a repetition that adds multiple OtherConcept instances in the property using the OtherConceptRule.

It is possible to define optional tokens in a parser rule:

Abstract syntax
interface MyConcept {
    name: string
    isActive: boolean
}
Concrete syntax
MyConceptRule returns MyConcept:
    'somekeyword' (isActive?='active')? name=ID ';'
;

  • A optional group of tokens is declared with parentheses () followed by a question mark ?. This means that the enclosed tokens can be found either zero or one time at this location.

  • The presence of an optional token can be stored in a boolean property of the concept using the =? operator. For instance here isActive is a boolean property which is true if the keyword active is found after the keyword somekeyword, and false otherwise.

It is possible to define alternatives in a group of tokens:

Abstract syntax
interface MyConcept {
    name: string
    isActive: boolean
    others: OtherConcept[]
    anothers: AnotherConcept[]
}

interface OtherConcept {}

interface AnotherConcept {}
Concrete syntax
MyConceptRule returns MyConcept:
    'somekeyword' ( others+=OtherConceptRule | anothers+=AnotherConceptRule )* ';'
;

OtherConceptRule returns OtherConcept: … ;

AnotherConceptRule returns AnotherConcept: … ;

  • Inside any group declared with parenthese (), the pipe operator | can be used to declare mutually exclusive sequences of tokens. This can be combined with a repetition, meaning that each iteration of the repetition can have multiple possibilities. For example here the repetition will use either OtherConceptRule or AnotherConceptRule at each iteration, storing the result in others or anothers respectively.

It is possible to define a specific kind of token corresponding to a cross-reference of the abstract syntax:

Abstract syntax
interface MyConcept {
    name: string
    existingOther: @OtherConcept
}

interface OtherConcept {
    name: string
}
Concrete syntax
MyConceptRule returns MyConcept:
    'somekeyword' name=ID existingOther=[OtherConcept:ID] ';'
;

OtherConceptRule returns OtherConcept: …
    'otherkeyword' name=ID
;

  • A special cross-reference token can be declared with brackets with the following syntax <cross-reference>=[<concept>:<terminal rule>]:

    • <cross-reference> is the name of a cross-reference property

    • <concept> is the name of the concept (and not the parser rule!) referenced by the cross-reference property

    • <terminal rule> is the name of the terminal rule that is used to obtain the name attribute of the referenced concept.

For instance here the name of an OtherConcept is obtained using the ID terminal rule. Accordingly, the value of the existingOther cross-reference is an instance of OtherConcept whose name is written as an ID.

Writing parser rules can be a difficult task when writing a Langium grammar − and we only cover here a small subset of possibilities! If you want to learn more, the corresponding part in the Langium documentation is very complete.

Finally, each Langium grammar must have a unique entry parser rule, which is a grammar rule declared with the keyword entry:

entry MyConceptRule returns MyConcept: …  ;

An entry rule is the first rule executed when parsing a file with the grammar. It is comparable to the main function of a program.

Example 8. Langium concrete syntax of a State Machines DSL

We continue the State Machines DSL started previously, and for which we stored the abstract syntax in a file named statemachines-dsl.abstractsyntax.langium, with the following contents:

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
}

We would like to be able to write a state machine program in the following way:

statemachine threestates

events:
    e1, e2, e3

commands:
    c1, c2, c3

initial: S1

state S1:
    on_entry: c1
    e1 => S2
end

state S2:
    on_entry: c2
    e2 => S3
end

state S3:
    on_entry: c3
    e3 => S1
end

We therefore write the following grammar (which, as a reminder, relies on the concepts of the previously defined abstract syntax):

grammar StateMachinesDsl

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

entry StateMachineRule returns StateMachine:
    'statemachine' name=ID
    ('events' ':' events+=EventRule (',' events+=EventRule)*)?
    ('commands' ':'  commands+=CommandRule  (',' commands+=CommandRule)*)?
    'initial' ':' initialState=[State:ID]
    states+=StateRule*;

EventRule returns Event:
    name=ID;

CommandRule returns Command:
    name=ID;

StateRule returns State:
    'state' name=ID ':'
        ('on_entry' ':' on_entry+=[Command:ID] (',' on_entry+=[Command:ID])* )?
        transitions+=TransitionRule*
    'end';

TransitionRule returns Transition:
    trigger=[Event:ID] '=>' target=[State:ID];


///////// Primitive rules //////////

hidden terminal WS: /\s+/;
terminal ID returns string: /[_a-zA-Z][\w_]*/;
terminal INT returns number: /[0-9]+/;
terminal STRING: /"(\\.|[^"\\])*"|'(\\.|[^'\\])*'/;

hidden terminal ML_COMMENT: /\/\*[\s\S]*?\*\//;
hidden terminal SL_COMMENT: /\/\/[^\n\r]*/;

Using the parser generated from this grammar, we can parse the example State Machines DSL program shown just before, which results in the following AST:

Diagram
Automatic inference of the abstract syntax

Langium offers the possibility to automatically infer the abstract syntax from the concrete syntax, which can reduce the amount of lines of code in a Langium grammar. For example, this Langium grammar file:

// Abtract syntax
interface ConceptA {
    name: string
}

// Concrete syntax
ConceptARule returns ConceptA:
    name=ID;
;

can be rewritten like this:

// Concrete syntax + automatic inference of the abstract syntax
ConceptA:
    name=ID;
;

However, because this method "hides" the underlying abstract syntax definition, we prefer in this chapter to always separate the abstract and concret syntaxes implementations.

Most Langium examples online rely on automatic inference.

2.2. Fixing ambiguity and left-recursion problems

A common difficulty when writing a grammar is to avoid having ambiguous rules. Ambiguity arises when, for the same input program, multiple different ASTs can be produced by the parser, depending on the order grammar rules are called.

In most simple cases, a common way to fix an ambiguity problem is through the clever use of keywords and punctuation in the grammar, to make sure each case in a program can only correspond to a single possible grammar rule.

Example 9. Fixing a simple ambiguity in a grammar

Consider the following abstract syntax implemented in Langium:

interface Staff {
    persons: Person[]
}

interface Person {
    name: string
}

interface Student extends Person {}

interface Teacher extends Person {}

We prepare the following concrete syntax as a Langium grammar:

entry StaffRule returns Staff:
    (persons+=StudentRule | persons+=TeacherRule)*;

StudentRule returns Student:
    name=ID;

TeacherRule returns Teacher:
    name=ID;

We build the Langium project, and we open an editor where we write this program:

Emmanuel
Aurore

What will the AST produced by the parser look like? For each line of the program, there is no way for the parser to know whether it should apply the StudentRule or the TeacherRule. This means the following AST is a possible valid result:

Diagram

But also the following AST:

Diagram

This means the grammar is ambiguous.

A simple solution to this problem is to disambiguate using dedicated keywords, like so:

StudentRule returns Student:
    'student' name=ID;

TeacherRule returns Teacher:
    'teacher' name=ID;

Then we can write this program:

teacher Emmanuel
student Aurore

Which can only be parsed into the following AST:

Diagram

While most ambiguity problems can be solved by adding keywords and/or punctuations in the rules, one particular type of ambiguity problem is called the left-recursion problem. We say that a grammar is left-recursive when a grammar rule will call itself (directly or indirectly) in the leftmost part of the rule. Not only this leads to many different ways to parse the same program (hence ambiguity), but it can also lead to infinite recursion in the parsing algorithm.

Langium will automatically detect a left-recursion problem in a grammar and trigger a build error.

The most common cases of left-recursion happen when a language provides infix operators (such as + and * in an expression such as 2+7*3). An infix operator is an notation where the operands of an operator are placed on the left and on the right of the operator. Different infix operators usually have different priorities (such as multiplication has higher priority than addition).

Example 10. A left-recursive grammar for typical arithmetic expressions

Consider the following abstract syntax implemented in Langium, which allows representing ASTs with binary expressions which are themselves composed of expressions:

interface Expression {}

interface BinaryExpression extends Expression {
    left: Expression
    operator: string
    right: Expression
}

interface IntegerLiteral extends Expression {
    value: number
}

We would like a grammar that, given the textual representation 2+7*3, gives us the following AST (where the higher priority of * is taken into account):

Diagram

To do so, we try writing the following (wrong) Langium grammar:

entry ExpressionRule returns Expression:
    BinaryExpressionRule | IntegerLiteralRule
;

BinaryExpressionRule returns BinaryExpression:
    left=ExpressionRule operator=('+' | '*') right=ExpressionRule
;

IntegerLiteralRule returns IntegerLiteral:
    value=INT
;

Unfortunately this grammar is left-recursive: when we apply ExpressionRule, then BinaryExpressionRule, we end-up with applying again ExpressionRule at the left-most part of our computation:

ExpressionRule

→ BinaryExpressionRule

→ ExpressionRule + ExpressionRule

Moreover, the grammar does not provide any way to ensure the multiplication (*) has a higher priority than the addition (+). This means if this grammar was applicable in Langium, we could obtain a wrong AST for the textual representation 2+7*3 such as:

Diagram

Fixing a left-recursion problem is called left-factoring, and consists in avoiding having a single grammar rule for all operators, and instead to have a "hierarchy" of grammar rules that each depend on the next one in a strict sequence. To do so, each grammar rule is dedicated at parsing all occurrences of a single type of operator (for example all additions), and then explicitely calls the (similar) grammar rule of the operator that has higher priority, and so on.

Unfortunately in Langium this is quite verbose, and this requires an advanced feature of Langium called tree-rewriting actions, written using braces {}, which define explicit action that must occur when building the AST during the parsing.

It is not required to know this method, we only show it to give an idea of the general principle before showing the better way to solve the problem using an infix rule.
Example 11. Left-factoring a left-recursive grammar (the old-fashioned way)

Consider the (wrong) left-recursive grammar prepared in the last example.

entry ExpressionRule returns Expression:
    BinaryExpressionRule | IntegerLiteralRule
;

BinaryExpressionRule returns BinaryExpression:
    left=ExpressionRule operator=('+' | '*') right=ExpressionRule
;

IntegerLiteralRule returns IntegerLiteral:
    value=INT
;

Left-factoring this grammar would give us the following (good) grammar, which would not be left-recursive anymore:

entry ExpressionRule returns Expression:
    AdditionRule
;

AdditionRule returns Expression:
    MultiplicationRule
    ({BinaryExpression.left=current} operator="+" right=MultiplicationRule)*
;

MultiplicationRule returns Expression:
    IntegerLiteralRule
    ({BinaryExpression.left=current} operator="*" right=IntegerLiteralRule)*
;

IntegerLiteralRule returns IntegerLiteral:
    value=INT
;

With this fixed grammar, given a textual representation such as 2+7*3, we would apply without any ambiguity the grammar rules in the following way:

ExpressionRule

→ AdditionRule

→ MultiplicationRule + MultiplicationRule

→ (IntegerLiteralRule) + (IntegerLiteralRule * IntegerLiteralRule)

Twice, we use the tree-rewriting action {BinaryExpression.left=current} to make sure we create a BinaryExpression node in the AST when an operator is encountered, and we assign to the left attribute the node built before encountering the operator.

Fortunately, Langium provides a much easier solution for left-factoring with a dedicated type of grammar rule called the infix grammar rule. An infix grammar rule is a special kind of grammar rule that only requires an ordered list of operators (from the highest priority to the lowest), and a complementary normal grammar rule that defines that is the simplest type of element we can find in an expression (for example, an integer).

An infix grammar rule must return an AST node that must have the attributes left, operator and right.
Example 12. Left-factoring a left-recursive grammar (using a Langium infix grammar rule)

Consider again the (wrong) left-recursive grammar prepared in the last example.

entry ExpressionRule returns Expression:
    BinaryExpressionRule | IntegerLiteralRule
;

BinaryExpressionRule returns BinaryExpression:
    left=ExpressionRule operator=('+' | '*') right=ExpressionRule
;

IntegerLiteralRule returns IntegerLiteral:
    value=INT
;

We can use an infix grammar rule to left-factor this grammar:

entry ExpressionRule returns Expression:
    BinaryExpressionRule
;

infix BinaryExpressionRule on IntegerLiteralRule returns BinaryExpression:
    '*' > '+'
;

IntegerLiteralRule returns IntegerLiteral:
    value=INT
;

The BinaryExpressionRule is an infix grammar rule, which uses the rule IntegerLiteralRule as the simplest type of elements that can be found in an expression, and which has two operators and +, with the one with the highest priority.

Moreover, BinaryExpressionRule returns a BinaryExpression, which is correct because BinaryExpression was implemented earlier with the required three attributes: left, operator and right.

2.3. The Langium generator

Once a complete Langium grammar has been defined in the packages/language/src folder in the form of one or multiple .langium files, it is time to call the Langium generator to automatically produce data types, an editor and a parser for our software language.

As already explained in the chapter on Langium, to run the Langium generator, and to compile the generated Typescript code:

npm run langium:generate && npm run build

This mainly automatically produces the following artifacts:

  • packages/language/src/generated/ast.ts: Typescript data types for all concepts of your abstract syntax, along with many utility functions and boilerplate code for an easy manipulation of your AST.

  • packages/language/src/generated/grammar.ts: a JSON representation of your grammar, which is then automatically used to configure the Langium parser.

  • packages/language/src/generated/module.ts: a Typescript module with metadata (such as the file extension) and pointers to the other language components.

You will never have to manually edit these files, as they are entirely derived from your Langium code.

3. Testing a generated editor of a Langium language

See the dedicated section in the chapter on Langium.