Yacc

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(wd)) parser generátor, amely egy LALR elemzőt(wd) (a fordítónak azt a részét, amely megpróbálja megérteni a forráskódot) 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(wd), egy előre kompatibilis(wd) Yacc helyettesítő programot.

Története

Az 1970-es évek elején Stephen C. Johnson, a Bell Labs/AT&T(wd) informatikusa fejlesztette ki az Yacc-ot, mert kizáró vagy(wd) operátort (XOR) akart beilleszteni egy B nyelvű fordítóba (amelyet McIlroy TMG(wd) fordító-fordítójának(wd) 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 Aho(wd) irányította Donald Knuth LR-elemzéssel(wd) kapcsolatos munkájához, 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ának(wd) 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 Compiler(wd) 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(wd), 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ő(wd), amely végrehajtja az egyes szabályokhoz tartozó C kódrészleteket, amint a szabály felismerésre kerül. A tipikus műveletek közé tartozik az elemzési fák(wd) felépítése. Egy Johnson-példát használva, ha a node(label, left, right) hívás egy bináris elemzési fa-csomópontot(wd) é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 $$, $1 és $3 az elemző vermének(wd) elemeire utalnak.

Az Yacc csak egy elemzőt (phrase analyzer) állít elő, amely egyedül is használható szkenner nélküli elemzés esetén, azonban a teljes szintaktikai elemzéshez általában egy külső lexikai elemzőre(wd) van szükség, amely először egy tokenizálási 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(wd). Az IEEE POSIX P1003.2 szabvány meghatározza a Lex és az Yacc funkcióit és követelményeit.

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

_

%{
#include <stdio.h>

int regs[26];
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);
}

%{
 
#include <stdio.h>
#include "y.tab.h"
int c;
extern int yylval;
%}
%%
" "       ;
[a-z]     {
            c = yytext[0];
            yylval = c - 'a';
            return(LETTER);
          }
[0-9]     {
            c = yytext[0];
            yylval = c - '0';
            return(DIGIT);
          }
[^a-z0-9\b]    {
                 c = yytext[0];
                 return(c);
               }

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(wd), a GNU Bison(wd), az MKS(wd) 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.

Az Yacc egyike volt a Charles River Data Systems UNOS(wd) 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(wd) és a Pic(wd). Az Yacc-t Unixon is használták a Portable C Compiler(wd), valamint olyan programozási nyelvek elemzőinek implementálására, mint a FORTRAN 77, Ratfor(wd), APL, bc, m4 stb.

Az Yacc-t más nyelvekre is átírták, többek között OCaml(wd), Ratfor(wd), ML, Ada, Pascal, Java, PHP, Python, Ruby, Go, Common Lisp és Erlang nyelvekre.

• Berkeley Yacc(wd): 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(wd): Az alapul szolgáló elemzési algoritmus az Yacc által generált értelmezőkben.
• Bison(wd): Az Yacc GNU verziója.
• Lex (and Flex lexical analyser(wd)), egy token elemző, amelyet általában az Yacc-al (és a Bison-nal) használnak.
• BNF egy metaszintaxis(wd), amelyet a környezetfüggetlen nyelvtan kifejezésére használnak: ez egy formális módja a kontextusmentes nyelvek leírásának.
• PLY (Python Lex-Yacc)(wd) a Lex és az Yacc alternatív megvalósítása Pythonban.

Lásd még

• Compiler-compiler(wd)
• hoc (programming language)(wd)

Jegyzetek

További információk

• Homokozó környezet a szintaxis tanulásához és teszteléséhez
• yacc Unix Manual
• yacc(1) – Linux kézikönyv
• ANSI C Yacc nyelvtan és Lex specifikáció
• The Single UNIX Specification

Fordítás

• Ez a szócikk részben vagy egészben a Yacc című angol Wikipédia-szócikk fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.