LbP Parser

Aus ProgrammingWiki

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

append([],Ys,Ys). append([X|Xs],Ys,[X|Zs]):- append(Xs,Ys,Zs).

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

satz(X) :- append(Y,Z,X), np(Y), vp(Z). np([X,Y]) :- art(X), nom(Y). np([X,Y,Z]) :- art(X), adj(Y), nom(Z). vp([X|Xs]) :- verb(X), np(Xs). nom(boy). nom(girl). nom(ball). verb(kicked). verb(loves). art(the). art(a). adj(happy). adj(sad).

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

satz([the,happy,boy,loves,a,sad,girl]).

ausführen

Syntaktisch fehlerhafte Sätze werden zurückgewiesen:

satz([the,happy,boy,loves,sad,girl]).

ausführen

Der Parser kann auch als Satzgenerators eingesetzt werden:

satz(X).

ausführen

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

findall(X,satz(X),Xs).

ausführen

Parser mit Anwendung der Differenzlistentechnik

satz(X,Y) :- np(X,Z), vp(Z,Y). np(X,Y) :- art(X,Z), nom(Z,Y). np(X,Y) :- art(X,Z), adj(Z,L), nom(L,Y). vp(X,Y) :- verb(X,Z), np(Z,Y). nom([boy|X],X). nom([girl|X],X). nom([ball|X],X). verb([kicked|X],X). verb([loves|X],X). art([the|X],X). art([a|X],X). adj([happy|X],X). adj([sad|X],X).

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

parse(X) :- satz(X,[]).

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

parse([the,happy,boy,loves,a,sad,girl]).

ausführen

parse kann auch als Satzgenerator verwendet werden:

parse(X).

ausführen

Man kann die Anzahl der erzeugbaren Sätze bestimmen:

findall(X,parse(X),Ys),length(Ys,Z),write(Z).

ausführen

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.

abcsatz1(Xs) :- append(U,V,R), append(R,W,Xs), as(U), bs(V), cs(W). as([a]). as([a|Xs]) :- as(Xs). bs([b]). bs([b|Xs]) :- bs(Xs). cs([c]). cs([c|Xs]) :- cs(Xs).

Aufrufbeispiel:

abcsatz1([a,a,a,a,a,a,b,b,b,b,b,c,c,c,c,c]).

ausführen

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.

abcsatz([]). abcsatz([a|Xs]) :- abcsatz(Xs). abcsatz([b|Xs]) :- retractall(abcsatz([a|_])), abcsatz(Xs). abcsatz([b|Xs]) :- abcsatz(Xs). abcsatz([c|Xs]) :- retractall(abcsatz([a|_])), retractall(abcsatz([b|_])), abcsatz(Xs). abcsatz([c|Xs]) :- retractall(abcsatz([b|_])), abcsatz(Xs). abcsatz([c|Xs]) :- abcsatz(Xs). :- dynamic(abcsatz/1).

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

abcsatz([a,a,a,a,a,a,a,a,b,b,b,b,b,b,c,c,b,c,c,c]).

ausführen

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