Re: [lojban] LALR1 question

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

On Mon, 27 Aug 2001, Robin Lee Powell wrote:

> On Mon, Aug 27, 2001 at 04:38:44PM -0400, Rob Speer wrote:
> > On Mon, Aug 27, 2001 at 11:17:55AM -0600, Jay Kominek wrote:
> > > Hrm. A parser with back tracking or more look ahead (or basically any
> > > parser which can parse a larger class of languages) could take the same
> > > YACC grammar and be able to parse "le broda joi le brode" correctly... I
> > > think...
> >
> > So, what is the advantage to having Lojban interpreted by a parser which can't
> > backtrack or look ahead more than one word?
>
> All other parsers turn out to be _extremely_ inefficient, IIRC from my
> course on such things.
>
> So, basically, it's to make computers happy.

LALR(1) deals in a table on the order of O(n^2), where n is the number of
productions in the language. (Maybe n is the size of the set of terminals
_and_ non-terminals. Not really relevent.)

LALR(2) would need a table around O((2*n)^2), IIRC.

Backtracking is a pain, but doesn't make things too much more inefficient.

The main advantage to using a non-backtracking parser with just one word
of lookahead is that parser generators for such grammars are commonly
available, and easy to implement.

In fact, I don't know that I've ever seen a reference to a C (or C++, or
Java, or Perl) parser generator which is anything _but_ LALR(1).

Most programming languages are LALR(1), so most programming language
courses, or compiler building courses wherein computer science students
are taught how to construct a parser tend to gloss over the details of all
other classes of parsers.

- Jay Kominek <jay.kominek@colorado.edu>
  Plus ça change, plus c'est la même chose