LbP Parser

Aus ProgrammingWiki

Wechseln zu: Navigation, Suche

Parser für kontextfreie Sprachen

Einfache Grammatik für englische Sätze

Nichtterminale: SATZ, NP, VP, NOM, VERB, ART, ADJ Die Symole stehen für Satz, Nominalphrase, Verbalphrase, Nomen, Verb, Artikel und Adjektiv.
Terminale: boy, girl, ball, kicked, loves, the, a, happy, sad
Produktionen:

SATZ 	-> 	NP VP;
NP 	-> 	ART NP | ART ADJ NP;
VP 	->	VERB NP;
NOM	->	boy | girl | ball;
VERB 	->	kicked | loves;
ART	->	the | a;
ADJ	->	happy | sad.

Spitzensymbol: SATZ

Repräsentation eines Parsers für diese Grammatik mit Prolog

Das Parsing ist äusserlich bekanntlich nicht sehr spektakulär:

Syntaktisch fehlerhafte Sätze werden zurückgewiesen:

Der Parser kann auch als Satzgenerators eingesetzt werden:

Der Versuch, alle erzeugbaren Sätze in eine Liste zu generieren, scheitert aus Ressourcengrüden. Da sind wir (weiter unten) mit Differenzlisten wesentlich erfolgreicher.

Parser mit Anwendung der Differenzlistentechnik

Dies kann durchaus das Produkt einer automatischen Programmtransformation sein. Wir fügen ein parse-Prädikat hinzu, um den Aufruf komfortabler zu gestalten.

Wir überprüfen den Satz the happy boy loves a sad girl auf syntaktische Korrektheit:

parse kann auch als Satzgenerator verwendet werden:

Man kann die Anzahl der erzeugbaren Sätze bestimmen:

Parser für , für

SATZ	-> AS BS CS;
AS	-> a | a AS;
BS	-> b | b BS;
CS	-> c | c CS.

Dies ist eine sehr einfache Grammatik. {a,b,c} ist die Menge der Terminale. Die Anzahlen der a’s, b’s und c’s können also ganz unterschiedlich sein.

Aufrufbeispiel:

Der Parser ist nicht in der Lage, syntaktisch fehlerhafte abc-Wörter als solche zu erkennen. Dies ist für den folgenden Lösungsvorschlag kein Problem: Sobald das erste b erscheint, werden alle Klauseln, die für a zuständig waren, aus der Datenbasis entfernt. Später verfährt das Programm mit c ganz analog.

Die folgende Frage wird nach sehr kürzer Rechenzeit mit No beantwortet.

Der Nachteil dieses Vorschlags besteht darin, dass vor jedem Anfrage die Datenbasis auf’s Neue geladen werden muss.

Persönliche Werkzeuge