GitPlanet

Cheap and reliable Node.js hosting starts at $3/month, and $1/month static HTML hosting

Created with love in Canada, visit hostnodejs.com today

Feel like to post an Ad? Learn Details
All Projects → Devorein → fauton

Devorein / fauton

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

Programming Languages

typescript
32286 projects
javascript
184084 projects - #8 most used programming language

Labels

parserregexcnfnfaautomatondfacfgcyk-algorithmfinite-automatanfa-to-dfa-conversionepsilon-nfall1-parserlr1-parser

Projects that are alternatives of or similar to fauton

Regex
An implementation of regular expressions for Rust. This implementation uses finite automata and guarantees linear time matching on all inputs.
Stars: ✭ 2,125 (+5802.78%)
Mutual labels:  regex, nfa, automaton, dfa
visual-automata
Visual Automata is a Python 3 library built as a wrapper for the Automata library to add more visualization features.
Stars: ✭ 55 (+52.78%)
Mutual labels:  nfa, automaton, dfa
dregex
Dregex is a JVM library that implements a regular expression engine using deterministic finite automata (DFA). It supports some Perl-style features and yet retains linear matching time, and also offers set operations.
Stars: ✭ 37 (+2.78%)
Mutual labels:  regex, dfa
chomsky-normal-form
Convert a Context Free Grammar (CFG) to Chomsky Normal Form (CNF)
Stars: ✭ 17 (-52.78%)
Mutual labels:  cnf, cfg
librxvm
non-backtracking NFA-based regular expression library, for C and Python
Stars: ✭ 57 (+58.33%)
Mutual labels:  regex, nfa
compiler-design-lab
These are my programs for compiler design lab work in my sixth semester
Stars: ✭ 47 (+30.56%)
Mutual labels:  regex, nfa
compiler lab
Some toy labs for compiler course
Stars: ✭ 49 (+36.11%)
Mutual labels:  nfa, dfa
ocaml-re-nfa
OCaml code to construct an NFA from a regular expression
Stars: ✭ 44 (+22.22%)
Mutual labels:  regex, nfa
js-diacritic-regex
Creates the inverse of transliterated string to a regex. What? Basically, diacritic insensitiveness
Stars: ✭ 20 (-44.44%)
Mutual labels:  regex
greptile
Fast grep implementation in python, with recursive search and replace
Stars: ✭ 17 (-52.78%)
Mutual labels:  regex
Socially
Socially is a textView which is able to create separate clickable views according to your requirements.
Stars: ✭ 28 (-22.22%)
Mutual labels:  regex
bosphorus
Bosphorus, ANF simplifier and solver, and ANF-to-CNF converter
Stars: ✭ 45 (+25%)
Mutual labels:  cnf
VBA-JSON-parser
Backus-Naur Form JSON Parser based on RegEx for VBA
Stars: ✭ 75 (+108.33%)
Mutual labels:  regex
git-search-replace
A utility on top of Git for project-wide search-and-replace that includes filenames too
Stars: ✭ 42 (+16.67%)
Mutual labels:  regex
AALpy
An Active Automata Learning Library Written in Python
Stars: ✭ 60 (+66.67%)
Mutual labels:  dfa
clausejs
Write contract once. Get data & function validators & conformers, an accurate & readable project contract, auto-generated API documentation, generative test coverage, plus more. A tool that enables a more predictable workflow for developing your JavaScript projects.
Stars: ✭ 29 (-19.44%)
Mutual labels:  regex
java-core
Collections of solutions for micro-tasks created while building modules as part of project. Also has very fun stuffs :)
Stars: ✭ 35 (-2.78%)
Mutual labels:  regex
APK-Downloader
Download latest version of android apps and games from Google Play.
Stars: ✭ 54 (+50%)
Mutual labels:  regex
renamer
Command line tool to rename multiple files at once.
Stars: ✭ 79 (+119.44%)
Mutual labels:  regex
globrex
Glob to regular expression with support for extended globs.
Stars: ✭ 52 (+44.44%)
Mutual labels:  regex
View All Similar Projects ➔

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.

Note that the project description data, including the texts, logos, images, and/or trademarks, for each open source project belongs to its rightful owner. If you wish to add or remove any projects, please contact us at [email protected].