[Caml-list] Need NFA/DFA conversion help

[Caml-list] Need NFA/DFA conversion help

[skaller]

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, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net



-------------------
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

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

[Luc Maranget]

> 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, mailto:skaller@users.sf.net
> voice: 061-2-9660-0850, 
> snail: PO BOX 401 Glebe NSW 2037 Australia
> Checkout the Felix programming language http://felix.sf.net


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

Here is the relevent comment from ocamllex sources (lex/lexgen.ml)

(* To generate directly a NFA from a regular expression.
     Confer Aho-Sethi-Ullman, dragon book, chap. 3 
   Extension to tagged automata.
     Confer
       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),
<http://kouli.iki.fi/~vlaurika/spire2000-tnfa.ps>
(See also)
<http://kouli.iki.fi/~vlaurika/regex-submatch.ps.gz>
*)

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

Bon courage !

--Luc

-------------------
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

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

[Jason Hickey]

skaller wrote:
> 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.

You might consider looking at the Mojave lexer--probably the easiest way
to get it is to download the omake sources at http://omake.metaprl.org,
and look at the file lm_lexer.{ml,mli}.  It is pure OCaml code, and
provides a tiny bit more functionality than ocamllex, but lexer
construction is online.

There is also a stub for (re)defining the Str functions in terms of
Lexer functions, but it is incomplete at the moment.

The regular expressions are egrep/awk style.  The lexer compiles regex
-> NFA -> DFA, but the DFA step is lazy--it is constructed as the input
is scanned.  Documentation for the regular expression syntax is under
the omake documentation page
http://cvs.metaprl.org:12000/omake/omake.html#section_171

Jason

-- 
Jason Hickey                  http://www.cs.caltech.edu/~jyh
Caltech Computer Science      Tel: 626-395-6568 FAX: 626-792-4257



-------------------
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

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

[Alain Frisch]

> > 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

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

[Jason Hickey]

skaller wrote:
> 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.

You might consider looking at the Mojave lexer--probably the easiest way
to get it is to download the omake sources at http://omake.metaprl.org,
and look at the file lm_lexer.{ml,mli}.  It is pure OCaml code, and
provides a tiny bit more functionality than ocamllex, but lexer
construction is online.

There is also a stub for (re)defining the Str functions in terms of
Lexer functions, but it is incomplete at the moment.

The regular expressions are egrep/awk style.  The lexer compiles regex
-> NFA -> DFA, but the DFA step is lazy--it is constructed as the input
is scanned.  Documentation for the regular expression syntax is under
the omake documentation page
http://cvs.metaprl.org:12000/omake/omake.html#section_171

Jason

-- 
Jason Hickey                  http://www.cs.caltech.edu/~jyh
Caltech Computer Science      Tel: 626-395-6568 FAX: 626-792-4257


-------------------
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

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

[skaller]

On Thu, 2004-09-16 at 01:05, skaller wrote:
> I need some help understanding how to convert
> an NFA with *labelled* arcs into an equivalent DFA.

Thx to those who responded. Just for motivation:

> Ocamllex functionality is already available,

This already works:

(* test matcher *)

(* tokens *)
type codes_t = [
  | `Word
  | `Ident
  | `Num
  | `White
  | `Dus
]

let string_of_code = function 
  | `Word -> "Word"
  | `Ident -> "Ident"
  | `Num -> "Num"
  | `White -> "White"
  | `Dus -> "Dus"
  | `Reserved -> "Reserved"

let string_of_result f = function
  | `Coded xs -> String.concat ", " (List.map f xs)
  | `Error _ -> "Match failure"

(* regexps *)
let digit = regexp_of_charset "0123456789"
let lower = regexp_of_inclusive_char_range 'a' 'z'
let upper = regexp_of_inclusive_char_range 'A' 'Z'
let letter = alt upper lower
let underscore = regexp_of_char '_'
let word = many letter
let idstart = alt letter underscore
let idrest = alt idstart digit
let space = regexp_of_char ' '
let white = many space
let ident = seq idstart (aster idrest)
let num = many digit
let us2 = seq underscore underscore

(* associate regexps with tokens *)
let tk_word = seq word (code `Word)
let tk_ident = seq ident (code `Ident)
let tk_num = seq num (code `Num)
let tk_white = seq white (code `White)
let tk_us2 = seq (seq us2 (code `Dus))

(* gather the alternatives *)
let re = alts [tk_word; tk_ident; tk_num; tk_white; tk_us2]
let alphabet, states, codes, matrix = process_regexp re;;

(* print all the token associated with command line argument *)
let data = Sys.argv.(1) ;;
let matcher = make_matcher matrix codes data;;
let result = recognize matcher;;
print_endline ("Result: " ^ string_of_result string_of_code result);;

---------------------------

With some minor fiddling this is a tokeniser
like Ocamllex, except you don't need any external tool 
or library, you can define everything 'in-caml' 
and dynamically, as shown.  (The core of the matcher
engine is also purely functional :)

