subogero linux blog

While reading esr’s book about UNIX and laziness, I found it referring to a mysterious “yacc” on many occasions. As if sed, awk, tr, ls, sudo et al were not confusing enough. I just could not resist and googled it. Voilá.

It turned out it was a high-level programming language to describe the grammar of, erm, a language, and parse it. It was created by Stephen C. Johnson back in 1973! The paper contains an appendix with an example of a simple command-line calculator.

Just try to imagine the horrors of parsing and executing simple mathematical expressions with a program written in the C language. For instance “-3*(5/2)-(5*-8)+1″.
Operator precedence, brackets, telling unary minus (-3) from the normal minus (6-2). I’d never try it.

But in yacc, the essence of the problem is solved in a few lines:

expr :    '('  expr  ')'
               {    $$  =  $2;  }
     |    expr  '+'  expr
               {    $$  =  $1  +  $3;  }
     |    expr  '-'  expr
               {    $$  =  $1  -  $3;  }
     |    expr  '*'  expr
               {    $$  =  $1  *  $3;  }
     |    expr  '/'  expr
               {    $$  =  $1  /  $3;  }
     |    '-'  expr        %prec  UMINUS
               {    $$  =  -  $2;  }
     |    number
     ;

This led me to a whole series of thoughts. But more of that next time…

Anyway, if yacc is yet another compiler-compiler, which was the previous compiler compiler?