Dolmen: A Generator for Lexical Analyzers and Parsers in Java

A better way of handling this parsing problem is to first split the source code into its atomic lexical elements, much like reading a sentence in a natural language requires to first identify the various words before checking whether their arrangement is grammatically correct. These lexical elements are called tokens and the phase which transforms the input stream of characters into a stream of tokens is called tokenization.

The tokens of a programming language usually consist of:

In particular, there are usually no tokens for whitespace or comments, although there could be tokens for special documentation comments if required. Looking at these couple of statements again:

the corresponding tokens would be

Some tokens such as constant literals or identifiers are associated to a value, such as the literal’s value or the identifier’s name, whereas the other tokens hold no particular value other than themselves.

The tokenization process is usually simple enough for the different tokens to be recognizable by regular expressions. For instance, one might informally describe some of the rules to identify the tokens of our language above as follows:

where SEMICOLON, IF, IDENT, etc. are the symbolic names given to the different kinds of tokens. The regular expressions for operators and keywords are straightforward and match the associated symbols exactly. Identifiers are simply a letter or an underscore followed by any number of alphanumeric characters, whereas decimal integer literals are either 0 or any number not starting with 0. There would be other rules for integer literals in other radices, but they could share the same token kind. Finally, string literals are formed by a pair of matching " without any double quotes in the middle; of course this is an oversimplification as it does not account for escaped characters appearing inside the string. The different rules are not necessarily exclusive, in which case some disambiguation rules must be applied. For instance, keywords look very much like valid identifiers, and in fact they are pretty much just that: reserved identifiers. A common way of handling this is to use the "longest-match rule", expressing that when a choice exists, the token that consumes the most characters in the input should be given preference. This ensures that defined is a single identifier token instead of the keyword def followed by an identifier ined, and that 1234 is a single integer instead of 1 followed by 234 or any other combination. When several rules match the same amount of input, a possible choice is to always pick the one which appears first in the set of rules; in our case above, this ensures the keyword if is matched as IF and not as an identifier.

Disambiguation aside, these regular expressions can be merged into a single regular expression which in turn can be transformed into a deterministic finite automaton (DFA) that recognizes the tokens. The final states of the DFA represent the various token rules and the DFA can be used to efficiently consume characters from the input stream. When the DFA reaches a final state, it emits the corresponding token, and in this fashion the input character stream can be transformed into a token stream. If ever the DFA fails to recognize the input characters at some point, this means the input string has a syntax error. With our rules above, this would for instance happen with an non-terminated string literal. Last but not least, we have not explained how whitespace and comments are handled: they must definitely be recognized and consumed but should produce no tokens. One way to do this in our informal description is to add the corresponding rules:

but have them produce no token at all. When the DFA reaches the corresponding state, it simply starts over with the remaining input without emitting any token in the output stream.

Lexical analyzer generators are tools which automate the process of turning a set of rules, such as those given informally above, into source code which implements the recognition mechanism for the DFA associated with the rules. This allows developers to keep a reasonably abstract view of the tokenization process, concentrate on designing the various regular expressions correctly, and leave everything else to the generator:

As none of the above is particularly easy to deal with, these generators are a great asset when trying to write a parser. Many generators, including Dolmen, will additionnally support input rules which are more expressive than simple regular expressions, like pushdown automata, making it possible to perform quite complex tasks during the tokenization phase.

Some lexical analyzer generators such as the ones in ANTLR or JavaCC are intrinsically linked to an associated parser generator and are used to produce tokens for these parsers, but lexical analysis is not limited to producing tokens for a grammar-based syntactic analysis. One can actually associate the lexer rules to any computable action, such as printing something or aggregating some information. Possible applications of a "standalone" lexical analyzer may be:

Lexers generated by Dolmen are not specialized for tokenization and can be used for any kind of lexical analysis by designing the appropriate actions. Another lexer generator in the Java ecosystem which produces standalone lexical analyzers is JFlex. In particular both can be used to produce token streams for other parser generators such as Cup or BYacc/J. The Lexical Analyzers chapter in this documentation explains how to write your own lexers with Dolmen.

The overall structure of a Dolmen lexer description is as follows:

We will come back to the options and regular expression definitions parts later. The Java imports section contains plain Java import declarations which are added by Dolmen to the generated lexical analyzer and can be used in the various Java actions of the lexer description. In our case, we will import the Token class for sure, and we may even import its static members to simplify access to the token static factories:

