makadev/re2dfa

Library for Regular Expression to DFA transformation.

0.1.0 2020-11-15 16:56 UTC

Requires

• php: >=7.4.0
• makadev/bitset: ^1.0

Requires (Dev)

• phpstan/phpstan: ^0.12.51
• phpunit/phpcov: ^8.2
• phpunit/phpunit: ^9.4
• psalm/plugin-phpunit: ^0.13.0
• vimeo/psalm: ^4.0

MIT

• Matthias Karbe

README

php-re2dfa

PHP Library for Regular Expression to DFA transformation.

What it is

A Library for transforming Regular Expressions (RegEx) into Nondeterministic Finitie Automaton with ɛ-transitions (ɛ-NFA) and Deterministic Finitie Automaton (DFA) with named final states for the purpose of analyzing and further use the constructed DFA / ɛ-NFA for example in visualizations or to build tokenizer.

What it's not

• PCRE compatible
• a fast Regular Expression matching alternative

Features

• RegEx to ɛ-NFA transformation
• direct ɛ-NFA construction
• transform multiple ɛ-NFA with separate finitie states into a DFA
• ɛ-NFA simulation
• DFA simulation

planned Features

• DFA minimization (f.e. Moore's partition algorithm)
• DFA and ɛ-NFA output (f.e. dot, json, text)

internal TODOs

• add usage examples for the features
• optimizations here and there
• replace stack oriented RegExParser with AST
  • character classes like whitespace (like :whitespace:)
  • repetition expression (like RE{min,max}, RE{exact})