Universität Bremen  
  Universität Bremen FB3 TZI BISS  
  AG BS > Lehre > WS 2007/2008 > Deutsch
English
 

Übersetzergenerierung mit lex und yacc, WiSe 2007/08
 

Veranstalter: Jan Bredereke

Termin: Mo 17:15-18:45 Uhr, MZH 7230

Beginn: Mo. 29.10.2007      Am 28.1.2008 fällt die Vorlesung aus.

ECTS: 2
Kategorie: A
VAK: 03-05-H-705.51

Überblick

Übersetzer sind grundlegende Werkzeuge der Informatiker. Für Standardsprachen stehen zwar bereits fertige Übersetzer zur Verfügung. Aber nur wenn man ihre Arbeitsweise kennt, kann man alltägliche Fragen beantworten wie etwa: Welche Fehler in meinem Programm kann der Übersetzer finden? Wie effizient kann er ein Konstrukt übersetzen?

Viele Implementierungsaufgaben können als Implementierung eines Übersetzers für eine spezialisierte, domänenspezifische Sprache aufgefaßt werden. Jede Übersetzung von Eingabedaten in Ausgabedaten ist eine Übersetzung von einer spezialisierten Sprache in eine andere spezialisierte Sprache. Auch die Interaktion mit einem Benutzer ist eine Übersetzung von Benutzereingaben in Programmausgaben. Für solche Aufgaben müssen auch heute noch ständig neue Übersetzer (und Interpreter) implementiert werden.

Es gibt Werkzeuge, mit denen man einen Übersetzer zu großen Teilen automatisch generieren kann. Die Menge der Eingaben und die Menge der Ausgaben des Übersetzers stellen je eine domänenspezifische Sprache (DSL, domain specific language) dar. In einer Meta-Sprache wird die Eingabe-DSL für das Generatorwerkzeug beschrieben.

In dieser Vorlesung lernen wir insbesondere die Werkzeuge lex und yacc kennen, beziehungsweise deren Varianten flex und bison. Ziel ist, mit diesen Werkzeugen Übersetzer für eigene domänenspezifische Sprachen generieren zu können. Weiterhin stellen wir kurz das Werkzeug sed vor, mit dem man auf regulären Ausdrücken basierende Textersetzungen in einem Datenstrom vornehmen kann, sowie das Werkzeug make, mit dem man die Schritte automatisieren kann, die bei der Generierung eines Programms aus vielen Quelldateien nötig sind. Insbesondere dient make der Verwaltung der Abhängigkeiten dieser Schritte, was bei Programmänderungen wichtig wird.

Ebenso wird der theoretische Hintergrund eingeführt: Lexikalische Analyse (reguläre Ausdrücke, endliche Automaten), Syntaxanalyse (kontextfreie Grammatiken, absteigende Analyse, aufsteigende Analyse, Fehlerbehandlung) und syntaxgesteuerte Übersetzung (Syntaxbäume, Übersetzungsschemata).

Voraussetzung für die Teilnahme ist das Vordiplom oder zumindest der erfolgreiche Abschluß der Grundstudiumsveranstaltungen "Theoretische Informatik I" und "Praktische Informatik 2".

Diese Veranstaltung richtet sich an alle, die an der praktischen Generierung von Übersetzern mit den Werkzeugen lex und yacc interessiert sind. Diese Vorlesung stellt die Werkzeuge lex und yacc viel ausführlicher vor als die von Berthold Hoffmann regelmäßig gehaltene Vorlesung und Übung "Übersetzer". Dort wird der theoretische Hintergrund des Übersetzerbaus breiter dargestellt, einschließlich weiterer Aspekte wie Kontextanalyse und Codeerzeugung. Weiterhin gibt es bei Berthold wechselnde Vertiefungsveranstaltungen zu "Übersetzer".

