LbP Parser

Aus ProgrammingWiki

Archivierte Version vom 2010-03-01T14:47:37+00:00. Aktuelle Version

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

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: <eval id="4b8bd388a09e4"> satz([the,happy,boy,loves,a,sad,girl]). </eval>

Syntaktisch fehlerhafte Sätze werden zurückgewiesen: <eval id="4b8bd388a159c"> satz([the,happy,boy,loves,sad,girl]). </eval>

Der Parser kann auch als Satzgenerators eingesetzt werden: <eval id="4b8bd388a2152">satz(X).</eval>

Der Versuch, alle erzeugbaren Sätze in eine Liste zu generieren, scheitert aus Ressourcengrüden. Da sind wir (weiter unten) mit Differenzlisten wesentlich erfolgreicher. <eval id="4b8bd388a2d26">findall(X,satz(X),Xs).</eval>

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: <eval id="4b8bd388a38ea">parse([the,happy,boy,loves,a,sad,girl]).</eval>

parse kann auch als Satzgenerator verwendet werden: <eval id="4b8bd388a4483">parse(X).</eval>

Man kann die Anzahl der erzeugbaren Sätze bestimmen: <eval id="4b8bd388a505a">findall(X,parse(X),Ys),length(Ys,Z),write(Z).</eval>

Parser für a^nb^mc^j, für n,m,j>0

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: <eval id="4b8bd388a5b5c">abcsatz1([a,a,a,a,a,a,b,b,b,b,b,c,c,c,c,c]).</eval>

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. <eval id="4b8bd388a6715">abcsatz([a,a,a,a,a,a,a,a,b,b,b,b,b,b,c,c,b,c,c,c]).</eval> Der Nachteil dieses Vorschlags besteht darin, dass vor jedem Anfrage die Datenbasis auf’s Neue geladen werden muss.

LbP Parser

Parser für kontextfreie Sprachen

Einfache Grammatik für englische Sätze

Suche