Station - Erzeugung eines Strukturgerüsts mit dem Parser
Aufgabe des Parsers
Ein Parser hat in der Regel nicht nur die Aufgabe, die Syntax zu überprüfen, ein Parser erzeugt auch für die weitere Verarbeitung eine strukturierte Darstellung des vorgegebenen Programms, sofern es syntaktisch korrekt ist.
Wir betrachten weiterhin den folgenden Quelltext:
Ziel ist es, aus diesem Quelltext ein strukturiertes Programm zu erstellen:
Die Struktur wird hier mit Hilfe geschachtelter Listen erzeugt. Wir nennen ein solches strukturiertes Programm auch MiniPythonList-Programm
Erweiterung der Produktionen
Zur Erzeugung der Strukturelemente eines MiniPythonList-Programms werden die Produktionregeln der Grammatik um Erzeugungsregeln erweitert.
Die Wirkungsweise der Erzeugungsregeln soll anhand eines einfachen Beispiels erläutert werden. Wir betrachten hierzu den folgenden Quelltext:
Ziel ist es, aus diesem Quelltext ein strukturiertes Programm zu erstellen:
In einem ersten Schritt erzeugen wir eine (Rechts-) Ableitung zur (vereinfachten) Tokenfolge, die vom Scanner aus dem Quelltext erzeugt wird:
Die Kommentare geben - zumindest für einige Ableitungsschritte - die benutzten Regeln an.
Die Ableitung wird jetzt rückwärts gelesen und um die Erzeugung von Strukturelementen ergänzt:
Im ersten Schritt wird die Produktion zahl -> ZAHL
rückwärts angewandt. Die Produktionsregel p[0] = p[1]
liefert das Strukturelement zum betreffenden Programmteil. Da p[1]
auf den Wert von ZAHL
zugreift und dieses Token den Wert '4'
hat, wird hier also das Strukturelement '4'
erzeugt.
Im zweiten Schritt wird die Produktion term -> zahl
rückwärts angewandt. Die Produktionsregel p[0] = [('ZAHL', p[1])]
liefert das Strukturelement zum betreffenden Programmteil. Da p[1]
jetzt auf Wert von zahl
zugreift und zahl
den Wert '4'
hat (wie oben gezeigt), wird hier also das Strukturelement [('ZAHL', '4')]
erzeugt.
Im dritten Schritt wird die Produktion zuweisung -> VAR ZUW term
rückwärts angewand. Die Produktionsregel p[0] = [p[2], ('VAR', p[1]), p[3]]
liefert das Strukturelement zum betreffenden Programmteil. Aus den Werten von p[1]
, p[2]
und p[3]
wird jetzt das Strukturelement ['=', ('VAR', 'x'), [('ZAHL', '1')]]
erzeugt.
Verwendung von YACC
Das Programm YACC (der Implementierung PLY) ist in der Lage, aus den erweiterten Produktionen das Strukturgerüst eines MiniPython-Programms zu erstellen.
Wir gehen im Folgenden davon aus, dass die Datei syntaxWhile.py
die regulären Ausdrücke zur Beschreibung der Token und die erweiterten Produktionen (s.o.) der Grammatik der Sprache MyWhile enthält. Mit dem gezeigten Testprogramm können jetzt MyWhileList-Programme erstellt werden.
import ply.lex as lex import ply.yacc as yacc from syntaxWhile import * # Testprogramm programm = ''' x = 4 while x != 0: x = x - 1 #end ''' # Erzeugung des Scanners scanner = lex.lex(debug=0) # Erzeugung des Parsers parser = yacc.yacc(debug=False) # syntaktische Analyse mit Erzeugung des Strukturbaums if len(programm) != 0: strukturbaum = parser.parse(programm, debug=0) else: strukturbaum = [] # Ausgabe print(strukturbaum)
Aufgabe 1
(a) Probiere das selbst einmal aus. Teste verschiedene Quelltexte, die syntaktisch korrekt sind.
(b) Was liefert der Parser, wenn ein syntaktischer Fehler vorliegt?
(c) Versuche auch einmal, die Strukturelemente anders zu gestalten.
Aufgabe 2
Erweitere die Grammatik zur Java-ähnlichen Syntax um Erzeugungsregeln für ein Strukturgerüst. Konzipiere die Erzeugungsregeln so, dass das gleiche Strukturgerüst wie bei der Python-ähnlichen Syntax entsteht.
Aus der Tokenfolge zum Programm
soll also das Strukturgerüst (vgl. oben)
erzeugt werden.