scanning and parsing short strings

scanning and parsing short strings

[Christian Lindig]

[sorry - no french version]

Dear Caml enthusiasts,

many applications rely on protocols which they must parse. This can
be either done ad hoc using regular expressions or scanner/parser
generated by Camllex/yacc. Which method is advisable when the scanned
items are relative short strings (< 100 Bytes)? In general I would
prefer to use Camllex/yacc specifications in order not distribute the
different parsers over the whole application. On the other hand start-up
time of the scanner/lexer may be too high when used for small strings
(Lexing.from_string). Any advice?

The background of my question: I like to implement a CGI library. There
are many headers that are passed to a CGI application that need to
be parsed. I already took a look at the MMM code which uses a mixed
approach. 

Christian

--                     
 Christian Lindig        
 lindig@ips.cs.tu-bs.de  
                         

Re: scanning and parsing short strings

[Francois Rouaix]

> many applications rely on protocols which they must parse. This can
> be either done ad hoc using regular expressions or scanner/parser
> generated by Camllex/yacc. Which method is advisable when the scanned
> items are relative short strings (< 100 Bytes)?
[...]
> The background of my question: I like to implement a CGI library.
> I already took a look at the MMM code which uses a mixed approach. 

I can't give performance comparisons, but here are some personal appreciations
on the various solutions.
* regular expressions dont scale
It's probably all right for CGI headers because these are small one-line
inputs, and their syntax is essentially trivial, but then it's also error
prone (you rarely write the correct pattern at once). Then, libstr also 
requires building custom binaries which make bigger applications (at least
with the bytecode compiler).
* camllex is easy. Besides lexical analysis, it can also handle simple
parsing strategies, such as recursive descent
* yacc (and therefore camlyacc) is a pain, and will always be. Moreover,
error handling is not that easy.

Also, streams and parsers are a possible alternative to camllex/yacc, although
here you will loose some speed.

--f