From: Ron Fox <fox@...>
Date: 2008-04-23T18:25:06+09:00
Subject: Re: Did using Yacc in the Ruby parser require a lot of messy hacking?

Can't answer for the Ruby parser's use of yacc but
Context free - the meaning of any token in the grammar does not depend 
on the state of the parse.  The classic example of a non-context free 
grammer is FORTRAN and the usual example given is:

DO 100 I = 1 + 5

Where the meaning of DO, 100, I, = and 1 are not clear until the + sign 
happens at which point the parser realizes this is an assignment 
statment rather than a DO loop.

LALR is an acronym for Look Ahead Left Right parser.  Very hard to give 
a simple definition as LALR really is a technique for generating parse 
tables for LR(0) grammars, where parse tables are generated from 
look-ahead sets.  LR(0) grammars, are a class of grammars that can be
parsed left right (no backtracking), without any lookahead.  Distilled a 
bit, the LALR tables maintain more state about the production that is 
being parsed than other techniques.  This allows for
1. Smaller parse tables, since the context of the parse can impose
    more limits on the allowed table entries than a context free parse.
2. More specific error recovery, since more is known about the parse
    state at the point of failure (e.g. I'm parsing an if statement and
    expected an end rather than just I expected an end).

RF


Robert wrote:
> I'm assuming that the grammar of Ruby does not follow the LALR grammar
> rules that Yacc assumes? Can anyone give a plain english definition of
> what LALR actually means? Or context free?
> Or does the grammar of Ruby fit quite nicely with the Lex/Yacc
> toolset?