/fauton

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

Primary LanguageTypeScriptMIT LicenseMIT


Fauton logo

Fauton

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

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.