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:

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

Ein Scanner erzeugt mit Hilfe vorgegebener Tokenmuster aus diesem Quelltext eine Tokenfolge:

>>> 
LexToken(ZAHL,'0',2,1)
LexToken(DP,':',2,2)
LexToken(TST,'tst',2,4)
LexToken(ZAHL,'1',2,8)
LexToken(ZAHL,'1',3,10)
LexToken(DP,':',3,11)
LexToken(JMP,'jmp',3,13)
LexToken(ZAHL,'3',3,17)
...
LexToken(KO,'#',9,63)
LexToken(ZAHL,'3',9,64)
LexToken(KO,'#',10,66)
LexToken(ZAHL,'5',10,67)

Der Parser muss jetzt u.a. überprüfen, ob eine Befehlszeile z.B. die Gestalt ZAHL DP TST ZAHL hat und nicht etwa in der Form ZAHL TST ZAHL (d.h. ohne Doppelpunkt) dargestellt wird. Hierzu wird die Grammatik der Bonsdaisprache 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 speicherbelegung
anweisungsfolge -> anweisung anweisungsfolge
anweisungsfolge -> anweisung
anweisung -> ZAHL DP INC ZAHL
anweisung -> ZAHL DP DEC ZAHL
anweisung -> ZAHL DP JMP ZAHL
anweisung > ZAHL DP TST ZAHL
anweisung -> ZAHL DP HLT
speicherbelegung -> KO ZAHL speicherbelegung
speicherbelegung -> λ

Aufgabe 1

Betrachte den folgenden Bonsai-Quelltext:

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

Aus diesem Quelltext ergibt sich die Tokenfolge (in vereinfachter Form):

ZAHL DP TST ZAHL
ZAHL DP JMP ZAHL 
ZAHL DP JMP ZAHL
ZAHL DP DEC ZAHL
ZAHL DP INC ZAHL
ZAHL DP JMP ZAHL
ZAHL DP HLT
KO ZAHL
KO ZAHL

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. syntaxBonsai.py) ab.

# Namen der Token

tokens = ['ZAHL', 'INC', 'DEC', 'JMP', 'TST', 'HLT', 'DP', 'KO']

# Beschreibung der Token

t_ZAHL  = r'0|[1-9][0-9]*'
t_INC   = r'inc'
t_DEC   = r'dec'
t_JMP   = r'jmp'
t_TST   = r'tst'
t_HLT   = r'hlt'
t_DP    = r':'
t_KO    = r'\#'

# 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_programm_anweisungsfolge_speicherbelegung(p):
    'programm : anweisungsfolge speicherbelegung'
    p[0] = None

def p_anweisungsfolge_anweisung_anweisungsfolge(p):
    'anweisungsfolge : anweisung anweisungsfolge'
    p[0] = None

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

def p_anweisung_inc(p):
    'anweisung : ZAHL DP INC ZAHL'
    p[0] = None

def p_anweisung_dec(p):
    'anweisung : ZAHL DP DEC ZAHL'
    p[0] = None

def p_anweisung_jmp(p):
    'anweisung : ZAHL DP JMP ZAHL'
    p[0] = None

def p_anweisung_tst(p):
    'anweisung : ZAHL DP TST ZAHL'
    p[0] = None

def p_anweisung_hlt(p):
    'anweisung : ZAHL DP HLT'
    p[0] = None

def p_speicherbelegung_kommentar_anweisungsfolge(p):
    'speicherbelegung : KO ZAHL speicherbelegung'
    p[0] = None

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

# 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 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 
parser.parse(quelltext, debug=0)

# Ausgabe
print("ok")

Aufgabe 2

Probiere das selbst einmal aus. Lade hierzu die Datei bonsai2.zip herunter und entpacke sie. Führe anschließend die Datei test_parser.py aus. Teste auch weitere Quelltexte. Teste Quelltexte, die den Syntaxregeln der Bonsaisprache entsprechen und teste auch fehlerhafte Quelltexte. Wie zeigt sich in der vorliegenden Implementierung, ob der Quelltext fehlerfrei ist?

Aufgabe 3

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