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.^[1] Franklin DeRemer esitteli käyttökelpoisen LALR-parserin väitöskirjassaan vuonna 1969.^[2]

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.^[3] Alan Snyder käänsi yaccin uudelle C-ohjelmointikielelle.^[4] Yaccin virallinen kuvaus julkaistiin 1975.^[5]

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.^[6] Richard Stallman teki siitä Yacc-yhteensopivan.^[7] 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.^[8]

1. ↑ Isoaho, LR-jäsennyksen toiminta ja käyttökohteet § 3.1 LR-jäsennyksen historiasta, URN:NBN:fi:jyu-201805132553.pdf
2. ↑ https://web.archive.org/web/20130819012838/http://publications.csail.mit.edu/lcs/pubs/pdf/MIT-LCS-TR-065.pdf
3. ↑ The A-Z of Programming Languages: YACC - a-z of programming languages - Operating Systems - Techworld web.archive.org. 31.1.2013. Arkistoitu 31.1.2013. Viitattu 2.1.2024.
4. ↑ Dennis, M. Ritchie, THE DEVELOPMENT OF THE C PROGRAMMING LANGUAGE § 14.11 S U C C E S S O R S [1]
5. ↑ Johnson, Stephen C. (1975). Yacc: Yet Another Compiler-Compiler (Technical report). Murray Hill, New Jersey: AT&T Bell Laboratories. [2]
6. ↑ Static Semantics and Compiler Error Recovery web.archive.org. 8.6.2017. Arkistoitu 8.6.2017. Viitattu 2.1.2024.
7. ↑ AUTHORS - bison.git - GNU bison (git mirror) git.savannah.gnu.org. Viitattu 2.1.2024.
8. ↑ BYACC – Berkeley Yacc – generate LALR(1) parsers invisible-island.net. Viitattu 2.1.2024.