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:

x = 9
y = 6
while x != y:
    if x <= y:
        y = y - x
    else:
        x = x - y
    #end
#end

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

[
  ['=', ('VAR', 'x'), [('ZAHL', '9')]],
  ['=', ('VAR', 'y'), [('ZAHL', '6')]],
  ['while', ['!=', ('VAR', 'x'), ('VAR', 'y')], 
    [
      ['if', ['<=', ('VAR', 'x'), ('VAR', 'y')], 
        [
          ['=', ('VAR', 'y'), ['-', ('VAR', 'y'), ('VAR', 'x')]]
        ], 
        [
          ['=', ('VAR', 'x'), ['-', ('VAR', 'x'), ('VAR', 'y')]]
        ]
      ]
    ]
  ]
]

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.

# Produktionen

def p_anweisungsfolge_programm(p):
    'programm : anweisungsfolge'
    p[0] = p[1]

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

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

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

def p_anweisung_if(p):
    'anweisung : IF bedingung DP anweisungsfolge ELSE DP anweisungsfolge END'
    p[0] = [p[1]] + [p[2]] + [p[4]] + [p[7]]

def p_zuweisung(p):
    'zuweisung : VAR ZUW term'
    p[0] = [p[2], ('VAR', p[1]), p[3]]

def p_term_var_op_zahl(p):
    'term : VAR op zahl'
    p[0] = [p[2], ('VAR', p[1]), ('ZAHL', p[3])]

def p_term_var_op_var(p):
    'term : VAR op VAR'
    p[0] = [p[2], ('VAR', p[1]), ('VAR', p[3])]

def p_term_zahl(p):
    'term : zahl'
    p[0] = [('ZAHL', p[1])]

def p_term_var(p):
    'term : VAR'
    p[0] = [('VAR', p[1])]

def p_zahl_null(p):
    'zahl : NULL'
    p[0] = p[1]

def p_zahl_nicht_null(p):
    'zahl : ZAHL'
    p[0] = p[1]

def p_bedingung_null(p):
    'bedingung : VAR rel0 NULL'
    p[0] = [p[2], ('VAR', p[1]), ('ZAHL', p[3])]

def p_bedingung(p):
    'bedingung : VAR rel VAR'
    p[0] = [p[2], ('VAR', p[1]), ('VAR', p[3])]

def p_op_plus(p):
    'op : PLUS'
    p[0] = p[1]

def p_op_minus(p):
    'op : MINUS'
    p[0] = p[1]

def p_rel_gleich_null(p):
    'rel0 : GL'
    p[0] = p[1]

def p_rel_ungleich_null(p):
    'rel0 : UG'
    p[0] = p[1]

def p_rel_gleich(p):
    'rel : GL'
    p[0] = p[1]

def p_rel_ungleich(p):
    'rel : UG'
    p[0] = p[1]

def p_rel_kleiner(p):
    'rel : KL'
    p[0] = p[1]

def p_rel_kleinergleich(p):
    'rel : KLGL'
    p[0] = p[1]

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

Die Wirkungsweise der Erzeugungsregeln soll anhand eines einfachen Beispiels erläutert werden. Wir betrachten hierzu den folgenden Quelltext:

x = 4
while x != 0:
  x = x - 1
#end

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

[
  ['=', ('VAR', 'x'), [('ZAHL', '4')]], 
  ['while', ['!=', ('VAR', 'x'), ('ZAHL', '0')], 
    [
      ['=', ('VAR', 'x'), ['-', ('VAR', 'x'), ('ZAHL', '1')]]
    ]
  ]
]

In einem ersten Schritt erzeugen wir eine (Rechts-) Ableitung zur (vereinfachten) Tokenfolge, die vom Scanner aus dem Quelltext erzeugt wird:

programm ->
anweisungsfolge -> 
anweisung anweisungsfolge ->
anweisung anweisung ->
anweisung WHILE bedingung DP anweisungsfolge ENDWH ->
anweisung WHILE bedingung DP anweisung ENDWH ->
anweisung WHILE bedingung DP zuweisung ENDWH ->
anweisung WHILE bedingung DP VAR ZUW term ENDWH ->
anweisung WHILE bedingung DP VAR ZUW VAR op ZAHL ENDWH ->
anweisung WHILE bedingung DP VAR ZUW VAR MINUS ZAHL ENDWH ->
anweisung WHILE VAR rel NULL DP VAR ZUW VAR MINUS ZAHL ENDWH ->
anweisung WHILE VAR GR NULL DP VAR ZUW VAR MINUS ZAHL ENDWH ->      # anweisung -> zuweisung
zuweisung WHILE VAR GR NULL DP VAR ZUW VAR MINUS ZAHL ENDWH ->      # zuweisung -> VAR ZUW term
VAR ZUW term WHILE VAR GR NULL DP VAR ZUW VAR MINUS ZAHL ENDWH ->   # term -> zahl
VAR ZUW zahl WHILE VAR GR NULL DP VAR ZUW VAR MINUS ZAHL ENDWH ->   # zahl -> ZAHL
VAR ZUW ZAHL WHILE VAR GR NULL DP VAR ZUW VAR MINUS ZAHL ENDWH

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:

VAR ZUW ZAHL WHILE VAR GR NULL DP VAR ZUW VAR MINUS VAR ENDWH

 zahl -> ZAHL
  |       |
p[0]    p[1]
p[0] = p[1]
zahl: '4'

VAR ZUW zahl WHILE VAR GR NULL DP VAR ZUW VAR MINUS VAR ENDWH

 term -> zahl
  |       |
p[0]    p[1]
p[0] = [('ZAHL', p[1])]
term: [('ZAHL', '4')] 

VAR ZUW term WHILE VAR GR NULL DP VAR ZUW VAR MINUS ZAHL ENDWH

zuweisung -> VAR ZUW term
  |           |   |   |
p[0]        p[1]p[2]p[3]
p[0] = [p[2], ('VAR', p[1]), p[3]]
zuweisung: ['=', ('VAR', 'x'), [('ZAHL', '4')]]

zuweisung WHILE VAR GR NULL DP VAR ZUW VAR MINUS ZAHL ENDWH

anweisung -> zuweisung 
  |              |
p[0]           p[1]
p[0] = p[1]
anweisung: ['=', ('VAR', 'x'), [('ZAHL', '4')]]

anweisung WHILE VAR GR NULL DP VAR ZUW VAR MINUS ZAHL ENDWH

...

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

x = 9:
y = 6;
while (x != y) {
    if (x <= y) {
        y = y - x;
	}
    else {
        x = x - y;
    };
};

soll also das Strukturgerüst (vgl. oben)

[
  ['=', ('VAR', 'x'), [('ZAHL', '9')]],
  ['=', ('VAR', 'y'), [('ZAHL', '6')]],
  ['while', ['!=', ('VAR', 'x'), ('VAR', 'y')], 
    [
      ['if', ['<=', ('VAR', 'x'), ('VAR', 'y')], 
        [
          ['=', ('VAR', 'y'), ['-', ('VAR', 'y'), ('VAR', 'x')]]
        ], 
        [
          ['=', ('VAR', 'x'), ['-', ('VAR', 'x'), ('VAR', 'y')]]
        ]
      ]
    ]
  ]
]

erzeugt werden.