Then you can either process some data,
or you can save the compiled automaton (possibly
as Ocaml or C sourcecode which can be compiled directly
to executable code like (Ocaml)lex output).

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).

If that could be made to work, we'd have a nice
pure Ocaml only library that could replace Ocamllex,
Str, and PCRE all at once -- and also allow a lot
of other things to be built on top, such as an RTN parser.

[It turns out polymorphic variants are quite useful
in extending the regular expression ASTs, as well
as being used as tokens.]

-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net



-------------------
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

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

[Diego Olivier Fernandez Pons]

    Bonjour,


It seems there are two different problems addressed in your request :
the first one is purely technical and the second one is more
theoretical.

> like Ocamllex, except you don't need any external tool or library,
> you can define everything 'in-caml' and dynamically, as shown.
> (The core of the matcher engine is also purely functional)

Tools like Lex or Yacc build an 'interpreter' (NFA, FDA, push-down
automata or transducers) which interprets your input language and
'does' something.

What you are asking is this set of tools to be done in a dynamic and
pure-caml way instead of a 2-stages mixed C/Caml. This is a technical
issue : just take the same principles that were used to build this
tools and replace the code generation by data structures construction
(sounds simple, doesn'it ?)

> Then you can either process some data, or you can save the compiled
> automaton (possibly as Ocaml or C sourcecode which can be compiled
> directly to executable code like (Ocaml)lex output).

Yes, one can imagine a generic framework that would allow you to
choose how your intepreter will be generated (source-code/data
structure, C/Caml, etc.)

> 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.

Yacc input language is not a context-free language but some kind of
restricted attribute grammar that lies somewhere between algebraic
transducers and contextual grammars. Hence tools like Bison will
contain a lot of strange hacks to handle all these extensions while
keeping the push-down automata machinery.

In the same way a grammar that admits 'actions in the middle of a
regexp [] rather than at the end' could hardly qualify as a 'rational
language' which is what regexp theoretically describe.

As far as I know, there is no simple way to handle all these useful
'extensions' and theoretically satisfactory ways tend to be very hard.

- general textbook

Parsing techniques (Dick Grune, Ceriel J.H. Jacobs) (electronic
version on free download)
http://www.cs.vu.nl/~dick/PTAPG.html

Dick Grune 'compilers' book has a chapter on attribute grammars

- attribute grammars

FNC2 (strongly non circular attribute grammars)
http://www-rocq.inria.fr/oscar/www/fnc2/

An attribute grammar system in Haskell
http://www.cs.uu.nl/groups/ST/twiki/bin/view/Center/AttributeGrammarSystem

- Yacc like tools

Jacke, Yacc-like parser generator with SML-consistent sytax
http://www.ps.uni-sb.de/~jan/jacke/jacke.html


        Diego Olivier

-------------------
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

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

[Luc Maranget]

> > 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 ?)


--Luc

-------------------
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

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

[james woodyatt]

everyone—

A lookahead operator is on my list of things to add to the Cf_dfa 
module (and Cf_lexer) in the Cf library component of the OCaml NAE 
project.  As far as I can tell, it's just a matter of coding it— not a 
problem with working out a theory.

Also missing from the feature set in Cf_lexer: regular expression 
parsing (to construct lexer automata from simpler expressions than what 
currently is required) and CamlP4 syntax sugar for them.

Here's the SourceForge project again:  
<URL:http://sf.net/projects/ocnae/>.


-- 
j h woodyatt <jhw@wetware.com>
markets are only free to the people who own them.
-------------------
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

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

[skaller]

On Thu, 2004-09-16 at 21:50, Diego Olivier Fernandez Pons wrote:

> In the same way a grammar that admits 'actions in the middle of a
> regexp [] rather than at the end' could hardly qualify as a 'rational
> language' which is what regexp theoretically describe.

Yes, so I am seeking an extension of the theory strong
enough to allow such 'actions' but weak enough to still
allow determinism -- if it exists. And I'll need a constructive
proiof -- that is, an algorithm :)

> - general textbook
> 
> Parsing techniques (Dick Grune, Ceriel J.H. Jacobs) (electronic
> version on free download)
> http://www.cs.vu.nl/~dick/PTAPG.html

This looks like it would be a great reference but the FTP site
seems to be down.

-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net



-------------------
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

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

[Diego Olivier Fernandez Pons]

    Bonjour,

> This looks like it would be a great reference but the FTP site seems
> to be down.

Works for me but you can always try here

http://books.pdox.net/Computers/


        Diego Olivier

-------------------
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

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

[skaller]

On Thu, 2004-09-16 at 22:07, Luc Maranget wrote:
> > > 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).
> > 
> > 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 ?)

I have read the Laurikari article and it describes the kind
of thing I was looking for. It provides a mathematical formalism
for Tagged NFAs and gives an modification of the subset
construction which handles determinising such TNFAs.

I think this gives all the functionality of lex
and Str/PCRE together (except for back references).

That seems a reasonable goal for a first release
because it can simplify the life or ordinary
programmers as well as compiler implementors.

Perhaps more expressive automata will follow
(as well as performance improvements :)

-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net



-------------------
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