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:

0: tst 1
1: jmp 3 
2: jmp 6
3: dec 1
4: inc 0
5: jmp 0
6: hlt
#3
#5

Ziel ist es, aus diesem Quelltext ein Strukturgerüst zu erstellen:

[
    [(0, 'tst', 1), (1, 'jmp', 3), (2, 'jmp', 6), (3, 'dec', 1), (4, 'inc', 0), (5, 'jmp', 0), (6, 'hlt')], 
    [3, 5]
]

Die Struktur wird hier mit Hilfe von Listen und Tupeln erzeugt.

Erweiterung der Produktionen

Zur Erzeugung des Strukturgerüsts werden die Produktionregeln der Grammatik um Erzeugungsregeln erweitert.

# erweiterte Produktionen

def p_programm_anweisungsfolge_speicherbelegung(p):
    'programm : anweisungsfolge speicherbelegung'
    p[0] = [p[1], p[2]]

def p_anweisungsfolge_anweisung_anweisungsfolge(p):
    'anweisungsfolge : anweisung anweisungsfolge'
    p[0] = [p[1]] + p[2]

def p_anweisungsfolge_anweisung(p):
    'anweisungsfolge : anweisung'
    p[0] = [p[1]]

def p_anweisung_inc(p):
    'anweisung : ZAHL DP INC ZAHL'
    p[0] = (eval(p[1]), p[3], eval(p[4]))

def p_anweisung_dec(p):
    'anweisung : ZAHL DP DEC ZAHL'
    p[0] = (eval(p[1]), p[3], eval(p[4]))

def p_anweisung_jmp(p):
    'anweisung : ZAHL DP JMP ZAHL'
    p[0] = (eval(p[1]), p[3], eval(p[4]))

def p_anweisung_tst(p):
    'anweisung : ZAHL DP TST ZAHL'
    p[0] = (eval(p[1]), p[3], eval(p[4]))

def p_anweisung_hlt(p):
    'anweisung : ZAHL DP HLT'
    p[0] = (eval(p[1]), p[3])

def p_speicherbelegung_kommentar_anweisungsfolge(p):
    'speicherbelegung : KO ZAHL speicherbelegung'
    p[0] = [eval(p[2])] + p[3]

def p_speicherbelegung(p):
    'speicherbelegung : '
    p[0] = []

# Fehlermeldung
def p_error(p):
    print("Syntaxfehler!")

Wie die Erzeugung des Strukturgerüsts funktioniert, wird ausführlich z.B. im Abschnitt Station - Erzeugung eines Strukturgerüsts mit dem Parser erklärt.

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 syntaxBonsai.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 syntaxBonsai import *

# Testprogramm
quelltext = '''
0: tst 1
1: jmp 3 
2: jmp 6
3: dec 1
4: inc 0
5: jmp 0
6: hlt
#3
#5
'''

# Erzeugung des Scanners
scanner = lex.lex(debug=0)
# Erzeugung des Parsers
parser = yacc.yacc(debug=False)

# syntaktische Analyse mit Erzeugung des Strukturbaums
if len(quelltext) != 0:
    strukturbaum = parser.parse(quelltext, debug=0)
else:
    strukturbaum = []

# Ausgabe
print(strukturbaum)

Aufgabe 1

Probiere das selbst einmal aus. Lade hierzu die Datei bonsai3.zip herunter und entpacke sie. Führe anschließend die Datei test_parser.py aus. Teste verschiedene Quelltexte, die syntaktisch korrekt sind.

Aufgabe 3

Im Abschnitt Zusammenfassung - JOHNNY-Maschinensprache wird die Maschinensprache des JOHHNY-Rechners erläutert. Entwickle einen Parser zur Erzeugung eines Strukturgerüsts für diese Sprache.