Version française
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

Browse thread
[Caml-list] Need NFA/DFA conversion help
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: luc.maranget@i...
Subject: Re: [Caml-list] Need NFA/DFA conversion help
> I need some help understanding how to convert
> an NFA with *labelled* arcs into an equivalent DFA.
> I'm not even sure it is possible. Any advice,
> pointers to papers, or code appreciated. The main
> use will be in a set of regexp related tools intended
> to replace Ocamllex, Str, and PCRE with pure caml code,
> and then extend that with an RTN based parsing system.
> Ocamllex functionality is already available,
> however group extraction and friends seem
> to require labelled arcs (and RTNs definitely do).
> I'm using the naive algorithm (regexp->DFA) from
> the Dragon book with the pattern-recognition 
> modification (which is enough for a tokeniser).
> I can't see how to modify it to keep track of
> the arcs (special marks in regexps like group
> brackets, lookahead operator, etc).
> -- 
> John Skaller,
> voice: 061-2-9660-0850, 
> snail: PO BOX 401 Glebe NSW 2037 Australia
> Checkout the Felix programming language

As regards ocamllex, I worked from various recent publications by
Ville Larikari.

Here is the relevent comment from ocamllex sources (lex/

(* To generate directly a NFA from a regular expression.
     Confer Aho-Sethi-Ullman, dragon book, chap. 3 
   Extension to tagged automata.
       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),
(See also)

To me, all that is far from being obvious...

Bon courage !


To unsubscribe, mail Archives:
Bug reports: FAQ:
Beginner's list: