Re: [Caml-list] stream parser problem/question

[Brian Hurt <bhurt@spnz.org>]

On Tue, 10 Aug 2004, Nicolas Cannasse wrote:

> > Hi,
> >
> > I'm using ocamllex/yacc to translate a little language into a parse-tree,
> then
> > processing the tree and putting the output into a queue. Then I iterate
> over
> > the queue, generating a new one and so on until finished.
> > My question is, instead of outputing the processed parse-tree into a
> queue, is
> > ist better/more elegant to generate a stream and then using a stream
> parser
> > to process that stream and eventual generating a new stream,... until
> > finished?
> > Are stream parsers useful for my purpose? Are there penalties using them?
> >
> > Another slight issue is, that I don't see how to generate a token stream
> (with
> > Stream.from) of my parse tree (because of the tree-stucture, I get
> confused
> > how to get the right next token); maybe someone can give me a hint?
> 
> It is actually not easy to generate a stream of tokens for a tree, since you
> have to simulate the call stack by yourself. In languages such as Python,
> the yield keyword is very useful for this. Is there any plans to get such
> thing in OCaml and is there any implementation notes available ?
> 

It's not *that* hard to hand manage a stack for walking a tree.  Almost 
trivial, I'd say.

Let's say you have a tree of nodes declared thusly:

type 'a node_t = 
    | Node of 'a node_t * 'a * 'a node_t
    | Empty
;;

Your bog-standard binary tree.  Now, we define an iterator on it.  An 
iterator has the following API:

val iter_make : 'a node_t -> 'a iter_t
val iter_first : 'a iter_t -> 'a option
val iter_rest : 'a iter_t -> 'a iter_t

I'll just give the code, commentary afterwards:

type 'a iter_t = 'a node_t list

let rec iter_push_left list = function
    | Empty -> list
    | Node(left, _, _) as n -> iter_push_left (n :: list) left
;;

let iter_make tree =
    iter_push_left [] tree
;;

let iter_first = function
    | [] -> None
    | Node(_, v, _) :: _ -> Some(v)
;;

let iter_rest = function
    | [] -> invalid_arg "iter_rest"
    | Node(_, _, r) :: t -> iter_push_left t r
;;

The "state" of the iterator is just the stack (implemented here as a list)  
of the unvisted nodes.  iter_make is O(log N) for N items in the tree.  
iter_first is always O(1).  iter_rest is on average O(1), worst case O(log
N).

The python yield keyword would be an improvement on this code- but not by 
that much.

-- 
"Usenet is like a herd of performing elephants with diarrhea -- massive,
difficult to redirect, awe-inspiring, entertaining, and a source of
mind-boggling amounts of excrement when you least expect it."
                                - Gene Spafford 
Brian

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