Scanner Generator. Regular Expressions to NFA, DFA, and Lexical Analyzer

Token Specification Instructions

Specify one token definition per line, with each in the form of TokenName:regex. TokenName is the name of the thing you're recognizing. regex is a regular expression that recognizes it.

Token Specification Example

identifier:L(L|D|_)*
int:D+
float:D*.D+|D+.D*
string:"([^"]|\\")*"
comment://[^\\n]*\n
comment:/\*(\*[^/]|[^*])*\*/
whitespace:\ |\n|\t

Token Specification Input

What is a Scanner Generator?

A scanner generator builds lexical analyzers from token definitions. Token definitions take this format: name:regex.

What is a Lexical Analyzer?

Lexical analyzers perform lexical analysis. Tautologies are tautologies. Lexers tokenize strings. Tokens get passed to parsers, and tokenization is the first major step in the process of compilation.

How to Generate Lexical Analyzers

Define tokens. Press button. Receive lexer.

Deep, right? Play around with the example.

What Manner of Sorcery Is This!?

This tool automatically generates a non-deterministic finite automata (NFA) for each given regex. It then attaches them all to a common start state via ε-edges (aka λ-edges). The subset construction algorithm is run on that composite NFA, resulting in a deterministic finite automaton (DFA). The DFA maps cleanly to a set of tables that drive a lexer. A generic driver uses those tables to separate and classify tokens in a string.

(No DFA minimization occurs.)

The ball of code you see on this page contains tables and a generic scanner written in Ruby. Prefer Python? Strip the @ signs off the table declarations and port the driver. Prefer C++? So manly!

Scanner Generator Notes & Nuances

Token names with multiple regex entries take the union of those regexes. E.g., int:D and int:DD on 2 lines ≡ specifying int:D|DD on one.
Character classes operate on all other existing edge labels. E.g., if your language only recognizes A, B, and C, then [^C] will become (A|B). Implication: "other" symbols won't satisfy the negation! You can get around this as follows:
- for each row corresponding to a state with a negated character class
- edit the rightmost entry so that instead of saying -1 (state) or 0 in action
- such that the number is the same as the non-"other", non-rejected columns for that row