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'\

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

Fehler melden

X

Suche