Station - Syntaxanalyse mit dem Parser
Aufgabe des Parsers
Ein Parser analysiert, ob eine Tokenfolge zu einem Programmquelltext vorgegebene Grammatikregeln befolgt.
Wir betrachten wieder den folgenden Quelltext:
x = 9
y = 6
while x != y:
if x <= y:
y = y - x
else:
x = x - y
#end
#end
Ein Scanner erzeugt mit Hilfe vorgegebener Tokenmuster aus diesem Quelltext eine Tokenfolge:
(VAR,'x') (ZUW,'=') (ZAHL,'9') (VAR,'y') (ZUW,'=') (ZAHL,'6') (WHILE,'while') (VAR,'x') (UG,'!=') (NULL,'0') (DP,':') ...
Der Parser muss jetzt u.a. überprüfen, ob eine Wiederholung aus Token der Gestalt
WHILE "Bedingung" : "Anweisungsfolge" END besteht. Hierzu wird zunächst
die Grammatik der Sprache MiniPython festgelegt.
Festlegung der Grammatik
Die Terminalsymbole der Grammatik sind die Tokennamen. Die Nichtterminalsymbole ergeben sich aus den linken Seiten der folgenden Produktionen. Startsymbol ist das Symbol auf der linken Seite der ersten Produktion.
# Produktionen programm -> anweisungsfolge anweisungsfolge -> anweisung anweisungsfolge anweisungsfolge -> anweisung anweisung -> zuweisung anweisung -> PASS anweisung -> WHILE bedingung DP anweisungsfolge ENDWH anweisung -> IF bedingung DP anweisungsfolge ELSE DP anweisungsfolge ENDIF zuweisung -> VAR ZUW term term -> VAR op zahl term -> VAR op VAR term -> zahl term -> VAR zahl -> NULL zahl -> ZAHL op -> PLUS op -> MINUS bedingung -> VAR rel0 NULL bedingung -> VAR rel VAR rel0 -> GL rel0 -> UG rel -> GL rel -> UG rel -> KL rel -> KLGL
Aufgabe 1
Betrachte das folgende einfache MyWhile-Programm:
x = 4
while x != 0:
x = x - 1
#end
Aus diesem Programm ergibt sich die Tokenfolge:
VAR ZUW ZAHL WHILE VAR UG NULL DP VAR ZUW VAR MINUS ZAHL END
Zeige, dass man mit den Produktionen der Grammatik eine Ableitung dieser Tokenfolge erzeugen kann.
Implementierung mit YACC
Das Programm YACC ist in der Lage, ausgehend von einer Grammatikbeschreibung ein System zur syntaktischen Analyse zu erzeugen. Letztlich generiert YACC einen Shift-Reduce-Parser (siehe Exkurs - Shift-Reduce-Parser), der die syntaktische Analyse vornimmt.
Bevor wir YACC aktivieren, speichern wir die Grammatik
zusätzlich zur Tokenfestlegung in einer Datei (z.B. syntaxWhile.py) ab.
# reservierte Wörter
reserved = {
'if' : 'IF',
'else' : 'ELSE',
'while' : 'WHILE',
'pass': 'PASS'
}
# Namen der Token
tokens = ['VAR', 'ZAHL', 'NULL', 'ZUW', 'PLUS', 'MINUS', 'GL', 'UG', 'KL', 'KLGL', 'DP', 'END']
tokens = tokens + list(reserved.values())
# Beschreibung der Token
def t_VAR(t):
r'[a-z][a-z0-9]*'
t.type = reserved.get(t.value, 'VAR') # Überprüfung auf reservierte Wörter
return t
t_ZAHL = r'[\+|-]?[1-9][0-9]*'
t_NULL = r'0'
t_ZUW = r'='
t_PLUS = r'\+'
t_MINUS = r'-'
t_GL = r'=='
t_UG = r'!='
t_KL = r'\<'
t_KLGL = r'\<='
t_DP = r':'
t_END = r'\#end'
# Ignorierte Zeichen
t_ignore = " \t"
def t_newline(t):
r'\n+'
t.lexer.lineno = t.lexer.lineno + t.value.count("\n")
def t_error(t):
print("Illegal character '%s'" % t.value[0])
t.lexer.skip(1)
# erweiterte Produktionen
def p_anweisungsfolge_programm(p):
'programm : anweisungsfolge'
p[0] = p[0]
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!")
Beachte, dass die Grammatikregeln hier innerhalb von Prozedurdeklarationen vorkommen. Die Bedeutung der zur Grammatikregel gehörenden Prozedur wird erst im nächsten Abschnitt geklärt.
Scanner und Parser zur Sprache MiniPython kann man jetzt folgendermaßen erzeugen:
import ply.lex as lex
import ply.yacc as yacc
from syntaxWhile import *
# Testprogramm
programm = '''
x = 9
y = 6
while x != y:
if x <= y:
y = y - x
else:
x = x - y
#end
#end
'''
# Erzeugung des Scanners
scanner = lex.lex(debug=0)
# Erzeugung des Parsers
parser = yacc.yacc(debug=False)
# syntaktische Analyse
parser.parse(programm, debug=0)
# Ausgabe
print("ok!")
Aufgabe 2
(a) Probiere das selbst einmal aus. Teste Quelltexte, die den Syntaxregeln von MiniPython entsprechen und teste auch fehlerhafte Quelltexte. Wie zeigt sich in der vorliegenden Implementierung, ob der Quelltext fehlerfrei ist?
(b) Du kannst ja auch einmal versuchen, die Grammatik von MiniPython in sinnvoller Weise zu ergänzen oder abzuändern.
Aufgabe 3
Ändere die Grammatik (und Tokenbeschreibungen) so ab, dass folgendes Programm erkannt wird:
x = 9:
y = 6;
while (x != y) {
if (x <= y) {
y = y - x;
}
else {
x = x - y;
};
};