LbP Parser

Wiki-Quelltext dieser Seite.

<language>Prolog</language>
==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.<br/>
Terminale: <tt>boy</tt>, <tt>girl</tt>, <tt>ball</tt>, <tt>kicked</tt>, <tt>loves</tt>, <tt>the</tt>, <tt>a</tt>, <tt>happy</tt>, <tt>sad</tt><br/>
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<br/>

<code id="4b8bd3889c3b9" hidden>
append([],Ys,Ys).
append([X|Xs],Ys,[X|Zs]):- append(Xs,Ys,Zs).
</code>

Repräsentation eines Parsers für diese Grammatik mit Prolog
<code id="4b8bd3889cf4f">
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).
</code>
Das Parsing ist äusserlich bekanntlich nicht sehr spektakulär:
<run id="4b8bd388a09e4">
satz([the,happy,boy,loves,a,sad,girl]).
</run>

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

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

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

Parser mit Anwendung der Differenzlistentechnik
<code id="4b8bd3889db03">
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).
</code>
Dies kann durchaus das Produkt einer automatischen Programmtransformation sein.
Wir fügen ein parse-Prädikat hinzu, um den Aufruf komfortabler zu gestalten.
<code id="4b8bd3889e6d9">parse(X) :- satz(X,[]).</code>

Wir überprüfen den Satz <tt>the happy boy loves a sad girl</tt> auf syntaktische Korrektheit:
<run id="4b8bd388a38ea">parse([the,happy,boy,loves,a,sad,girl]).</run>

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

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

Parser für <math>a^nb^mc^j</math>, für <math>n,m,j>0</math>
 SATZ	-> AS BS CS;
 AS	-> a | a AS;
 BS	-> b | b BS;
 CS	-> c | c CS.

Dies ist eine sehr einfache Grammatik. {<tt>a</tt>,<tt>b</tt>,<tt>c</tt>} ist die Menge der Terminale. Die Anzahlen der <tt>a</tt>’s, <tt>b</tt>’s und <tt>c</tt>’s können also ganz unterschiedlich sein.
<code id="4b8bd3889f271">
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).
</code>
Aufrufbeispiel:
<run id="4b8bd388a5b5c">abcsatz1([a,a,a,a,a,a,b,b,b,b,b,c,c,c,c,c]).</run>

Der Parser ist nicht in der Lage, syntaktisch fehlerhafte <tt>abc</tt>-Wörter als solche zu erkennen. Dies ist für den folgenden Lösungsvorschlag kein Problem: Sobald das erste <tt>b</tt> erscheint, werden alle Klauseln, die für <tt>a</tt> zuständig waren, aus der Datenbasis entfernt. Später verfährt das Programm mit <tt>c</tt> ganz analog.
<code id="4b8bd3889fe2f">
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).
</code>
Die folgende Frage wird nach sehr kürzer Rechenzeit mit <tt>No</tt> beantwortet.
<run id="4b8bd388a6715">abcsatz([a,a,a,a,a,a,a,a,b,b,b,b,b,b,c,c,b,c,c,c]).</run>
Der Nachteil dieses Vorschlags besteht darin, dass vor jedem Anfrage die Datenbasis auf’s Neue geladen werden muss.