Nicklas Nidhögg

Automata theory, maximal-munch lexing and the exact behaviour of real tokenizers.

I work on where lexers and tokenizers can cut text. A lexer that scans its input in parallel needs cuts it can trust: single bytes where every occurrence begins a token, exactly or once comments and whitespace are discarded, and short windows that fix where a token began when no single byte does. The same certificates choose where a failed scan resumes, so that error recovery lands where every repair of the input places a token boundary. Certification is decided from the token set alone, for maximal-munch scanners and for every tokenizer whose segmentations a finite automaton can verify, and it supplies the anchors for cutting, editing and auditing. For byte-pair encoding I decide, for every dictionary, how far text prepended on the left can change a tokenization, and when that ripple has no bound. Each result comes with the C++ that implements it and exhaustive executions that test its limits.

ORCID arXiv Google Scholar GitHub

Papers

Software