Re: [lojban] LALR1 question

[Jay Kominek <jay.kominek@colorado.edu>]

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 <jay.kominek@colorado.edu>
  Plus ça change, plus c'est la même chose