From rmcivor@macsrule.com Mon Aug 27 15:48:47 2001 Return-Path: X-Sender: rmcivor@macsrule.com X-Apparently-To: lojban@yahoogroups.com Received: (EGP: mail-7_3_2); 27 Aug 2001 22:48:47 -0000 Received: (qmail 95844 invoked from network); 27 Aug 2001 22:45:50 -0000 Received: from unknown (10.1.10.26) by l8.egroups.com with QMQP; 27 Aug 2001 22:45:50 -0000 Received: from unknown (HELO tomts6-srv.bellnexxia.net) (209.226.175.26) by mta1 with SMTP; 27 Aug 2001 22:45:49 -0000 Received: from localhost ([64.230.90.234]) by tomts6-srv.bellnexxia.net (InterMail vM.4.01.03.16 201-229-121-116-20010115) with ESMTP id <20010827224549.JLGX3759.tomts6-srv.bellnexxia.net@localhost>; Mon, 27 Aug 2001 18:45:49 -0400 Date: Mon, 27 Aug 2001 18:45:47 -0400 Content-Type: text/plain; format=flowed; charset=us-ascii Subject: Re: [lojban] LALR1 question Cc: To: Jay Kominek X-Mailer: Apple Mail (2.388) In-Reply-To: Mime-Version: 1.0 (Apple Message framework v388) Content-Transfer-Encoding: 7bit Message-Id: <20010827224549.JLGX3759.tomts6-srv.bellnexxia.net@localhost> From: Robert McIvor X-Yahoo-Message-Num: 10190 On Monday, August 27, 2001, at 05:19 PM, Jay Kominek wrote: > > On Mon, 27 Aug 2001, Robin Lee Powell wrote: > >> On Mon, Aug 27, 2001 at 04:38:44PM -0400, Rob Speer wrote: >>> On Mon, Aug 27, 2001 at 11:17:55AM -0600, Jay Kominek wrote: >>>> Hrm. A parser with back tracking or more look ahead (or basically any >>>> parser which can parse a larger class of languages) could take the >>>> same >>>> YACC grammar and be able to parse "le broda joi le brode" >>>> correctly... I >>>> think... >>> >>> So, what is the advantage to having Lojban interpreted by a parser >>> which can't >>> backtrack or look ahead more than one word? >> >> All other parsers turn out to be _extremely_ inefficient, IIRC from my >> course on such things. >> >> So, basically, it's to make computers happy. > > LALR(1) deals in a table on the order of O(n^2), where n is the number > of > productions in the language. (Maybe n is the size of the set of > terminals > _and_ non-terminals. Not really relevent.) > > LALR(2) would need a table around O((2*n)^2), IIRC. > > Backtracking is a pain, but doesn't make things too much more > inefficient. > > The main advantage to using a non-backtracking parser with just one word > of lookahead is that parser generators for such grammars are commonly > available, and easy to implement. > > In fact, I don't know that I've ever seen a reference to a C (or C++, or > Java, or Perl) parser generator which is anything _but_ LALR(1). > > Most programming languages are LALR(1), so most programming language > courses, or compiler building courses wherein computer science students > are taught how to construct a parser tend to gloss over the details of > all > other classes of parsers. I have always been led to believe that LALR(1) parsers are the maximum that can be conclusively proved to be unambiguous, which is why TLI Loglan grammar was based on YACC (and incidentally, Robin, has no shift-reduce conflicts) Bob