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 = 24
y = 15
d = x - y
while d != 0:
    if d > 0:
        x = x - y
    else:
        y = y - x
    #if
    d = x - y
#while

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

(VAR,'x')
(ZUW,'=')
(ZAHL,'24')
(VAR,'y')
(ZUW,'=')
(ZAHL,'15')
(VAR,'d')
(ZUW,'=')
(VAR,'x')
(MINUS,'-')
(VAR,'y')
(WHILE,'while')
(VAR,'d')
(UG,'!=')
(NULL,'0')
(DP,':')
...

Der Parser muss jetzt u.a. überprüfen, ob eine Wiederholung aus Token der Gestalt WHILE "Bedingung" : "Anweisungsfolge" ENDWH besteht. Hierzu wird zunächst die Grammatik der Sprache MyWhile 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
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 rel NULL
rel -> GL
rel -> UG
rel -> GR
rel -> KL

Aufgabe 1

Betrachte das folgende einfache MyWhile-Programm:

x = 4
while x > 0:
  x = x - 1
#while

Aus diesem Programm ergibt sich die Tokenfolge:

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

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', 'GR', 'KL', 'DP', 'ENDWH', 'ENDIF']
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_GR      = r'\>'
t_KL      = r'\<'
t_DP      = r':'
t_ENDWH   = r'\#while'
t_ENDIF   = r'\#if'

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

# Produktionen

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

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

def p_anweisung_wh(p):
    'anweisung : WHILE bedingung DP anweisungsfolge ENDWH'
    p[0] = None

def p_anweisung_if(p):
    'anweisung : IF bedingung DP anweisungsfolge ELSE DP anweisungsfolge ENDIF'
    p[0] = None

def p_zuweisung(p):
    'zuweisung : VAR ZUW term'
    p[0] = None

def p_term_var_op_zahl(p):
    'term : VAR op zahl'
    p[0] = None

def p_term_var_op_var(p):
    'term : VAR op VAR'
    p[0] = None

def p_term_zahl(p):
    'term : zahl'
    p[0] = None

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

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

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

def p_bedingung(p):
    'bedingung : VAR rel NULL'
    p[0] = None

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

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

def p_rel_groesser(p):
    'rel : GR'
    p[0] = None

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

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

def p_rel_ungleich(p):
    'rel : UG'
    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 MyWhile kann man jetzt folgendermaßen erzeugen:

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

# Testprogramm
programm = '''
x = 24
y = 15
d = x - y
while d != 0:
    if d > 0:
        x = x - y
    else:
        y = y - x
    #if
    d = x - y
#while
'''

# 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 MyWhile 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 MyWhile in sinnvoller Weise zu ergänzen oder abzuändern.

Aufgabe 3

Ändere die Grammatik (und Tokenbeschreibungen) so ab, dass folgendes Programm erkannt wird:

x = 24;
y = 15;
d = x - y;
while (d != 0) {
    if (d > 0) {
        x = x - y;
    }
    else {
        y = y - x;
    };
    d = x - y;
};