From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id RAA25629; Tue, 10 Aug 2004 17:03:19 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id RAA29691 for ; Tue, 10 Aug 2004 17:03:18 +0200 (MET DST) Received: from herd.plethora.net (herd.plethora.net [205.166.146.1]) by concorde.inria.fr (8.12.10/8.12.10) with ESMTP id i7AF3GRM001915 for ; Tue, 10 Aug 2004 17:03:17 +0200 Received: from bhurt.plethora.net (bhurt.plethora.net [205.166.146.49]) by herd.plethora.net (8.11.6/8.10.1) with ESMTP id i7AF2kJ18869; Tue, 10 Aug 2004 10:02:47 -0500 (CDT) Date: Tue, 10 Aug 2004 10:10:26 -0500 (CDT) From: Brian Hurt X-X-Sender: bhurt@localhost.localdomain To: Nicolas Cannasse cc: micha-1@fantasymail.de, caml Subject: Re: [Caml-list] stream parser problem/question In-Reply-To: <000901c47ec1$22f1db00$ef01a8c0@warp> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-Miltered: at concorde with ID 4118E3B4.001 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Loop: caml-list@inria.fr X-Spam: no; 0.00; caml-list:01 cannasse:01 python:01 iterator:01 iterator:01 api:01 val:01 val:01 implemented:01 python:01 tokens:01 ocaml:01 nicolas:01 token:01 token:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk 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