From: skaller <skaller@users.sourceforge.net>
To: Markus Mottl <markus.mottl@gmail.com>
Cc: Jon Harrop <jon@jdh30.plus.com>, caml-list@yquem.inria.fr
Subject: Re: [Caml-list] Right recursion with ocamlyacc
Date: 16 Feb 2005 15:42:24 +1100 [thread overview]
Message-ID: <1108528944.5095.125.camel@pelican.wigram> (raw)
In-Reply-To: <20050216035811.GA17612@mobile>
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
prev parent reply other threads:[~2005-02-16 4:42 UTC|newest]
Thread overview: 7+ messages / expand[flat|nested] mbox.gz Atom feed top
2005-02-16 2:10 Jon Harrop
2005-02-16 2:28 ` [Caml-list] " Eric C. Cooper
2005-02-16 3:58 ` Markus Mottl
2005-02-16 4:35 ` Jon Harrop
2005-02-16 9:18 ` Radu Grigore
2005-02-18 15:27 ` Radu Grigore
2005-02-16 4:42 ` skaller [this message]
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=1108528944.5095.125.camel@pelican.wigram \
--to=skaller@users.sourceforge.net \
--cc=caml-list@yquem.inria.fr \
--cc=jon@jdh30.plus.com \
--cc=markus.mottl@gmail.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).