Mirror of https://github.com/nekodata/tdfa
|
|
||
|---|---|---|
| src | Initial commit | |
| gnat.adc | Initial commit | |
| license.txt | Initial commit | |
| paper_notes.md | Add notes on [1] | |
| readme.txt | Add notes on [1] | |
| tdfa.gpr | Initial commit | |
Neko Data Systems Type-III Library: Program 2614-XLP. This program was produced as a prototype implementation of the algorithms described in [1], as a basis for a future implementation of a lexer generator using TDFA. It is written in Ada 2022 to allow for quick prototyping. It is released as part of the Nekodata Type-III library, a catalogue of permissively licensed programs. The intended audience includes anyone who: wants to write their own TDFA implementation; wants to understand or experiment with parts of the algorithms described in [1]; or needs a more readable reference than the C++ re2c source code. Note that this program is not guaranteed to be correct and may have bugs. If you are writing your own implementation you should compare your results with re2c, but you can still use this source code as a reference. It is also not optimized for determinization performance and may not be suited for use in lexer generators in its current form, but may still be useful as a base. If you find any bugs, you can report them as an issue on this repository. You can also send bug reports or questions to <lisa@felidae.bam.moe>. We do not accept pull requests or code contributions at this time. Most algorithms are implemented as a fairly literal translation of the pseudocode in [1]. TDFA minimization uses a modified version of Hopcroft's algorithm, as given by Xu [2]. Some other algorithms (e.g. CFG construction) are custom. To build the program, install a recent version of GNAT and gprbuild, and run `gprbuild -P tdfa.gpr`. You can add -j<number of processors> to speed it up. When you run the program, it will create a bunch of .dot files. These are graphs, in GraphViz DOT format. To format them, install GraphViz and use a command like `dot -Tpng -Gdpi=300 -o dfa.png dfa.dot`. If you want to see what the program is actually doing, tweak the Debug_* flags in the various *.ads files. `paper_notes.md` contains some notes on [1], clearing up some confusing or potentially incorrect parts of the paper. Currently implemented: • TNFA construction • TNFA simulation • TDFA determinization • Fallback operations • Register optimizations (liveness analysis, dead code elimination, interference analysis, register allocation) • TDFA minimization (based on [2]) • Fixed tags • Character classes • Single-valued tags • Leftmost greedy disambiguation Not implemented (and not currently planned): • Multi-valued tags • POSIX disambiguation References used during development: [1] Borsotti, Angelo; Trafimovich, Ulya. (2022). "A closer look at TDFA" [2] Xu, Yingjie (2009). "Describing an n log n algorithm for minimizing states in deterministic finite automaton" [3] The re2c source code (https://github.com/skvadrik/re2c) Copyright (c) 2026, Lisa Felidae trading as Neko Data Systems. "Neko Data Systems" or "Nekodata" is a fictitious business name or trade name of Lisa Felidae, A/K/A @kohuept, @kittybwained. No generative AI was used in the production of this software.