Yacc

Yacc (Yet Another Compiler-Compiler) on ohjelma, joka generoi yhteydettömän kieliopin sääntöjen mukaan LALR-jäsentimen (look-ahead, left-to-right, rightmost derivation parser).

Noam Chomsky julkaisi kontekstittomien kielioppien kuvauksen 1957. Niiden hyödyllisyyden tajuaminen johti siihen että Algol 60 -raportista julkaistiin uusi painos, jossa kielioppi kuvattiin BNF-notaatiolla. Donald Knuth oli keksinyt LR-parserin 1965. Franklin DeRemer esitteli käyttökelpoisen LALR-parserin väitöskirjassaan vuonna 1969.

Yaccin kehitti Stephen Johnson Bell Labsilla. Dennis Ritchie oli kirjoittanut B-kielen kääntäjän, mutta Johnson halusi lisätä siihen XOR-operaattorin, mikä osoittautui monimutkaiseksi. Al Aho kertoi Knuthin keksineen julkaisussaan paremman tavan ja Johnson ja Aho päättivät kirjoittaa B:n syntaksin formaalisti, mikä vei kaksi päivää. 50 säännön kieliopin kääntäminen vei 20 minuuttia koneaikaa. Myöhemmin Johnson sai nopeutettua ohjelmaa 10000-kertaisesti. Alan Snyder käänsi yaccin uudelle C-ohjelmointikielelle. Yaccin virallinen kuvaus julkaistiin 1975.

Yacc on POSIX-standardissa määritelty Unix-käyttöjärjestelmien ohjelma. Siitä on GNU-projektiin vapaa avoimen lähdekoodin toteutus GNU Bison, jonka kirjoitti alun perin Robert Corbett UCB:llä väitöskirjaansa varten. Richard Stallman teki siitä Yacc-yhteensopivan. Vuonna 1990 Corbett julkaisi toisenkin version, joka tunnetaan nykyisin nimellä Berkeley Yacc (byacc), josta tuli myöhemmin suosituin Yaccin versio nopeuden, yhteensopivuuden, bugittomuuden ja public domain -lisenssin ansiosta.

Toiminta

Yaccin säännöt kirjoitetaan Backus–Naur-muotoa muistuttavalla kielellä.

Ohjelma generoi tiedoston y.tab.c, jonka voi kääntää C-kääntäjällä. Ohjelmaan on lisäksi toteuttava leksikaalinen analysaattori nimellä yylex(void), virheenkäsittelyrutiini yyerror(char*) ja pääohjelma. Leksikaalisen analysaattorin voi luoda Lex-ohjelmalla.

Seuraava esimerkki toteuttaa triviaalin nelilaskimen, joka osaa operaattorien presedenssijärjestyksen ja assosiatiivisuuden vasemmalle, sulkulausekkeet ja miinuksen luvun etumerkkinä.

%{
#include <stdio.h>
%}

%token NUMBER
%left '+' '-'
%left '*' '/'

%%

input:
     | input line
     ;

line: '\n'
    | X '\n' { printf("result = %d\n", $$); }
    ;

X   : X '+' X { $$ = $1 + $3; }
    | X '-' X { $$ = $1 - $3; }
    | X '*' X { $$ = $1 * $3; }
    | X '/' X { $$ = $1 / $3; }
    | '-' NUMBER { $$ = -$2; }
    | '(' X ')' { $$ = $2; }
    | NUMBER { $$ = $1; }

%%

int main(int argc, char **argv) {
  yyparse();
  return 0;
}

int yyerror(char *s) {
  fprintf(stderr, "Error: %s\n", s);
  return 0;
}

/* lexical analyzer */
#include <ctype.h>
yylex() {
  int c;
  while ((c = getchar()) == ' ' || c == '\t') ;
  if (isdigit(c)) {
    ungetc(c, stdin);
    scanf("%d", &yylval);
    return NUMBER;
  }
  if (c == EOF) return 0;
  return c; // everything else is a token
}