Prof. Dr. Reinhard Wilhelm Dipl.-Inform. Andreas Kerren                                                                     Fachbereich Informatik                                                                   Universität des Saarlandes                                                                      Tel.: (0681) 302-3235

    Proseminar im Wintersemester 99/00

Syntaktische Analyse von Programmiersprachen

Abb.: Modell eines LR-Parsers    

Inhalt:

Die syntaktische Analyse von Programmen wird durch einen sogenannten Parser realisiert. Er erhält die Eingabeprogramme in Form einer Folge von Symbolen. Seine Aufgabe ist es, in diesen Folgen von Symbolen die syntaktische Struktur der Programme zu finden, d.h. Teilfolgen zu immer größeren syntaktischen Einheiten zusammenzufassen. Solche Einheiten sind in imperativen Sprachen z.B. Variablen, Ausdrücke, Anweisungen, Deklarationen, Spezifikationen, etc.. Eine mögliche Darstellung der syntaktischen Struktur ist der Syntaxbaum des Programms. Dieser wird vom Parser erzeugt und nachfolgenden Übersetzungsphasen zur Verfügung gestellt, damit daraus schließlich ein Maschinenprogramm generiert werden kann.
Die syntaktische Analyse ist ein wichtiges Anwendungsgebiet der Theorie von formalen Sprachen und Automaten. Die permanente Entwicklung moderner Programmierhochsprachen weckt das Bedürfnis nach einer allgemeinen und theoretisch sauberen Methode, um Compiler für diese Programmiersprachen zu schreiben. Kontextfreie Grammatiken beschreiben die syntaktische Struktur von Programmen und sind deterministisch analysierbar. Aus einer solchen Grammatik läßt sich automatisch ein zugehöriger Syntaxanalysator, ein sogenannter Kellerautomat, generieren.
Eine weitere wichtige Aufgabe eines Parsers ist die Erkennung und gute Behandlung von Syntaxfehlern. Er soll syntaktische Fehler möglichst exakt lokalisieren, evtl. diagnostizieren und möglichst bald wieder in einen Zustand kommen, von dem aus er den Rest des Eingabeprogramms analysieren kann. Einige Teilgebiete der "Parsing Theory", die im Seminar vorgestellt werden, sind u.a.:
 
• Formale Sprachen (reguläre und kontextfreie Sprachen)
• Kontextfreie Grammatiken
• Kellerautomaten
• Syntaxanalyse und -analysatoren:
  • LR(k) Syntaxanalyse
  • Konstruktion und Implementierung von LR(1) Parsern
  • (Starke) LL(k) Syntaxanalyse
  • Konstruktion und Implementierung von (starken) LL(1) Parsern
  • Syntaxfehlerbehandlung
  • Test auf LL(k)- bzw. LR(k)-Eigenschaft einer gegebenen Grammatik
 

Liste der Vorträge:

Termin	Thema	Betreuer	Referent
15.11.1999 11:00 c.t.	Reguläre Sprachen	A. Kerren	A. Rurainski
06.12.1999 11:00 c.t.	Kontextfreie Sprachen	A. Kerren	M. Bergau
13.12.1999 11:00 c.t.	Einführung in die Syntaxanalyse und -analysatoren	A. Kerren	K. Roberts
10.01.2000 11:00 c.t.	LR(k) Syntaxanalyse, Teil I	A. Kerren	C. Bieg
17.01.2000 11:00 c.t.