[PRL] Fwd: [Programming] First Seminar of the Semester, Wednesday @ 4:15

[David Van Horn]

-------- Original Message --------
Subject: 	[Programming] First Seminar of the Semester, Wednesday @ 4:15
Date: 	Mon, 12 Sep 2011 14:57:48 -0400
From: 	Gregory Malecha <gmalecha at eecs.harvard.edu>
Reply-To: 	gmalecha at cs.harvard.edu
To: 	programming at eecs.harvard.edu



Hello everyone,

The programming language seminar will be starting this week, in MD 323
at 4:15 (immediately after cs252r). This week David is going to talk
about his ICFP paper on parsing with derivatives (abstract below). I'm
also looking for other people who want to share their interesting work.
Either the talks nor the work need to be completely polished and it is a
good way to get feedback and interesting points of view. If you'd like
to talk at one, please send me an email, at the moment the entire
semester is available.


Matthew Might, David Darais, and Daniel Spiewak. /Functional Pearl:
Parsing with Derivatives/.

Abstract

We present a functional approach to parsing unrestricted context-free
grammars based on Brzozowski's derivative of regular expressions.  If we
consider context-free grammars as recursive regular expressions,
Brzozowski's
equational theory extends without modification to context-free grammars (and
it generalizes to parser combinators).  The supporting actors in
this story are three concepts familiar to functional programmers---laziness,
memoization and fixed points; these allow Brzozowski's original equations to
be transliterated into purely functional code in about 30 lines spread over
three functions.

Yet, this almost impossibly brief implementation has a drawback: its
performance is sour---in both theory and practice.  The culprit?  Each
derivative can doublehe size of a grammar, and with it, the cost of
the next derivative.

Fortunately, much of the new structure inflicted by the derivative is either
dead on arrival, or it dies after the very next derivative.  To
eliminate it,
we once again exploit laziness and memoization to transliterate an
equational
theory that prunes such debris into working code. Thanks to
this compaction, parsing times become reasonable in practice.

We equip the functional programmer with two equational theories that, when
combined, make for an abbreviated understanding and implementation of a
system for parsing context-free languages.
-- 
gregory malecha
http://www.people.fas.harvard.edu/~gmalecha/

-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: Attached Message Part
Url: http://lists.ccs.neu.edu/pipermail/prl/attachments/20110912/33667082/attachment.txt