From jay.kominek@colorado.edu Mon Aug 27 16:55:38 2001 Return-Path: X-Sender: kominek@ucsub.colorado.edu X-Apparently-To: lojban@yahoogroups.com Received: (EGP: mail-7_3_2); 27 Aug 2001 23:55:38 -0000 Received: (qmail 44524 invoked from network); 27 Aug 2001 23:55:27 -0000 Received: from unknown (10.1.10.26) by m8.onelist.org with QMQP; 27 Aug 2001 23:55:27 -0000 Received: from unknown (HELO ucsub.colorado.edu) (128.138.129.12) by mta1 with SMTP; 27 Aug 2001 23:55:27 -0000 Received: from ucsub.colorado.edu (kominek@ucsub.colorado.edu [128.138.129.12]) by ucsub.colorado.edu (8.11.6/8.11.2/ITS-5.0/student) with ESMTP id f7RNtN311494 for ; Mon, 27 Aug 2001 17:55:23 -0600 (MDT) Date: Mon, 27 Aug 2001 17:55:23 -0600 (MDT) To: Subject: Re: [lojban] LALR1 question In-Reply-To: Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=utf-8 Content-Transfer-Encoding: QUOTED-PRINTABLE From: Jay Kominek On Mon, 27 Aug 2001, Robert J. Chassell wrote: > LR(k) and LL(k) (for all k) grammars are also unambiguous. > > Like Robert McIvor, I, too, was under the impression that 20 years ago > people were not sure whether the LR(k) parsers were truly unambiguous. > That is when the relevant grammar choices were made (1970s, early > 1980s). I'd imagine that Knuth(?) would've proven the unambiguity when he wrote the initial LR parsing paper. (I think it was Knuth...) If I had to guess, I'd say that the concern was more with whether or not other parsers were actually bug free, not whether or not the class of languages was unambiguous. > The only tool that generated confidence was YACC, which had only > recently been developed. If I remember rightly, it worked only with > LALR(1) grammars. YACC could not handle the Loglan grammer directly, > but required a preproccessor that might not have been unambiguous > itself. I doubt that YACC has ever worked with anything except LALR(1). Lojban itself still requires a bit of preprocessing, but mostly for things like zoi quoting. > Also, very practically, no one in the project had fast machines back > then. *LR parsing is convinently O(n). The time (and space!) requirements get nasty if you want generalized parsing and such. --- Ok, the URL for the book I was thinking about is: http://www.cs.vu.nl/~dick/PTAPG.html "Parsing Techniques: A Practical Guide" It has an unbelievably _HUGE_ annotated bibliography in the back covering easily everything important in the field up to the publication of the book. - Jay Kominek Plus =C3=A7a change, plus c'est la m=C3=AAme chose