First of all, when reading a program written in a programming language, the implementation has to make sure that the program respects the syntax of that language.

To this aim, we need to break the program into tokens. Each token is a single atomic element of the language; this can be a keyword (such as class in Java), an identifier (such as a Java class name), or a literal, that is, a fixed value. Examples of literals are string literals, typically surrounded by quotes, integer literals, and boolean literals (for example, true and false). Other kinds of tokens are operators (such as arithmetic and comparison operators) and separators (such as parentheses and terminating semicolons).

For instance, in the preceding example, employed is a keyword, the parentheses are separators, James is an identifier, and 50 is an integer literal.

The process of converting a sequence of characters into a sequence of tokens is called lexical analysis, and the program or procedure that performs such analysis is called a lexical analyzer, lexer, or simply a scanner. This analysis is usually implemented by using regular expressions syntax.

Having the sequence of tokens from the input file is not enough, we must make sure that they form a valid statement in our language; that is, they respect the syntactic structure expected by the language. This phase is called parsing or syntactic analysis. The program or procedure that performs such analysis is called a parser.

Let's recall the DSL to describe the name and age of various people and a possible input text:

James Smith (50)
John Anderson (40) employed

In this example, each line of the input must respect the following structure:

In our language, tokens are separated by white spaces, and lines are separated by a newline character.

You can now deduce that the parser relies on the lexer. In fact, the parser asks the lexer for tokens and tries to build valid statement of the language.

If you have never implemented a programming language, you might be scared at this point by the task of implementing a parser, for instance, in Java. You are probably right, since this is not easy. The DSL we just used as an example is very small and still it would require some effort to implement. What if your DSL has to deal also with, say, arithmetic expressions? In spite of their apparently simple structure, arithmetic expressions are recursive by their own nature; thus a parser implemented in Java would have to deal with recursion as well, and, in particular, it should avoid possible endless loops.

There are tools to deal with parsing so that you do not have to implement a parser by hand. In particular, there are DSLs to specify the grammar of the language, and from this specification, they automatically generate the code for the lexer and parser. For this reason, these tools are called parser generators or compiler-compilers. In this context, such specifications are called grammars. A grammar is a set of rules that describe the form of the elements that are valid according to the language syntax.

Here are some examples of tools for specifying grammars.

Bison and Flex (Levine 2009) are the most famous in the C context: from a high level specification of the syntactic structure (Bison) and lexical structure (Flex) of a language, they generate the parser and lexer in C, respectively. Bison is an implementation of Yacc (Yet Another Compiler-compiler, Brown et al. 1995), and there are variants for other languages as well, such as Racc for Ruby.

In the Java world, the most well-known is probably ANTLR (ANother Tool for Language Recognition) pronounced Antler, (see the book Parr 2007). This allows the programmer to specify the grammar of the language in one single file (without separating the syntactic and lexical specifications in different files), and then it automatically generates the parser in Java.

Just to have an idea of what the specification of grammars looks like in ANTLR, here is a very simplified grammar for an expression language for arithmetic expressions with sum and multiplication (as we will see in Chapter 9, Type Checking we cannot write a recursive rule such as the one shown in the following snippet):

expression
  : INT
  | expression '*' expression
  | expression '+' expression
;

Even if you do not understand all the details, it should be straightforward to get its meaning—an expression is either an integer literal or (recursively) two expressions with an operator in between (either * or +).

From such a specification, you automatically get the Java code that will parse such expressions.

Parsing a program is only the first stage in a programming language implementation. Once the program is checked as correct from the syntactic point of view, the implementation will have to do something with the elements of the program.

First of all, the overall correctness of a program cannot always be determined during parsing. One of the correctness checks that cannot be performed during parsing is type checking, that is, checking that the program is correct with respect to types. For instance, in Java, you cannot assign a string value to an integer variable, or you can only assign instances of a variable's declared type or subclasses thereof.

Trying to embed type checking in a grammar specification could either make the specification more complex, or it could be simply impossible, since some type checks can be performed only when other program parts have already been parsed.

