--- /dev/null
+Daniel Ehrenberg
--- /dev/null
+! Copyright (C) 2009 Daniel Ehrenberg
+! See http://factorcode.org/license.txt for BSD license.
+USING: help.syntax help.markup regexp strings ;
+IN: regexp.combinators
+
+ABOUT: "regexp.combinators"
+
+ARTICLE: "regexp.combinators" "Regular expression combinators"
+"The " { $vocab-link "regexp.combinators" } " vocabulary defines combinators which can be used to build up regular expressions to match strings. This is in addition to the traditional syntax defined in the " { $vocab-link "regexp" } " vocabulary."
+{ $subsection <literal> }
+{ $subsection <nothing> }
+{ $subsection <or> }
+{ $subsection <and> }
+{ $subsection <not> }
+{ $subsection <sequence> }
+{ $subsection <zero-or-more> }
+{ $subsection <one-or-more> }
+{ $subsection <option> } ;
+
+HELP: <literal>
+{ $values { "string" string } { "regexp" regexp } }
+{ $description "Creates a regular expression which matches the given literal string." } ;
+
+HELP: <nothing>
+{ $values { "value" regexp } }
+{ $description "The empty regular language." } ;
+
+HELP: <or>
+{ $values { "regexps" "a sequence of regular expressions" } { "disjunction" regexp } }
+{ $description "Creates a new regular expression which matches the union of what elements of the sequence match." } ;
+
+HELP: <and>
+{ $values { "regexps" "a sequence of regular expressions" } { "conjunction" regexp } }
+{ $description "Creates a new regular expression which matches the intersection of what elements of the sequence match." } ;
+
+HELP: <sequence>
+{ $values { "regexps" "a sequence of regular expressions" } { "regexp" regexp } }
+{ $description "Creates a new regular expression which matches strings that match each element of the sequence in order." } ;
+
+HELP: <not>
+{ $values { "regexp" regexp } { "not-regexp" regexp } }
+{ $description "Creates a new regular expression which matches everything that the given regexp does not match." } ;
+
+HELP: <one-or-more>
+{ $values { "regexp" regexp } { "regexp+" regexp } }
+{ $description "Creates a new regular expression which matches one or more copies of the given regexp." } ;
+
+HELP: <option>
+{ $values { "regexp" regexp } { "regexp?" regexp } }
+{ $description "Creates a new regular expression which matches zero or one copies of the given regexp." } ;
+
+HELP: <zero-or-more>
+{ $values { "regexp" regexp } { "regexp*" regexp } }
+{ $description "Creates a new regular expression which matches zero or more copies of the given regexp." } ;
accessors fry ;
IN: regexp.combinators
-: <nothing> ( -- regexp )
- R/ (?~.*)/ ;
+<PRIVATE
+
+: modify-regexp ( regexp raw-quot tree-quot -- new-regexp )
+ [ '[ raw>> @ ] ]
+ [ '[ parse-tree>> @ ] ] bi* bi
+ make-regexp ; inline
+
+PRIVATE>
+
+CONSTANT: <nothing> R/ (?~.*)/
: <literal> ( string -- regexp )
- [ "\\Q" "\\E" surround ] [ <concatenation> ] bi make-regexp ;
+ [ "\\Q" "\\E" surround ] [ <concatenation> ] bi make-regexp ; foldable
: <or> ( regexps -- disjunction )
[ [ raw>> "(" ")" surround ] map "|" join ]
[ [ parse-tree>> ] map <alternation> ] bi
- make-regexp ;
+ make-regexp ; foldable
: <any-of> ( strings -- regexp )
- [ <literal> ] map <or> ;
+ [ <literal> ] map <or> ; foldable
: <sequence> ( regexps -- regexp )
[ [ raw>> ] map concat ]
[ [ parse-tree>> ] map <concatenation> ] bi
- make-regexp ;
-
-: modify-regexp ( regexp raw-quot tree-quot -- new-regexp )
- [ '[ raw>> @ ] ]
- [ '[ parse-tree>> @ ] ] bi* bi
- make-regexp ; inline
+ make-regexp ; foldable
: <not> ( regexp -- not-regexp )
[ "(?~" ")" surround ]
- [ <negation> ] modify-regexp ;
+ [ <negation> ] modify-regexp ; foldable
: <and> ( regexps -- conjunction )
- [ <not> ] map <or> <not> ;
+ [ <not> ] map <or> <not> ; foldable
: <zero-or-more> ( regexp -- regexp* )
[ "(" ")*" surround ]
- [ <star> ] modify-regexp ;
+ [ <star> ] modify-regexp ; foldable
: <one-or-more> ( regexp -- regexp+ )
[ "(" ")+" surround ]
- [ <plus> ] modify-regexp ;
+ [ <plus> ] modify-regexp ; foldable
: <option> ( regexp -- regexp? )
[ "(" ")?" surround ]
- [ <maybe> ] modify-regexp ;
+ [ <maybe> ] modify-regexp ; foldable
--- /dev/null
+Combinators for creating regular expressions
-! Copyright (C) 2008 Doug Coleman.
+! Copyright (C) 2008, 2009 Doug Coleman, Daniel Ehrenberg.
! See http://factorcode.org/license.txt for BSD license.
USING: kernel strings help.markup help.syntax ;
IN: regexp
+ABOUT: "regexp"
+
+ARTICLE: "regexp" "Regular expressions"
+"The " { $vocab-link "regexp" } " vocabulary provides word for creating and using regular expressions."
+{ $subsection { "regexp" "syntax" } }
+{ $subsection { "regexp" "construction" } }
+{ $vocab-subsection "regexp.combinators" "Regular expression combinators" }
+{ $subsection { "regexp" "operations" } }
+{ $subsection regexp }
+{ $subsection { "regexp" "theory" } } ;
+
+ARTICLE: { "regexp" "construction" } "Constructing regular expressions"
+"Words which are useful for creating regular expressions:"
+{ $subsection POSTPONE: R/ }
+{ $subsection <regexp> }
+{ $subsection <optioned-regexp> }
+{ $heading "See also" }
+{ $vocab-link "regexp.combinators" } ;
+
+ARTICLE: { "regexp" "syntax" } "Regular expression syntax"
+"Regexp syntax is largely compatible with Perl, Java and extended POSTFIX regexps, but not completely." $nl
+"A new addition is the inclusion of a negation operator, with the syntax " { $snippet "(?~foo)" } " to match everything that does not match " { $snippet "foo" } "." $nl
+"One missing feature is backreferences. This is because of a design decision to allow only regular expressions following the formal theory of regular languages. For more information, see " { $link { "regexp" "theory" } } ". You can create a new regular expression to match a particular string using " { $vocab-link "regexp.combinators" } " and group capture is available to extract parts of a regular expression match." $nl
+"A distinction from Perl is that " { $snippet "\\G" } ", which references the previous match, is not included. This is because that sequence is inherently stateful, and Factor regexps don't hold state." $nl
+"Additionally, none of the operations which embed code into a regexp are supported, as this would require the inclusion of the Factor parser and compiler in any application which wants to expose regexps to the user. None of the casing operations are included, for simplicity." ; ! Also describe syntax, from the beginning
+
+ARTICLE: { "regexp" "theory" } "The theory of regular expressions"
+"Far from being just a practical tool invented by Unix hackers, regular expressions were studied formally before computer programs were written to process them." $nl
+"A regular language is a set of strings that is matched by a regular expression, which is defined to have characters and the empty string, along with the operations concatenation, disjunction and Kleene star. Another way to define the class of regular languages is as the class of languages which can be recognized with constant space overhead, ie with a DFA. These two definitions are provably equivalent." $nl
+"One basic result in the theory of regular language is that the complement of a regular language is regular. In other words, for any regular expression, there exists another regular expression which matches exactly the strings that the first one doesn't match." $nl
+"This implies, by DeMorgan's law, that, if you have two regular languages, their intersection is also regular. That is, for any two regular expressions, there exists a regular expression which matches strings that match both inputs." $nl
+"Traditionally, regular expressions on computer support an additional operation: backreferences. For example, the Perl regexp " { $snippet "/(.*)$1/" } " matches a string repated twice. If a backreference refers to a string with a predetermined maximum length, then the resulting language is still regular." $nl
+"But, if not, the language is not regular. There is strong evidence that there is no efficient way to parse with backreferences in the general case. Perl uses a naive backtracking algorithm which has pathological behavior in some cases, taking exponential time to match even if backreferences aren't used. Additionally, expressions with backreferences don't have the properties with negation and intersection described above." $nl
+"The Factor regular expression engine was built with the design decision to support negation and intersection at the expense of backreferences. This lets us have a guaranteed linear-time matching algorithm. Systems like Ragel and Lex also use this algorithm, but in the Factor regular expression engine, all other features of regexps are still present." ;
+
+ARTICLE: { "regexp" "operations" } "Matching operations with regular expressions"
+{ $subsection match }
+{ $subsection matches? }
+{ $subsection match-at }
+{ $subsection match-range }
+{ $subsection first-match }
+{ $subsection re-cut }
+{ $subsection re-split }
+{ $subsection re-replace }
+{ $subsection next-match }
+{ $subsection all-matches }
+{ $subsection count-matches }
+{ $subsection re-replace } ;
+
HELP: <regexp>
{ $values { "string" string } { "regexp" regexp } }
-{ $description "Compiles a regular expression into a DFA and returns this object. Regular expressions only have to be compiled once and can then be used multiple times to match input strings." } ;
+{ $description "Creates a regular expression object, given a string in regular expression syntax. When it is first used for matching, a DFA is compiled, and this DFA is stored for reuse so it is only compiled once." } ;
+
+HELP: <optioned-regexp>
+{ $values { "string" string } { "options" string } { "regexp" regexp } }
+{ $description "Given a string in regular expression syntax, and a string of options, creates a regular expression object. When it is first used for matching, a DFA is compiled, and this DFA is stored for reuse so it is only compiled once." } ;
+
+HELP: R/
+{ $syntax "R/ foo.*|[a-zA-Z]bar/i" }
+{ $description "Literal syntax for a regular expression. When this syntax is used, the DFA is compiled at compile-time, rather than on first use." } ;
+
+HELP: regexp
+{ $class-description "The class of regular expressions. To construct these, see " { $link { "regexp" "construction" } } "." } ;
regexp.negation ;
IN: regexp
-TUPLE: regexp raw parse-tree options dfa ;
+TUPLE: regexp
+ { raw read-only }
+ { parse-tree read-only }
+ { options read-only }
+ dfa ;
: make-regexp ( string ast -- regexp )
- f f <options> f regexp boa ;
+ f f <options> f regexp boa ; foldable
+ ! Foldable because, when the dfa slot is set,
+ ! it'll be set to the same thing regardless of who sets it
: <optioned-regexp> ( string options -- regexp )
[ dup parse-regexp ] [ string>options ] bi*
<PRIVATE
-: get-dfa ( regexp -- dfa )
- dup dfa>> [ ] [
+: compile-regexp ( regexp -- regexp )
+ dup dfa>> [
dup
[ parse-tree>> ]
[ options>> ] bi
<with-options> ast>dfa
- [ >>dfa drop ] keep
- ] ?if ;
+ >>dfa
+ ] unless ;
: (match) ( string regexp -- dfa-traverser )
- get-dfa <dfa-traverser> do-match ; inline
+ compile-regexp dfa>> <dfa-traverser> do-match ; inline
PRIVATE>
[ [ index-from dup 1+ swap ] 2keep swapd subseq swap ] change-lexer-column
lexer get dup still-parsing-line?
[ (parse-token) ] [ drop f ] if
- <optioned-regexp> dup get-dfa drop parsed ;
+ <optioned-regexp> compile-regexp parsed ;
PRIVATE>
projects / factor.git / commitdiff