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

**URL:** <https://www.ruby-forum.com/t/did-using-yacc-in-the-ruby-parser-require-a-lot-of-messy-hacking/135532>\
**Category:** Ruby\
**Created:** [April 22, 2008, 10:25pm UTC](https://www.ruby-forum.com/t/did-using-yacc-in-the-ruby-parser-require-a-lot-of-messy-hacking/135532 "2008-04-22T22:25:49Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![robert](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/r/e95f7d/32.png) [@robert](https://www.ruby-forum.com/u/robert)\
**Post date:** [April 22, 2008, 10:25pm UTC](https://www.ruby-forum.com/t/did-using-yacc-in-the-ruby-parser-require-a-lot-of-messy-hacking/135532/1 "2008-04-22T22:25:49Z")

</div>

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?

---

<div class="post-metadata">

**Author:** ![robert](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/r/e95f7d/32.png) [@robert](https://www.ruby-forum.com/u/robert)\
**Post date:** [April 23, 2008, 11:12am UTC](https://www.ruby-forum.com/t/did-using-yacc-in-the-ruby-parser-require-a-lot-of-messy-hacking/135532/2 "2008-04-23T11:12:16Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![robert](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/r/e95f7d/32.png) [@robert](https://www.ruby-forum.com/u/robert)\
**Post date:** [April 24, 2008, 4:28am UTC](https://www.ruby-forum.com/t/did-using-yacc-in-the-ruby-parser-require-a-lot-of-messy-hacking/135532/3 "2008-04-24T04:28:06Z")

</div>

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