Subject: Re: [lojban] LALR1 question

From: Jay Kominek <[email-masked]>
Date: Mon, 27 Aug 2001 17:55:23 -0600 (MDT)

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 <[email-masked]>
Plus ça change, plus c'est la même chose