Browse thread
Right recursion with ocamlyacc
[
Home
]
[ Index:
by date
|
by threads
]
[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: | 2005-02-16 (04:42) |
From: | skaller <skaller@u...> |
Subject: | Re: [Caml-list] Right recursion with ocamlyacc |
On Wed, 2005-02-16 at 14:58, Markus Mottl wrote: > On Wed, 16 Feb 2005, Jon Harrop wrote: > > I've just been converting a new Computer Language Shootout submission from > > OCaml to C++ and found that bison falls over very easily with right recursion > > (failing to load a 10^4-element list) but ocamlyacc had no problems (even on > > a 10^5-element list). > > Why use right recursive productions in the grammar? Left recursion runs > in constant stack space so this would be the way to go... Kind of tricky to represent right associative binary operator with left recursion .. right recursion is much more natural: rterm: atom rterm { Rterm ($1, $2) } The thing is, right assoc requires terms to be stacked up one way or another. Left recursion defers the problem to client code, and must introduce intermediate term structure to do that. Why would I believe my own data structures would perform more efficiently than the parser stack? -- 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