The S&D parser I was referring to was based on tracking FIRST sets, and provided a nice linear time parsing bound for (infinite) LL(1) grammars. (You can't really compute FOLLOW sets without knowing the grammar has a finite number of productions, but FIRST sets work perfectly well with infinite grammars.) By doing so you can transform parsing into more or less a series of map lookups for dispatch.
You need to carry a set of all characters that a parser will consume in the case of legal parses, and whether or not the parser accepts the empty parse. http://www.cse.chalmers.se/~rjmh/afp-arrows.pdf mentions this style of FIRST-set tracking parser as the original motivation for arrows. Of course, they didn't see fit to stop puttering around with parsers after 1998, so referring to "the S&D parser" is quite ambiguous! =) -Edward On Wed, Dec 21, 2016 at 4:00 AM, Henrik Nilsson < henrik.nils...@nottingham.ac.uk> wrote: > Hi Edward, > CC Others, > > On 12/21/2016 05:15 AM, Edward Kmett wrote: > >> Arrows haven't seen much love for a while. In part this is because many >> of the original applications for arrows have been shown to be perfectly >> suited to being handled by Applicatives. e.g. the Swiestra/Duponcheel >> parser that sort of kickstarted everything. >> > > Thanks for a very thorough reply. > > A quick side-remark: a parser library due to Sweistra (and maybe > Dupncheel, I can't remember) used an applicative structure a long time > before applicatives became apkicatives and even idioms. (I used a > variation of this library myself for the Freja compiler around 1995. > Freja was part of my PhD work and was close to what Haskell looked like at > the time.) > > I've never used arrows for parsing, or seen the need for arrows in that > context, but find arrows a very good fit for many EDSLs, including > stream-processing/FRP/Yampa of course, along with other circuit-like > abstractions, which I'd say were the original motivation for arrows. > Altenkirch have also used arrow-like notions in the context of quantum > computation. More recently for probabilistic programming and > Bayesian inference. Except then that the current hard-wired "pseudo- > product" in particular often gets in the way. Along with the fact > that there is no good support for constrained arrows (or monads). > > Best, > > /Henrik > > > > > > This message and any attachment are intended solely for the addressee > and may contain confidential information. If you have received this > message in error, please send it back to me, and immediately delete it. > Please do not use, copy or disclose the information contained in this > message or in any attachment. Any views or opinions expressed by the > author of this email do not necessarily reflect the views of the > University of Nottingham. > > This message has been checked for viruses but the contents of an > attachment may still contain software viruses which could damage your > computer system, you are advised to perform your own checks. Email > communications with the University of Nottingham may be monitored as > permitted by UK legislation. > >
_______________________________________________ ghc-devs mailing list ghc-devs@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
