Re: [lojban] LALR1 question

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

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