Parsen und Übersetzen

Übersetzung regulärer Ausdrücke

 aufwärts

Ziel ist es, aus einem regulären Ausdruck z in systematischer Weise einen nicht­deterministischen endlichen Automaten N(z) zu konstruieren, der die von z erzeugte reguläre Sprache L(z) erkennt. Hierzu wird zuerst eine kontextfreie Grammatik für reguläre Ausdrücke angegeben. Basierend auf dieser Grammatik wird mithilfe der Recursive-Descent-Methode ein Übersetzer erzeugt, der einen regulären Ausdruck in den ent­sprechenden Automaten übersetzt. Die Übersetzungs­aktionen entsprechen den Schritten, die im Abschnitt Konstruktion eines nicht­deterministischen endlichen Automaten aus einem regulären Ausdruck angegeben sind.

Grammatik

Zur Beschreibung regulärer Ausdrücke verwenden wir eine Grammatik mit folgenden Produktionen:

expr geht über nachterm (| term)*
term geht über nachfactor factor*
factor geht über nachatom **
atom geht über nach( expr )  |  literal
literal geht über nacha  |  b  |  c  |  %

Die Zeichen |, *, (, ) kommen einerseits in regulären Ausdrücken vor, sind also Terminal­zeichen der Grammatik, andererseits aber auch Metazeichen zur Beschreibung der Grammatik. Zur Unter­scheidung sind Terminal­zeichen rot dargestellt, Metazeichen schwarz.

Die Grammatik berück­sichtigt die Präzedenz­regeln bei der Auswertung regulärer Ausdrücke: * bindet am stärksten, | bindet am schwächsten. Das in den regulären Ausdrücken verwendete Alphabet besteht hier nur aus den Zeichen a, b und c. Das Zeichen % steht für die leere Menge.

Es folgt das Programm.

Klasse RegExprCompiler

Die folgende, von der Klasse Parser abgeleitete Klasse RegExprCompiler übersetzt einen regulären Ausdruck in den zugehörigen nicht­deterministischen endlichen Automaten. Sie enthält für jede Produktionen der Grammatik eine ent­sprechende Funktion.

Der Automat wird bottom-up aus einfachen Automaten durch Parallel- und Hinter­einander­schaltung sowie Abschluss­bildung mittels der Funktionen parallel, concat und star der unten angegebenen Klasse Nfa aufgebaut.

 

from Parser import *
from Nfa import *

# Compiler, der einen regulaeren Ausdruck in einen nichtdeterministischen
# endlichen Automaten (Klasse Nfa) uebersetzt (Bottom-up-Konstruktion)
def expr():
    v=term()
    while comes("|"):
        consume()
        v=v.parallel(term())
    return v

def term():
    v=factor()
    while comesAnyOf("abc%("):
        v=v.concat(factor())
    return v

def factor():
    v=atom()
    while comes("*"):
        consume()
        v=v.star()
    return v

def atom():
    if comes("("):
        consume()
        v=expr()
        match(")")
        return v
    else:
        return literal()

def literal():
    if comesAnyOf("abc%"):
        a=getSymbol()
        return Nfa(a)  # Elementarautomat fuer Symbol a
    else:
        raise Exception("Buchstabe oder % erwartet")

 

Ein möglicher Aufruf des Übersetzers ist

from RegExprCompiler import *

v=compile("(a|b)*a", expr)
showErrorPosition()
print "Ergebnis:", v

Klassen State und Nfa

Zunächst folgt die Klasse State, die einen Zustand des Automaten darstellt. Bedingt durch die spezielle Konstruktion des Automaten ist die Klasse State sehr einfach aufgebaut.

Der Automat hat genau einen Endzustand. Dieser ist der einzige Zustand, der keinen Folgezustand hat. Alle anderen Zustände des Automaten haben einen oder zwei Folge­zustände. Hat ein Zustand zwei Folge­zustände, so sind beide Zustands­übergänge mit ε markiert.

Attribute der Klasse sind eine Liste nextstate mit bis zu zwei Einträgen, die Verweise auf die beiden möglichen Folge­zustände enthält, sowie ein String symbol, der das Zeichen enthält, mit dem der Zustand in den Folgezustand übergeht. Ferner trägt jeder Zustand eine Nummer; diese wird mithilfe der Klassen­variable n bei jeder Erzeugung eines neuen Zustands hochgezählt. Für die Ausgabe und die Simulation des Automaten wird außerdem das boolesche Attribut marked benötigt.

