Ugrás a tartalomhoz

Yacc

Ellenőrzött
A Wikipédiából, a szabad enciklopédiából
Yacc
FejlesztőStephen C. Johnson
Programozási nyelvC
Operációs rendszerUnix, Unix-like, Plan 9, Inferno
Platformplatformfüggetlen
Kategóriacommand
LicencPlan 9: MIT License(wd)
A Yacc weboldala

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]

Története

[szerkesztés]

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]

Leírás

[szerkeszté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]

Számológép példa

[szerkesztés]
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):

[szerkesztés]
%{
#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):

[szerkesztés]
%{
 
#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:

[szerkesztés]

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

[szerkesztés]

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]

Lásd még

[szerkesztés]

Jegyzetek

[szerkesztés]
  1. ↑ Az 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.
  2. ↑ The A-Z of Programming Languages: YACC. Computerworld. [2013. január 31-i dátummal az eredetiből archiválva]. (Hozzáférés: 2012. november 30.)
  3. ↑ Levine, John. Lex & yacc. O'Reilly & Associates, xx. o. (1992). ISBN 1-56592-000-7 
  4. ↑ A 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.
  5. ↑ Levine, John. Flex & bison. O'Reilly Media, xv. o. (2009). ISBN 978-0-596-15597-1 
  6. ↑ a b „Stephen Curtis Johnson: Geek of the Week”, Red Gate Software, 2009. október 1. (Hozzáférés: 2018. január 19.) 
  7. ↑ A TMG (TransMoGrifier) ​​egy recursive-descent parser(wd) fordító-fordító, amelyet Robert M. McClure fejlesztett ki és mutatott be 1965-ben.
  8. ↑ Az 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.
  9. ↑ a b Ritchie, Dennis M. (Dennis MacAlistair Ritchie) (1993. április 1.). „The Development of the C Language”., Association for Computing Machinery, Inc.. doi:10.1145/234286.1057834. „After the TMG version of B was working, Thompson rewrote B in itself(a bootstrapping step).…When Johnson returned to Bell Labs in 1973, he was disconcerted to find that the language whose seeds he had brought to Canada had evolved back home; even his own yacc program had been rewritten in C, by Alan Snyder.” 
  10. ↑ Alfred 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(wd) és Brian Kernighan mellett.
  11. ↑ Az LR-elemzőknek számos változata létezik: SLR-parser(wd), LALR parser(wd), kanonikus LR(1) értelmező(wd), minimális LR(1) értelmező és általánosított LR értelmező (GLR parser(wd)).
  12. ↑ A számítástechnikában az LR elemzők olyan alulról felfelé építkező elemzők(wd), amelyek lineáris időben elemzik a determinisztikus kontextusmentes nyelveket(wd).
  13. ↑ a b c Johnson, Stephen C.: Yacc: Yet Another Compiler-Compiler. AT&T Bell Laboratories, 1975. (Hozzáférés: 2020. január 31.)
  14. ↑ Early Translator Writing Systems. Atlas Computer Laboratory
  15. ↑ A Research Unix a Unix operációs rendszer korai verziói a DEC PDP-7(wd), PDP-11, VAX és Interdata 7/32 és 8/32(wd) számítógépekhez.
  16. ↑ a b c A Research Unix reader: annotated excerpts from the Programmer's Manual, 1971–1986, 1987
  17. ↑ A Portable C Compiler (más néven pcc) egy korai fordító a C programozási nyelvhez.
  18. ↑ Stroustrup, Bjarne: A History of C++: 1979−1991
  19. ↑ 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.
  20. ↑ a b Stroustrup, Bjarne: Cfront source code
  21. ↑ „Yacc, Unix, and advice from Bell Labs alumni Stephen Johnson”, 2008. július 9.. [2020. augusztus 22-i dátummal az eredetiből archiválva] (Hozzáférés: 2020. november 10.) 
  22. ↑ 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.
  23. ↑ 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.
  24. ↑ A 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.
  25. ↑ A 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.
  26. ↑ Johnson, Stephen C (1975). Yacc: Yet Another Compiler-Compiler (Technical report). Murray Hill, New Jersey: AT&T Bell Laboratories. 32. Retrieved 31 January 2020.
  27. ↑ A 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(wd) (a karakterfolyamot szavakra bontja) és az elemzést (a szavak mondatokká rendezése), ahelyett, hogy egy lexer(wd) és egy elemző által párhuzamosan végrehajtott csővezetékre bontaná azt.
  28. ↑ A lexikális token egy hozzárendelt és így azonosított jelentéssel rendelkező karakterlánc.
  29. ↑ ISO/IEC/IEEE 9945:2009
  30. ↑ 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.
  31. ↑ plan9: UC Berkeley release of Plan 9 under the GPLv2. GitHub , 2017. december 26. (Hozzáférés: 2018. január 2.)
  32. ↑ Bison Manual: History
  33. ↑ The Insider's Guide To The Universe. Charles River Data Systems, Inc., 13. o. (1983) 
  34. ↑ UNIX Special: Profs Kernighan & Brailsford. Computerphile, 2015. szeptember 30. [2021. december 11-i dátummal az eredetiből archiválva].
  35. ↑ The Unix Programming Environment. Prentice Hall (1984). ISBN 0-13-937681-X 
  36. ↑ OCaml User's Manual: Chapter 12 Lexer and parser generators (ocamllex, ocamlyacc). (Hozzáférés: 2013. november 25.)
  37. ↑ Yacc.go: A version of Yacc for the Go Programming Language. (Hozzáférés: 2017. július 15.)
  38. ↑ CL-Yacc: A Common Lisp version of Yacc
  39. ↑ yecc: An Erlang implementation of Yacc
  40. ↑ John Levine (August 2009), flex & bison, O'Reilly Media

További információk

[szerkesztés]

Fordítás

[szerkeszté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.
A lap eredeti címe: „https://hu.wikipedia.org/w/index.php?title=Yacc&oldid=27722211”