Blog Posts from December 10, 2007 (page 1 of 1)

Practical Parsing in F#

I’m interested in parsing because I’m interested in Domain Specific Languages. F# is pretty good for internal DSLs, but internal DSLs are obviously limited by the syntax of the host language. If you want complete control over the language, you’ve got to build your own parser.

The defacto standard for parser development is Yet Another Compiler Compiler, or yacc. There’s a version of yacc for .NET as well as one specifically for F#. However, I’m not a fan of yacc. Yacc parsers are specified using context-free grammar (aka CFG). But CFG’s can be ambiguous – actually, it’s nearly impossible to build an unambiguous CFG. Personally, I’m a big fan of Parsing Expression Grammars (or PEGs) which among other advantages makes it impossible to develop ambiguous grammars. Furthermore, PEGs don’t require a separate lexical analyzer like lex, so I think they’re more suitable for building modular compilers.

Since I like PEGs and F# so much, I developed a parser for the PEG grammar from the original PEG whitepaper using F#. The grammar is much simpler than a language like C#, but with twenty nine grammar productions it’s certainly not trivial. The F# implementation is fairly straightforward backtracking recursive decent parser, which makes it easy to understand even if you’re not a parser guru. It’s also small – around 400 lines of code including comments. But I think the code illustrates both the general value of Functional Programming as well as the specific value of F#. Here’s how the series is shaping up (though this is subject to change):

I was originally planning to post the code for the parser itself with this post. However, i find that I’m revising the code as I write the articles in this series, so I’m going to hold off for now. If you’re really desperate, drop me a line and I’ll see what I can do.

Update: Almost forgot, if you’re going to follow along at home, I’m using the latest version of F#, v1.9.3.7. Note, the F# Downloads page on the MS Research is woefully out of date, so go to the MS Research Downloads page. Currently, it’s the most recent release. It snaps into VS 2005 and 2008 plus has command line tools. If you’re an VS Express user, Douglas Stockwell explained how to roll your own F# Express.

Much Later Update: The code is now available on my Skydrive.

Morning Coffee 129

  • Short coffee this morning, as I’m home with a tweaked ankle.
  • I started playing Indigo Prophecy over the weekend. It’s an original Xbox game, released as part of the new Xbox Originals program. It has a good metacritic score (84), though apparently it wasn’t much of a retail success. I’m enjoying it, though it’s not very challenging. It’s more an interactive movie than a game. Good story, though.
  • The ASP.NET MVC preview dropped today, Scott Guthrie has the details. Scott Hanselman has a 40 minute how-to video and Phil Haack has severalarticles up already.
  • Speaking of ASP.NET MVC and Scott Guthrie, he’s got another post in his series on ASP.NET MVC. This time, he’s covering how to handle form input / POST data.
  • Erik Meijer has posted some of his thoughts on Volta. He’s one of the guys behind Volta, so it’s worth a good look. (via Dare Obasanjo)
  • Late Addition – the ASP.NET Extensions is more than just the MVC stuff. It also includes AJAX improvements, Silverlight support, ADO.NET Data Services and ASP.NET Dynamic Data Support. Data Services (formerly Astoria) let’s you easily expose your database via RESTful services. I think Dynamic Data Support used to be code named Jasper. It’s a “rich scaffolding framework” for ASP.NET. I assume that’s to compete w/ Ruby on Rails.