From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id QAA14497; Fri, 13 Aug 2004 16:12:56 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id QAA14938 for ; Fri, 13 Aug 2004 16:12:55 +0200 (MET DST) Received: from herd.plethora.net (herd.plethora.net [205.166.146.1]) by concorde.inria.fr (8.12.10/8.12.10) with ESMTP id i7DECsRM032425 for ; Fri, 13 Aug 2004 16:12:54 +0200 Received: from bhurt.plethora.net (bhurt.plethora.net [205.166.146.49]) by herd.plethora.net (8.11.6/8.10.1) with ESMTP id i7DECkJ10262; Fri, 13 Aug 2004 09:12:47 -0500 (CDT) Date: Fri, 13 Aug 2004 09:20:37 -0500 (CDT) From: Brian Hurt X-X-Sender: bhurt@localhost.localdomain To: skaller cc: caml-list Subject: Re: [Caml-list] Context Free Grammars? In-Reply-To: <1092374548.29139.86.camel@pelican.wigram> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-Miltered: at concorde with ID 411CCC66.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Loop: caml-list@inria.fr X-Spam: no; 0.00; caml-list:01 recursion:01 lalr:01 recursion:01 expr:01 expr:01 lalr:01 recursively:01 work-:99 mul:01 mul:01 it'd:01 it'd:01 parser:02 tree:02 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk 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