An ecosystem of packages to work with automaton and parsers (dfa/nfa/e-nfa/regex/cfg/pda)
- Full typescript support
- Easy to use api
- High test coverage
- Supports both node and browser environment (except a few packages)
- Well documented with examples
@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
Wikipedia sources for all the algorithms used in the package
- Thompson-McNaughton-Yamada algorithm for converting regex to e-nfa
- Hopcroft algorithm for dfa-minimization
- Rabin–Scott powerset construction algorithm to convert nfa to dfa
- Shunting-Yard algorithm to convert regex string from infix to postfix
- Chomsky Normal Form Algorithm to make parsing a string easier
- Cocke–Younger–Kasami Parsing algorithm using a CFG
- Earley Parser algorithm for parsing strings that belong to a given context-free language
- LL parser a top-down parser for a restricted context-free language
Big thanks to all these wonderful repos.
- Orban Regular expression engine that uses the Thompson-McNaughton-Yamada algorithm implemented in Python.
- CFGChecker A program that cross references a context free grammar with a given language.
- CFG Epsilon Removal A detailed article on how to remove epsilon from CFG
- 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.)
- earley-parser-js Tiny JavaScript implementation of context-free languages parser - Earley parser (including generation of the parsing-forest).
- probabilistic-earley-parser-javascript An efficient implementation of a probabilistic Context Free Grammar parser in Javascript
- https://github.com/caleb531/automata A Python library for simulating finite automata, pushdown automata, and Turing machines
- Safwan Shaheer github Author, Maintainer
Feel free to submit a pull request or open a new issue, contributions are more than welcome.