| Yacc | |
|---|---|
| Kehittäjä | Stephen Johnson |
| Kehityshistoria | |
| Vakaa versio | Unknown |
| Tiedot | |
| Ohjelmointikielet | C |
| Lisenssi | Unknown |
| Aiheesta muualla | |
| Versiohallinta | |
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. 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.
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
}