Yacc

elemző generátor From Wikipedia, the free encyclopedia

Remove ads

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[1]) generál egy formális nyelvtan alapján, amely a Backus-Naur formához (BNF) hasonló jelöléssel íródott.[2] A BSD és az AT&T Unix szabványos segédprogramként szállítja az Yacc-t.[3] A GNU-alapú Linux disztribúciók tartalmazzák a Bison-t(wd), egy előre kompatibilis(wd)[4] Yacc helyettesítő programot.[5]

Gyors adatok
Remove ads

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[6] (amelyet McIlroy TMG(wd)[7] fordító-fordítójának(wd)[8] felhasználásával fejlesztett ki[9]), de ez nehéz feladatnak bizonyult. Ennek eredményeként a Bell Labs-nél dolgozó kollégája, Al Aho(wd)[10] irányította Donald Knuth LR-elemzéssel(wd)[11] kapcsolatos munkájához[12], amely az Yacc alapjául szolgált.[6] Az Yacc a TMG fordító-fordítóra[13] volt hatással, és a TMG fordító-fordítóra utalva (Még egy fordító-fordító) kapta a nevét.[14]

Az Yacc eredetileg B programozási nyelven íródott, de hamarosan Alan Snyder átírta C nyelven.[9] A Unix 3-as verziójának(wd)[15] részeként jelent meg,[16] és az Yacc teljes leírása 1975-ben jelent meg.[13]

Johnson az Yacc-t használta a Portable C Compiler(wd)[17] megalkotásához.[16] 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”.[18] 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),[19] a C++ első implementációját.[20]

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”.[21]

Remove ads

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.[22] A tipikus műveletek közé tartozik az elemzési fák(wd) felépítése.[23] 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)[24] é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)[25] elemeire utalnak.[26]

Az Yacc csak egy elemzőt (phrase analyzer) állít elő, amely egyedül is használható szkenner nélküli elemzés[27] 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[28] szakaszt végez (szóelemzés), amelyet aztán a tényleges elemzési szakasz követ.[13] 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[29] meghatározza a Lex és az Yacc funkcióit és követelményeit.[30]

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ő.[31]

Remove ads

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[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);
}

Lexical analyzer (calc.lex):

%{
 
#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);
               }

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.

Remove ads

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.[32]

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.[33]

Az Yacc segítségével elsőként megvalósított nyelvek között szerepel az AWK, a C++,[20] az eqn(wd) és a Pic(wd).[34] 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(wd) stb.[16][35]

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

  • 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.[40]
  • 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.
Remove ads

Lásd még

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

Jegyzetek

További információk

Fordítás

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads
Remove ads