The Java prelude and postlude are arbitrary Java snippets which will be added respectively to the top and bottom of the generated lexical analyzer. They can typically be used for local auxiliary methods or static initializers. We can leave them empty for now, and will come back and add convenient methods to the prelude if need arises.

The main part of a Dolmen lexer consists of lexer entries, of which there must be at least one per lexer. At this point, our partial lexer description looks like this and is just missing some entries:

When a lexical analyzer starts consuming a file, a string or any stream of characters, it needs a set of rules explaining what patterns must be recognized and what actions must be taken in response. In Dolmen lexer descriptions, such a set of rules is called a lexer entry and has the following structure:

An entry has a visibility and a name; the entry’s visibility can be either public or private and specifies the visibility of the corresponding entry point in the generated lexer. Each of the following line is called a clause and specifies some regular expression and an associated semantic action in Java. Each entry must have at least one clause.

Using a lexer entry will match the character stream for the regular expressions in the entry’s clauses, and when a match is found, will consume the corresponding part of the character stream and execute the corresponding Java action.

The entry defines a Java return type which is the actual return type of the corresponding Java entry point in the lexical analyzer, and the semantic actions in the entry’s clauses must be consistent with that return type. In the case of our JSON lexical analyzer, let us add a main public rule which will return an instance of the Token class:

We can first add the clauses to recognize the punctuation tokens, these clauses simply match the punctuation character and return the associated token:

When used in a regular expression, a simple character literal will exactly match said character. Similarly, a double-quoted string literal will exactly match the given string, so we can easily add clauses to match the tokens for the true, false and null JSON keywords:

The exact syntax for number literals is for instance described in the JSON standard by the following railroad diagram:

A JSON number literal is therefore a decimal integer (without leading zeroes), preceded by an optional sign, and optionally followed by a fractional part and/or an exponent part, allowing common scientific notation to be used. It is straightforward to translate that diagram into a regular expression, but that expression would get quite large, which is both error-prone and hard to maintain. To alleviate this issue, Dolmen allows defining auxiliary regular expressions and composing them into bigger regular expressions. In a lexer description, definitions of auxiliary regular expressions can be inserted between the prelude and the lexer entries. Let us add a few auxiliary definitions to our description in order to tackle number literals:

We define a digit as being any character between 0 and 9. The […​] syntax defines a character set; it can contain any number of single characters, as well as character ranges described by the first and last characters of the range separated by -. The second definition uses the difference operator # to define a non-zero digit (nzdigit) as being any digit except 0. The difference operator can only be used with characters or character sets and will match any character in the left-hand side operand that is not also in the right-hand operand. The third definition makes use of traditional regular expression operators to define the integral part of a JSON number literal: ? for an optional match, | for the choice operator and * for matching any number of repetitions of a regular expression. Of course, the operator + is not needed here but can also be used to match one or more repetitions.

Similarly, it is straightforward to add definitions for the fractional and exponent parts, and finally to define number as the concatenation of the integral and (optional) fractional and exponent parts. We can now simply use number in the clause which must match number literals in the main lexer entry:

Unlike the symbols and keywords we had matched so far, the number token which must be constructed depends on the actual contents that have been matched by the clause; in other words, we need to construct the adequate double value to pass to the NUMBER static factory. The string which has been matched can be retrieved in the semantic action using the method getLexeme(). The various methods and fields which are available in semantic actions to interact with the lexing engine are listed in the reference section on semantic actions. In our case here, we can simply use getLexeme() and the Double.parseDouble method from the Java API:

At this point, our lexer is far from finished but it is not too early to try and generate the lexical analyzer. As with regular programs, it is not advised to write several hundred lines of lexer description without stopping regularly to test their behaviour.

Suppose we have created a file JsonLexer.jl with our lexer description so far, which looks as follows:

We also assume our working directory has the following structure:

Besides the source folder with our Token class and lexer file, we also have a bin/ folder for compiled classes, where Token has already been compiled, and the Dolmen JAR. The JAR contains both the runtime for Dolmen-generated analyzers, and the command line interface to Dolmen. We can invoke the latter to generate a lexical analyzer from our JsonLexer.jl:

