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: 2004-09-15 (15:06)
From: skaller <skaller@u...>
Subject: [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

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