close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

9 Wie kann man das Wortproblem bei kontextfreien Sprachen lösen?

EinbettenHerunterladen
9
Wie kann man das Wortproblem bei kontextfreien
Sprachen lösen?
Zur Erinnerung: Erstens, das Wortproblem ist folgende Fragestellung: „Gegeben eine Zeichenkette w 0 G* über einem Alphabet G und eine Grammatik G. Frage: Ist w 0 L(G)?”. Zweitens,
kontextfreie Grammatiken G = (V, G, P, S) sind solche, bei denen die Produktionen die Gestalt
A 6 σ haben, wobei A 0 V und σ 0 (V c G)* ist.
Bei regulären Sprachen ist die Sachlage bzgl. des Wortproblems relativ einfach: Liegt eine
Sprache L(G) in Form ihrer regulären Grammatik vor, konstruiert man den äquivalenten DEA
A zu G und schaut, ob w von A akzeptiert wird. Immer gibt es eine ja/nein-Entscheidung.
Kontextfreie Sprachen wie die für korrekt geklammerte Ausdrücke spielen neben den regulären eine zentrale Rolle bei der Definition von Programmiersprachen. Hier tritt das Wortproblem
in anschaulicher Form z.B. stets bei der Übersetzung von Programmen durch einen Compiler auf
und wird Parsing genannt, das in drei Phasen aufgeteilt wird, in die lexikalische, die syntaktische und die semantische Analyse. HTML-Text gehorcht z.B. einer kontextfreien Grammatik.
Es wurde bereits erwähnt, dass eine geeignete Darstellung für Wörter, die von einer kontextfreien Grammatik erzeugt werden, die Baumstruktur ist. Das Wortproblem für kontextfreie
Grammatiken könnte im Kern auch so gestellt werden: Suche den Parsebaum zu w relativ zu G.
Betrachten wir eine naheliegende Methode zur Erstellung des Syntaxbaumes. Prinzip: Vom
Startsymbol ausgehend werden die Nonterminale „horizontal” expandiert und verglichen, ob das
Erzeugte noch mit der Eingabe kompatibel ist (z. B. dadurch, dass man die übereinstimmenden
Terminale aus Eingabe und Erzeugtem gegeneinander „weg kürzt”). Die „Restwörter” werden
bei Expansion nach unten bzw. oben weitergegeben.
Beispiel:
(1) S 6 aSbS
(2) S 6 aS
(3) S 6 c
78
79
Das gezeigte graphische Verfahren ist sehr intuitiv und wenig geeignet um es zu programmieren. Wir verwenden für eine potenzielle Implementierung einen Kellerungsmechanismus, der in
zwei Ausprägungen vorhanden ist, einen um die Restzeichenkette zu verwalten und einen, der
als „Buchführungskeller” die „Backup”- oder „Sackgassen”-Verwaltung realisiert.
(1) S 6 aSbS
(2) S 6 aS
(3) S 6 c
Eingabe
Satzformkeller
BuchführKeller
Test E/K
Aktion
aacbc
aacbc
acbc
acbc
cbc
cbc
cbc
cbc
cbc
cbc
bc
c
c
c
c
c
c
g
c
c
bc
cbc
cbc
acbc
acbc
acbc
cbc
cbc
cbc
cbc
cbc
cbc
bc
c
c
c
c
c
c
g
S
aSbS
SbS
aSbSbS
SbSbS
aSbSbSbS
SbSbS
aSbSbS
SbSbS
cbSbS
bSbS
SbS
aSbSbS
SbS
aSbS
SbS
cbS
bS
cbS
SbS
bSbS
cbSbS
SbSbS
aSbSbS
SbS
aSbS
SbS
aSbSbS
SbS
aSbS
SbS
cbS
bS
S
aSbS
S
aS
S
c
g
g
1
1a
1a1
1a1a
1a1a1
1a1a
1a1a2
1a1a
1a1a3
1a1a3c
1a1a3cb
1a1a3cb1
1a1a3cb
1a1a3cb2
1a1a3cb
1a1a3cb3
1a1a3cb3c
1a1a3cb3
1a1a3cb
1a1a3c
1a1a3
1a1a
1a1
1a
1a2
1a2a
1a2a1
1a2a
1a2a2
1a2a
1a2a3
1a2a3c
1a2a3cb
1a2a3cb1
1a2a3cb
1a2a3cb2
1a2a3cb
1a2a3cb3
1a2a3cb3c
a…S
a=a
a…S
a=a
c…S
c…a
c…S
c…a
c…S
c=c
b=b
c…S
c…a
c…S
c…a
c…S
c=c
ε…b
k. weit. Prod.
c…S
expandiere mit 1
lösche und merke
expandiere mit 1
lösche und merke
expandiere mit 1
rückgängig machen
expandiere mit 2
rückgängig machen
expandiere mit 3
lösche und merke
lösche und merke
expandiere
rückgängig machen
expandiere
rückgängig machen
expandiere
lösche und merke
restauriere
Y backup
restauriere
k. weit. Prod.
Y backup
restauriere
nächste Prod.
a…S
a=a
c…S
c…a
c…S
c…a
c…S
c=c
b=b
c…S
c…a
c…S
c…a
c…S
c=c
g=g
expandiere mit 2
lösche und merke
expandiere mit 1
rückgängig machen
expandiere mit 2
rückgängig machen
expandiere mit 3
lösche und merke
lösche und merke
expandiere mit 1
rückgängig machen
expandiere mit 2
rückgängig machen
expandiere mit 3
lösche und merke
accept
Ê
80
Bemerkungen:
>
Man beachte im Beispiel, dass Breitensuche durchgeführt wird. Reine Tiefensuche macht
Probleme bei linksrekursiven Symbolen.
>
Werden beim Eingabe/Keller-Test Terminale verglichen, wird bei Gleichheit die Richtigkeit der letzten Produktion angenommen, aber prophylaktisch die Eingabe gespeichert
(könnte auch durch Merker für die Eingabe-Position realisiert werden).
>
Bei Eingabe/Keller-Test auf Nonterminale wird mit der „nächsten” Produktion expandiert. Gibt es keine mehr, wird der aktuelle Expansions-Versuch abgebrochen. Damit ist
aber die vorhergehende Expansion auch eine Sackgasse und die nächste Möglichkeit ist
zu testen.
>
Die Erstellung des Syntaxbaumes nach dieser Methode geschieht von links nach rechts
und liefert die linkskanonische Ableitung (leftmost derivation). Den Vorgang könnte man
wie folgt visualisieren.
81
>
Das Verfahren („systematisches Ausprobieren”) ist intuitiv und deshalb einfach und
verständlich, aber sehr aufwändig. Es gibt zwar bessere Verfahren (etwa von EARLEY
oder von COCKE & KASAMI & YOUNGER), die das Wortproblem hinsichtlich beliebiger kontextfreier Grammatiken zu lösen gestatten; sie sind aber trotzdem für die Praxis
wegen eines immer noch hohen Speicherplatz- und Laufzeitbedarfs als ungeeignet zu betrachten. In der Compilertechnik werden deshalb nur solche Verfahren eingesetzt, die
das Wortproblem in linearer Zeit zu lösen gestatten. Das ist aber nur möglich, wenn man
weitere Einschränkungen hinsichtlich der rechten Seite der Produktionen der kontextfreien Grammatiken macht. Dies führt zu den LL(k)- bzw. LR(k)-Grammatiken.
82
Document
Kategorie
Gesundheitswesen
Seitenansichten
7
Dateigröße
264 KB
Tags
1/--Seiten
melden