Yacc - Yacc

Yacc
Pierwotny autor (autorzy) Stephen C. Johnson
Magazyn Edytuj to na Wikidata
System operacyjny Unix , uniksopodobny , plan 9 , piekło
Platforma Wieloplatformowy
Rodzaj Komenda

Yacc ( Yet Another Compiler-Compiler ) to program komputerowy dla systemu operacyjnego Unix opracowany przez Stephena C. Johnsona . Jest to generator parserów Look Ahead Left-to-Right (LALR) , generujący parser LALR (część kompilatora, która próbuje nadać kodowi źródłowemu sens składniowy ) w oparciu o formalną gramatykę napisaną w notacji podobnej do Backus –Formularz Naura (BNF) . Yacc jest dostarczany jako standardowe narzędzie w BSD i AT&T Unix. Dystrybucje Linuksa oparte na GNU zawierają Bison , kompatybilny z nowszymi wersjami Yacc.

Historia

W roku 1970, Stephen C. Johnson , informatyk w Bell Labs / AT & T , opracowany Yacc bo chciał włożyć wyłącznym lub operator do języka B kompilatora (opracowanego przy użyciu McIlroy „s TMG Generator Parserów), ale okazało się trudnym zadaniem. W rezultacie został skierowany przez swojego kolegę z Bell Labs Al Aho do pracy Donalda Knutha nad parsowaniem LR , które posłużyło jako podstawa Yacc. Yacc był pod wpływem i otrzymał swoją nazwę w odniesieniu do kompilatora-kompilatora TMG.

Yacc został pierwotnie napisany w języku programowania B , ale wkrótce został przepisany w C . Pojawił się jako część wersji 3 Unix , a pełny opis Yacc został opublikowany w 1975 roku.

Johnson użył Yacc do stworzenia Portable C Compiler . Bjarne Stroustrup również próbował użyć Yacc do swojej początkowej pracy nad C++ , ale "został pokonany przez składnię C" (która zawiera na przykład operatory przedrostkowe i przyrostkowe).

W wywiadzie z 2008 roku Johnson stwierdził, że „ jestem najbardziej dumny z wkładu Yacc w rozpowszechnianie Uniksa i C ”.

Opis

Dane wejściowe do Yacc to gramatyka z fragmentami kodu C (zwanymi "akcjami") dołączonymi do jego reguł. Jego wyjściem jest parser shift-reduce w C, który wykonuje fragmenty C powiązane z każdą regułą, gdy tylko reguła zostanie rozpoznana. Typowe działania obejmują budowę drzew parsowania . Korzystając z przykładu z Johnsona, jeśli węzeł wywołania (etykieta, lewy, prawy) konstruuje binarny węzeł drzewa analizy z określoną etykietą i dziećmi, wówczas reguła

expr : expr '+' expr  { $$ = node('+', $1, $3); }

rozpoznaje wyrażenia sumujące i konstruuje dla nich węzły. Specjalne identyfikatory $$ , $1 i $3 odnoszą się do elementów na stosie parsera .

Yacc tworzy tylko parser (analizator fraz); dla pełnej analizy składniowej wymaga to zewnętrznego analizatora leksykalnego do wykonania pierwszego etapu tokenizacji (analizy słów), po którym następuje właściwy etap parsowania. Generatory analizatorów leksykalnych, takie jak Lex lub Flex , są powszechnie dostępne. Standard IEEE POSIX P1003.2 definiuje funkcjonalność i wymagania zarówno dla Lex, jak i Yacc.

Niektóre wersje AT&T Yacc stały się open source . Na przykład kod źródłowy jest dostępny w standardowych dystrybucjach Planu 9 .

Wpływ

Programy Yacc i podobne (w dużej mierze reimplementacje) cieszą się dużą popularnością. Sam Yacc był kiedyś dostępny jako domyślny generator parsera w większości systemów uniksowych, chociaż od tego czasu został wyparty przez nowsze, w dużej mierze kompatybilne programy, takie jak Berkeley Yacc , GNU Bison , MKS Yacc i Abraxas PCYACC. Zaktualizowana wersja oryginalnego AT&T Yacc jest częścią projektu OpenSolaris firmy Sun. Każdy oferuje niewielkie ulepszenia i dodatkowe funkcje w stosunku do oryginalnego Yacc, ale koncepcja i podstawowa składnia pozostały takie same.

Wśród języków, które zostały po raz pierwszy zaimplementowane w Yacc, są AWK , eqn i Pic . Yacc był również używany na Uniksie do implementacji Portable C Compiler , jak również parserów dla takich języków programowania jak FORTRAN 77 , Ratfor , APL , bc , m4 , itp.

Yacc został również przepisany na inne języki, w tym OCaml , Ratfor , ML , Ada , Pascal , Java , Python , Ruby , Go , Common Lisp i Erlang .

Zobacz też

Bibliografia

Linki zewnętrzne