Archives of the Caml mailing list > Message from Alain Frisch

Browse thread

[Caml-list] ocamllex problem

Jonathan Roewen
- Jonathan Roewen
  - skaller
    - Alain Frisch
    - james woodyatt
      - skaller
      - Berke Durak
        
        skaller
        
        Jonathan Bryant
        
        David MENTRE

Date:	-- (:)
From:	Alain Frisch <Alain.Frisch@i...>
Subject:	Re: [Caml-list] ocamllex problem

skaller wrote:
> How does that work??? The algorithm for handling
> this for a DFA is non-trivial. Any pointers to
> the algorithm used?

As you can find in the source code of ocamllex:


(* To generate directly a NFA from a regular expression.
     Confer Aho-Sethi-Ullman, dragon book, chap. 3
   Extension to tagged automata.
     Confer
       Ville Larikari
      ``NFAs with Tagged Transitions, their Conversion to Deterministic
        Automata and Application to Regular Expressions''.
       Symposium on String Processing and Information Retrieval (SPIRE
2000),
     http://kouli.iki.fi/~vlaurika/spire2000-tnfa.ps
(See also)
     http://kouli.iki.fi/~vlaurika/regex-submatch.ps.gz
*)

-- Alain