Basisklassen

Klasse Parser

Die Klasse Parser stellt die (abstrakte) Basisklasse für alle Parser und Compiler dar. Die Methode startSymbol, die in der Methode compile aufgerufen wird, muss in einer abgeleiteten Klasse implementiert werden.

 

# Basisklasse fuer Parser und Compiler
class Parser(object):

    # Uebernimmt einen Eingabestring und ruft das Startsymbol
    # der Grammatik auf; erzeugt ggf. Fehlermeldung und
    # Position des Fehlers im Eingabestring.
    def compile(self, x):
        self.inputstring=x
        self.parsestring=x
        self.haserrors=False
        self.errormessage="ok"
        r=None
        try:
            r=self.startSymbol()
            if self.parsestring:
                raise Exception("Zuviele Zeichen: "+self.parsestring)
        except Exception as e:
            self.haserrors=True
            self.errormessage=str(e)
        self.errorposition=len(x)-len(self.parsestring)
        return r
    
    # Andere Bezeichnung fuer compile ohne Rueckgabewert
    def parse(self, x):
        self.compile(x)
    
    
    # Liefert True, wenn das Eingabewort mit String x beginnt
    def comes(self, x):
        return self.parsestring.startswith(x)

    # Entfernt k Zeichen am Anfang des Eingabewortes
    def consume(self, k):
        self.parsestring=self.parsestring[k:]

    # Entfernt String x am Anfang des Eingabewortes
    def consumeStr(self, x):
        self.consume(len(x))    # Praefix x wird konsumiert

    # Wenn das Eingabewort mit String x beginnt, wird
    # der String x am Anfang des Eingabewortes entfernt.
    # Anderenfalls wird eine Exception ausgeloest.
    def match(self, x):
        if self.comes(x):
            self.consumeStr(x)
        else:
            raise Exception("Erwartet: "+x)

Konkreter Parser

Ein konkreter Parser wird anhand einer Grammatik nach der Recursive-Descent-Methode geschrieben. Hierzu wird eine konkrete Parser-Klasse erstellt, die von der Klasse Parser abgeleitet wird. In der konkreten Klasse muss die Methode startSymbol implementiert sein.

Als Beispiel betrachten wir folgende Grammatik:

Sgeht über nachaSb  |  ε

Die Grammatik erzeugt die Sprache { anbn  |  n ∈ ℕ0 }.

In der Methode startSymbol wird das Startsymbol der Grammatik, hier S, aufgerufen.

from Parser import *

class ParserAnbn(Parser):
    
    def startSymbol(self):
        self.s()
    
    def s(self):
        if self.comes("a"):
            self.match("a")
            self.s()
            self.match("b")

Mit folgenden Anweisungen wird ein Objekt vom Typ ParserAnbn erzeugt und anschließend das Wort aabb analysiert.

    p=ParserAnbn()
    p.parse("aabb")
    print p.errormessage

Compiler

Während ein Parser nur die Syntax prüft, übersetzt ein Compiler zusätzlich den Eingabe­string in einen Wert. Dieser Wert kann eine Zahl sein, ebenfalls wieder ein String, oder ein beliebiges Objekt.

Der folgende Compiler übersetzt logische Formeln, die aus den Konstanten 0 und 1 sowie den Operanden +, * und ! gebildet sind, in einen Wahrheits­wert. Hierbei stehen 0 und 1 für die Wahrheits­werte False und True; die Operatoren +, * und ! stehen für die logischen Ver­knüpfungen Oder, Und und Nicht. Die Auswertungs­reihenfolge kann durch Klammern gesteuert werden; zusätzlich gilt: Der Operator ! bindet am stärksten, der Operator * am zweit­stärksten, und der Operator + bindet am schwächsten (Punkt­rechnung geht vor Strich­rechnung).

Die ent­sprechende Grammatik ist folgende:

expr geht über nachterm (+ term)*
term geht über nachfactor (* factor)*
factor geht über nach! factor  |  ( expr )  |  literal
literal geht über nach0  |  1

Aus der Grammatik ergibt sich folgender Recursive-Descent-Übersetzer:

from Parser import *

class CompilerLogic(Parser):
    
    def startSymbol(self):
        return self.expr()
    
    def expr(self):
        v=self.term()
        while self.comes("+"):
            self.match("+")
            v|=self.term()
        return v
        
    def term(self):
        v=self.factor()
        while self.comes("*"):
            self.match("*")
            v&=self.factor()
        return v
    
    def factor(self):
        if self.comes("!"):
            self.match("!")
            v=not self.factor()
        elif self.comes("("):
            self.match("(")
            v=self.expr()
            self.match(")")
        else:
            v=self.literal()
        return v
    
    def literal(self):
        if self.comes("0"):
            self.match("0")
            return False
        elif self.comes("1"):
            self.match("1")
            return True
        else:
            raise Exception("Erwartet: 0 oder 1")

Mit folgenden Anweisungen wird ein Objekt vom Typ CompilerLogic erzeugt und anschließend das Wort 0+!0*1+!0 analysiert.

    p=CompilerLogic()
    print(p.compile("0+!0*1+!0"))
    print(p.errormessage)

 

[up]

 


H.W. Lang   mail@hwlang.de   Impressum   Datenschutz
Created: 26.03.2010   Updated: 19.02.2023
Diese Webseiten sind während meiner Lehrtätigkeit an der Hochschule Flensburg entstanden