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.Isoaho, LR-jäsennyksen toiminta ja käyttökohteet § 3.1 LR-jäsennyksen historiasta, URN:NBN:fi:jyu-201805132553.pdf Franklin DeRemer esitteli käyttökelpoisen LALR-parserin väitöskirjassaan vuonna 1969.https://web.archive.org/web/20130819012838/http://publications.csail.mit.edu/lcs/pubs/pdf/MIT-LCS-TR-065.pdf

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. Yaccille on vaihtoehtona 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 }

Lähteet

Luokka:Ohjelmointityökalut Luokka:Unix-ohjelmat Luokka:Vuoden 1971 ohjelmistot