On Jul 27, 2010, at 6:57 AM, Sebastian Fischer wrote:

Maybe I'll add it [noMatch] to the next version. I only need a better string representation ;)

Ha! It's already provided by character classes: ghci> accept (fromString "[]") "abc" False I'll add noMatch :: RegExp c noMatch = psym "[]" (const False) Sebastian -- Underestimating the novelty of the future is a time-honored tradition. (D.G.)

On Jul 27, 2010, at 7:09 AM, Sebastian Fischer wrote:

I'll add

noMatch :: RegExp c noMatch = psym "[]" (const False)

Oh, by the way, with noMatch, eps, alt and seq_ RegExp is itself a Semiring, but I'm not sure what that would do. -- Sjoerd Visscher http://w3future.com

On 27 jul 2010, at 09:30, Eugene Kirpichov wrote:

Perhaps this might mean that we can get incremental and parallel regexp matching by associating each character with a linear operator

This is exactly what is happening in the uu-parsinglib. Doaitse

(matrix) over this or related semiring, or something, and mixing that with two sigfpe's articles: http://blog.sigfpe.com/2008/11/approach-to-algorithm-parallelisation.html http://blog.sigfpe.com/2009/01/fast-incremental-regular-expression.html

2010/7/27 Sjoerd Visscher :

...

On Jul 27, 2010, at 7:09 AM, Sebastian Fischer wrote:

...

I'll add

noMatch :: RegExp c noMatch = psym "[]" (const False)

Oh, by the way, with noMatch, eps, alt and seq_ RegExp is itself a Semiring, but I'm not sure what that would do. -- Sjoerd Visscher http://w3future.com

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

-- Eugene Kirpichov Senior Software Engineer, Grid Dynamics http://www.griddynamics.com/ _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

On 28 jul 2010, at 13:17, Eugene Kirpichov wrote:

This is very interesting! Could you provide some more info? T.i. where to look in the source, or on the web?

see: file:///Users/doaitse/.cabal/share/doc/uu-parsinglib-2.4.2/html/index.html The README.hs module contains some further references. Doaitse

2010/7/28 S. Doaitse Swierstra :

...

On 27 jul 2010, at 09:30, Eugene Kirpichov wrote:

...

Perhaps this might mean that we can get incremental and parallel regexp matching by associating each character with a linear operator

This is exactly what is happening in the uu-parsinglib.

Doaitse

...

(matrix) over this or related semiring, or something, and mixing that with two sigfpe's articles: http://blog.sigfpe.com/2008/11/approach-to-algorithm-parallelisation.html http://blog.sigfpe.com/2009/01/fast-incremental-regular-expression.html

2010/7/27 Sjoerd Visscher :

...

On Jul 27, 2010, at 7:09 AM, Sebastian Fischer wrote:

...

I'll add

noMatch :: RegExp c noMatch = psym "[]" (const False)

Oh, by the way, with noMatch, eps, alt and seq_ RegExp is itself a Semiring, but I'm not sure what that would do. -- Sjoerd Visscher http://w3future.com

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

-- Eugene Kirpichov Senior Software Engineer, Grid Dynamics http://www.griddynamics.com/ _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

-- Eugene Kirpichov Senior Software Engineer, Grid Dynamics http://www.griddynamics.com/

On Jul 27, 2010, at 9:15 AM, Sjoerd Visscher wrote:

Oh, by the way, with noMatch, eps, alt and seq_ RegExp is itself a Semiring,

Yes, but it's hard to define an Eq instance for arbitrary regular expressions that reflects equivalence of regexps. There is currently only `instance Eq (RegExp Char)` which implements structural identity used for the QuickCheck tests.

but I'm not sure what that would do.

I think matching a regular expression against a word in the "regular expressions semiring" returns an unfolding of the original regular expression which matches exactly the given word. Sebastian -- Underestimating the novelty of the future is a time-honored tradition. (D.G.)

...

...

Oh, by the way, with noMatch, eps, alt and seq_ RegExp is itself a Semiring,

Yes, but it's hard to define an Eq instance for arbitrary regular expressions that reflects equivalence of regexps.

How hard is this exactly?

The standard algorithm to decide regexp equivalence transforms both expressions into DFAs and checks whether they are equivalent. DFAs can be checked for equivalence by forming their in-equivalence-product and checking whether the result DFA does not accept any input. See http://www.cs.rice.edu/~vardi/papers/sigcse06t1.pdf.gz This algorithm is quadratic in the sizes of the DFAs but they can themselves be exponentially large in the sizes of the regexps. I don't know whether there is more efficient way to decide regexp equivalence. Sebastian -- Underestimating the novelty of the future is a time-honored tradition. (D.G.)

Maybe I underestimated the utility of ^ and $. The definition seems intricate. I thought about adding a combinator for matching newline but now think that would lead to wrong start and end positions. For example the start position of the matching substring for ^a in "a\na" should be 2 not 1, right? Or is it 0 although there is no newline at the beginning?

The first "a" would match with indexes (0,1) and the second "a" would match with indexes (1,2).

Is there a page with examples that show how ^ and $ should behave exactly?

