[Python-de] [LANG] Parser

Gerson Kurz Gerson.Kurz at t-online.de
Mon May 6 18:26:16 EDT 2002


Ich habe ja ein Reihe von Parsern für meine diversen obskuren
Programmiersprachen geschrieben (siehe http://p-nand-q.com/languages.htm)
und ich wollte selber schon lange mal eine Art "Mini-HOWTO" dafür schreiben.
Ich hatte vor zig Jahren auf dem Amiga (Gott habe ihn selig) in Assembler
(Motorola 68000, das war wenigstens schöner Code und nicht son'
Intelschrott) mal einen Parser geschrieben, und das war ein Aha-Erlebnis: es
geht -zumindest, solange du bei recursive-descent-parsern bleibst- ganz
einfach; ist nicht schwerer zu verstehen als Lex&Yacc&Co, und der Code ist
sogar noch lesbar. Zudem ist es so ziemlich das einzig Sinnvolle, daß ich
von der Vorlesung "Compilerbau" behalten habe ;)

Betrachte folgende Aufgabe: Du sollst einen mathematischen Ausdruck
auswerten, mit +,-,*,/, unter Berücksichtigung von "Punkt-vor-Strich", und
mit Klammern beliebiger Tiefe. Das ist eine prima Aufgabe für einen
Anfänger-Parser.

Zuerst solltest du dir die Syntax überlegen. Die Syntax (in meinem privaten
UBNF-Dialekt) fällt vom Himmel und schaut so aus:

EINGABE = AUSDRUCK.
AUSDRUCK = TERM { ('+'|'-') TERM }.
TERM = FAKTOR { ('*'|'/') FAKTOR }.
FAKTOR = '(' AUSDRUCK ')' | ZAHL.
ZAHL = ZIFFER { ZIFFER }.
ZIFFER = '0' ... '9'.

Erklärung: Sachen in Anführungszeichen sind "literals", Zeichen die so
explizit im Code stehen. Du kannst daraus erkennen, daß der Ausdruck aus
'+', '-', '*', '/', '(', ')', und '0' bis '9' bestehen darf. (Daß "..." für
die Ziffern '1', '2' etc. steht, ist denke ziemlich klar). Da 'W' nicht in
der Syntax vorkommt, darf "W" auch nicht in einem Ausdruck vorkommen.

Also bedeutet die Zeile

ZIFFER = '0' ... '9'.

umgangssprachlich: Eine Ziffer ist ein Zeichen '0', '1', '2' ... oder '9'.

Sachen, die in geschweiften Klammern stehen, können beliebig oft wiederholt
werden (0 bis n mal). Also sagt

ZAHL = ZIFFER { ZIFFER }.

aus, daß eine ZAHL mindestens eine ZIFFER hat, gefolgt von beliebig vielen
weiteren ZIFFERn. Sachen, die durch '|' getrennt sind, sind optional, also
bedeutet

FAKTOR = '(' AUSDRUCK ')' | ZAHL.

das ein FAKTOR entweder ein AUSDRUCK in Klammern ist, ODER eine Zahl. (Die
drei Bestandteile "'('", "AUSDRUCK" und "')'" haben die selbe "Priorität").
Mit runden Klammern kann man den "|" Operator schachteln, also bedeutet

TERM = FAKTOR { ('*'|'/') FAKTOR }.

daß ein TERM ein FAKTOR ist, gefolgt von beliebig oft (Entweder ein '*' oder
ein '/'; JEWEILS gefolgt von einem FAKTOR). Dito für

AUSDRUCK = TERM { ('+'|'-') TERM }.

Ein AUSDRUCK ist ein TERM, gefolgt von beliebig oft (Entweder ein '+' oder
ein '-'; JEWEILS gefolgt von einem TERM).

Mit diesem Wissen kannst du schon mal auf einem Stück Papier "überprüfen",
ob

2*(3-7)

ein gültiger Ausdruck ist:

- Der AUSDRUCK ist "2*(3-7)"
- Der TERM ist "2*(3-7)"
- FAKTOR ist "2"
- 2 ist eine ZAHL
- die aus genau einer ZIFFER besteht.
- Nach FAKTOR kommt ein '*', also musst du den Rest gegen "FAKTOR"
überprüfen, also must du testen, ob "(3-7)" ein gültiger FAKTOR ist.
- Der FAKTOR fängt mit '(' an und hört mit ')' auf, also musst du testen, ob
3-7 ein gültiger AUSDRUCK ist.
- Der TERM ist 3 (FAKTOR=>ZAHL=>ZIFFER, also gültig), gefolgt von '-' und
dem TERM 7 (FAKTOR=>ZAHL=>ZIFFER, also gültig).

Im gegensatz dazu ist

2+/5

KEIN gültiger Ausdruck, weil "/5" kein gültiger TERM ist.

Übrigens, Punkt-vor-strich ist mit dieser Syntax automatisch behandelt: Der
Ausdruck

2+3*4

bedeutet TERM(2) "+" TERM(FAKTOR(3) "*" FAKTOR(4)). Probier es aus!

