lexmachine

lexmachine - Lexical Analysis Framework for Golang

By Tim Henderson

Copyright 2014-2017, All Rights Reserved. Made available for public use under the terms of a BSD 3-Clause license.

What?

lexmachine is a full lexical analysis framework for the Go programming language. It supports a restricted but usable set of regular expressions appropriate for writing lexers for complex programming languages. The framework also supports sub lexers and non-regular lexing through an "escape hatch" which allows the users to consume any number of further bytes after a match. So if you want to support nested C-style comments or other paired structures you can do so at the lexical analysis stage.

Subscribe to the mailing list to get announcement of major changes, new versions, and important patches.

Goal

lexmachine intends to be the best, fastest, and easiest to use lexical analysis system for Go.

1. Documentation Links
2. Narrative Documentation
3. Regular Expressions in lexmachine
4. History
5. Complete Example

Documentation

• Tutorial
• How It Works
• Narrative Documentation
• Using lexmachine with goyacc Required reading if you want to use lexmachine with the standard yacc implementation for Go (or its derivatives).
• 

What is in Box

lexmachine includes the following components

1. A parser for restricted set of regular expressions.
2. A abstract syntax tree (AST) for regular expressions.
3. A backpatching code generator which compiles the AST to (NFA) machine code.
4. Both DFA (Deterministic Finite Automata) and a NFA (Non-deterministic Finite Automata) simulation based lexical analysis engines. Lexical analysis engines work in a slightly different way from a normal regular expression engine as they tokenize a stream rather than matching one string.
5. Match objects which include start and end column and line numbers of the lexemes as well as their associate token name.
6. A declarative "DSL" for specifying the lexers.
7. An "escape hatch" which allows one to match non-regular tokens by consuming any number of further bytes after the match.

Narrative Documentation

lexmachine splits strings into substrings and categorizes each substring. In compiler design, the substrings are referred to as lexemes and the categories are referred to as token types or just tokens. The categories are defined by patterns which are specified using regular expressions. The process of splitting up a string is sometimes called tokenization, lexical analysis, or lexing.

Defining a Lexer

The set of patterns (regular expressions) used to tokenize (split up and categorize) is called a lexer. Lexer's are first class objects in lexmachine. They can be defined once and re-used over and over-again to tokenize multiple strings. After the lexer has been defined it will be compiled (either explicitly or implicitly) into either a Non-deterministic Finite Automaton (NFA) or Deterministic Finite Automaton (DFA). The automaton is then used (and re-used) to tokenize strings.

Creating a new Lexer

lexer := lexmachine.NewLexer()

Adding a pattern

Let's pretend we want a lexer which only recognizes one category: strings which match the word "wild" capitalized or not (eg. Wild, wild, WILD, ...). That expression is denoted: [Ww][Ii][Ll][Dd]. Patterns are added using the Add function:

lexer.Add([]byte(`[Ww][Ii][Ll][Dd]`), func(s *lexmachine.Scanner, m *machines.Match) (interface{}, error) {
	return 0, nil
})

Add takes two arguments: the pattern and a call back function called a lexing action. The action allows you, the programmer, to transform the low level machines.Match object (from github.com/lexmachine/machines) into a object meaningful for your program. As an example, let's define a few token types, and a token object. Then we will construct appropriate action functions.

Tokens := []string{
	"WILD",
	"SPACE",
	"BANG",
}
TokenIds := make(map[string]int)
for i, tok := range Tokens {
	TokenIds[tok] = i
}

Now that we have defined a set of three tokens (WILD, SPACE, BANG), let's create a token object:

type Token struct {
	TokenType int
	Lexeme string
	Match *machines.Match
}

Now let's make a helper function which takes a Match and a token type and creates a Token.

func NewToken(tokenType string, m *machines.Match) *Token {
	return &Token{
		TokenType: TokenIds[tokenType], // defined above
		Lexeme: string(m.Bytes),
		Match: m,
	}
}

Now we write an action for the previous pattern

lexer.Add([]byte(`[Ww][Ii][Ll][Dd]`), func(s *lexmachine.Scanner, m *machines.Match) (interface{}, error) {
	return NewToken("WILD", m), nil
})

Writing the action functions can get tedious, a good idea is to create a helper function which produces these action functions:

func token(tokenType string) func(*lexmachine.Scanner, *machines.Match) (interface{}, error) {
	return func(s *lexmachine.Scanner, m *machines.Match) (interface{}, error) {
		return NewToken(tokenType, m), nil
	}
}

