From jay.kominek@colorado.edu Mon Aug 27 16:03:09 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:03:08 -0000 Received: (qmail 26378 invoked from network); 27 Aug 2001 23:02:34 -0000 Received: from unknown (10.1.10.142) by l10.egroups.com with QMQP; 27 Aug 2001 23:02:34 -0000 Received: from unknown (HELO ucsub.colorado.edu) (128.138.129.12) by mta3 with SMTP; 27 Aug 2001 23:02:34 -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 f7RN2U316007 for ; Mon, 27 Aug 2001 17:02:30 -0600 (MDT) Date: Mon, 27 Aug 2001 17:02:30 -0600 (MDT) To: Subject: Re: [lojban] LALR1 question In-Reply-To: <20010827224549.JLGX3759.tomts6-srv.bellnexxia.net@localhost> 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 McIvor wrote: > 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) LR(k) and LL(k) (for all k) grammars are also unambiguous. LALR(k) is in fact a subset of LR(k). There are likely to be a very large number of other classes of grammars which are unambiguous, but noone has bothered to give them names, or they're buried in obscure theses in the bottom huge libraries. Proving ambiguity is what is more complex. I have, somewhere in my pile of bookmarks, a URL for a PDF book on parsing and parsing techniques. If I can dig it up, I'll send that URL to the list this evening. Until then, any introductary text on compilers, programming languages, or CS theory ought to discuss the topic at least briefly. - Jay Kominek Plus =C3=A7a change, plus c'est la m=C3=AAme chose