Re: [Caml-list] Context Free Grammars?

[David Brown <caml-list@davidb.org>]

On Fri, Aug 13, 2004 at 03:22:28PM +1000, skaller wrote:

> tlelement:
>   | lelement COLON factor { $1,Some (typecode_of_expr $3) } 
>   | lelement { $1,None }
> 
> lexprs:
>   | tlelement COMMA lexprs { $1 :: $3 }
>   | tlelement { [$1] }
> 
> This works -- its part of the Felix grammar: tlelement
> is left recursive, lexprs is right recursive,
> and the reason is clear -- its the most efficient
> way to build a list. 
> 
> Perhaps someone can explain why this actually works ..??

It is similar to tail recursion and non-tail recursion in ocaml code.  The
right recursive one works (at least some forms work), but you end up
shifting the entire expression off and not reducing the entire thing until
the end.  In other words, even if you can use right recursion, the left
recursive version will be more efficient.

I think there are situations where a right recursive version wouldn't be
able to parse, but a left one would.  But, it is too late, and I don't
think I can think about it right now :-)

Dave

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