Yacc - Yacc
Pierwotny autor (autorzy) | Stephen C. Johnson |
---|---|
Magazyn | |
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 .
- Berkeley Yacc : Implementacja Yacc w Berkeley szybko stała się bardziej popularna niż sama AT&T Yacc ze względu na jej wydajność i brak ograniczeń ponownego użycia.
- Parser LALR : Podstawowy algorytm parsowania w parserach generowanych przez Yacc.
- Bison : wersja GNU Yacc.
- Lex (i analizator leksykalny Flex ), parser tokenów powszechnie używany w połączeniu z Yacc (i Bison).
- BNF to metaskładnia używana do wyrażania gramatyk bezkontekstowych : jest to formalny sposób opisu języków bezkontekstowych.
- PLY (Python Lex-Yacc) to alternatywna implementacja Lexa i Yacc w Pythonie.
Zobacz też
Bibliografia
Linki zewnętrzne
- The Single UNIX Specification , wydanie 7 od The Open Group – Commands & Utilities Reference,
- Plan 9 , tom 1 – Podręcznik programisty
- Instrukcja poleceń ogólnych Inferno –