Yacc
Računarski program yacc je generator parsera, koji je razvio Stiven C. Džonson iz kompanije AT&T za operativni sistem Juniks. Ime predstavlja skraćenicu još jedan kompilator kompilatora (engl. Yet Another Compiler Compiler). On generiše parser (deo kompilatora koji pokušava da sintaksno obradi izvodni kod) na osnovu formalne gramatike zapisane u formi sličnoj BNF. Yacc generiše kod za parser u programskom jeziku C.
Yacc je dugo bio dostupan kao podrazumevani generator parsera na većini Juniks sistema. Međutim, danas je u velikoj meri zamenjen novijim, ali u velikoj meri kompatibilnim programima, kao što su Berkeley Yacc, GNU bison, MKS yacc i Abraxas pcyacc. Osamrevenjena verzija originalnog AT&T programa je dostupna kao deo Sanovog projekta OpenSolaris. Svaki od ovih programa pruža sitna poboljšanja i dodatne opcije u odnosu na originalni yacc, ali je koncept ostaio isti. Yacc je takođe napisan i za druge programske jezike, uključujući Ratfor, EFL, ML, Ada, Java, i Limbo.
Parseru koji generiše yacc je neophodan leksički analizator. Generatori leksičkih analizatora, kao što su Lex ili Flex su široko dostupni. IEEE POSIX P1003.2 standard definiše funkcionalnost i zahteve i za Lex i za Yacc.
Rad yacc-а zasniva se na metodi LALR(1)-analize. Ulaz u sistem yacc predstavlja izvorna datoteka koja sadrži opis pravila kontekstno slobodne gramatike. Opisi pravila gramatike proširuju se semantičkim akcijama koje predstavljaju programski kod u C-u koji se izvršava kada se prepozna određeni deo ulaza. Rezultat rada yacc-а je datoteka koja se obično naziva y.tab.c. Nju je potrebno prevesti nekim C prevodiocem i povezati sa ostatkom programa koji pišemo da bismo dobili izvršnu verziju programa.
Struktura ulazne datoteke
[uredi | uredi izvor]Ulazna datoteka yacc sistema obično ima ekstenziju .c i sastoji se iz tri dela međusobno razdvojena separatorom %%:
Prvi deo je deo deklaracija koji sadrži deklaracije svih tokena gramatike. U njemu se navodi i prioritet i asocijativnost operatora ukoliko je potrebno i vrši deklarisanje tipa atributa simbola date gramatike. U ovom delu se mogu definisati i deklarisati razni globalni objekti na jeziku C koji se kasnije mogu koristiti u svim akcijama koje vrše obradu ulaza. Taj C kod se navodi između %{ i %}.
Centralni deo je deo pravila u kome su navedena gramatička pravila proširena akcijama koje predstavljaju kod koji se izvršava kada se prepozna deo ulaza opisan tim pravilom.
Treći deo je deo funkcija koji sadrži funkcije pisane u programskom jeziku C. One se, bez ikakve obrade, dopisuju na odgovarajuća mesta u y.tab.c datoteku. U ovom delu se obično nalaze i definicije funkcije main() i funkcije yylex() koja vrši fazu leksičke analize.
Vidi još
[uredi | uredi izvor]- GNU bison: GNU verzija yacc-a
- LALR parser: algoritam za parsiranje koji se nalazi u pozadini yacc-a
- Lex i Flex, leksički analizatori koji se najčešće koriste zajedno sa yacc-om (Bison-om)
Literatura
[uredi | uredi izvor]- Stephen C. Johnson. YACC: Yet another compiler-compiler. Unix Programmer's Manual Vol 2b, 1979.
Spoljašnje veze
[uredi | uredi izvor]- Tutorial lex/yacc/kompilator tutorijal
- Berkeley Yacc varijanta yacc-a koja je napisana da bi se izbegla zavisnost od bilo kog konkretnog kompajlera za C
- Yaxx varijanta yacc-a koja je napisana da bi se izbegla zavisnost od bilo kog konkretnog programskog jezika
- Essence, generator parsera za Scheme
- CL-Yacc, generator parsera za Lisp
- Eyapp, proširenje yacc-a za Perl