Type checking is part of the semantic analysis of a program. This often includes managing the symbol table, that is, for instance, handling the variables that are declared and that are visible only in specific parts of the program (think of fields in a Java class and their visibility in methods).

For these reasons, during parsing, we should also build a representation of the parsed program and store it in memory so that we can perform the semantic analysis on the memory representation without needing to parse the same text over and over again. A convenient representation in memory of a program is a tree structure called the Abstract Syntax Tree (AST). The AST represents the abstract syntactic structure of the program. Being abstract, the tree representation does not represent many details of the original program, such as grouping parentheses and formatting spaces. In this tree, each node represents a construct of the program.

Once the AST is stored in memory, we will not need to parse the program anymore, and we can perform all the additional semantic checks on the AST. If all the checks succeed, we can use the AST for the final stage of the implementation, which can be the interpretation of the program or code generation.

In order to build the AST, we need two additional things.

First of all, we need the code for representing the nodes of such a tree. If we are using Java, this means that we need to write some Java classes, typically one for each language construct. For instance, for the expression language, we might write one class for the integer literal and one for the binary expression. Remember that since the grammar is recursive, we need a base class for representing the abstract concept of an expression. For example:

public interface Expression { }

public class Literal implements Expression {
  Integer value;
  // constructor and set methods...
}

public class BinaryExpression implements Expression {
  Expression left, right;
  String operator;
  // constructor and set methods...
}

Then, we need to annotate the grammar specification with actions that construct the AST during the parsing. These actions are basically Java code blocks embedded in the grammar specification itself. The following is just an (simplified) example, and it does not necessarily respect the actual ANTLR syntax:

expression:
  INT { $value = new Literal(Integer.parseInt($INT.text)); }
| left=expression '*' right=expression {
  $value = new BinaryExpression($left.value, $right.value);
  $value.setOperator("*");
}
| left=expression '+' right=expression {
  $value = new BinaryExpression($left.value, $right.value);
  $value.setOperator("+");
}
;

The ability to see the program colored and formatted with different visual styles according to the elements of the language (for example, comments, keywords, strings, and so on) is not just cosmetic.

First of all, it gives immediate feedback concerning the syntactic correctness of what you are writing. For instance, if string constants (typically enclosed in quotes) are rendered as red, and you see that at some point in the editor the rest of your program is all red, you may soon get an idea that somewhere in between you forgot to insert the closing quotation mark.

The programming cycle consisting of writing a program with a text editor, saving it, switching to the command line, running the compiler, and in the case of errors, shifting back to the text editor is surely not productive.

The programming environment should not let the programmer realize about errors too late. On the contrary, it should continuously check the program in the background while the programmer is writing, even if the current file has not been saved yet. The sooner the environment can tell the programmer about errors, the better it is. The longer it takes to realize that there is an error, the higher the cost in terms of time and mental effort to correct it.

When your DSL parser and checker issue some errors, the programmer should not have to go to the console to discover such errors. Your implementation should highlight the parts of the program with errors directly in the editor by underlining (for instance, in red) only the parts that actually contain the errors. It should also put some error markers with an explicit message on the left of the editor in correspondence to the lines with errors, and should also fill the Problems view with all these errors. The programmer will then have the chance to easily spot the parts of the program that need to be fixed.

Content assist is the feature that automatically, or on demand, provides suggestions on how to complete the statement/expression the programmer just typed. The proposed content should make sense in that specific program context in order to be effectively useful. For instance, when editing a Java file, after the keyword new, Eclipse proposes only Java class names as possible completions.

Again, this has to do with productivity. It does not make much sense to be forced to know all the syntax of a programming language by heart (especially for DSLs, which are not common languages such as Java), neither to know all the language's library classes and functions.

In Eclipse, the content assist is usually accessed with the keyboard shortcut Ctrl + Space bar.

Hyperlinking is a feature that makes it possible to navigate between references in a program. For example, from a variable to its declaration, or from a function, call to the function definition. If your DSL provides declarations of any sort (for instance, variable declarations or functions) and a way to refer to them (for instance, referring to a variable or invoking a declared function), then it should also provide Hperlinking from a token referring to a declaration. It should be possible to directly jump to the corresponding declaration. This is particularly useful if the declaration is in a file different from the one being edited. In Eclipse, this corresponds to pressing F3 or using Ctrl + click.