Wenn du das Prinzip der Syntax verstehst, ist die Implementation ein
Kinderspiel. (Nur mal so: Ich persönlich mag C-Parser fast lieber als
Python-Parser, weil das String-Handling für den Parser IMHO etwas unhandlich
ist - und du immer auf die blöden Exceptions gefasst sein mußt. Ich *hasse*
Exceptions!)

Egal, laß uns eine Klasse definieren:

class Parser:

Als erste Funktion bauen wir unseren eigenen "Eval":

    # "EINGABE = AUSDRUCK."
    def Eval(self, expression):
        self.expression = expression
        self.index = 0
        return self.AUSDRUCK()

Die zwei Member-Variablen self.expression und self.index brauche ich, damit
ich immer die aktuelle Analyseposition im String weiß. Der eigentliche
Programmcode steckt in der Angabe "return self.AUSDRUCK()", das ist einfach
direkt die Umsetzung der Zeile

EINGABE = AUSDRUCK.

aus der obigen Syntax. Wenn du z.B. eine Programmiersprache hast, in der
mehrere Befehle hintereinander stehen, dann gibt es nicht nur einen
Ausdruck, sondern z.B. sowas:

EINGABE = ZEILE { ZEILE }.

Zurück zum Programm. Laß uns mal den Teil

ZIFFER = '0' ... '9'.

realisieren:

    def ZIFFER(self):
        try:
            result = int(self.expression[self.index])
            self.index +=1
            return result
        except:
            pass

Whoa! Was passiert:

	self.expression[self.index]

ist das aktuelle Zeichen. mit int() wandelst du es in eine Ziffer um. Wenn
es keine Ziffer ist, gibt es eine Exception und die Funktion wird None
zurückgeben. Wenn es eine Ziffer ist, dann weisst du, daß und welche Ziffer
dieses Zeichen ist, du kannst also schon mal auf die nächste Leseposition
vorschalten.

Die Funktion gibt also None zurück, wenn das aktuelle Zeichen keine Ziffer
ist, oder die Ziffer, wenn es eine ist. => Du kannst im Prinzip die Syntax
DIREKT in Code umsetzen <=

Betrachte die Syntax-Zeile

ZAHL = ZIFFER { ZIFFER }.

angenommen, du kriegst die Ziffernfolge, "1", "2", "3". Dann musst du daraus
die Zahl 123 machen. Das machst du wie folgt (Pseudocode):

ergebnis = 0
nächste ziffer ist die 1
ergebnis = ergebnis * 10
addiere nächste ziffer auf das ergebnis: ergebnis wird zu 1
nächste ziffer ist die 2
ergebnis = ergebnis * 10 (also 10)
addiere nächste ziffer auf das ergebnis: ergebnis wird zu 12
nächste ziffer ist die 3
ergebnis = ergebnis * 10 (also 120)
addiere nächste ziffer auf das ergebnis: ergebnis wird zu 123

Das ganze als Routine:

    def ZAHL(self):
        r, z = 0, self.ZIFFER()
        if z is not None:
            while 1:
                if z is None:
                    break
                r *= 10
                r += z
                z = self.ZIFFER()
            return r

Beachte, daß die erste Ziffer gesondert überprüft werden muß, sonst kannst
du "0" nicht von einem ungültigen Ziffernausdruck unterscheiden. Das
Ergebnis dieser FUnktion ist None, wenn es sich nicht um eine mindestens aus
einer Ziffer bestehende Zahl handelt, oder eben die Zahl selber => Du kannst
im Prinzip die Syntax DIREKT in Code umsetzen <=.

Nächster Schritt:

FAKTOR = '(' AUSDRUCK ')' | ZAHL.

die Realisierung schaut bei mir so aus:

    def FAKTOR(self):
        if self.IST_ZEICHEN('('):
            ausdruck = self.AUSDRUCK()
            if ausdruck is not None and self.IST_ZEICHEN(')'):
                return ausdruck
            return None

        return self.ZAHL()

Zuerst überprüfst du, ob das aktuelle Zeichen ein "(" ist. Wenn nicht, dann
kannst du gleich zur Auswertung als ZAHL springen. Falls aber doch, dann
MUSS ein AUSDRUCK folgen, und ferner ein ')'. Eine Eingabe wie "()" ist
genauso falsch wie "(4" - weil festgelegt ist, daß auf "(" immer ein
AUSDRUCK und darauf immer ein ")" folgen muss. => Du kannst im Prinzip die
Syntax DIREKT in Code umsetzen <=

Bleibt als letztes

TERM = FAKTOR { '*'|'/' FAKTOR }

Das ist ein winziges bisserl umfangreicher, aber nur nanotechnologisch
winzig:

    def TERM(self):
        faktor = self.FAKTOR()
        if faktor is not None:
            while 1:
                if self.IST_ZEICHEN('*'):
                    v = self.FAKTOR()
                    if v is None:
                        raise "Syntax-Fehler: Nach einem TERM+ muß ein