Dolmen reports the various steps of the generation process and successfully generates a Java compilation unit JSonLexer.java in the mypackage directory (as instructed by the -o option). It also found one "potential problem" along the way; unlike errors which are fatal, problems are mere warnings which do not prevent the generation of the analyzer. We will see below how to check and address these problem reports, but for now let us continue with our main goal and compile the generated analyzer:

We have to add Dolmen_1.0.0.jar to the class path when invoking javac since the JAR contains the Dolmen runtime that is used by the generated lexer. Once the class is compiled, we can use the javap disassembler tool to check that the generated lexer consists in a single class JsonLexer with:

In order to actually test this generated lexer, we write the following Tokenizer class in mypackage:

We can compile Tokenizer and execute it, this shows us a prompt waiting for some input to feed to the lexical analyzer:

If we try a couple of very simple sentences using some JSON literals, we see the tokens seem to be recognized correctly but our lexer always ends up throwing an exception:

The Empty token lexical error is Dolmen’s way of expressing that the input stream at this point did not match any of the clauses in the main lexer entry. Dolmen also reports the position in the input stream at which the error occurred, in our case it always seems to occur at the end of our input string. Indeed, we never put any rule in our lexer entry to express what needed to be done when running out of input; because the entry cannot match an empty string either, it fails with an empty token error when reaching end of input.

A typical way of handling the end of input when parsing a language is to use a dedicated token to represent when it has been reached. In order to produce such token, we need to write a clause which recognizes the end of input specifically: for that purpose, the eof keyword can be used in regular expressions inside Dolmen lexer descriptions. eof will match the input if and only if the end of input has been reached, and will not consume any of it. Therefore, let us add a new token Token.EOF to our token factory, and a new clause to our lexer description:

We also fix the inner loop of the Tokenizer class so that it stops the lexical analysis as soon as it reaches the EOF token:

After generating the lexer anew and recompiling everything, we see the end of input seems to be handled correctly now:

Armed with such success, surely we can start testing more complex sequences of tokens!

This time, the empty token error occurs at the space following the first comma in our input string. So far our clauses have only dealt with recognizing and producing actual tokens of the language, but we have not yet instructed the lexer as to what sequences of characters, if any, can safely be skipped during lexical analysis, in other words we have not dealt with whitespace. The JSON standard defines exactly what constitutes whitespace in a JSON file:

We can now define a regular expression to match that definition and use it in a clause to correctly skip whitespace:

We will, for reasons that will be explained later on, do things slightly differently and handle regular whitespace and line terminators separately. Moreover, we use the more traditional escape characters to keep things more readable:

Along with the regular expressions, We added clauses at the beginning of our main lexer entry to handle both whitespace and newline sequences. The way we express in our semantic actions that the matched whitespace should be skipped is by simply starting the main entry again on the remaining input. There are mostly two ways to do that:

The trade-offs of choosing the latter over the continue statement are discussed in advanced concepts, but a good rule of thumb is that continue should be preferred whenever possible.

After recompiling everything, we can test that whitespace now seems to be handled correctly, and we can tokenize non-trivial JSON contents:

The only JSON feature missing at this point in our lexer is actually string literals, and we will see how to handle them in the next section.

The last kind of tokens we need to recognize is string literals. Again, the JSON standard proposes a railroad diagram for JSON string values:

A literal string is therefore a sequence of unicode code points delimited by double-quote characters. Between the delimiters, all unicode code points are valid except for the control characters (code points below 0x20), the backslash character \ and the quotation mark " itself of course. The " and \ characters can be inserted via escape sequences instead, as well as a few common control characters. Finally, any code point in the Basic Multilingual Plane can be inserted via its four-digit hexadecimal value using the \uxxxx escaping sequence.

A possible approach to recognizing these string literals would be to write a complex regular expression such as this:

and add the corresponding clause in our main lexer entry:

where decode would be some Java method to decode the contents of the literal string, by removing the quotation marks and replacing the escape sequences with the characters they stand for. Now there are at least two shortcomings with proceeding in this fashion:

The solution to both of those issues is simply to use the lexical analyzer itself to recognize, and decode at the same time, the contents of a string literal. As explained earlier in this tutorial, a lexical analyzer can be used for many things besides simply tokenizing input in a parser, and unescaping a string is one of them. To that end, we introduce in JSonLexer.jl a new lexer entry called string:

