Re: [Caml-list] Context Free Grammars?

[Brian Hurt <bhurt@spnz.org>]

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