Re: Bison table compression algorithm

[Hans Aberg]

On 19 Aug 2006, at 00:35, Satya wrote:

> I was reading the original paper about Bison - "Static Semantics and
> Compiler Error Recovery" by Robert Paul Corbett, and it says  
> Bison's table
> organization is based on a technique proposed by Ziegler and  
> described in
> Tarjan and Yao in [TY78] ("Storing a Sparse Table");
>
> My question is this: does Bison still follow that scheme? I  
> wouldn't want to
> dive into this paper ([TY78]) if  you have changed the compression  
> scheme
> during the course of Bison development history.

Earlier versions of Bison, before the days of M4, used to have a  
skeleton file called bison.hairy, which derived from Robert Corbett's  
thesis. It fell out of use, unsupported, and nobody could get it  
running. After suggestions from himself, it was removed.

> Also, is there is a simpler explanation of the rationale behind the  
> tables
> being organized in that way (specific to Bison)? I'd want to read  
> about
> that. Thanks!!

According to him, this stuff was dead. But the study of error  
recovery techniques continues at Berkley by Susan L. Graham.

You might search the Bison mail list archives for "Corbett" to see  
this discussion.

  Hans Aberg