Mar 3rd 2016

Taming the Lexer

Sven EfftingeSven Efftinge

Language parsing is traditionally split into two phases: Lexing and Parsing. In this post I want to talk about how a Lexer generally works and what you can do if it doesn’t.

What a lexer does

The duty of a lexer is to turn a sequence of single characters into a sequence of so called tokens. A token is a chunk of characters associated with a certain token-type. Most programming languages define individual lexer rules for things like names (identifiers), string literals, numbers, whitespace and comments. The latter two are usually not passed to the parser, or at least sent in a special way, so that we don’t have to deal with whitespace and comments explicitly afterwards.

Within the parser rules we can then use the more coarse grained token types to define the grammar of a language. It’s possible to parse without a lexer (or scanner), which is then called scanner-less parsing. The main reason for having a lexer doing the tokenizing first is performance.

How a lexer works

There are a lot of similarities in how a lexer and a parser work; in Xtext and ANTLR the lexer and parser rules share most of the concepts and only have a few differences. The most important difference is that a lexer is usually free of context.

Most lexers work by following these two principles:

  1. Be greedy That is use the lexer rule that consumes the most characters
  2. First Rule Wins If there are two or more rules matching the same amount of characters, the first one wins.

Example

In Xtext, the lexer consists of all the lexer rules plus the keywords used in the parser rules. Because we want to give keywords a higher precedence, they are ‘copied’ before the defined lexer rules. Let’s consider the following two rules:

HelloWorld : 'Hello' ID ;

terminal ID: ('a'..'z' | 'A'..'Z' | '_') ('a'..'z' | 'A'..'Z' | '_' | '0'..'9')* ;

The input

Hello Xtext will be lexed into two tokens, ‘Hello’ and ID (if we ignore the whitespace). Although ‘Hello’ would be a perfect match for ID, it is also a match for the ‘hello’ keyword, which is always preferred (declared before any lexer rule). So principle 2 applies here.

For the input

HelloXtext we end up with one token ID. In this case principle 1 applies, as the sequence ‘HelloXtext’ is longer than what the keyword rule could have matched.

Problems with the ANTLR 3 Lexer

Xtext generates an ANTLR 3 based lexer, which also follows the two principles above. Unfortunately it only guesses on what rule will possibly match the longest sequence using a statemachine that does look ahead. Based on that outcome, it decides on one of the lexer rules. The problem is that the statemachine doesn’t do the full lexing and sometimes is wrong.

Example:

TheNumber : 'the' 'number' 'is' number=NUMBER '.';

terminal NUMBER : '0'..'9'+ ('.' '0'..'9'+)?;

With this grammar it should be possible to write the number is 24. and the number is 23.00.

but not

the number is 23.. The lexer generated by ANTLR 3 will however not work as expected, but will always try to consume any dots following numbers as part of the NUMBER rule. As a result the first and the last text will have errors.

Ways to solve this issue

Most of the time, you can get around this kind of problems by using parser rules instead. E.g. you could write the following:

TheNumber : 'the' 'number' 'is' number=Decimal '.';
Decimal : NUMBER ->('.' NUMBER)?;
terminal NUMBER : '0'..'9'+;

But sometimes it is more involved and you really need (or want) to solve this on the lexer level. In that case you can use a different implementation. Both ANTLR 4 and JFlex will work fine with the above example. I just recently replaced the lexer in a customer’s project which is actually open-source. If you want to see how this can be done, you can find the code here.

Of course I will be happy to do that for you, as well. Happy Lexing! :)

About the Author

Sven Efftinge

Sven Efftinge

Sven loves finding sweet spots in product development. Always keeping an eye on pragmatism and the real benefit for the end user, he has proven to be a creative source for many sucessful technologies. He is a co-founder of TypeFox, co-lead of Eclipse Theia and product manager of Gitpod.

Read more about this topic

read the article

Mar 18th 2024

Article

Irina Artemeva

Run fast, debug easy: Exploring the synergy of Langium and LLVM

Ensuring your language is both executable and debuggable is an interesting challenge. Let's discover how to achieve this using Langium and LLVM.

read the article
watch the videoOpen Video

Mar 7th 2024

Video

Benjamin F. Wilson

Getting started with Langium – Part 7 "Generating Drawing Commands"

In this tutorial Ben will demonstrate how we can generate drawing commands from a MiniLogo program, building on the generator work we’ve already established in the prior tutorial.

watch the video
read the article

Mar 5th 2024

Article

Benjamin F. Wilson

Langium 3.0 is Released!

Langium 3.0 is released! This release brings us new improvements & features, like reduced bundle size, ESM support, and more.

read the article
LOAD MORE