Lexer State Machines

Some eye-candy: PDF files showing the Larceny lexer's NFA (generated from nfa.dot) and Minimized DFA (generated from mdfa.dot).

The GraphViz project provides the dot program that generated the visualizations. I used the command line tool installed with Mac OS X port of dot, as follows

  % dot -O -T pdf nfa.dot
  % dot -O -T pdf mdfa.dot

Of course, I did not write those dot files by hand; they were generated by combining Larceny's lexical specification and LexGen with some Scheme glue code.

  > (define larceny-nfa (time (regular->nfa scheme_terminals)))
  Words allocated: 262080
  Words reclaimed: 0
  Elapsed time...: 5 ms (User: 4 ms; System: 1 ms)
  Elapsed GC time: 1 ms (CPU: 1 in 1 collections.)
  
  > (define larceny-dfa (time (nfa->dfa larceny-nfa)))
  Words allocated: 47960284
  Words reclaimed: 0
  Elapsed time...: 16889 ms (User: 16502 ms; System: 267 ms)
  Elapsed GC time: 583 ms (CPU: 560 in 183 collections.)
  
  > (define larceny-mindfa (time (dfa->minimal larceny-dfa)))
  Words allocated: 11007294
  Words reclaimed: 0
  Elapsed time...: 62096 ms (User: 61156 ms; System: 250 ms)
  Elapsed GC time: 40 ms (CPU: 38 in 42 collections.)
  
  > (define larceny-nfa.dot (time (nfa->dot larceny-nfa)))
  Words allocated: 17555810
  Words reclaimed: 0
  Elapsed time...: 177 ms (User: 171 ms; System: 5 ms)
  Elapsed GC time: 12 ms (CPU: 9 in 67 collections.)
  
  > (define larceny-mindfa.dot (time (nfa->dot larceny-mindfa)))
  Words allocated: 1833782
  Words reclaimed: 0
  Elapsed time...: 37 ms (User: 31 ms; System: 1 ms)
  Elapsed GC time: 2 ms (CPU: 2 in 7 collections.)
  
  > (call-with-output-file "nfa.dot" (lambda (p) (write-dot "nfa" larceny-nfa.dot p)))
  
  > (call-with-output-file "mdfa.dot" (lambda (p) (write-dot "mindfa" larceny-mindfa.dot p)))

I have not managed to run the .dot file for the DFA itself through dot; dot complains about syntax errors on many of the lines. It is probably silly to even try to make a rendering of the DFA anyway; its .dot file is 66 megabytes (the other two .dot files are less than 500 kilobytes).

But I may later try using a simpler lexical specification to generate the triumvirate of (NFA, DFA, min DFA), to convince myself that my code is generating accurate dot graphs of the state machines.