which differs from the main entry in several aspects:

This entry is intended to be called after encountering the opening quotation mark of a string literal, and must stop at the corresponding closing delimiter. This is handled by the first clause above, which returns the contents of the given buffer buf when matching ". We need two other clauses: one for escape sequences introduced by the \ character and the other for all other valid Unicode characters. Here is our string entry in full:

The third clause matches all non-escaped contents and uses the [^…​] construct to match all characters that do not belong to the specified character set; the characters \000 and \037 are given in octal code syntax and their interval corresponds to control characters. Matched input in this clause is simply appended to the string buffer that will be returned eventually, and the rule is started over using the continue operator. Now the second clause is more interesting as it deals with escape sequences; it simply matches a backslash character and then calls a method escapeSequence to retrieve the escaped character, append it to the buffer and continue the analysis. This escapeSequence method is simply yet another lexer entry whose job it is to parse and interpret any escape character or code and return the corresponding character:

The rule escapeSequence is private, expects no arguments, and simply returns a simple Java char. It matches all accepted escape characters as well as Unicode escape codes. For the latter, the regular expression hexDigit<4> as code is particularly interesting:

At this point, our string entry—​and its auxiliary rule for escape sequences—​can recognize and decode JSon string literals' contents in an elegant fashion, the last step is simply to call string from our main lexer entry:

This simply matches the opening quotation mark, and calls the string rule recursively with a fresh StringBuilder instance before returning the overall token. Now, our analyzer’s entries are not reentrant (or rather, they do not need to be), so it seems a bit wasteful to build a StringBuilder instance for every string that we are going to encounter, especially because typical JSON objects contain many string literals, in part as keys of JSON objects. A more resourceful way of proceeding is to use a single local buffer. We can add such a buffer to the fields of the generated lexer by using the prelude or postlude, which we had left empty so far, and adapt our clause accordingly:

We are now ready to regenerate our lexical analyzer:

and after recompiling the Java units, we can finally handle full JSON:

Our full lexer description now looks like this:

The description is merely 63 lines long, relatively easy to read and understand, and it can correctly analyze any correct JSON file! In the next section of this tutorial, we will see how to improve the lexer’s behaviour in the case where it is fed syntactically incorrect files.

So far, we have designed a working lexical analyzer for JSON files, but we have kept ignoring the "potential problems" that are reported by Dolmen every time we regenerate the lexer from the description:

As you can see, there are now three potential problems reported. Unlike errors which force Dolmen to abort the generation and are always reported on the standard output, these problems are recorded in a special reports file. By default, the reports file has the name of the lexer description with an extra .reports extension; this can be controlled on the command line with the -r/--reports option. Inspecting the file shows it reports three warnings:

These warnings are three instances of the same potential issue, one for each of our entries. The message explains that the entry "cannot recognize all possible input sequences" and goes on to give a few examples of unrecognized input strings.

This warning may come as a surprise: after all, a lexer is usually supposed to recognize some kind of language, and therefore should often reject at least some input sequences. As we have experienced already, an "Empty token" lexical error is raised by the generated lexer when an entry faces input which does not match any of the entry’s clauses. The actual idea behind this warning is to avoid occurrences of this lexical error, by encouraging programmers to account for invalid or unexpected input in their lexer descriptions, and raising exceptions with more specialized messages. Indeed, the "Empty token" message is really generic and rather unhelpful in most situations; in essence, it tells you the input cannot be recognized but does not tell you what is wrong, or what could be expected at this point in the stream.

Let us illustrate how our lexer can be improved can looking at the escapeSequence rule:

The warning report for this rule lists the following as possible input sequences which would result in an empty token error:

Indeed, the strings "u\000", "u0\000" and so on cannot be matched by the escapeSequence rule. This is not an exhaustive list, of course. In fact, when Dolmen internally compiles a lexer entry into a deterministic finite automaton, it will look for different ways to "get stuck" in the automaton, which correspond to input which would not be recognized. When a way of traversing the automaton and getting stuck is found, a corresponding canonical example is produced, by taking the adequate string with the smallest characters. For instance, the sequence "u0\000" stems for all input strings which start with a u, followed by some hexadecimal digit (of which 0 is the smallest), and then by any character other than a hexadecimal digit (of which the null character \000 is the smallest). Similarly, the null character in the sequence "\000" is the smallest possible character which cannot start a valid escape sequence. This is why the null character frequently appears in these report messages.

