Yacc

Yacc
Originalautor (en) Stephen C. Johnson
Repository
Geschrieben in C
Betriebssystem Unix, Unix-artig, Plan 9, Inferno
Plattform Plattformübergreifend
Typ Befehl
Lizenz Plan 9: MIT -Lizenz

Yacc (Ein weiterer Compiler-Compiler) ist ein Computer Programm für die Unix Betriebssystem entwickelt von durch Stephen C. Johnson. Es ist ein Schauen Sie nach links nach rechts die Ableitung (LALR) Parser Generator, erzeugen a Lalr Parser (der Teil von a Compiler das versucht, syntaktisch Sinn für das zu machen Quellcode) basierend auf a formelle Grammatik, geschrieben in einer ähnlichen Notation wie Backus -Naur -Form (BNF).[1] YACC wird als Standard -Dienstprogramm für BSD und AT & T UNIX geliefert.[2] GNU-basierend Linux Verteilungen umfassen Bison, a Vorwärtskompatibel Yacc -Austausch.[3]

Geschichte

In den frühen 1970er Jahren, Stephen C. Johnson, ein Informatiker bei Bell Labs / AT&T, entwickelte yacc, weil er eine einfügen wollte Exklusiv oder Operator in a B Sprache Compiler (entwickelt mit Verwendung McIlroy's Tmg Compiler-Compiler[4]), aber es stellte sich als schwierige Aufgabe heraus. Infolgedessen wurde er von seinem Kollegen bei Bell Labs geleitet Al Aho zu Donald Knutharbeitet an LR Parsen, was als Grundlage für yacc. diente.[5] Yacc wurde von beeinflusst von[6] und erhielt seinen Namen in Bezug auf TMG Compiler-Compiler.[7]

Yacc wurde ursprünglich in der geschrieben B Programmiersprache, wurde aber bald umgeschrieben C.[4] Es erschien als Teil von Version 3 Unix,[8] und eine vollständige Beschreibung von YACC wurde 1975 veröffentlicht.[6]

Johnson benutzte yacc, um die zu erstellen Tragbarer C -Compiler.[8] Bjarne Stroustrup Auch versucht, YACC zu verwenden, um eine formale Spezifikation von zu erstellen C ++, aber "wurde von Cs Syntax besiegt".[9] Während es für eine formale Spezifikation der Sprache ungeeignet war CFRONTdie erste Implementierung von C ++.[10]

In einem Interview von 2008 dachte Johnson darüber nach, dass "der Beitrag yacc zur Verbreitung von Unix und C ist das, worauf ich stolz am stolzesten bin ".[11]

Beschreibung

Der Eingang zu YACC ist eine Grammatik mit Ausschnitten von C Code (genannt "Aktionen") an seine Regeln angehängt. Seine Ausgabe ist a Shift-Reduce-Parser In C, das die mit jeder Regel verbundenen C -Snippets ausführt, sobald die Regel erkannt wird. Typische Maßnahmen beinhalten die Konstruktion von Bäume analysieren. Verwenden eines Beispiels von Johnson, falls der Anruf Knoten (Etikett, links, rechts) Konstruiert einen binären Parse -Baumknoten mit dem angegebenen Etikett und Kinder, dann die Regel

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

Erkennt Summationsausdrücke und konstruiert Knoten für sie. Die besonderen Kennungen $$, $ 1 und $ 3 Beziehen Sie sich auf Elemente auf dem Parser Stapel.[6]

YACC erzeugt nur einen Parser (Phrase -Analysator); Für die vollständige syntaktische Analyse erfordert dies eine externe Lexikalanalysator Um die erste Tokenisierungsphase (Word -Analyse) durchzuführen, folgt dann die angemessene Analysestufe.[6] Lexikalanalysatorgeneratoren wie z. Lex oder Biegen, sind weit verbreitet. Das IEEE Posix P1003.2 Standard definiert die Funktionalität und Anforderungen für Lex und YACC.[12]

Einige Versionen von AT & T YACC sind geworden Open Source. Zum Beispiel, Quellcode ist mit den Standardverteilungen von erhältlich Plan 9.[13]

Einfluss

YACC und ähnliche Programme (größtenteils Neuauflagen) waren sehr beliebt. YACC selbst war früher als Standard -Parser -Generator für die meisten Unix -Systeme verfügbar, obwohl er seitdem durch neuere, weitgehend kompatible Programme wie z. Berkeley Yacc, Gnu Bison, Mks Yacc und Abraxas Pcyacc. Eine aktualisierte Version des ursprünglichen AT & T YACC wird als Teil von enthalten Sonne OpenSolaris Projekt. Jedes bietet leichte Verbesserungen und zusätzliche Merkmale gegenüber dem ursprünglichen YACC, aber das Konzept und die grundlegende Syntax sind gleich geblieben.[14]

Unter den Sprachen, die erstmals mit YACC implementiert wurden, sind Awk, C ++,[10] EQN und Bild.[15] YACC wurde auch bei Unix verwendet, um die zu implementieren Tragbarer C -Compilersowie Parser für Programmiersprachen wie Forran 77, Ratte, Apl, BC, M4, etc.[8][16]

YACC wurde auch für andere Sprachen umgeschrieben, einschließlich Ocaml,[17] Ratte, Ml, Ada, Pascal, Java, Python, Rubin, gehen,[18] Common Lisp[19] und Erlang.[20]

  • Berkeley Yacc: Die Berkeley -Implementierung von YACC wurde aufgrund seiner Leistung und mangelnden Wiederverwendungbeschränkungen schnell beliebter als AT & T YACC.[21]
  • Lalr Parser: Der zugrunde liegende Parsingalgorithmus in YACC-generierten Parsers.
  • Bison: Die GNU -Version von yacc.
  • Lex (und Flex Lexikalanalysator) ein Token -Parser, der üblicherweise in Verbindung mit YACC (und Bison) verwendet wird.
  • Bnf ist ein Metasyntax verwendet, um auszudrücken Kontextfreie Grammatiken: Das ist eine formelle Möglichkeit, kontextfreie Sprachen zu beschreiben.
  • Ply (Python Lex-yacc) ist eine alternative Implementierung von Lex und YACC in Python.

Siehe auch

Verweise

  1. ^ "Der A-Z der Programmiersprachen: yacc". Computerwelt. Archiviert von das Original am 31. Januar 2013. Abgerufen 30. November 2012.
  2. ^ Levine, John (1992). Lex & Yacc. Sebastopol, CA: O'Reilly & Associates. p. xx. ISBN 1-56592-000-7.
  3. ^ Levine, John (2009). Flex & Bison. Sebastopol, Kalifornien: O'Reilly Media. p. xv. ISBN 978-0-596-15597-1.
  4. ^ a b Ritchie, Dennis M. (April 1993). Die Entwicklung der C -Sprache (PDF). Association for Computing Machinery, Inc.
  5. ^ Morris, Richard (1. Oktober 2009). "Stephen Curtis Johnson: Geek der Woche". Rote Gate -Software. Abgerufen 19. Januar 2018.
  6. ^ a b c d Johnson, Stephen C. (1975). YACC: Ein weiterer Compiler-Compiler (Technischer Bericht). Murray Hill, New Jersey: AT & T Bell Laboratories. 32. Abgerufen 31. Januar 2020.
  7. ^ "Frühe Übersetzer -Schreibsysteme". Atlas Computerlabor.
  8. ^ a b c McIlroy, M. D. (1987). A Research Unix Reader: Annotierte Auszüge aus dem Programmierhandbuch, 1971–1986 (PDF) (Technischer Bericht). Cstr. Bell Labs. 139.
  9. ^ Stroustrup, Bjarne. "Eine Geschichte von C ++: 1979–1991" (PDF).
  10. ^ a b Stroustrup, Bjarne. "CFRONT -Quellcode".
  11. ^ Hamilton, Naomi (2008-07-09). "Yacc, Unix und Rat von Bell Labs Alumni Stephen Johnson". www.computerworld.com. Archiviert vom Original am 2020-08-22. Abgerufen 2020-11-10.
  12. ^ Lex- Shell and Utilities Referenz, Die einzelne Unix -Spezifikation, Version 4 von Die offene Gruppe, yacc- Shell and Utilities Referenz, Die einzelne Unix -Spezifikation, Version 4 von Die offene Gruppe.
  13. ^ "Plan9: UC Berkeley Veröffentlichung von Plan 9 unter der GPLV2". 26. Dezember 2017. Abgerufen 2. Januar 2018.
  14. ^ Bisonhandbuch: Geschichte
  15. ^ "Unix Special: Profs Kernighan & Brailsford". Computerphile. 30. September 2015. Archiviert vom Original am 2021-12-11.
  16. ^ Kernighan, Brian W.; Pike, Rob (1984). Die UNIX -Programmierumgebung. Prentice Hall. ISBN 0-13-937681-x.
  17. ^ "OCAML -Benutzerhandbuch: Kapitel 12 Lexer- und Parser -Generatoren (Ocamllex, Ocamlyacc)". Abgerufen 25. November 2013.
  18. ^ "Yacc.go: Eine Version von YACC für die Go -Programmiersprache". Abgerufen 15. Juli 2017.
  19. ^ "Cl-YACC: Eine gemeinsame Lisp-Version von yacc".
  20. ^ "YECC: Eine Erlang -Implementierung von yacc".
  21. ^ John Levine (August 2009), Flex & Bison, O'Reilly Media

Externe Links