# Repraesentiert einen Zustand in einem nichtdeterministischen
# endlichen Automaten mit Epsilon-Uebergaengen (Epsilon wird
# durch $ dargestellt)
class State(object): 
    n=0    # Zaehler fuer Zustaende
    
    def __init__(self, a="$"):
        self.nextstate=[]
        self.symbol=a
        self.number=State.n
        State.n+=1
        self.marked=False
    
    def setNextState(self, s):
        self.nextstate.append(s)
        
    def mark(self, b=True):
        self.marked=b

    def __str__(self):
        return str(self.number)

 

Die folgende Klasse Nfa (nondeterministic finite automaton) repräsentiert einen nicht­deterministischen endlichen Automaten. Sie enthält einen Konstruktor zur Erzeugung eines Elementar­automaten für ein Alphabet­zeichen a. Derselbe Konstruktor wird verwendet, um den Elementar­automaten für die leere Sprache, hier bezeichnet durch das Zeichen %, zu erzeugen. Da das Zeichen % nicht im Alphabet vorkommt, kann der Zustands­übergang mit dem Zeichen % nie ausgeführt werden, sodass der Automat wie gewünscht die leere Sprache akzeptiert.

Die Klasse enthält ferner Methoden zur Parallel­schaltung und Hinter­einander­schaltung des Automaten mit einem anderen Automaten sowie eine Methode für die Abschluss­bildung, also die Anwendung des Stern-Operators, außerdem eine Methode zur Darstellung des Automaten als Tabelle der Übergangs­relation.

from State import *

# Repraesentiert einen nichtdeterministischen endlichen Automaten mit
# Epsilon-Ubergaengen (nondeterministic finite automaton - NFA)
# und stellt die Operationen Parallel- und Hintereinanderschaltung
# sowie Abschluss zur Verfuegung
class Nfa(object):

    # Elementarautomat mit Symbol a
    def __init__(self, a):
        self.startstate=State(a)
        self.endstate=State()
        self.startstate.setNextState(self.endstate)

    # Schaltet Nfa self und Nfa other parallel
    def parallel(self, other):
        s=State()
        t=State()
        s.setNextState(self.startstate)
        s.setNextState(other.startstate)
        self.endstate.setNextState(t)
        other.endstate.setNextState(t)
        self.startstate=s
        self.endstate=t
        return self

    # Verkettet Nfa self mit Nfa other
    def concat(self, other):
        self.endstate.setNextState(other.startstate)
        self.endstate=other.endstate
        return self

    # Bildet den Abschluss Nfa self*
    def star(self):
        s=State()
        t=State()
        s.setNextState(self.startstate)
        s.setNextState(t)
        self.endstate.setNextState(s)
        self.startstate=s
        self.endstate=t
        return self

    # Loescht oder setzt alle Markierungen
    def mark(self, b=True):
        q=[self.startstate]  # Queue
        while q!=[]:
            s=q.pop(0)
            if s.marked!=b:
                s.mark(b)
                for t in s.nextstate:
                    q.append(t)

    # Stellt den Automaten in Form einer Tabelle dar:
    # Zustand / Zeichen / Folgezustaende unter diesem Zeichen
    # Startzustand ist der erste Zustand, Endzustand ist
    # derjenige Zustand, der keine Folgezustaende hat
    def __str__(self):
        self.mark(False)     # alle Markierungen entfernen
        w=""
        q=[self.startstate]  # Queue
        while q!=[]:
            s=q.pop(0)
            if not s.marked:
                s.mark()
                w+="\n"+str(s)+"  "+s.symbol+"  "
                for t in s.nextstate:
                    w+=str(t)+"  "
                    q.append(t)
        return w+"\n"
    

Zusammenfassung

Die Struktur regulärer Ausdrücke ist durch die Grammatik für reguläre Ausdrücke vorgegeben. Aus dieser Grammatik haben wir mit der Recursive-Descent-Methode einen Übersetzer für reguläre Ausdrücke konstruiert. Ziel der Übersetzung eines bestimmten regulären Ausdrucks ist ein zugehöriger nicht­deterministischer endlicher Automat, der die von dem regulären Ausdruck erzeugte Sprache erkennt.

Mithilfe des so konstruierten Automaten lässt sich feststellen, ob ein bestimmtes Wort w von einem gegebenen regulären Ausdruck erzeugt wird (siehe Simulation eines nicht­deterministischen endlichen Automaten).

 

Weiter mit:   [Simulation eines nichtdeterministischen endlichen Automaten]   oder   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   Datenschutz   ©   Created: 24.08.2012   Updated: 10.06.2018
Valid HTML 4.01 Transitional

Hochschule Flensburg
Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik