Universität Bremen  
  Universität Bremen FB3 TZI BISS  
  AG BS > Lehre > SoSe 2004 > Deutsch
English
 

Übersetzergenerierung mit lex und yacc, SoSe 2004
 

Veranstalter: Jan Bredereke

Termin: Mo 8:30-10:00 Uhr, MZH 1400 (gr. Senatssaal)

Beginn: 26. April 2004

ECTS: 2

Ü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, Bezeichnertabellen), Syntaxanalyse (kontextfreie Grammatiken, absteigendes Parsieren, aufsteigendes Parsieren, Fehlerbehandlung, abstrakte Syntaxbäume), semantische Analyse (Identifizierung und Typisierung, syntax-orientierte Attributierung, Vereinbarungstabellen) und evtl. Transformation und Codeerzeugung.

Geändert, 28.4.2004: Voraussetzung für die Teilnahme ist das Vordiplom, oder zumindest der erfolgreiche Abschluß der Grundstudiumsveranstaltungen "Theoretische Informatik I" (in der Version seit WiSe 2002/03) 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, insbesondere an die Teilnehmer des Projektes TRACS.

Struktur und Folien

  • 1. Überblick und Einführung. (pdf)
    26.4.2004
  • 2. Lexikalische Analyse. (pdf)
    3.5.2004
    • 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)
    10.5.2004
    • 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)
      17.5.2004
      • 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)
      24.5.2004
        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.
    • 7.6.2004:
      (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.
    • 14.6.2004:
      (pdf) - Beispiele (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.
    • 21.6.2004, 28.6.2004:
      (pdf) - Beispiele und Lösungen (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)
    28.6.2004, 5.7.2004
    • 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)
    5.7.2004, 12.7.2004
    • 7.1 Grundlagen von make.
    • 7.2 Arbeiten mit make.
    • 7.3 Ein wenig Fortgeschrittenes.
  • Wiederholung. (pdf)
    12.7.2004
    Ausgewählte Folien der gesamten Vorlesung zur Wiederholung des Stoffs.

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

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.
[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 8.2 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

Am Montag, den 26.4.2004 wurde (für die DPO'03) 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. 19.7.2004, Di. 20.7.2004, Do. 22.7.2004, jeweils zwischen 9:30 Uhr und 17:00 Uhr, außerdem wegen des großen Andrangs am Fr. 23.7.2004 zwischen 10:00 Uhr und 11:30 sowie zwischen 16:00 Uhr und 17:00 Uhr.
(Leider war Mi. 21.7. doch nicht möglich.)

Am 5.7.2004 wird in der Vorlesung eine Liste mit Terminen und Uhrzeiten zum Eintragen herumgegeben. Am 12.7.2004 wird 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.

Bitte bringt ein ausgefülltes Scheinformular mit! ("Studienbegleitender Leistungsnachweis")

  • "Titel der Lehrveranstaltung": Übersetzergenerierung mit lex und yacc
  • "Veranstaltungskennziffer": 03-705.51
  • "SS/WS": SS 2004
  • "Wochenstunden": 2
  • "anerkannt für den Diplomstudiengang/Magisterstudiengang": Informatik
  • "Art und Inhalt der Veranstaltung": Vorlesung
  • "Einzelleistung": X
  • "Inhalt und Form der Leistung": mündliche Prüfung
  • "Prüfungsgebiet der Leistung": Praktische Informatik
  • "Note": [bitte noch nicht ausfüllen ;-) ]
  • "Datum": [bitte passend ausfüllen]
  • "Unterschrift des Hochschullehrers": [bitte noch nicht ausfüllen ]
 
   
Autor: jp 		 
  AG Betriebssysteme, Verteilte Systeme 
Zuletzt geändert am: 2. November 2022   Impressum