Themen der Vorlesung "Übersetzergenerierung mit lex und yacc", SoSe 2004 ======================================================================== 1. Überblick und Einführung. - Interpreter und Übersetzer - Programme rund um einen Übersetzer - Die Phasen der Übersetzung: Überblick - Läufe vs. Phasen 2. Lexikalische Analyse. 2.1 Einleitung. - Aufgabe der lexikalischen Analyse - Struktur der lexikalischen Analyse - Die Begriffe Symbol, Lexem, Muster - Lexikalische vs. syntaktische Analyse 2.2 Beschreiben von Lexemen: reguläre Ausdrücke. - Definition reguläre Ausdrücke - Bezeichnete reguläre Sprachen - Reguläre Definitionen 2.3 Erkennen von Lexemen: endliche Automaten. - Definition: Endlicher Automat - Äquivalenz regulärer Ausdrücke und endlicher Automaten - Erkennen einer Sprache mit einem endlichen Automaten - Umwandlung regulärer Ausdrücke in endliche Automaten - Umwandlung nichtdeterministischer in deterministische Automaten - Implementierung eines deterministischen endlichen Automaten - Mehrdeutigkeiten bei der Lexemerkennung - Erkennung der Schlüsselworte 2.4 Fehlerbehandlung. - Mögliche Recovery-Strategien 2.5 Transformation von Lexemen. - Transformationsregeln für verschiedene Teile der Eingabe 2.6 Symboltabellenverwaltung. - Streuspeicher (Hashing) 3. Der Textstrom-Editor sed. 3.1 Grundprinzip eines Textstrom-Editors. - Einfache typische Anwendungen - Die Grundkommandos von sed 3.2 Reguläre Ausdrücke in sed. - Typische Anwendungen von regulären Ausdrücken - Reguläre Ausdrücke von sed/grep 4. Der Scanner-Generator lex. 4.1 Grundlagen. 4.1.1 Einführung. 4.1.2 Aufbau einer lex-Datei. - Aufbau einer lex-Datei 4.1.3 Einfacher Aufruf von flex. - Einfacher Aufruf von flex 4.1.4 Basiskonstrukte. - Reguläre Ausdrücke von lex - Unterschiede zu sed/grep - Aufbau einer Aktion - Die main()-Funktion 4.1.5 Weitere nützliche Konstrukte. - Abkürzungen für reguläre Ausdrücke - mehrere Ausdrücke für eine Aktion - Variable yytext - Makro ECHO 4.1.6 Übung: Einfacher Taschenrechner. 4.1.7 Der Match-Algorithmus. - Der Match-Algorithmus - Variable yyleng 4.1.8 Kommunikation mit einem Parser. - Kommunikation mit einem Parser 4.1.9 Übung: Konversion römischer Zahlen. 4.2 Fortgeschrittenes. 4.2.1 Wiederholung und Festigung. 4.2.2 Scanner-Zustände, Grundlagen. - Wechselweise Aktivierung verschiedener Sätze von Mustern - Typische Anwendungsbeispiele - Mengen von Scanner-Zuständen 4.2.3 Umlenken der Ein- und Ausgabe. - Dateieingabe und -ausgabe umlenken - Lesen aus Strings - Mehrere Eingabequellen nacheinander - Mehrere Eingabequellen abwechselnd - Typische Anwendungen 4.2.4 Reguläre Ausdrücke, Fortgeschrittenes. - Vordefinierte Buchstabenmengen in Mustern - Muster für Dateiende - Vorschau-Operator 4.2.5 Scanner-Zustände, Fortgeschrittenes. - Bereiche für Scanner-Zustände - Stack von Scanner-Zuständen - Exklusive/inklusive Scanner-Zustände 4.2.6 Mehrere Lexer in einem Programm. - Anderes Präfix für jeden der Lexer 4.2.7 Aufruf- und Datei-Optionen von flex. - Aufruf- und Datei-Optionen von flex 4.2.8 flex und andere Lexer. - Was kann flex mehr als andere Lexer 5. Syntaxanalyse und der Parser-Generator yacc. 5.1 Einleitung. - Ableitungsbaum (Parse-Baum) und Syntaxbaum 5.2 Kontextfreie Grammatiken. - Definition: Kontextfreie Grammatik - Kontextfreie Sprache - Spezifikation kontextfreier Grammatiken mit BNF - Erweiterungen zu EBNF - Ableitung: Definition - Sprache einer kontextfreien Grammatik - Links- und Rechtsableitung - vollständige und terminale Ableitung - Ableitungsbaum: Definition - Zusammenhang Ableitungsbaum und Linksableitung - Mehrdeutigkeit: Definition 5.3 Grundlagen von yacc. - Aufbau einer yacc-Datei - EBNF-Erweiterungen und yacc - Aufruf- und Datei-Optionen von bison 5.4 Absteigende Analyse. - Absteigende Analyse versus aufsteigende Analyse - SLL(1)-Bedingung; Transformation in SLL(1)-Grammatik nötig 5.5 Aufsteigende Analyse. 5.5.1 Prinzip der aufsteigenden Analyse. - "Reduzieren" des Eingabeworts auf das Startsymbol - Rechtsableitung in umgekehrter Reihenfolge - Implementierung der aufsteigenden Analyse mit einem Stack - Die vier Grundoperationen eines Shift-Reduce-Parsers - Konflikte bei der Shift-Reduce-Syntaxanalyse - Shift/Reduce- und Reduce/Reduce-Konflikte - Die Leistungsfähigkeit der absteigenden Analyse und die der aufsteigenden Analyse 5.5.2 Algorithmus der LR-Syntaxanalyse. - LR(k) - Eigenschaften der LR-Syntaxanalyse - Die feste Struktur eines LR-Parsers - Vereinfachte Implementierung des Stacks - Der Algorithmus - bison: %verbose, Debug-Ausgaben 5.5.3 Konstruktion der Syntaxanalysetabellen. - Idee der SLR-Methode - LR(0)-Element - LR(1)-Grammatik, die nicht SLR(1) ist - Idee der kanonischen LR-Methode - LR(1)-Element - Idee der LALR-Methode - Vorteile der LALR-Methode 5.5.4 Konflikte. - Typische Konflikte und ihre Auflösung - mehrdeutige Grammatik - Konflikt in Ausdrücken - Konflikt in if-then-else - Konflikt in verschachtelten Listen - Konflikt in überlappenden Alternativen - Nicht-LALR(1)-Grammatik - Konflikt wegen begrenzter Vorschau - Konflikt wegen Nicht-LALR-Grammatik 5.5.5 Präzedenzen. - Grund der Einführung - Zwei Arten: Assoziativität und Priorität - Realisierung in yacc - Algorithmus für Präzedenzen in yacc - Kontextabhängige Präzedenz in yacc 5.5.6 Fehlerbehandlung. - Zweck einer Fehlerbehandlung - Fehler-Regeln in yacc - Terminalsymbol "error" - Algorithmus zur Fehlerbehandlung bei yacc - Vorteil von Synchronisationszeichen 6. Syntaxgesteuerte Übersetzung. - Unterschied zu explizit aufgebautem Syntaxbaum - Attribute - synthetisierte und ererbte Attribute 6.1 Syntaxgesteuerte Definitionen. - Semantikregel - Was ist eine syntaxgesteuerte Definition - Attributgrammatik - S-attributierte Definition - Abhängigkeitsgraph über einem Ableitungsbaum - Verschiedene Methoden zur Bestimmung der Auswertungsreihenfolge 6.2 Konstruktion expliziter Syntaxbäume. - Vorteile und Nachteile expliziter Syntaxbäume - Implementation der Konstruktion expliziter Syntaxbäume (für Ausdrücke) - Rekursive Auswerter für Attribute 6.3 Aufsteigende Auswertung. - Vorteil einer S-attributierten Definition - Idee der Auswertung einer S-attributierten Definition - L-attributierte Definition - Eigenschaften L-attributierter Definitionen - Depth-First-Traversierung des Syntaxbaums - Übersetzungsschema - Semantische Aktionen in yacc - Übergabe von semantischen Werten von lex an yacc - Notation für Attributwerte in yacc - Verschiedene Typen für die Attributwerte in yacc - Default-Aktion von yacc - Implizites Attribut für die Position der Eingabe in yacc - Übersetzungsschema mit semantischen Aktionen in der Mitte - Entfernen eingebetter Aktionen aus Übersetzungsschemata - Implementierung ererbter Attribute in yacc - Über globale Variablen - Über den Parser-Stack 7. Übersetzungssteuerung mit make. 7.1 Grundlagen von make. - Motivation: Wann und wozu braucht man make - Grundaufbau eines Makefiles - Aufbau einer Regel - Grundalgorithmus von make - Variablen im Makefile - Aufruf von Makefile mit Nicht-Standard-Namen - Eingebaute implizite Regeln 7.2 Arbeiten mit make. - Struktur eines Makefiles, genauer - Default-Namen für Makefiles - Default-Regel - Vorbedingungen - Anweisungen - Unechte Ziele - Mehrere ausführbare Programme - Mehrere Regeln für ein Ziel - Statische-Muster-Regeln - Ausführung von Anweisungen in getrennten Shells - Echo ausgeführter Anweisungen - Fehlererkennung - Ignorieren von Fehlern - Inkonsistente Zieldateien bei Fehlern oder Unterbrechungen 7.3 Ein wenig Fortgeschrittenes. - Rekursive Verwendung von make - Muster-Regeln - Altmodische Suffix-Regeln - Automatische Variablen - Variablen in vordefinierten impliziten Regeln - Verkettung impliziter Regeln - Variablenexpansion - Ersetzungen in Variablen - Aufrufoptionen von make - Gnu-make und andere makes - Idee von autoconf/automake