In essence, these examples of problematic input sequences remind us that our escapeSequence rule will fail to match:

Both instances reveal distinct syntactic problems and call for separate specific error messages. To that end, let us add two extra clauses to our entry:

The first clause handles any invalid Unicode escaping sequence by matching a single u character—​recall that by the longest-match disambiguation rule, this clause will not be used if u happens to be followed by four hexadecimal digits. The second clause uses the special wildcard regular expression _, which matches any single character, to handle the case of all invalid escape characters. The error() method used in the semantic actions here is a method exported by Dolmen’s base class for lexical analyzers and which simply returns a LexicalError exception with the given message and associated to the current lexer location. You can learn more about semantic actions here.

Now, if we recompile our lexer and look at the reports, we are disappointed to see that there still is a warning about escapeSequence being incomplete, albeit this time only a single input example is reported in the diagnostic:

The problematic input sequence is simply EOF, which is Dolmen’s way of writing the special "end-of-input" character (not to be confused with eof, which is the Dolmen keyword for the regular expression that exactly matches this special character). Indeed, for reasons which are detailed in a section dedicated to wildcards in this manual, the _ regular expression in a clause will match any character except EOF. Similarly, the character-set complement construct [^…​] will not match EOF either (which means that _ and [^] are completely equivalent). In short, this stems from the fact that the special end-of-input character behaves differently from regular characters in regular expressions, and usually calls for different error diagnostics in a lexical analyzer anyways. In our case, we can fix our escapeSequence rule for good by adding yet another clause, this time simply dealing with the case when the input ends right at the beginning of the escape sequence:

With these three fall-back clauses, our rule is finally warning-free, and we can test their effect by trying to tokenize a few various invalid sentences:

We can fix the similar warnings pertaining to the main and string entries in a similar fashion, by adding clauses to deal with unhandled characters:

The lexer description now compiles without any warnings! Altogether, we added six simple clauses, around 10 lines of code, and we statically made sure the generated lexical analyzer will never throw a generic empty token error, always using our custom messages.

Reporting nice helpful messages when encountering ill-formed input is very valuable, but reporting them at the correct place is equally important! The various lexical errors we encountered in our earlier tests were always located at some position in the input, displayed in terms of a line and a column number:

This is true for both the generic token errors raised by Dolmen-generated code and the custom lexical errors we raise ourselves in the semantic actions. Yet, for the latter, we never bothered to explicitly specify an input location when throwing the exception; in fact, the error() library function inherited from LexBuffer that we used to build the lexical exception did choose a position automatically. To make sure these positions are relevant, one needs to get a good grasp of the principles behind them. Not only are positions used to report lexical errors, they are also typically used in parsers built on top of the lexers, to report syntactic errors, decorate parsed abstract syntax trees with source locations, etc. It is quite hard to debug these mechanisms thoroughly and make sure they always use correct locations, and errors later reported at invalid or random locations in a compiler back-end can cause quite a few headaches. Fortunately, we will see how Dolmen can help assist in achieving and maintaining relevant locations throughout the lexical analysis.

For a start, it is about time we confront our lexical analyzer to a fully fledged JSON file instead of one-line sentences. We could adapt our Tokenizer class to read from a file and display all tokens, but this time we are interested in displaying the input locations associated to the tokens as well. The two methods getLexemeStart() and getLexemeEnd() inherited from the base LexBuffer class can be used in semantic actions to retrieve the positions of the part of the input which matched the current clause: getLexemeStart() will return the position of the first character of the match, while getLexemeEnd() will return the position of the first character which follows the match. The positions themselves consist of the following information:

Part of the position information, namely the name and absolute offset, are managed automatically by the generated lexer, whereas the other part is the responsibility of the developer writing the lexer description. The org.stekikun.dolmen.debug package contains utilities to help one debug lexical analyzers; using the Tokenizer class from this package, it is very easy to tokenize an input file as follows:

The Tokenizer.file method used in this example requires an interface describing what lexical analyzer to use, and how to use it, and will tokenize any given input file, printing the results to the specified output file. Suppose we have a simple JSON file, adequately called simple.json, in a resources folder of our working directory:

Calling this tokenizer on simple.son will produce the following results:

Each token is followed by its (start..end) locations, where each position is given in the format name[l,b+c] where name is the name of the input, l the line number, b the absolute offset of the beginning of that line, and c the 0-based column number of the position in that line. It is immediately clear that JsonLexer does not update line numbers correctly since every token is supposedly at line 1, whereas the column offsets keep growing. For instance, the last closing curly brace is showed as being on the 99-th column of the first line, wheras it is actually the first character of the 5-th line; that being said, it is indeed the 99-th character of the whole file, which shows the absolute position for this token was actually right.

The issue here is that lexers generated by Dolmen keep track of a current line number, but do not update it automatically. In order to fix our locations, we must thus tell the underlying lexing buffer when a new line starts. This is typically done from a semantic action by calling the helper method newline(), available from the base LexBuffer class. Calling newline() will simply increment the current line count, and tell the engine that a new line starts at the end of the current match. This is the reason why, earlier in this tutorial, we took care of writing two separate clauses for regular whitespace and for linebreaks, making sure we matched linebreaks separately, and one at a time:

It is easy now to fix the semantic action for our linebreak clause, by calling newline() before continuing with the main rule:

There is no other clause in JsonLexer.jl which successfully matches a line break, but if JSON allowed multi-line string literals for instance, we would need a similar clause with a call to newline() in the string entry. After this fix, the locations of our tokens look better:

Looking closer at the locations returned for simple.json, it seems that even though the line numbers now seem accurate, the actual positions for some of the tokens look very suspicious; for instance, the token STRING(open) for the "open" literal on line 2 only spans one character according to the locations. We could look up the actual positions in detail manually, but Dolmen’s TokenVisualizer class offers a more convenient way to check the token’s positions against the actual input. Its usage is very similar to Tokenizer but instead of simply displaying the tokens' information, it will generate a standalone HTML page showing the tokens superimposed onto the original input:

In addition to the simpler Tokenizer, TokenVisualizer requires a function to partition the tokens into several categories; tokens in the same category will be highlighted with the same colour. Here we simply use Token::getClass to sort the tokens by their actual type.

Compiling our Visualizer class and running it on simple.json will produce a simple.json.html file in the resources folder which looks like this:

The various tokens are conveniently displayed on top of the JSON input. Opening the file in a browser, we can hover the mouse over the various tokens to show the actual corresponding token and its recorded position:

In this instance, we can see the contents of the token itself are correct, in the sense that it is the string literal STRING(sdfk"j), but its position is reduced to the closing double-quote, as is the case for every string literal in the page. Tokens other than string literals seem alright. To understand the issue with string literals, remember that the lexeme start and end positions are updated each time a clause is applied. Now, consider how the lexer will analyze the first literal appearing in the file, "persons":

In order to fix this, it is sufficient to simply save the current start position after having matched the opening ", and restore it after the nested call to the string rule has been completed. That way, the situation in the lexer when the STRING(..) token is returned is as follows:

This tampering with positions is the main downside to using nested entries in a lexer description. It must be noted though that only nested calls returning a token require this: there is no issue with the nested call to escapeSequence or with the various continue main and continue string — which incidentally is the reason why Dolmen does not automatically save positions on the stack in nested calls. Moreover, the saving and restoring of a position can be performed in an elegant fashion by simply wrapping the nested call with the saveStart method exported by LexBuffer:

After having amended our lexer description as above, recompiled everything, and executed Visualizer again, the produced simple.json.html file now seems good all around:

We have now completed our lexical analyzer for JSON! In this tutorial, we have come a long way in terms of understanding the various features of a Dolmen lexer, how to best use them, and also how to overcome the potential obstacles that frequently arise. Here is our final lexer description:

It is 73 lines long, for a corresponding generated lexical analyzer of just above 1000 lines. It strictly conforms to the lexical conventions described in the JSON standard and handles all lexical errors explicitly. Looking back at the complete lexer description, it should be noted that there was nothing particularly difficult in the lexer we wrote: we took things step-by-step in a slow fashion, went astray at times for didactic purposes, detailed many aspects of working with Dolmen lexers, but the resulting lexer is short, arguably easy to read and understand, and performs as fast as a manually crafted lexical analyzer (see comparison with Gson below).
Whether you need lexical analysis for parsing a programming language or for character streams' pre-processing, have fun with Dolmen!

In this section, we describe the Dolmen syntax for regular expressions. Regular expressions appear as part of clauses in lexer entries, but auxiliary regular expressions can also be defined before the lexer entries:

The identifier on the left-hand side in a regular expression definition is the name which can be used to denote that regular expression in subsequent definitions as well as in clauses. The various regular expression constructs are summarized in this table, we detail each of them in the following.

The following table summarizes the different regular expression constructs in order of decreasing precedence, i.e. operators appearing first bind tighter than those appearing later down the table.

When a matching clause has been chosen by the lexing engine and the corresponding prefix of the input consumed, the associated semantic action is executed. The semantic action can be almost arbitrary Java code, but must respect a few principles.

We conclude this section on semantic actions with an exhaustive presentation of the fields and methods from LexBuffer which are available for use in semantic actions. One can always refer to the Javadoc associated to these members, either via the HTML pages or using your IDE when accessing the Dolmen runtime.

In this section, we discuss the meaning of the special regular expressions eof and _, which can sometimes be confusing, as well as the special orelse keyword which can be used to introduce a "catch-everything-else" clause in a lexer entry.

The lexical analyzer generator accepts some options which can be specified right at the top of a lexer description, with the following syntax:

A configuration option given as a key-value pair where the key identifies the option being set, and the value is a string literal. Unlike string literals in regular expressions, option values can be multi-line string literals.

In the following, we list the different configuration options available in lexer descriptions and document their effect.

The Dolmen runtime is an executable Java archive which can be used as a command-line tool to generate a lexical analyzer from a lexer description. Another way of using Dolmen is via the companion Eclipse plug-in; nonetheless, the command line is useful in a variety of scenarios like building scripts, Makefile, continuous integration, etc.

The command line interface can be invoked as follows:

where source is the name of the source lexer description. The -l option instructs Dolmen that the source is a lexer description and that a lexical analyzer should be generated. The -l flag can be omitted if the source file has the .jl extension. The other available command line options are detailed in the following table.

String options must follow the option name directly, e.g. -o mydir --class Foo instructs Dolmen to generate the class Foo.java in the mydir directory. Flag values in their short form can be grouped together. For instance, -lq instructs Dolmen to generate a lexical analyzer in quiet mode. Note that the --package/-p option is required: the generated class will be declared in the given package, and Dolmen does not support generating classes in the default package.

When trying to tokenize an input stream containing some sentences in a programming language or some data in an non-binary exchange format, it it usually apparent that the same characters may take on very different meanings depending on the context in which they appear.

For instance, special symbols like + or ; which represent operators or separators in one part of the input, need not be interpreted in any special manner when they appear inside a string literal, or inside some comment. Similarly, a keyword loses its special status should it belong to some comment or literal. Many languages even embed some other language in their syntax, in one form or another; consider for instance GCC’s preprocessor directives which are added on top of the C language, or more evidently the presence of Java actions inside Dolmen lexer descriptions. Even simple traits such as literals supporting a variety of escape sequences, or interpreted documentation comments such as Javadoc or Doxygen, can be thought of as "mini"-languages inside the main programming language.

The GCC preprocessor does not need to parse the C declarations between the preprocessor directives, no more than Dolmen actually needs to parse the semantic actions in Java, but both need to be able to care for the lexical conventions of the embedded language. Trying to write a lexical analyzer which can handle preprocessing directives, complex literals, structured comments and embedded snippets in some external language, without being able to effectively separate the different concerns raised by these different contexts, amounts to writing a single very complex entry rule whose clauses are able to recognize everything. Imagine clauses like these:

Let us first ignore how complex these regular expressions ought to be, and just discuss each clause’s purpose:

These examples basically sum up the main reasons why we want some form of contextual rules in lexer generation:

Lexer generators like ANTLR, JavaCC or JFlex allow contextualization by introducing a notion of state and letting users associate different lexing rules to different states, as well as switching states in semantic actions.

Dolmen does not follow a state-based approach but a function-based one, inspired by OCaml’s lexer generator ocamllex. In this approach, lexing rules are grouped in different lexer entries which each correspond to a different function in the generated lexer. Each entry can correspond to a different lexing context, and switching from one context to another is done by calling the adequate entry. A lexer description could contain different public entries which are designed to be called independently from an external class; it can also feature a main entry and other private entries which are only designed to be called from other entries' semantic actions. We call such rules which are accessed via calls nested in other rules' semantic actions nested rules.

We now demonstrate the use of nested rules on the examples of string literals and nested comments.

There is yet another possible advantage of using separate dedicated entries for parts of a language, and it is to factorize the rules for similar patterns which can be found in different contexts. For instance, the escape sequences available in string literals may be completely identical to the escape sequences in character literals, and having a dedicated entry for escape sequences can help factorize the two in a single set of rules.

When using nested rules, one must be aware of the couple of subtleties. First, it is possible to write a recursive entry, or a group of mutually recursive entries, in which case the user should be aware of the possibility of stack overflow. This is discussed below. Second, the internal state of the lexing buffer is updated when performing nested calls, and a number of the inherited methods available during semantic actions do depend on this internal state. For instance the following clause may observe the internal state being overwritten by the nested call inside:

If you find this situation surprising, consider that preventing it would require Dolmen to keep a stack of all relevant information across nested calls, which would be costly for the frequent cases when this information is not needed. When it indeed is needed, it is straightforward to just retrieve it before performing nested calls, as is the case in the example above for start and lex. The next section precisely covers how to deal with managing token positions across nested rules.

Coming soon

When using nested rules in a lexer description, one should be wary of nested calls being so deep that the lexical analysis could cause the Java program to excess its stack space, leading to a StackOverflowError being thrown. This is realistically only an issue with recursive calls, i.e. when some rule is called from its own semantic actions, either directly or indirectly through other rules.

For instance, consider a lexing rule main() with a clause for skipping Python comments (assuming for the sake of conciseness that the only line terminator is the line feed character):

This clause will consume the comment until (and including) the end of the line, and continues analyzing the input stream with the same rule by calling main() recursively. This recursive call to main() has the peculiarity of being a tail-call, i.e. that this call is the very final action taken in this function. As such, the call could be optimized so that the callee’s frame can reuse the space of the caller’s frame, a process dubbed tail-call optimization. Tail-call optimization is not limited to recursive tail-calls, but it is an important feature of compilers for functional languages where recursion is a key paradigm. Unfortunately, Java does not have tail-call optimization in general, so code like the clause above will use an amount of stack space that is proportional to the largest number of consecutive comment lines # …​ in the source. This can be arbitrary large, and it is not rare to find very long comment blocks in real code.

The standard countermeasure to prevent a recursive function from blowing up the stack in the absence of tail-call optimization is to rewrite the recursion as a regular loop. It is particularly straightforward when the function was tail-recursive in the first place. Dolmen provides this possibility by generating the code for every lexer entry inside a while loop labelled with the name of the rule itself. Therefore, the code for the entry main will follow this structure:

This layout allows using Java’s continue statement to continue executing the rule main without explicitly calling it recursively, namely by rewriting our clause for Python comments as follows:

As the semantic action will simply jump back to the beginning of the entry and start scanning again, this version of main uses a constant amount of stack (barring issues in other clauses) and can accomodate thousands of contiguous lines of comments.

The strategy of resorting to a continue statement has two limitations.

The following lexical conventions explain how the raw characters in a Dolmen lexer description are split into the lexical elements that are then used as terminals of the grammar.

Any input sequence which does not match any of the categories above will result in a lexical error.

We give the complete grammar for Dolmen lexer descriptions below. The terminals of the grammar are the lexical elements described infra, and keywords, punctuation and operator symbols are displayed in boldface. The main symbol is Lexer and we use traditional BNF syntax to present the grammar’s rules, augmented with the usual repetition operators ? (at most one), + (at least one) and * (any number of repetitions).

The following lexical conventions explain how the raw characters in a Dolmen parser description are split into the lexical elements that are then used as terminals of the grammar.

Any input sequence which does not match any of the categories above will result in a lexical error.

We give the complete grammar for Dolmen parser descriptions below. The terminals of the grammar are the lexical elements described infra, and keywords, punctuation and operator symbols are displayed in boldface. The main symbol is Parser and we use traditional BNF syntax to present the grammar’s rules, augmented with the usual repetition operators ? (at most one), + (at least one) and * (any number of repetitions).