Logo des digitalen Schulbuchs inf-schule.de. Schriftzug in Zustandsübergangsdiagramm eines endlichen Automaten.

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;
    };
};
X

Fehler melden

X

Suche