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:

links
while nichtVorWand:
  ziegelHinlegen
  schritt
#while

Ziel ist es, aus diesem Quelltext ein strukturiertes Programm zu erstellen:

[
    ['links'], 
    ['while', 
        ['nichtVorWand'], 
        [
            ['ziegelHinlegen'], 
            ['schritt']
        ]
    ]
]

Die Struktur wird hier mit Hilfe geschachtelter Listen erzeugt. Wir nennen ein solches strukturiertes Programm auch MyKaList-Programm

Erweiterung der Produktionen

Zur Erzeugung der Strukturelemente eines WhileList-Programms werden die Produktionregeln der Grammatik um Erzeugungsregeln erweitert.

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_elementar(p):
    'anweisung : ELANW'
    p[0] = [p[1]]

def p_anweisung_pass(p):
    'anweisung : PASS'
    p[0] = [p[1]]

def p_anweisung_wh(p):
    'anweisung : WH bedingung DP anweisungsfolge WH_ENDE'
    p[0] = [p[1]] + [p[2]] + [p[4]]

def p_anweisung_if(p):
    'anweisung : IF BED DP anweisungsfolge ELSE DP anweisungsfolge IF_ENDE'
    # ...

def p_bedingung(p):
    'bedingung : BED'
    p[0] = [p[1]]

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

Die Wirkungsweise der Erzeugungsregeln soll anhand von Beispielen erläutert werden. Wir betrachten zunächst die Erzeugung des Strukturelements für eine Bedingung:

def p_anweisung_wh(p):
    'anweisung : WH bedingung DP anweisungsfolge WH_ENDE'
    p[0] = [p[1]] + [p[2]] + [p[4]]

Die Prozedur hat einen Parameter p, der für eine Sequenz von Werten für die in der Produktion vorkommenden Terminal (und Nichtterminalsymbole) steht. Dabei werden die Werte wie folgt den Symbolen zugeordnet:

def p_anweisung_wh(p):
    'anweisung : WH bedingung DP anweisungsfolge WH_ENDE'

    #    |       |      |     |        |           |
    #   p[0]    p[1]   p[2]  p[3]     p[4]        p[5]

    p[0] = [p[1]] + [p[2]] + [p[4]]

Mit der Zuweisung p[0] = [p[1]] + [p[2]] + [p[4]] wird hier festgelegt, wie das Strukturelement einer Wiederholeanweisung gebildet wird. Es ergibt sich folgender Aufbau: Das Strukturelement ist eine Liste, deren erstes Element aus dem Wert p[1] erzeugt wird. Da p[1] hier dem Token WH zugeordnet ist und dieses den Wert 'while' hat, wird also die Zeichenkette 'while' als erstes Element in die Liste aufgenommen. Das zweite Element der Liste ergibt sich aus dem Wert p[2], also dem Wert, der bei der Verarbeitung der Regel zum Nichtterminalsymbol bedingung gebildet wird. Das dritte Element der Liste ergibt sich aus dem Wert p[4], - also dem Wert, der bei der rekursiven Verarbeitung einer Regel zum Nichtterminalsymbol anweisungsfolge gebildet wird.

Nutzung von YACC

Das Programm YACC (der Implementierung PLY) ist in der Lage, aus den erweiterten Produktionen das Strukturgerüst eines While-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 while enthält. Mit dem gezeigten Testprogramm können jetzt WhileList-Programme erstellt werden.

import ply.lex as lex
import ply.yacc as yacc
from syntaxMyKa import *

# Testprogramm
programm = '''
links
while nichtVorWand:
  ziegelHinlegen
  schritt
#while
'''

# 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)

Der im Programm integrierte Test liefert dann folgende Ausgabe:

>>> 
[['links'], ['while', ['nichtVorWand'], [['ziegelHinlegen'], ['schritt']]]]

Aufgabe 1

Probiere das selbst einmal aus. Teste verschiedene Quelltexte, die syntaktisch korrekt sind. Was liefert der Parser, wenn ein syntaktischer Fehler vorliegt?

Aufgabe 2

Ergänze die noch fehlende Erzeugungsregel für Fallunterscheidungen. Teste deinen Vorschlag.