I'm assuming that implementing a recursive descent parser ought to be
relatively simple in Haskell, given how recursive in nature functional
programming is. (Of course this also assumes that it's easy and efficient
in Haskell to have the input as a byte array, and it's efficient to read
said array byte by byte, without much copying things around.)

An interesting thing about this type of parsing, though, is how to parse
things like numeric literals (especially if they are not integers) or
UTF-8 encoded characters.

Most languages have some kind of standard functionality for parsing the
former. The only thing one has to do is to detect when such a literal is
appearing in the input, and then call said function. (The C/C++ standard
libraries in particular offer functions to parse numeric values that are
in ASCII format in-place, without having to first copy them anywhere,
which is a major help when writing such efficient parsers.)

Parsing UTF-8 encoded characters is a bit trickier, especially if the
language does not offer standard utility functions for that purpose.
The most efficient way of doing that is to, basically, write a small
state machine that reads the input byte by byte until a character not
in a valid sequence appears, and returns how many bytes the found name
consists of. (During this parsing, or afterwards, you can then do with
those characters whatever you need to.)

(Remember that we are writing an extremely *efficient* parser here. That
means no copying characters around and parsing them separately. They have
to be parsed in-place, where they appear in the byte array.)

-- 
                                                          - Warp

Post a reply to this message