Station - Syntaxanalyse mit dem Parser

Aufgabe des Parsers

Ein Parser analysiert, ob eine Tokenfolge zu einem Programmquelltext die vorgegebenen Grammatikregeln befolgt.

Wir betrachten wieder den folgenden Quelltext:

links
while nichtVorWand:
  ziegelHinlegen
  schritt
#while

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

(ELANW,'links')
(WH,'while')
(BED,'nichtVorWand')
(DP,':')
(ELANW,'ziegelHinlegen')
(ELANW,'schritt')
(WH_ENDE,'#while')

Der Parser muss jetzt u.a. überprüfen, ob eine Wiederholung aus Token der Gestalt WH BED : ... WH_ENDE besteht. Hierzu wird zunächst die Grammatik der Sprache While 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 -> ELANW
anweisung -> PASS
anweisung -> WH bedingung DP anweisungsfolge WH_ENDE
...
bedingung -> BED

Nutzung von 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 ...), der die syntaktische Analyse vornimmt.

Bevor wir YACC aktivieren, speichern wir die Grammatik in einer bestimmten Form zusätzlich zur Tokenfestlegung in einer Datei (z.B. syntaxMyKa.py) ab.

# Namen der Token
tokens = ['ELANW', 'BED', 'DP', 'WH', 'WH_ENDE', 'IF', 'IF_ENDE', 'ELSE', 'PASS']

# Beschreibung der Token
t_ELANW    = r'schritt|links|rechts|ziegelHinlegen|ziegelAufheben|markeSetzen|markeLoeschen'
t_BED      = r'vorZiegel|nichtVorZiegel|vorWand|nichtVorWand|aufMarke|nichtAufMarke'
t_DP       = r':'
t_WH       = r'while'
t_WH_ENDE  = r'\#while'
t_IF       = r'if'
t_IF_ENDE  = r'\#if'
t_ELSE     = r'else'
t_PASS     = r'pass'

# 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_elementar(p):
    'anweisung : ELANW'
    p[0] = None

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

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

# def p_anweisung_if(p):

def p_bedingung(p):
    'bedingung : BED'
    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 klar werden.

Scanner und Parser zur Syntax von MyKa kann man jetzt folgendermaßen erzeugen:

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

# Testprogramm
programm = '''
links
while nichtVorWand:
  ziegelHinlegen
  schritt
#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 1

Probiere das selbst einmal aus. Teste Quelltexte, die den Syntaxregeln von MyKa entsprechen und teste auch fehlerhafte Quelltexte. Wie zeigt sich in der vorliegenden Implementierung, ob der Quelltext fehlerfrei ist?

Aufgabe 2

Ergänze die noch fehlende Syntaxregel für Fallunterscheidungen. Teste deinen Vorschlag.