Version française
Home     About     Download     Resources     Contact us    
Browse thread
Str.string_match incorrect
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: skaller <skaller@u...>
Subject: Re: [Caml-list] Str.string_match incorrect
On Wed, 2004-12-22 at 19:00, William Lovas wrote:
> On Tue, Dec 21, 2004 at 11:44:55PM -0800, Evan Martin wrote:
> > This is consistent with the docs, which say:
> >   [string_match r s start] tests whether the characters in s starting at
> >   position start match the regular expression r.
> > and in general with how regular expression systems work. 

Then they're simply wrong. The fundamental operation is
to check if a string is in a regular set of strings.
Plainly 'aa' is not in the set { 'a' }.

string_match is actually testing if some prefix of the
argument is in the regular set -- this is core operation
of a lexical analyser.

I'm not against having that operation -- Felix does --
but it leaves us without the most fundamental and
important operation -- validation.

> I concur with your assessment, but i think you're characterization of the
> semantics of string_partial_match is inaccurate:

Looks like partial_match runs thru the whole string,
and if it doesn't encounter an error returns true.

This is the same automaton in which all non-error states
are considered accepting states.

An error state is actually a state where an accepting state 
is not reachable.

There is a transformation: construct the DFA, mark non-error
states accepting, then generate the corresponding regexp.
Whether that is a 'simple' transformation is another issue :))


-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net