Did using Yacc in the Ruby parser require a lot of messy hacking?

Ruby
1

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?

2

On Apr 22, 2008, at 13:25 , 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?

LALR and context free can be found in fundamental CS literature or on
wikipedia.

Or does the grammar of Ruby fit quite nicely with the Lex/Yacc
toolset?

I’m not sure what you mean by “fit”. It works with Lex/Yacc (bison
actually) and my ruby_parser project works with racc… but I dunno
about “fit”. Probably “no” if I had to guess your intent.

3

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