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-16 (12:07)
From: luc.maranget@i...
Subject: Re: [Caml-list] Need NFA/DFA conversion help

> > What doesn't work is sub-group matching, look ahead, etc -- things
> > requiring actions in the middle of a regexp (rather than at the
> > end).
> Here is the second problem. You did exactly what was expected (taking
> a textbook on formal languages and implement what is said). The
> problem is that tools like PCRE, Lex, Yacc, etc. do not work as
> textbook say. They do not accept rational or context-free languages,
> they do not use DFA, NFA or LR(k) automata as claimed.

Perhaps I should make my previous post (on the theoretic side of ocamllex)
a bit more precise.

The cited articles relate to << sub-group matching >> in DFA implementation
of regexp matching.

The proposed technique is an extension of the Dragon-Book technique
(Glukov ?)


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