Subject: Re: [lojban] LALR1 question

From: Robert McIvor <[email-masked]>
Date: Mon, 27 Aug 2001 18:45:47 -0400

On Monday, August 27, 2001, at 05:19 PM, Jay Kominek wrote:

>
> 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.

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)

Bob