Struktur und Folien

  • 1. Überblick und Einführung. (pdf)
    29.10.2007
  • 2. Lexikalische Analyse. (pdf)
    5.11.2007
    • 2.1 Einleitung.
    • 2.2 Beschreiben von Lexemen: reguläre Ausdrücke.
    • 2.3 Erkennen von Lexemen: endliche Automaten.
    • 2.4 Fehlerbehandlung.
    • 2.5 Transformation von Lexemen.
    • 2.6 Symboltabellenverwaltung.
  • 3. Der Textstrom-Editor sed. (pdf) - Beispiele und Lösungen (als tar/gzip - in Verzeichnis)
    12.11.2007
    • 3.1 Grundprinzip eines Textstrom-Editors.
    • 3.2 Reguläre Ausdrücke in sed.
  • 4. Der Scanner-Generator lex.
    • 4.1 Grundlagen. (pdf) - Beispiele und Lösungen (als tar/gzip - in Verzeichnis)
      19.11.2007
      • 4.1.1 Einführung.
      • 4.1.2 Aufbau einer lex-Datei.
      • 4.1.3 Einfacher Aufruf von flex.
      • 4.1.4 Basiskonstrukte.
      • 4.1.5 Weitere nützliche Konstrukte.
      • 4.1.6 Übung: Einfacher Taschenrechner.
      • 4.1.7 Der Match-Algorithmus.
      • 4.1.8 Kommunikation mit einem Parser.
      • 4.1.9 Übung: Konversion römischer Zahlen.
    • 4.2 Fortgeschrittenes. (pdf) - Beispiele und Lösungen (als tar/gzip - in Verzeichnis)
      26.11.2007
        4.2.1 Wiederholung und Festigung.
      • 4.2.2 Scanner-Zustände, Grundlagen.
      • 4.2.3 Umlenken der Ein- und Ausgabe.
      • 4.2.4 Reguläre Ausdrücke, Fortgeschrittenes.
      • 4.2.5 Scanner-Zustände, Fortgeschrittenes.
      • 4.2.6 Mehrere Lexer in einem Programm.
      • 4.2.7 Aufruf- und Datei-Optionen von flex.
      • 4.2.8 flex und andere Lexer.
  • 5. Syntaxanalyse und der Parser-Generator yacc.
    • 3.12.2007:
      (pdf) - Beispiele und Lösungen (als tar/gzip - in Verzeichnis)
      • 5.1 Einleitung.
      • 5.2 Kontextfreie Grammatiken.
      • 5.3 Grundlagen von yacc.
      • 5.4 Absteigende Analyse.
    • 10.12.2007, 17.12.2007:
      (pdf) - Beispiele für Kap. 5.5.1 bis 5.5.3 (als tar/gzip - in Verzeichnis)
      • 5.5 Aufsteigende Analyse, 1. Teil.
        • 5.5.1 Prinzip der aufsteigenden Analyse.
        • 5.5.2 Algorithmus der LR-Syntaxanalyse.
        • 5.5.3 Konstruktion der Syntaxanalysetabellen.
    • 17.12.2007, 7.1.2008:
      (pdf) - Beispiele für Kap. 5.5.4, 1. Teil (als tar/gzip - in Verzeichnis) - Beispiele und Lösungen für den Rest (als tar/gzip - in Verzeichnis)
      • 5.5 Aufsteigende Analyse, 2. Teil.
        • 5.5.4 Konflikte.
        • 5.5.5 Präzedenzen.
        • 5.5.6 Fehlerbehandlung.
    • 6. Syntaxgesteuerte Übersetzung. (pdf) - Beispiele (als tar/gzip - in Verzeichnis)
      14.1.2008:
      • 6.1 Syntaxgesteuerte Definitionen.
      • 6.2 Konstruktion expliziter Syntaxbäume.
      • 6.3 Aufsteigende Auswertung.
    • 7. Übersetzungssteuerung mit make. (pdf) - Beispiele und Lösungen (als tar/gzip - in Verzeichnis)
      21.1.2008, 4.2.2008:
      • 7.1 Grundlagen von make.
      • 7.2 Arbeiten mit make.
      • 7.3 Ein wenig Fortgeschrittenes.
    • Wiederholung. (pdf)
      4.2.2008:
      Ausgewählte Folien der gesamten Vorlesung zur Wiederholung des Stoffs.

    Die Folien werden immer eine Woche vor der zugehörigen Vorlesung hier veröffentlicht.

    Errata: Fehler in den Folien, die wir erst während der Vorlesung finden, werden auf einer eigenen Seite gesammelt.

    Eine noch detailliertere Liste der Themen jedes Kapitels findet sich auf einer eigenen Seite.

    Literatur

    [AhSeUl99] Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman.
    Compilerbau, Teil 1. Oldenbourg, 2. Aufl. (Dez. 1999). ISBN 3-486-25294-1.
    Das "Drachenbuch", das Standardwerk zum Thema Compilerbau. Teil 1 reicht für diese Vorlesung voll aus. (Im Jahr 2006 ist eine neue Auflage des englischen Originals erschienen, die deutsche Übersetzung davon steht aber noch aus.)
    [NN93] N. N.
    sed(1) Manual-Seite. In: LunetIX Linuxhandbuch (Juli 1993). (ps/gzip 7 kB - pdf 20 kB)
    [HaWoOl93] Mike Haertel, James A. Woods und David Olson.
    grep(1) Manual-Seite. In: LunetIX Linuxhandbuch (Juli 1993). (ps/gzip 5 kB - pdf 12 kB)
    [LeMaBr95] John R. Levine, Tony Mason und Doug Brown.
    lex & yacc. O'Reilly, zweite korrigierte Auflage (1995). ISBN 1-56592-000-7.
    Für die, die ein ausführliches Lehrbuch zu den Werkzeugen lex und yacc möchten. Die Manuals von flex und bison sind aber auch sehr gut. Wir verwenden flex und bison, dieses Buch konzentriert sich auf lex und yacc.
    [Pax90] Vern Paxson.
    Flex, version 2.5 - A fast scanner generator. University of California (1990). (ps/gzip 108 kB - pdf 328 kB)
    Die Version von flex, die bei SuSE-Linux 8.2 dabei ist.
    [DoSt02] Charles Donelly and Richard Stallman.
    Bison - The YACC-compatible parser generator. Version 1.75. Free Software Foundation (2002). ISBN 1-882114-44-2. GNU Free Documentation License. (ps/gzip 266 kB - pdf 454 kB)
    Die Version von bison, die bei SuSE-Linux 8.2 dabei ist.
    [StMcSm02] Richard M. Stallman, Roland McGrath und Paul Smith.
    GNU Make - A Program for Directing Recompilation. Version 3.80. Free Software Foundation (Juli 2002). ISBN 1-882114-81-7. GNU Free Documentation License. (ps/gzip 385 kB - pdf 699 kB)
    Die aktuelle Version von GNU make. Sie ist bei SuSE-Linux 10.1 dabei.

    Software

    Quellen für die verwendete Software

    Die freien Versionen von lex und yacc, flex und bison, sollten auf allen Unix-Rechnern des Fachbereiches installiert sein. Auch bei allen aktuellen Linux-Distributionen sollten sie dabei sein. Windows-Nutzer finden sie im Cygwin-Paket.

    Das gleiche gilt natürlich für GNU make, sed und grep.

    Übersetzergeneratoren für Java

    lex und yacc generieren Code in C bzw. C++, aber es gibt auch Generatoren für Code in Java. CUP ist ein LALR-Parser, ganz ähnlich wie yacc. Man kann als Scanner-Generator dazu z.B. JFlex oder JLex verwenden. Wem die eingeschränkteren Möglichkeiten eines LL-Parsers reichen, der kann sich auch javacc oder antlr ansehen. Alle diese Programme sind wie yacc ebenfalls frei erhältlich.

    Download-Links

    Scheinbedingung

    Die Scheinbedingungen werden am ersten Vorlesungstermin ausgehandelt.

    Am Montag, den 29.10.2007, wurde ausgehandelt:

    • keine Übungsaufgaben
      • deswegen 2 ECTS
    • mündliche Prüfung am Ende
      • 20-30 min. pro Kandidat
      • auf Wunsch mit Beisitzer

    Prüfung

    Termine: Mo. 11.2.2008 zwischen 10:00 Uhr und 14:30 Uhr in MZH 8090.

    Am 17.12.2008 wurde in der Vorlesung eine Liste mit Terminen und Uhrzeiten zum Eintragen herumgegeben. Am 7.1.2008 wurde diese Liste noch einmal herumgegeben.

    Zur Vorbereitung auf die Prüfung ist vielleicht die detaillierte Liste der Themen jedes Kapitels hilfreich, die auf einer eigenen Seite steht. Wer zu jedem Stichpunkt etwas Sinnvolles erzählen kann, der kann der Prüfung sehr, sehr zuversichtlich entgegensehen.

    Wiederholungsprüfung

    Termine: Mo. 10.3.2008 zwischen 16:30 Uhr und 17:30 Uhr in MZH 8090.

 
   
Autor: jp 		 
  AG Betriebssysteme, Verteilte Systeme 
Zuletzt geändert am: 2. November 2022   Impressum