Regex/CTFG in F#/.net

I would like to know how to do regex, or context free grammers in F#.

I have some experience with F#, (I've never seen/used Active patterns, (it was explictly left out of the course i did for timecontraints)) and I've done alittle regex in python, and also regex and grammers from a descrete math开发者_如何学JAVAematics point of view.

I've don a bit of looking around I've done, I get kinda stumped. the MSDN documentation for regex isn't so clear to me me.

I was a little disapointed to find that

match str with
|a + "." + b + "." + c -> Some(a,b,c)
|[] -> None

didn't work.

I suspect that an effect like this can be achieved with active patterns

EDIT to clarify: I would like to know how to do regex Or Context Free Grammers Or both

The MSDN documentation for regex isn't so clear to me me.

For the simple case of whether a string matches a regex, it couldn't be easier:

open System.Text.RegularExpressions
let r = Regex("^a*$")
r.IsMatch("a")
> val it : bool = true
r.IsMatch("b")
> val it : bool = false

Replace a* with the desired regex. Note that you need ^ and $ around the regex for a full match.

I was a little disapointed to find that this didn't work.

match str with
| a + "." + b + "." + c -> Some(a,b,c)
| [] -> None

F# patterns are for matching and binding parts of nested tree-like data structures (algebraic data types) not for strings and regular languages, which is why this doesn't work.

I suspect that an effect like this can be achieved with active patterns

Yes, you can go a long way towards achieving this effect using active patterns. Chris Smith has an article showing the details (as first posted by Brian).

http://blogs.msdn.com/b/chrsmith/archive/2008/02/22/regular-expressions-via-active-patterns.aspx

I would like to know how to do regex Or Context Free Grammers Or both ... I've done alittle regex in python, and also regex and grammers from a descrete mathematics point of view.

For matching patterns on strings, the builtin .Net regular expressions as shown above are usually good enough. However, beware that, despite the name, they are not strictly regular since they can represent a bigger class of languages. As a consequence, they might not always have the time/space complexity that you might expect if you've encoutered them in a theoretical setting. (This is also true for Perl/Python/etc.)

As for CFGs, that's an entirely different question. Fsyacc (togther with the lexer fslex) from the F# PowerPack is the standard F# LALR parser generator which will match a useful subclass of CFGs. Alternatively, you could try the FParsec parser combinator library from http://www.quanttec.com/fparsec/.

I'd suggest this excerpt from Expert F#:

Using Regular expressions and formatting

It covers a lot of ground - using perl style operators, using f# pattern matching, active patterns etc.

This guy wrote a tutorial on how to build a complete regular expression parser in F#:

http://stevehorsfield.wordpress.com/2009/08/04/f-a-complete-regular-expression-processor/

http://stevehorsfield.wordpress.com/2009/07/25/f-building-a-regular-expression-pattern-parser/

Is this what you're looking for?

http://blogs.msdn.com/b/chrsmith/archive/2008/02/22/regular-expressions-via-active-patterns.aspx

I never truly understood regular expressions until a read the first couple chapters of Modern Compiler Implementation in ML: whereas typical programming resources on the subject are more oriented towards the practice of using regular expressions, the author of this books lays out the mathematically foundation behind the subject (and for me at least, that is always crucial for my understanding of any complex topic, and something woefully missing from most treatments in general in the larger programming community).

As a day to day practical reference, this site has been useful.

As for the .NET framework Regex API, it's robust but a bit of a beast and awkward to work with since it hasn't been updated much since .NET 1.1 (no generics, and goes a bit overboard on inheritance hierarchies). I think you'll just need to play around with it a bit to get a feel for it (and the F# Interactive is ideal for such experimentation).