Without REG_NEWLINE the meanings are: . matches any single character (though note that handling of a zero byte is impossible for C style strings for a different reason). ^ is an assertion that instead of being AlwaysTrue (eps)or AlwaysFalse (noMatch) is true before any characters have been accepted and false afterward. $ is an assertion that is true only when there are no more characters to match and false before this. With REG_NEWLINE the meanings are: . matches any single character EXCEPT '\n' newline (ASCII 10, I think). ^ is true before any characters have been matched and true right after a newline has been matched, else false. ^ is true when there are no more characters to match and true if the next character to match is a newline, else false. Let 'a' and 'b' and 'c' be some complicated regular expressions that cannot accept a newline with REG_NEWLINE enabled: ^$ finds blank lines, the indexes between newlines or between a newline and the start or end of the text. ^a$ requires 'a' to exactly fill a line and the captured string has no newlines. A more complicated use, perhaps as part of a crazy parser: "(a(\n)?)(^|b)(c|$)" has 'a' much some text and perhaps the newline. If the newline was there then the ^ matches and b might be skipped, otherwise b must be used. The match ends with '(c|$)' is thus either starting the new line or trailing b. And (c|$) can avoid matching 'c' if the next character is a newline. Note that the regular expression "(^|[aA])" has a non-trivial "can_accept_empty" property: it can sometimes accept empty. And if you are recording parenthetical captures then "(^)?" is subtle. When ^ is true the (^) succeeds like () and when it is false it does not. This inserts a test into the pattern that can be checked later. And "((^$)|(^)|($))" is worse: it does not always succeed and which sub-pattern gets captured depends on the presence of one or two newlines. In "((^)|(^$))" it is impossible for (^$) to be used since the first (^) will always be favored by the POSIX rules. Similarly "(()|(^))" will never use (^). A small chunk of regex-tdfa sifts through the possible ways to accept 0 characters for each node in the parse-tree and keeps an ordered list of sets of assertions to check, and cleans outs those that are logically excluded. Slightly more useful anchors are added in Perl/PCRE:

ANCHORS AND SIMPLE ASSERTIONS \b word boundary \B not a word boundary ^ start of subject also after internal newline in multiline mode \A start of subject $ end of subject also before newline at end of subject also before internal newline in multiline mode \Z end of subject also before newline at end of subject \z end of subject \G first matching position in subject

I added \b \B as above, and added \` \' to be like \A and \Z above, and added \< and \> to be beginning and end of word assertions. With enough assertions and negated assertions one could level up to using a binary decision diagram to express when a sub-pattern can accept 0 characters. Ville's libtre gets this wrong:

Searched text: "searchme" Regex pattern: "((s^)|(s)|(^)|($)|(^.))*" Expected output: "(0,1)(0,1)(-1,-1)(0,1)(-1,-1)(-1,-1)(-1,-1)" Actual result : "(0,1)(0,1)(-1,-1)(0,1)(1,1)(1,1)(-1,-1)" And sometimes very wrong: Searched text: "searchme" Regex pattern: "s(^|())e" Expected output: "(0,2)(1,1)(1,1)" Actual result : "NOMATCH"

Cheers, Dr. Chris Kuklewicz

On Jul 29, 2010, at 12:47 AM, Benedikt Huber wrote:

Taking a quick look at the PyPy blog post on JIT code generation for regular expressions, I thought it would be fun to implement a generator using the excellent LLVM bindings for haskell.

Interesting. Would you mind elaborating on your code? Maybe even write a blog about how it works? Sebastian -- Underestimating the novelty of the future is a time-honored tradition. (D.G.)

Sebastian Fischer schrieb:

On Jul 29, 2010, at 12:47 AM, Benedikt Huber wrote:

...

Taking a quick look at the PyPy blog post on JIT code generation for regular expressions, I thought it would be fun to implement a generator using the excellent LLVM bindings for haskell.

Interesting. Would you mind elaborating on your code? Maybe even write a blog about how it works?

Hi, so the current implementation (a little bit cleaned up at http://github.com/visq/llvm-regexp ), works as follows: It generates an LLVM function which matches a bytestring against a given regular expression. The state of the 'automaton' consists of one bit for each leaf of the regexp AST, corresponding to the marks in the article's figure. It then generates straight-line code updating the state given an input character (generateRegexpCode and matchCharSet in Text.RegExp.LLVM). For example, for matching '.a' , the generated code looks like this in a simplified pseudo code notation:

... next ~ first character matched ... ch ~ input character next1 = bitmask[0] -- was '.' marked ? bitmask[0] = next -- mark '.' if initial next2 = bitmask[1] -- was 'a' marked ? bitmask[1] = ch == 'a' && next1 -- mark 'a' if '.' was marked

-- and input is 'a' At the end of the string, code is generated to check whether the automaton is in a final state (genFinalStateCheck). In the example above, this corresponds to

final = bitmask[1]

The rest is either LLVM boilerplate (regexMatcher) or adaptions from weighed-regexp. Additionally, I've adapted the Parser.y from weighted-regexp, but some things (e.g. character classes like \w) are not implemented. Generating one big basic block for the whole regular expressions does not work well when there are more than a few thousand nodes in the AST. Using functions for large regular expressions and loop for repititions would be one solution. The other problem is that the matcher only operates on Word8s at the moment. Trying it out (if you have llvm+haskell bindings) is also easy (do not cabal-easy):

$ git clone git@github.com:visq/llvm-regexp.git && cd llvm-regexp $ make $ ./Grep '.*spotlight.*' < /etc/passwd < Line 45 matches

cheers, benedikt