Then adding patterns for our 3 tokens is concise:

lexer.Add([]byte(`[Ww][Ii][Ll][Dd]`), token("WILD"))
lexer.Add([]byte(` `), token("SPACE"))
lexer.Add([]byte(`!`), token("BANG"))

Built-in Token Type

Many programs use similar representations for tokens. lexmachine provides a completely optional Token object you can use in lieu of writing your own.

type Token struct {
    Type        int
    Value       interface{}
    Lexeme      []byte
    TC          int
    StartLine   int
    StartColumn int
    EndLine     int
    EndColumn   int
}

Here is an example for constructing a lexer Action which turns a machines.Match struct into a token using the scanners Token helper function.

func token(name string, tokenIds map[string]int) lex.Action {
    return func(s *lex.Scanner, m *machines.Match) (interface{}, error) {
        return s.Token(tokenIds[name], string(m.Bytes), m), nil
    }
}

Adding Multiple Patterns

When constructing a lexer for a complex computer language often tokens have patterns which overlap -- multiple patterns could match the same strings. To address this problem lexical analysis engines follow 2 rules when choosing which pattern to match:

1. Pick the pattern which matches the longest prefix of unmatched text.
2. Break ties by picking the pattern which appears earlier in the user supplied list.

For example, let's pretend we are writing a lexer for Python. Python has a bunch of keywords in it such as class and def. However, it also has identifiers which match the pattern [A-Za-z_][A-Za-z0-9_]*. That pattern also matches the keywords, if we were to define the lexer as:

lexer.Add([]byte(`[A-Za-z_][A-Za-z0-9_]*`), token("ID"))
lexer.Add([]byte(`class`), token("CLASS"))
lexer.Add([]byte(`def`), token("DEF"))

Then, the keywords class and def would never be found because the ID token would take precedence. The correct way to solve this problem is by putting the keywords first:

lexer.Add([]byte(`class`), token("CLASS"))
lexer.Add([]byte(`def`), token("DEF"))
lexer.Add([]byte(`[A-Za-z_][A-Za-z0-9_]*`), token("ID"))

Skipping Patterns

Sometimes it is advantageous to not emit tokens for certain patterns and to instead skip them. Commonly this occurs for whitespace and comments. To skip a pattern simply have the action return nil, nil:

lexer.Add(
	[]byte("( |\t|\n)"),
	func(scan *Scanner, match *machines.Match) (interface{}, error) {
		// skip white space
		return nil, nil
	},
)
lexer.Add(
	[]byte("//[^\n]*\n"),
	func(scan *Scanner, match *machines.Match) (interface{}, error) {
		// skip white space
		return nil, nil
	},
)

Compiling the Lexer

lexmachine uses the theory of finite state machines to efficiently tokenize text. So what is a finite state machine? A finite state machine is a mathematical construct which is made up of a set of states, with a labeled starting state, and accepting states. There is a transition function which moves from one state to another state based on an input character. In general, in lexing there are two usual types of state machines used: Non-deterministic and Deterministic.

Before a lexer (like the ones described above) can be used it must be compiled into either a Non-deterministic Finite Automaton (NFA) or a Deterministic Finite Automaton (DFA). The difference between the two (from a practical perspective) is construction time and match efficiency.

Construction time is the amount of time it takes to turn a set of regular expressions into a state machine (also called a finite state automaton). For an NFA it is O(r) which r is the length of the regular expression. However, for DFA it could be as bad as O(2^r) but in practical terms it is rarely worse than O(r^3). The DFA's in lexmachine are also automatically minimized which reduces the amount of memory they consume which takes O(r*log(log(r))) steps.

However, construction time is an upfront cost. If your program is tokenizing multiple strings it is less important than match efficiency. Let's say a string has length n. An NFA can tokenize such a string in O(n*r) steps while a DFA can tokenize the string in O(n). For larger languages r becomes a significant overhead.

By default, lexmachine uses a DFA. To explicitly invoke compilation call Compile:

err := lexer.Compile()
if err != nil {
	// handle err
}

To explicitly compile a DFA (in case of changes to the default behavior of Compile):

err := lexer.CompileDFA()
if err != nil {
	// handle err
}

To explicitly compile a NFA:

err := lexer.CompileNFA()
if err != nil {
	// handle err
}

Tokenizing a String

To tokenize (lex) a string construct a Scanner object using the lexer. This will compile the lexer if it has not already been compiled.

