Fauton

An ecosystem of packages to work with automaton and parsers (dfa/nfa/e-nfa/regex/cfg/pda)

• Features
• Packages
• Algorithm Sources
• Credits
• Contributors

Features

1. Full typescript support
2. Easy to use api
3. High test coverage
4. Supports both node and browser environment (except a few packages)
5. Well documented with examples

Packages

• @fauton/cfg Github NPM: A package to work with cfg
• @fauton/fa Github NPM: A package to work with finite automata
• @fauton/regex Github : A package to work with regex validation and parsing
• @fauton/testing Github NPM : A package to test your automaton (regex/dfa/nfa/e-nfa/cfg)
• @fauton/language Github : A package to generate language from a given set of tokens

Algorithm Sources

Wikipedia sources for all the algorithms used in the package

1. Thompson-McNaughton-Yamada algorithm for converting regex to e-nfa
2. Hopcroft algorithm for dfa-minimization
3. Rabin–Scott powerset construction algorithm to convert nfa to dfa
4. Shunting-Yard algorithm to convert regex string from infix to postfix
5. Chomsky Normal Form Algorithm to make parsing a string easier
6. Cocke–Younger–Kasami Parsing algorithm using a CFG
7. Earley Parser algorithm for parsing strings that belong to a given context-free language
8. LL parser a top-down parser for a restricted context-free language

Credits

Big thanks to all these wonderful repos.

1. Orban Regular expression engine that uses the Thompson-McNaughton-Yamada algorithm implemented in Python.
2. CFGChecker A program that cross references a context free grammar with a given language.
3. CFG Epsilon Removal A detailed article on how to remove epsilon from CFG
4. python-formal-langs-practicum-automata-cfg Automata, Context-free-grammar classes (implementation of CYK algorithm, converting grammar to Chomsky normal form, Thompson algo for building automaton from regex, etc.)
5. earley-parser-js Tiny JavaScript implementation of context-free languages parser - Earley parser (including generation of the parsing-forest).
6. probabilistic-earley-parser-javascript An efficient implementation of a probabilistic Context Free Grammar parser in Javascript
7. https://github.com/caleb531/automata A Python library for simulating finite automata, pushdown automata, and Turing machines

Contributors

1. Safwan Shaheer github Author, Maintainer

Feel free to submit a pull request or open a new issue, contributions are more than welcome.