JSPM

  • ESM via JSPM
  • ES Module Entrypoint
  • Export Map
  • Keywords
  • License
  • Repository URL
  • TypeScript Types
  • README
  • Created
  • Published
  • Downloads 1487094
  • Score
    100M100P100Q198254F
  • License MIT

A library for finite automata and regular expressions in the context of JS RegExp

Package Exports

  • refa

This package does not declare an exports field, so the exports above have been automatically detected and optimized by JSPM instead. If any package subpath is missing, it is recommended to post an issue to the original package (refa) to support the "exports" field. If that is not possible, create a JSPM override to customize the exports field for this package.

Readme

Regular Expressions and Finite Automata (refa)

Actions Status npm

A library for regular expressions (RE) and finite automata (FA) in the context of Javascript RegExp.

About

This is a general library for DFA, NFA, and REs of formal regular languages.

It also supports additional methods to easily convert from JS RegExp to the internal RE AST and vice versa.

At this point in time, the library is still in development and partially incomplete!

Features

  • Conversions

    • RE to NFA (lookarounds are not implemented yet)
    • NFA to DFA and DFA to NFA
    • NFA to RE and DFA to RE

  • DFA and NFA operations

    • Construction from other FA, the intersection of two FA, or a finite set of words
    • Print internal representation in a human-readable form
    • Test whether a word is accepted
    • Test whether the language of an FA is the empty set/a finite set
    • Accept all prefixes of a language

  • DFA specific operations

    • Minimization
    • Complement
    • Structural equality

  • NFA specific operations

    • Union and Concatenation with other FA
    • Quantification
    • Reverse
    • Accept all suffixes of a language

  • Javascript RegExp

    • RegExp to RE and RE to RegExp (non-trivial backreferences are not supported)

Limitations

This library will never be able to support some modern features of regex engines such as backreferences and recursion because these features, generally, cannot be be represented by a DFA or NFA.