scanner, err := lexer.Scanner([]byte("some text to lex"))
if err != nil {
	// handle err
}

The scanner object is an iterator which yields the next token (or error) by calling the Next() method:

for tok, err, eos := scanner.Next(); !eos; tok, err, eos = scanner.Next() {
	if ui, is := err.(*machines.UnconsumedInput); is {
		// skip the error via:
		// scanner.TC = ui.FailTC
		//
		return err
	} else if err != nil {
		return err
	}
	fmt.Println(tok)
}

Let's break down that first line:

for tok, err, eos := scanner.Next();

The Next() method returns three things, the token (tok) if there is one, an error (err) if there is one, and eos which is a boolean which indicates if the End Of String (EOS) has been reached.

; !eos;

Iteration proceeds until the EOS has been reached.

; tok, err, eos = scanner.Next() {

The update block calls Next() again to get the next token. In each iteration of the loop the first thing a client must do is check for an error.

	if err != nil {
		return err
	}

This prevents an infinite loop on an unexpected character or other bad token. To skip bad tokens check to see if the err is a *machines.UnconsumedInput object and reset the scanners text counter (scanner.TC) to point to the end of the failed token.

	if ui, is := err.(*machines.UnconsumedInput); is {
		scanner.TC = ui.FailTC
		continue
	}

Finally, a client can make use of the token produced by the scanner (if there was no error:

	fmt.Println(tok)

Dealing with Non-regular Tokens

lexmachine like most lexical analysis frameworks primarily deals with patterns which are represented by regular expressions. However, sometimes a language has a token which is "non-regular." A pattern is non-regular if there is no regular expression (or finite automata) which can express the pattern. For instance, if you wanted to define a pattern which matches only consecutive balanced parentheses: (), ()()(), ((()()))()(), ... You would quickly find there is no regular expression which can express this language. The reason is simple: finite automata cannot "count" or keep track of how many opening parentheses it has seen.

This problem arises in many programming languages when dealing with nested "c-style" comments. Supporting the nesting means solving the "balanced parenthesis" problem. Luckily, lexmachine provides an "escape-hatch" to deal with these situations in the Action functions. All actions receive a pointer to the Scanner. The scanner (as discussed above) has a public modifiable field called TC which stands for text counter. Any action can modify the text counter to point at the desired position it would like the scanner to resume scanning from.

An example of using this feature for tokenizing nested "c-style" comments is below:

lexer.Add(
	[]byte("/\\*"),
	func(scan *Scanner, match *machines.Match) (interface{}, error) {
		for tc := scan.TC; tc < len(scan.Text); tc++ {
			if scan.Text[tc] == '\\' {
				// the next character is skipped
				tc++
			} else if scan.Text[tc] == '*' && tc+1 < len(scan.Text) {
				if scan.Text[tc+1] == '/' {
					// set the text counter to point to after the
					// end of the comment. This will cause the
					// scanner to resume after the comment instead
					// of picking up in the middle.
					scan.TC = tc + 2
					// don't return a token to skip the comment
					return nil, nil
				}
			}
		}
		return nil,
			fmt.Errorf("unclosed comment starting at %d, (%d, %d)",
				match.TC, match.StartLine, match.StartColumn)
	},
)

Regular Expressions

Lexmachine (like most lexical analysis frameworks) uses Regular Expressions to specify the patterns to match when splitting the string up into categorized tokens. For a more advanced introduction to regular expressions engines see Russ Cox's articles. To learn more about how regular expressions are used to tokenize string take a look at Alex Aiken's video lectures on the subject. Finally, Aho et al. give a through treatment of the subject in the Dragon Book Chapter 3.

A regular expression is a pattern which matches a set of strings. It is made up of characters such as a or b, characters with special meanings (such as . which matches any character), and operators. The regular expression abc matches exactly one string abc.

Character Expressions

In lexmachine most characters (eg. a, b or #) represent themselves. Some have special meanings (as detailed below in operators). However, all characters can be represented by prefixing the character with a \.

Any Character

. matches any character.

Special Characters

1. \ use \\ to match
2. newline use \n to match
3. carriage return use \r to match
4. tab use \t to match
5. . use \. to match
6. operators: {|, +, *, ?, (, ), [, ], ^} prefix with a \ to match.

Character Classes

Sometimes it is advantages to match a variety of characters. For instance, if you want to ignore capitalization for the work Capitol you could write the expression [Cc]apitol which would match both Capitol or capitol. There are two forms of character ranges:

1. [abcd] matches all the letters inside the [] (eg. that pattern matches the strings a, b, c, d).
2. [a-d] matches the range of characters between the character before the dash (a) and the character after the dash (d) (eg. that pattern matches the strings a, b, c, d).

These two forms may be combined:

For instance, [a-zA-Z123] matches the strings {a, b, ..., z, A, B, ... Z, 1, 2, 3}

Inverted Character Classes

Sometimes it is easier to specify the characters you don't want to match than the characters you do. For instance, you want to match any character but a lower case one. This can be achieved using an inverted class: [^a-z]. An inverted class is specified by putting a ^ just after the opening bracket.

Built-in Character Classes

1. \d = [0-9] (the digit class)
2. \D = [^0-9] (the not a digit class)
3. \s = [ \t\n\r\f] (the space class). where \f is a form feed (note: \f is not a special sequence in lexmachine, if you want to specify the form feed character (ascii 0x0c) use []byte{12}.
4. \S = [^ \t\n\r\f] (the not a space class)
5. \w = [0-9a-zA-Z_] (the letter class)
6. \W = [^0-9a-zA-Z_] (the not a letter class)

Operators

1. The pipe operator | indicates alternative choices. For instance the expression a|b matches either the string a or the string b but not ab or ba or the empty string.

2. The parenthesis operator () groups a subexpression together. For instance the expression a(b|c)d matches abd or acd but not abcd.

3. The star operator * indicates the "starred" subexpression should match zero or more times. For instance, a* matches the empty string, a, aa, aaa and so on.

4. The plus operator + indicates the "plussed" subexpression should match one or more times. For instance, a+ matches a, aa, aaa and so on.

5. The maybe operator ? indicates the "questioned" subexpression should match zero or one times. For instance, a? matches the empty string and a.

Grammar

The canonical grammar is found in the handwritten recursive descent parser. This section should be considered documentation not specification.

Note: e stands for the empty string

Regex -> Alternation

Alternation -> AtomicOps Alternation'

Alternation' -> `|` AtomicOps Alternation'
              | e

AtomicOps -> AtomicOp AtomicOps
           | e

AtomicOp -> Atomic
          | Atomic Ops

Ops -> Op Ops
     | e

Op -> `+`
    | `*`
    | `?`

Atomic -> Char
        | Group

Group -> `(` Alternation `)`

Char -> CHAR
      | CharClass

CharClass -> `[` Range `]`
           | `[` `^` Range `]`

Range -> CharClassItem Range'

Range' -> CharClassItem Range'
        | e

CharClassItem -> BYTE
              -> BYTE `-` BYTE

CHAR -> matches any character except '|', '+', '*', '?', '(', ')', '[', ']', '^'
        unless escaped. Additionally '.' is returned as the wildcard character
        which matches any character. Built-in character classes are also handled
        here.

BYTE -> matches any byte

History

This library was started when I was teaching EECS 337 Compiler Design and Implementation at Case Western Reserve University in Fall of 2014. It wrote two compilers one was "hidden" from the students as the language implemented was their project language. The other was tcel which was written initially as an example of how to do type checking. That compiler was later expanded to explain AST interpretation, intermediate code generation, and x86 code generation.

Complete Example

Using the Lexer

package main

import (
    "fmt"
    "log"
)

import (
	"github.com/timtadh/lexmachine"
	"github.com/timtadh/lexmachine/machines"
)

func main() {
    s, err := Lexer.Scanner([]byte(`digraph {
  rankdir=LR;
  a [label="a" shape=box];
  c [<label>=<<u>C</u>>];
  b [label="bb"];
  a -> c;
  c -> b;
  d -> c;
  b -> a;
  b -> e;
  e -> f;
}`))
    if err != nil {
        log.Fatal(err)
    }
    fmt.Println("Type    | Lexeme     | Position")
    fmt.Println("--------+------------+------------")
    for tok, err, eof := s.Next(); !eof; tok, err, eof = s.Next() {
        if ui, is := err.(*machines.UnconsumedInput); is{
            // to skip bad token do:
            // s.TC = ui.FailTC
            log.Fatal(err) // however, we will just fail the program
        } else if err != nil {
            log.Fatal(err)
        }
        token := tok.(*lexmachine.Token)
        fmt.Printf("%-7v | %-10v | %v:%v-%v:%v\n",
            Tokens[token.Type],
            string(token.Lexeme),
            token.StartLine,
            token.StartColumn,
            token.EndLine,
            token.EndColumn)
    }
}

Lexer Definition

package main

import (
	"fmt"
	"strings"
)

import (
	"github.com/timtadh/lexmachine"
	"github.com/timtadh/lexmachine/machines"
)

var Literals []string       // The tokens representing literal strings
var Keywords []string       // The keyword tokens
var Tokens []string         // All of the tokens (including literals and keywords)
var TokenIds map[string]int // A map from the token names to their int ids
var Lexer *lexmachine.Lexer // The lexer object. Use this to construct a Scanner

// Called at package initialization. Creates the lexer and populates token lists.
func init() {
	initTokens()
	var err error
	Lexer, err = initLexer()
	if err != nil {
		panic(err)
	}
}

func initTokens() {
	Literals = []string{
		"[",
		"]",
		"{",
		"}",
		"=",
		",",
		";",
		":",
		"->",
		"--",
	}
	Keywords = []string{
		"NODE",
		"EDGE",
		"GRAPH",
		"DIGRAPH",
		"SUBGRAPH",
		"STRICT",
	}
	Tokens = []string{
		"COMMENT",
		"ID",
	}
	Tokens = append(Tokens, Keywords...)
	Tokens = append(Tokens, Literals...)
	TokenIds = make(map[string]int)
	for i, tok := range Tokens {
		TokenIds[tok] = i
	}
}

// Creates the lexer object and compiles the NFA.
func initLexer() (*lexmachine.Lexer, error) {
	lexer := lexmachine.NewLexer()

	for _, lit := range Literals {
		r := "\\" + strings.Join(strings.Split(lit, ""), "\\")
		lexer.Add([]byte(r), token(lit))
	}
	for _, name := range Keywords {
		lexer.Add([]byte(strings.ToLower(name)), token(name))
	}

	lexer.Add([]byte(`//[^\n]*\n?`), token("COMMENT"))
	lexer.Add([]byte(`/\*([^*]|\r|\n|(\*+([^*/]|\r|\n)))*\*+/`), token("COMMENT"))
	lexer.Add([]byte(`([a-z]|[A-Z]|[0-9]|_)+`), token("ID"))
	lexer.Add([]byte(`[0-9]*\.[0-9]+`), token("ID"))
	lexer.Add([]byte(`"([^\\"]|(\\.))*"`),
		func(scan *lexmachine.Scanner, match *machines.Match) (interface{}, error) {
			x, _ := token("ID")(scan, match)
			t := x.(*lexmachine.Token)
			v := t.Value.(string)
			t.Value = v[1 : len(v)-1]
			return t, nil
		})
	lexer.Add([]byte("( |\t|\n|\r)+"), skip)
	lexer.Add([]byte(`\<`),
		func(scan *lexmachine.Scanner, match *machines.Match) (interface{}, error) {
			str := make([]byte, 0, 10)
			str = append(str, match.Bytes...)
			brackets := 1
			match.EndLine = match.StartLine
			match.EndColumn = match.StartColumn
			for tc := scan.TC; tc < len(scan.Text); tc++ {
				str = append(str, scan.Text[tc])
				match.EndColumn += 1
				if scan.Text[tc] == '\n' {
					match.EndLine += 1
				}
				if scan.Text[tc] == '<' {
					brackets += 1
				} else if scan.Text[tc] == '>' {
					brackets -= 1
				}
				if brackets == 0 {
					match.TC = scan.TC
					scan.TC = tc + 1
					match.Bytes = str
					x, _ := token("ID")(scan, match)
					t := x.(*lexmachine.Token)
					v := t.Value.(string)
					t.Value = v[1 : len(v)-1]
					return t, nil
				}
			}
			return nil,
				fmt.Errorf("unclosed HTML literal starting at %d, (%d, %d)",
					match.TC, match.StartLine, match.StartColumn)
		},
	)

	err := lexer.Compile()
	if err != nil {
		return nil, err
	}
	return lexer, nil
}

// a lexmachine.Action function which skips the match.
func skip(*lexmachine.Scanner, *machines.Match) (interface{}, error) {
	return nil, nil
}

// a lexmachine.Action function with constructs a Token of the given token type by
// the token type's name.
func token(name string) lexmachine.Action {
	return func(s *lexmachine.Scanner, m *machines.Match) (interface{}, error) {
		return s.Token(TokenIds[name], string(m.Bytes), m), nil
	}
}