Re: [Caml-list] Thread safe Str

[Gerd Stolpmann <info@gerd-stolpmann.de>]

On Die, 2005-01-11 at 09:06, skaller wrote:
> On Tue, 2005-01-11 at 18:03, Chris King wrote:
> > On 11 Jan 2005 14:54:30 +1100, skaller <skaller@users.sourceforge.net> wrote:
> > > If you want captures use the proper tool, namely a parser,
> > > [...]
> > > If some technology is to be integrated, please use the right technology
> > > and integrate Ocamllex.

Which is already done. There is a camlp4 extension allowing one to
define ocamllex-like scanners as part of normal modules (pa_ocamllex).
It is even part of the O'caml distribution, in camlp4/unmaintained.
Well, there is also a maintained and internationalised version called
ulex by the same author.

> > Why write a lexer and all its necessary event handlers when one can
> > just write "s/foo(.*)bar/bar\1foo/g"?  

This is a typical example where one would prefer regexp engines over
lex-type scanners. Just because of simplicity.

> Just compare a real example from the Alioth Shootout:
> 
> Specification:
> ---------------------------------------------------
> The telephone number pattern: 
> 
>       * there may be zero or one telephone numbers per line of input
>       * a telephone number may start at the beginning of the line or be
>         preceeded by a non-digit, (which may be preceeded by anything)
>       * it begins with a 3-digit area code that looks like this (DDD) or
>         DDD (where D is [0-9])
>       * the area code is followed by one space
>       * which is followed by the 3 digits of the exchange: DDD
>       * the exchange is followed by a space or hyphen [ -]
>       * which is followed by the last 4 digits: DDDD
>       * which can be followed by end of line or a non-digit (which may
>         be followed by anything).

This is already a problem near the limit of writing regexps directly, in
one step. I think the problem is not the complexity of the problem, but
the string notation of regexps which makes any solution hard to read.

However, there are better criterions when to use which lexing
technology:

- When one wants to have a token stream as result: use (ocaml)lex
- When one can profit from recursive lexer definitions: use (ocaml)lex
- When the regexp is computed: use regexp engine

> ------ FELIX SOLUTION---------------------
> 
> regexp digit = ["0123456789"];
> regexp digits3 = digit digit digit;
> regexp digits4 =  digits3 digit;
> 
> regexp area_code = digits3 | "(" digits3 ")";
> regexp exchange = digits3;
> 
> regexp phone = area_code " " exchange (" " | "-") digits4;
> 
> fun lexit (start:iterator, finish:iterator): iterator * string =>
>   reglex start to finish with
>   | phone => check_context (lexeme_start, lexeme_end)
>   | _ => ""
>   endmatch
> ;

The pa_ocamllex/ulex solution would be very similar to this.

> > Regular expressions were
> > designed for pattern matching and substitution,
> 
> So called regular expressions are NOT mathematically
> regular expressions, and they were certainly NOT designed by
> people that knew what they were doing from a theoretical viewpoint.
> 
> Regular expressions have a precise mathematical foundation,
> and they do NOT include captures.

You mean back references, e.g.

((a|b|c)*)d\1

here matching strings where the part of the string before "d" is
identical to the part after "d". The set of matched strings is a
context-sensitive language!

Capturing just for the purpose of string extraction is not problematic.
Back references are unsound when they can match the empty word.

> Attempts to add captures to the theory have been made, 
> and none are satisfactory IMHO. Certainly none actually agree 
> with any implementations.

This is true, but I think it is practically irrelevant.

> PCRE has some wording about longest matches
> and left most capture but these semantics turn out to
> be inconsistent, and are not what PCRE actually implements.

There are often several ways of capturing. In practice, I found this
never to be a real problem, because there are almost always alternate
regexps avoiding such problems.

I still think that a regexp engine is a useful addition to a language
like ocaml. Even with camlp4 integration ocamllex is an overkill
solution for many simple matching problems (notation and execution
overhead).

Gerd
-- 
------------------------------------------------------------
Gerd Stolpmann * Viktoriastr. 45 * 64293 Darmstadt * Germany 
gerd@gerd-stolpmann.de          http://www.gerd-stolpmann.de
------------------------------------------------------------