Parser

Aufgabe des Parsers

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

Wir betrachten wieder den folgenden Quelltext:

x = 2
y = 3
p = 0
while y != 0:
    p = p + x
    y = y - 1
#end

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

(VAR,'x')
(ZUW,'=')
(ZAHL,'2')
(VAR,'y')
(ZUW,'=')
(ZAHL,'3')
(VAR,'p')
(ZUW,'=')
(ZAHL,'0')
(WHILE,'while')
(VAR,'y')
(UG,'!=')
(NULL,'0')
(DP,':')
...

Der Parser muss jetzt u.a. überprüfen, ob eine Wiederholung aus Token der Gestalt WHILE "Bedingung" : "Anweisungsfolge" END besteht. Damit das möglich ist, wird die Grammatik der Sprache MiniPython präzise festgelegt (siehe Entwicklung eines Compilers - MiniPython).

Ein Parser hat nicht nur die Aufgabe, die Syntax zu überprüfen, ein Parser erzeugt zusätzlich auch eine strukturierte Darstellung des vorgegebenen Programms für die weitere Verarbeitung , sofern das Programm syntaktisch korrekt ist.

Für das oben gezeigte Beispielprogramm könnte die strukturierte Darstellung z.B. so aussehen:

[
  ['=', ('VAR', 'x'), [('ZAHL', '2')]],
  ['=', ('VAR', 'y'), [('ZAHL', '3')]],
  ['=', ('VAR', 'p'), [('ZAHL', '0')]],
  ['while', ['!=', ('VAR', 'y'), ('ZAHL', '0')],
  [
    ['=', ('VAR', 'p'), ['+', ('VAR', 'p'), ('VAR', 'x')]],
    ['=', ('VAR', 'y'), ['-', ('VAR', 'y'), ('ZAHL', '1')]]]
  ]
]

Die Abbildung zeigt noch einmal das Verhalten des Parsers.

[1]

Aufgabe 1

Benutze das Simulationsprogramm, um MiniPython-Quelltexte zu parsen.

[2]