Skip to content

An implementation of regular expressions for Python that uses a finite state automaton(正则引擎的Python实现,包括从NFA到DFA和DFA的最小化)

Notifications You must be signed in to change notification settings

dejavudwh/Regex

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

37 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Regex

This is a regular expression engine implemented in Python that uses NFA and DFA and optionally minimizes DFA sets.

Begin to use

from regex import Regex


st = 'THISISREGEXTEST'
pattern = '([A-Z]*|[0-9]+)'
regex = Regex(st, pattern)
result = regex.match()
log(result)

Regex build parameter

(input_string, pattern_string, mode=1, minimize=True)
  • mode

    Finite state automata used

    mode = 1 - NFA

    mode = 2 - DFA

  • minimize

    Whether to minimize if using DFA

see sample.py for details.

BNF

group ::= ("(" expr ")")*
expr ::= factor_conn ("|" factor_conn)*
factor_conn ::= factor | factor factor*
factor ::= (term | term ("*" | "+" | "?"))*
term ::= char | "[" char "-" char "]" | .

Implementation of the

Implemented all the basic syntax

Tokens = {
    '.': Token.ANY,
    '^': Token.AT_BOL,
    '$': Token.AT_EOL,
    ']': Token.CCL_END,
    '[': Token.CCL_START,
    '}': Token.CLOSE_CURLY,
    ')': Token.CLOSE_PAREN,
    '*': Token.CLOSURE,
    '-': Token.DASH,
    '{': Token.OPEN_CURLY,
    '(': Token.OPEN_PAREN,
    '?': Token.OPTIONAL,
    '|': Token.OR,
    '+': Token.PLUS_CLOSE,
}

in lex.token

Code structure

For the sake of simplicity, the code style of this implementation is not very good.

  • lex

    Lexical analysis of regular expressions
  • nfa

    Definition of an NFA node the construction of an NFA
  • dfa

    Definition of an DFA node the construction of an DFA
  • parse

    About parsing DFA or NFA based on input

About

An implementation of regular expressions for Python that uses a finite state automaton(正则引擎的Python实现,包括从NFA到DFA和DFA的最小化)

Topics

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages