This site is updated infrequently. For up-to-date information, please visit the new OCaml website at ocaml.org.

[Caml-list] Context Free Grammars?
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: 2004-08-13 (14:12) From: Brian Hurt Subject: Re: [Caml-list] Context Free Grammars?
```On 13 Aug 2004, skaller wrote:

> Perhaps someone can explain why this actually works ..??

Right recursion "works".  The problem is that LALR parsers can do
something akin to tail recursion with left recursion that they can't do
with right recursion.  Say, for example, you have the rules:

mul_expr: mul_expr '*' term
| mul_expr '/' term
| mul_expr MOD term
| term

term: NUMBER

Here, mul_expr is "left recursive"- the "recursive" call to mul_expr is on
the left hand side of the expression.  Now, with an LALR parser, no mater
how many multiplications you had, it'd use constant stack space.  Each
time it'd see a new multiplication term, it'd immediately collapse back
down to a mul_expr.  An equally valid way to parse this would be right
recursively:

mul_expr: term '*' mul_expr
| term '/' mul_expr
| term MOD mul_expr
| term

The problem here is that if you had N multiplications in a row, it'd take
O(N) stack spaces on the parse tree to parse them all.  This would still
work- right up until you hit the point where you have so many
multiplication terms that you blow stack.

It works, and there are times when it's the correct thing to use, but if
you have the choice between left recursive and right recursive grammars,
pick left recursive for LALR parsers.

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

```