Language tools such as compilers, interpreters, and code generators are a critical part of the software development landscape. Any software project will include several procured tools and very likely several in-house tools. Experience shows that the only guarantee with such tools is change: the underlying language may change due to improvements or extensions and the functionality provided by the tool expands, driven by user-requested features and the need to stay in front of the competition. The specific changes that will be made are rarely known at the outset, but change is coming.

This implies that when designing such a tool, extensibility is paramount. So it's important that the design is modular. A clean division of responsibilities is needed to support maintainability, which in turn is needed to support the rapid pace of change typically associated with language tools.

This article describes a proven approach to developing language-based tools in a way that is modular, extensible, and maintainable. The approach is based on two principles: establishing the core modules at the outset and using the visitor pattern to interact with language sentences.

To illustrate the approach a simple calculator example is given. This calculator supports the addition, subtraction, multiplication, and division of integers. The language supported by this calculator is informally described below:

expression = constant |
   expression op expression
constant = 0 | 1 | 2 | ...
op = + | - | * | /

This language is very simple, but it's sufficient to illustrate the main concepts related to the development of language tools. The example is developed in Java based on the JavaCC parser generator. However the concepts presented are language-independent and apply equally to C++ and C#. All of the code shown in this article is available for download.

A key objective when developing a language tool is to ensure that the tool isn't dependent on the actual representation of the language. This allows simple support for multiple language formats, imports from other tools, and so on. To meet this objective, a distinction is made between concrete and abstract syntax. This is described below. After this the notion of context is introduced followed by a description of the actual mechanism for parsing. Then the use of the generated parse tree is explained.

Concrete Syntax
Concrete syntax represents the way in which a specific file format represents the input for the tool. This is often described using BNF or a similar structured representation. If a parser generator such as Lex/Yacc, Antlr, or JavaCC is used, the concrete syntax will be described in a generator-specific manner. A simple concrete syntax for the calculator using JavaCC shown is Listing 1.

Note that normally semantic actions would be included in such a JavaCC description. These are presented later in the article.

In general there can be several concrete syntaxes for a language (plain text, XML, RTF, etc.). The tool design should be sufficiently flexible to support multiple concrete syntaxes (as well as the ability to add further concrete syntaxes) without having a major impact on the rest of the tool.

Abstract Syntax
Abstract syntax is a representation of the language that's independent of the concrete syntax. The abstract syntax representation contains only information that's necessary for the tool to perform its task; any other information is discarded. In principle this necessary information should be included in all concrete syntaxes. So there should only be one abstract syntax regardless of the number of concrete syntaxes. In an OO setting, an abstract syntax is typically a tree-structure that reflects the way in which language sentences can be constructed. The abstract syntax fulfils a number of functions. It:

• Represents the program
• Stores any necessary information related to the concrete representation (e.g., for pretty printing, relating error messages to specific file locations, etc.). This is explored further in the next section.
• Exposes the above information to tools without revealing implementation details.

Notice that the package arrangement in Figure 1 follows the convention used in Eclipse that dictates that classes in a package named intern are not to be exposed to other tools.

Context Information
The idea of creating abstract syntax is that the tool will use these objects to achieve its goals. This means that the tool is not dependent on the specific concrete format being used. However, this separation can be problematic since in some situations information from the concrete representation is actually needed. For instance, a type checker might generate an error message that has to be displayed to the user. For this message to be of value, the specific location of the error has to be provided.

The solution to this problem is to associate each abstract syntax node with an object defining the context of that node. This might, for example, be the start and end line and column for the node; the information required here may vary according to the nature of the language, the tool, and the concrete format in question. As with the abstract syntax, client tools should be shielded from the implementation details of context information, so an interface is used and classes implementing this interface are internal. It's possible that there may be multiple context information classes according to the concrete representation. This is suggested in Figure 2 where a plain text context information class is used.

Parsing
To create a parser, the concrete syntax presented earlier needs to be married with the abstract syntax classes. This is shown in Listing 2. Note that there will typically be one parser for each concrete syntax supported.

This example is based on JavaCC, but the principle applies to other parser generators: the semantic actions in the matching rules in the parser definition are used to create and instantiate abstract syntax objects, resulting in the creation of an abstract syntax tree corresponding to the input text. This abstract syntax tree will be the input to other components in the tool that require the input text.