Hovering is a similar IDE feature—if you need some information about a specific program element, just hovering on that element should display a pop-up window with some documentation about that element.

If the programmer made a mistake and your DSL implementation is able to fix it somehow, why not help the programmer by offering suggested quickfixes?

As an example, in the Eclipse Java editor, if you invoke a method that does not exist in the corresponding class, you are provided with some quickfixes. For instance, you are given a chance to fix this problem by actually creating such a method. This is typically implemented by a context menu available from the error marker.

In a test-driven scenario this is actually a methodology. Since you write tests before the actual code to test, you can simply write the test that invokes a method that does not exist yet, and then employ the quickfix to let the IDE create that method for you.

If a program is big, it is surely helpful to have an outline of it showing only the main components. Clicking on an element of the outline should bring the programmer directly to the corresponding source line in the editor.

Furthermore, the outline can also include other pieces of information such as types and structure that are not immediately understood by just looking at the program text. It is handy to have a view that is organized differently, perhaps sorted alphabetically to help with navigation.

In an Eclipse Java project, when you modify one Java file and save it, you know that Eclipse will automatically compile that file and, consequently, all the files that depend on the file you have just modified. There is no need to manually call the Java compiler.

In this section, we briefly and informally introduced the main steps to implement a DSL.

The IDE tooling can be implemented on top of Eclipse, which already provides a comprehensive framework.

Indeed, all the features of the Eclipse Java editor, which is part of the project JDT (Java Development Tools), are based on the Eclipse framework; thus, you can employ all the mechanisms offered by Eclipse to implement the same features for your own DSL.

Unfortunately, this task is not really easy, it certainly requires a deep knowledge of the internals of the Eclipse framework and lot of programming.

Finally, the parser and the checker will have to be connected to the Eclipse editing framework.

To make things a little bit worse, if you learned how to use all these tools (and this requires time) for implementing a DSL, when it comes to implement a new DSL, your existing knowledge will help you, but the time to implement the new DSL will still be huge.

All these learning and timing issues might push you to stick with XML, since the effort to produce a new DSL does not seem to be worthwhile. Indeed, there are many existing parsing and processing technologies for XML for different platforms that can be used, not to mention existing editors and IDE tooling for XML.

But what if there was a framework that lets you achieve all these tasks in a very quick way? What if this framework, once learned (yes, you cannot avoid learning new things), lets you implement new DSLs even quicker than the previous ones?

We will use the latest version of Eclipse. At the time of writing this book, the latest version of Eclipse is 4.6, named Neon. This version requires Java 8, so you will also have to make sure that you have Java 8 installed (see https://www.eclipse.org/downloads).

Xtext is an Eclipse framework; thus, it can be installed into your Eclipse installation using the update site as follows:

http://download.eclipse.org/modeling/tmf/xtext/updates/composite/releases

Just copy this URL into the dialog you get when you navigate to Help | Install New Software… in the textbox Work with and press Enter; after some time (required to contact the update site), you will be presented with lots of possible features to install, grouped by categories. Navigate to the Xtext category and select the Xtext Complete SDK feature.

Alternatively, an Eclipse distribution for DSL developers based on Xtext is also available from the main Eclipse downloads page, http://www.eclipse.org/downloads, called Eclipse IDE for Java and DSL Developers.

Using Xtext with IntelliJ will be discussed later in Chapter 11, Continuous Integration.

Hopefully, by now you should be eager to see for yourself what Xtext can do! In this section, we will briefly present the steps to write your first Xtext project and see what you get. Do not worry if you have no clue about most of the things you will see in this demo; they will be explained in the coming chapters.

Perform the following steps:

This short demo should have convinced you about the powerful features of Xtext. Implementing the same features manually would require a huge amount of work. The result of the code generated by Xtext is so close to what Eclipse provides you for Java that your DSLs implemented in Xtext will be of high-quality and will provide the users with all the IDE tooling benefits.