[Caml-list] stream parser problem/question

[Caml-list] stream parser problem/question

[Michael]

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?

cheers,
 Michael

-------------------
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] stream parser problem/question

[Nicolas Cannasse]

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

Regards,
Nicolas Cannasse

-------------------
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] stream parser problem/question

[Brian Hurt]

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

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

[Micha]

Am Wednesday 11 August 2004 00:38 schrieb Jean-Baptiste Rouquier:
> OK
> Here is a code sample, then.

thanks for the sample code, I will review it, tomorrow (or today :-)

> If the two queues have different token types, it will allow slightly
> better typechecking...

yes thats the case. I was wondering if the `(polymorhic) variants would help 
not to have that much types for the variants

> Ah yes. I didn't had the time to submit anything, but I'll look at it
> again and again. I'm only interested in the lightening division since I
> hate sacrificing my sleeping time.

yes, nice try :-)

> Did you send somehting ?

The idea was really funny. I spent too much time for the compiler and too less 
time for a genius ant :-) We send two ants, but the good ideas came 
afterwards, as usual :-) There are still some private ant-contests going on, 
and someone announced a ant which could not be beaten (he said)... 
I'll try to write a ant, just to see what my compiler generates ....

cheers
 Michael

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