Re: [Caml-list] Need NFA/DFA conversion help

[Alain Frisch <Alain.Frisch@ens.fr>]

> > I need some help understanding how to convert
> > an NFA with *labelled* arcs into an equivalent DFA.
>
> As regards ocamllex, I worked from various recent publications by
> Ville Larikari.

Lexer generators (and regexp packages) are usually pretty weak for what
concerns extraction; you can only extract very unstructured information
(a finite number of groups), and the semantics of capture groups
below Kleene stars is not always satisfactory.

The algorithm presented in this paper (sorry for citing myself):

Greedy regular expression matching. A. Frisch, and L. Cardelli. In ICALP 2004
http://www.cduce.org/papers/icalp04.pdf
(or the older and extended version: http://www.cduce.org/papers/greedy.pdf)

makes it possible to write a lexer generator (and a regexp package) with a
more structured semantics, where, for instance, a capture inside a star
returns a list of bindings, a capture below a ? returns a(n?) 'a option.
The (quite straightforward) algorithm in the paper returns a parse tree
with a specified disambiguation policy, using two linear traversals of the
input word. The first traversal is just running a very standard automaton
(without marks), keeping the intermediate states for each position;  the
second traversal is driven by the syntax of the regexp and builds the
parse tree. Let me know (off-list) if you are interested in implementing
this kind of structured capture semantics.


-- Alain

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners