Yacc (Yet Another Compiler-Compiler) egy számítógépes program a Unix operációs rendszerhez, amelyet Stephen C. Johnson fejlesztett ki. Ez egy előretekintő balról jobbra elemző (LALR) parser generátor, amely egy LALR elemzőt (a fordítónak azt a részét, amely megpróbálja megérteni a forráskódotAz informatikában az LALR elemző (look-ahead, left-to-right, rightmost derivation parser; look-ahead, left-to-right, rightmost derivation parser) a fordítási folyamat része, ahol az ember által olvasható szöveget strukturált reprezentációvá alakítják, amelyet a számítógépek elolvashatnak.) generál egy formális nyelvtan alapján, amely a Backus-Naur formához (BNF) hasonló jelöléssel íródott. A BSD és az AT&T Unix szabványos segédprogramként szállítja az Yacc-t. A GNU-alapú Linux disztribúciók tartalmazzák a Bison-t, egy előre kompatibilisA jövőbeli (forward compatibility) vagy felfelé irányuló (upward compatibility) kompatibilitás olyan tervezési jellemző, amely lehetővé teszi a rendszer számára, hogy elfogadja a saját egy későbbi verziójához szánt bemenetet. Yacc helyettesítő programot.
Története Az 1970-es évek elején Stephen C. Johnson, a Bell Labs/AT&T informatikusa fejlesztette ki az Yacc-ot, mert kizáró vagy operátort (XOR) akart beilleszteni egy B nyelvű fordítóba (amelyet McIlroy TMGA TMG (TransMoGrifier) egy recursive-descent parser fordító-fordító, amelyet Robert M. McClure fejlesztett ki és mutatott be 1965-ben. fordító-fordítójánakAz informatikában a fordító-fordító (compiler-compiler) vagy fordítógenerátor (compiler generator) olyan programozási eszköz, amely egy programozási nyelv és gép valamilyen formális leírásából elemzőt (parser), értelmezőt (interpreter) vagy fordítót (compiler) hoz létre. felhasználásával fejlesztett ki), de ez nehéz feladatnak bizonyult. Ennek eredményeként a Bell Labs-nél dolgozó kollégája, Al AhoAlfred Vaino Aho (született: 1941. augusztus 9.) kanadai informatikus, aki leginkább programozási nyelvekkel, fordítóprogramokkal és kapcsolódó algoritmusokkal kapcsolatos munkáiról, valamint a számítógépes programozás művészetéről és tudományáról szóló tankönyveiről ismert. Az awk nyelv társszerzője, Peter Weinberger és Brian Kernighan mellett. irányította Donald Knuth LR-elemzésselAz LR-elemzőknek számos változata létezik: SLR-parser, LALR parser, kanonikus LR(1) értelmező, minimális LR(1) értelmező és általánosított LR értelmező (GLR parser). kapcsolatos munkájáhozA számítástechnikában az LR elemzők olyan alulról felfelé építkező elemzők, amelyek lineáris időben elemzik a determinisztikus kontextusmentes nyelveket., amely az Yacc alapjául szolgált. Az Yacc a TMG fordító-fordítóra volt hatással, és a TMG fordító-fordítóra utalva (Még egy fordító-fordító) kapta a nevét.
Az Yacc eredetileg B programozási nyelven íródott, de hamarosan Alan Snyder átírta C nyelven. A Unix 3-as verziójánakA Research Unix a Unix operációs rendszer korai verziói a DEC PDP-7, PDP-11, VAX és Interdata 7/32 és 8/32 számítógépekhez. részeként jelent meg, és az Yacc teljes leírása 1975-ben jelent meg.
Johnson az Yacc-t használta a Portable C CompilerA Portable C Compiler (más néven pcc) egy korai fordító a C programozási nyelvhez. megalkotásához. Bjarne Stroustrup szintén megpróbálta az Yacc-t használni a C++ formális specifikációjának megalkotásához, de „a C szintaxisa legyőzte”. Bár Stroustrup nem találta alkalmasnak a nyelv formális specifikációjára, mégis az Yacc segítségével implementálta a Cfrontot,1983 körül a Cfront volt a C++ (akkori nevén „C with Classes”) eredeti fordítója, amely a C++-t C-vé alakította; Bjarne Stroustrup fejlesztette ki az AT&T Bell Labs-nál. a C++ első implementációját.
Egy 2008-as interjúban Johnson azt mondta, hogy „az Yacc hozzájárulása a Unix és a C elterjedéséhez az, amire a legbüszkébb vagyok”.
Leírás Az Yacc bemenete egy nyelvtan, amelynek szabályaihoz C kódrészleteket (úgynevezett „akciókat”) csatolnak. A kimenete egy C nyelvű shift-reduce elemző, amely végrehajtja az egyes szabályokhoz tartozó C kódrészleteket, amint a szabály felismerésre kerül.A shift-reduce parser hatékony, táblázatvezérelt alulról felfelé irányuló elemzési módszerek osztálya számítógépes nyelvekhez és más, a nyelvtan által formálisan meghatározott jelölésekhez. A tipikus műveletek közé tartozik az elemzési fák felépítése.Az elemző fa vagy parse tree (más néven származékos fa vagy konkrét szintaxisfa) egy rendezett, gyökeres fa, amely valamilyen környezetfüggetlen nyelvtan szerint egy karakterlánc szintaktikai szerkezetét reprezentálja. Egy Johnson-példát használva, ha a hívás egy bináris elemzési fa-csomópontotA csomópont (node) egy adatstruktúra alapegysége, például egy láncolt lista vagy fa adatstruktúra. A csomópontok adatokat tartalmaznak, és más csomópontokra is hivatkozhatnak. A csomópontok közötti kapcsolatokat gyakran mutatók valósítják meg. épít a megadott címkével (label) és gyermekekkel, akkor a szabály expr : expr '+' expr { $$ = node('+', $1, $3); } felismeri az összegző kifejezéseket, és csomópontokat hoz létre számukra. A speciális azonosítók , és az elemző verménekA számításelméletben, az elméleti számítástechnika egyik ágában, a pushdown automata egy olyan típusú automata, amely egy vermet (stack) alkalmaz. elemeire utalnak.Johnson, Stephen C (1975). Yacc: Yet Another Compiler-Compiler (Technical report). Murray Hill, New Jersey: AT&T Bell Laboratories. 32. Retrieved 31 January 2020.
Az Yacc csak egy elemzőt (phrase analyzer) állít elő, amely egyedül is használható szkenner nélküli elemzésA számítástechnikában a szkenner nélküli elemzés (scannerless parsing vagy lexerless parsing) egyetlen lépésben végzi a tokenizálást (a karakterfolyamot szavakra bontja) és az elemzést (a szavak mondatokká rendezése), ahelyett, hogy egy lexer és egy elemző által párhuzamosan végrehajtott csővezetékre bontaná azt. esetén, azonban a teljes szintaktikai elemzéshez általában egy külső lexikai elemzőre van szükség, amely először egy tokenizálásiA lexikális token egy hozzárendelt és így azonosított jelentéssel rendelkező karakterlánc. szakaszt végez (szóelemzés), amelyet aztán a tényleges elemzési szakasz követ. Erre a célra széles körben elérhetőek lexikai elemző generátorok, mint például a Lex vagy a Flex. Az IEEE POSIX P1003.2 szabványISO/IEC/IEEE 9945:2009 meghatározza a Lex és az Yacc funkcióit és követelményeit.lex – Shell and Utilities Reference, The Single UNIX Specification, Version 4 from The Open Group, yacc – Shell and Utilities Reference, The Single UNIX Specification, Version 4 from The Open Group.
Az AT&T Yacc néhány verziója nyílt forráskódúvá vált. A forráskód például a Plan 9 standard disztribúcióival együtt elérhető.
Számológép példa Példaprogram a lex és yacc programokhoz Ezek a példaprogramok együtt egy egyszerű, asztali számológépet hoznak létre, amely összeadási, kivonási, szorzási és osztási műveleteket hajt végre. Ez a számolóprogram azt is lehetővé teszi, hogy értékeket rendeljen a változókhoz (mindegyik kisbetűvel van jelölve), majd a változókat számításokban használja. A példa lex és yacc programokat tartalmazó fájlok a következők: calc.lex – A lex fájl meghatározza a lexikális elemzési szabályokat. calc.yacc – Megadja az yacc parancs nyelvtani fájlját, amely meghatározza az elemzési szabályokat, és meghívja a lex parancs által létrehozott yylex szubrutint a bemenet biztosítására.
A következő leírások feltételezik, hogy a calc.lex és calc.yacc example példaprogramok az aktuális könyvtárban találhatók.
A példaprogram fordítása
A számológép példa programjának elkészítéséhez a következő lépéseket kell sorrendben végrehajtani:
1. Az yacc nyelvtani fájl feldolgozása a -d opcionális kapcsolóval (amely arra utasítja az yacc parancsot, hogy hozzon létre egy fájlt, amely meghatározza a C nyelv forráskódja mellett használt tokeneket): yacc -d calc.yacc
2. Az ls paranccsal ellenőrizhető, hogy a következő fájlok létrejöttek-e: y.tab.c – A C nyelvű forrásfájl, amelyet az yacc parancs hozott létre az értelmező számára. y.tab.h – Fejlécfájl, amely definiálási utasításokat tartalmaz az elemző által használt tokenekhez.
3. A lex specifikációs fájl feldolgozása: lex calc.lex
4. Az ls parancs ellenőrzi, hogy a következő fájl létrejött-e: lex.yy.c – A C nyelvű forrásfájl, amelyet a lex parancs a lexikai elemző számára létrehozott.
5. Fordítsa le és linkelje a két C nyelvű forrásfájlt: cc y.tab.c lex.yy.c
6. Az ls paranccsal ellenőrizze, hogy a következő fájlok létrejöttek-e: y.tab.o – Az y.tab.c object-fájl lex.yy.o – A lex.yy.c object-fájlja a.out – A futtatható programfájl A program futtatásához írja be: $ a.out
Vagy nevezze át és úgy futtassa: $ mv a.out calculate $ calculate
Mindkét esetben a program elindítása után a kurzor a $ (parancssor) alatti sorba kerül. Ezután számokat és operátorokat írunk be számológépes módon. Az Enter billentyű megnyomásakor a program megjeleníti a művelet eredményét. Miután értéket rendel egy változóhoz: m=4 <enter> _
a kurzor a következő sorra lép. Amikor a változót a következő számításokban használja, a változó a hozzárendelt értékkel fog rendelkezni: m+5 <enter> 9 _
Parser (calc.yacc file) %{ #include <stdio.h>
int regs; int base;
%}
%start list
%token DIGIT LETTER
%left '|' %left '&' %left '+' '-' %left '*' '/' '%' %left UMINUS /* elsőbbséget biztosít az unáris mínuszhoz */
%% /* szabályok szakasz eleje */
list: /*empty */
list stat '\n'
list error '\n'
yyerrok;
stat: expr
printf("%d\n",$1);
LETTER '=' expr
regs[$1] = $3;
expr: '(' expr ')'
$$ = $2;
expr '*' expr
$$ = $1 * $3;
expr '/' expr
$$ = $1 / $3;
expr '%' expr
$$ = $1 % $3;
expr '+' expr
$$ = $1 + $3;
expr '-' expr
$$ = $1 - $3;
expr '&' expr
$$ = $1 & $3;
expr '|' expr
$$ = $1 | $3;
'-' expr %prec UMINUS
$$ = -$2;
LETTER
$$ = regs[$1];
number
number: DIGIT
$$ = $1; base = ($1==0) ? 8 : 10;
number DIGIT
$$ = base * $1 + $2;
%% main() { return(yyparse()); }
yyerror(s) char *s; { fprintf(stderr, "%s\n",s); }
yywrap() { return(1); }
Lexical analyzer (calc.lex) %{
#include <stdio.h> #include "y.tab.h" int c; extern int yylval; %} %% " " ; [a-z] { c = yytext; yylval = c - 'a'; return(LETTER);
[0-9] { c = yytext; yylval = c - '0'; return(DIGIT);
[^a-z0-9\b] { c = yytext; return(c);
Megjegyzések Annak ellenére, hogy a példák a C nyelv szintaxisára hasonlítanak, azok nem C-programok, hanem az yacc és a lex forrásprogramjai.Az itt ismertetett példaprogram megfelelő környezetben (UNIX/Linux) lefordítható és működőképes.
Hatása Az Yacc és a hasonló programok (nagyrészt újraimplementációk) nagyon népszerűek voltak. Maga az Yacc a legtöbb Unix rendszerben alapértelmezett elemzőgenerátorként volt elérhető, bár azóta olyan újabb, nagyrészt kompatibilis programok váltották fel, mint a Berkeley Yacc, a GNU Bison, az MKS Yacc és az Abraxas PCYACC. Az eredeti AT&T Yacc frissített változata a Sun OpenSolaris projekt részeként szerepel. Mindegyik kisebb javításokat és további funkciókat kínál az eredeti Yacc-hoz képest, de a koncepció és az alapvető szintaxis ugyanaz maradt.Bison Manual: History
Az Yacc egyike volt a Charles River Data Systems UNOS operációs rendszeréhez Bell Laboratories licenc alapján elérhető UNIX eszközöknek.
Az Yacc segítségével elsőként megvalósított nyelvek között szerepel az AWK, a C++, az eqn és a Pic. Az Yacc-t Unixon is használták a Portable C Compiler, valamint olyan programozási nyelvek elemzőinek implementálására, mint a FORTRAN 77, Ratfor, APL, bc, m4 stb.
Az Yacc-t más nyelvekre is átírták, többek között OCaml, Ratfor, ML, Ada, Pascal, Java, PHP, Python, Ruby, Go, Common Lisp és Erlang nyelvekre.
Berkeley Yacc: Az Yacc Berkeley megvalósítása gyorsan népszerűbbé vált, mint maga az AT&T Yacc a teljesítménye és az újrahasználati korlátozások hiánya miatt. LALR parser: Az alapul szolgáló elemzési algoritmus az Yacc által generált értelmezőkben. Bison: Az Yacc GNU verziója.