Browse thread
[Caml-list] Need NFA/DFA conversion help
[
Home
]
[ Index:
by date
|
by threads
]
[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: | 2004-09-15 (19:15) |
From: | Alain Frisch <Alain.Frisch@e...> |
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. > > 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