weiterer TERM kommen."
                    faktor *= v
                elif self.IST_ZEICHEN('/'):
                    v = self.FAKTOR()
                    if v is None:
                        raise "Syntax-Fehler: Nach einem TERM- muß ein
weiterer TERM kommen."
                    faktor /= v
                else:
                    break
        return faktor

Zuerst ist festgelegt, daß ein TERM mit einem FAKTOR beginnen muß, daß steht
so in der Syntax. Darauf folgt entweder "*" und FAKTOR, oder "/" und FAKTOR.
Nur "*" ohne FAKTOR oder nur "/" ohne FAKTOR wäre ein Syntaxfehler. Ferner
ist die Auswertung klar: aus "/" wird geteilt-durch, aus "*" mal.

Das selbe Spielchen noch für

AUSDRUCK = TERM { '+'|'-' TERM }

und du hast einen fertigen Parser, in ca. 100 Programmzeilen. Der AHA-Effekt
besteht darin, daß die eigentliche Arbeit in der Syntax besteht- wenn die
mal festgelegt ist, kann man diese Art von Parsern mehr-oder-minder simpel
runterschreiben.

Übungsaufgaben mit steigendem Schwierigkeitsgrad: (Änderungen immer *zuerst*
in der Syntax, dann im Code)

- Erweitere die ZAHL-Definition um "Floating-Point" Zahlen.
- Erweitere die ZAHL-Definition um HEX-Zahlen.
- Erweitere die ZAHL-Definition um die Möglichkeit, statt auf eine Zahl auf
eine vordefinierte Variable zuzugreifen.
- Erweitere die AUSDRUCK-Definition um verschiedene Ebenen, die du z.B. für
logische Operatoren brauchst.

Auf http://p-nand-q.com/kalk.htm kannst du einen relativ umfangreichen
Taschenrechner sehen (mit kompletten C++-Sourcecode) sehen, der so
realisiert wurde (was heisst realisiert: ich hab es vor geraumer Zeit
hingerotzt und mich seitdem nicht mehr drum gekümmert ;)

HTH,
Gerson




-------------- next part --------------

## SYNTAX:
##
## EINGABE = AUSDRUCK.
## AUSDRUCK = TERM { '+'|'-' TERM }.
## TERM = FAKTOR { '*'|'/' FAKTOR }.
## FAKTOR = '(' AUSDRUCK ')' | ZAHL.
## ZAHL = ZIFFER { ZIFFER }.
## ZIFFER = '0' ... '9'.
    
class Parser:

    # "EINGABE = AUSDRUCK."
    def Eval(self, expression):
        
        # merke dir die startposition
        self.expression = expression
        self.index = 0
        
        # Die Eingabe ist ein Ausdruck.
        return self.AUSDRUCK()

    # AUSDRUCK = TERM { '+'|'-' TERM }.
    def AUSDRUCK(self):
        term = self.TERM()
        if term is not None:
            while 1:
                if self.IST_ZEICHEN('+'):
                    v = self.TERM()
                    if v is None:
                        raise "Syntax-Fehler: Nach einem TERM+ muß ein weiterer TERM kommen."
                    term += v
                elif self.IST_ZEICHEN('-'):
                    v = self.TERM()
                    if v is None:
                        raise "Syntax-Fehler: Nach einem TERM- muß ein weiterer TERM kommen."
                    term -= v                    
                else:
                    break
        return term

    # TERM = FAKTOR { '*'|'/' FAKTOR }.
    def TERM(self):
        faktor = self.FAKTOR()
        if faktor is not None:
            while 1:
                if self.IST_ZEICHEN('*'):
                    v = self.FAKTOR()
                    if v is None:
                        raise "Syntax-Fehler: Nach einem TERM+ muß ein weiterer TERM kommen."
                    faktor *= v
                elif self.IST_ZEICHEN('/'):
                    v = self.FAKTOR()
                    if v is None:
                        raise "Syntax-Fehler: Nach einem TERM- muß ein weiterer TERM kommen."
                    faktor /= v                    
                else:
                    break
        return faktor

    ## FAKTOR = ZAHL | '(' AUSDRUCK ')'.
    def FAKTOR(self):
        if self.IST_ZEICHEN('('):
            ausdruck = self.AUSDRUCK()
            if ausdruck is not None and self.IST_ZEICHEN(')'):
                return ausdruck
            return None
            
        return self.ZAHL()

    ## ZAHL = ZIFFER { ZIFFER }.
    def ZAHL(self):
        r, z = 0, self.ZIFFER()
        if z is not None:
            while 1:
                if z is None:
                    break
                r *= 10
                r += z
                z = self.ZIFFER()
            return r

    # ZIFFER = '0' ... '9'.
    def ZIFFER(self):
        try:
            result = int(self.expression[self.index])
            self.index +=1
            return result
        except:
            pass

    def IST_ZEICHEN(self,zeichen):
        try:
            l = len(zeichen)
            c = self.expression[self.index:self.index+l]
            if c == zeichen:
                self.index += l
                return 1
        except:
            pass

p = Parser()

print p.Eval("2*(5-6*1)")



More information about the Python-de mailing list