crystal-dfa
crystal-dfa
A Regex syntax parser, and Thompson NFA to DFA transformer and matcher based on Russ Cox's article "Regular Expression Matching Can Be Simple And Fast" with parse tree simplifications from Guangming Xings paper Minimized Thompson NFA - Chapter 3.
It is used in Scanner the new lexer implementation of the Crystal Language Toolkit to improve the lexing performance.
Currently implemented Regex syntax:
- literals and concatenation
ab
- quantifiers
*
,+
,?
and alternation|
- groupings
a(ab)
(no capturing) - quantifiers
{2,4}
,{2}
,{4,}
- character classes
[^a-bK-Lxyß]
- special character classes
.
,\s
,\t
,\r
,\d
,\w
,\W
,\D
Performance beats PCRE
$ crystal run --release benchmark/compare.cr
building "(?-imsx:(?:x+x+)+y)" with Regex (PCRE)
0.000000 0.000000 0.000000 ( 0.000111)
building "(?-imsx:(?:x+x+)+y)" with RegExp (own impl
0.000000 0.000000 0.000000 ( 0.000205)
matching "xxxxxxxxxxxxxy" a first time with Regex (PCRE)
0.000000 0.000000 0.000000 ( 0.000035)
rx1.match(string) # => #<Regex::MatchData "xxxxxxxxxxxxxy">
matching "xxxxxxxxxxxxxy" a first time with RegExp (own impl
0.000000 0.000000 0.000000 ( 0.000027)
rx2.match(string) # => #<DFA::DFA::MatchData:0x55adf4afcd00
@match="xxxxxxxxxxxxxy">
Regex (PCRE) matching : xxxxxxxxxxxxxy 2.25M (443.56ns) (± 8.61%) 3.92× slower
RegExp (own impl) matching : xxxxxxxxxxxxxy 8.83M (113.24ns) (±11.62%) fastest
Installation
Add this to your application's shard.yml
:
dependencies:
crystal-dfa:
github: ziprandom/crystal-dfa
Usage
require "crystal-dfa"
rex = DFA::RegExp.new "(crystal|ruby) (just )?looks like (crystal|ruby)!"
rex.match("crystal just looks like ruby!") # => #<DFA::DFA::MatchData:0x556758a89d00
# @match=
# "crystal just looks like ruby!">
rex.match("ruby looks like crystal!") # => #<DFA::DFA::MatchData:0x556758a89aa0
# @match=
# "ruby looks like crystal!">
rex.match("python just looks like crystal!") # => nil
rex = DFA::RegExp.new "crystal"
rex.match("crystal-lang !!", true, false) # => #<DFA::DFA::MatchData:0x556758a8e3a0
# @match=
# "crystal">
Contributing
- Fork it ( https://github.com/ziprandom/crystal-dfa/fork )
- Create your feature branch (git checkout -b my-new-feature)
- Commit your changes (git commit -am 'Add some feature')
- Push to the branch (git push origin my-new-feature)
- Create a new Pull Request
Contributors
- ziprandom - creator, maintainer
Repository
crystal-dfa
Owner
Statistic
- 19
- 3
- 4
- 1
- 0
- 7 months ago
- April 13, 2017
License
MIT License
Links
Synced at
Fri, 22 Nov 2024 03:30:24 GMT
Languages