Versionsvergleich
Aus ProgrammingWiki
Vergleich: 2010-03-01T14:47:37+00:00 → 2011-01-10T19:42:04+00:00
<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: | |
| − | <eval id="4b8bd388a09e4"> |
| + | <run id="4b8bd388a09e4"> |
satz([the,happy,boy,loves,a,sad,girl]). | |
| − | </eval> |
| + | </run> |
Syntaktisch fehlerhafte Sätze werden zurückgewiesen: | |
| − | <eval id="4b8bd388a159c"> |
| + | <run id="4b8bd388a159c"> |
satz([the,happy,boy,loves,sad,girl]). | |
| − | </eval> |
| + | </run> |
Der Parser kann auch als Satzgenerators eingesetzt werden: | |
| − | <eval id="4b8bd388a2152">satz(X).</eval> |
| + | <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. | |
| − | <eval id="4b8bd388a2d26">findall(X,satz(X),Xs).</eval> |
| + | <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: | |
| − | <eval id="4b8bd388a38ea">parse([the,happy,boy,loves,a,sad,girl]).</eval> |
| + | <run id="4b8bd388a38ea">parse([the,happy,boy,loves,a,sad,girl]).</run> |
<tt>parse</tt> kann auch als Satzgenerator verwendet werden: | |
| − | <eval id="4b8bd388a4483">parse(X).</eval> |
| + | <run id="4b8bd388a4483">parse(X).</run> |
Man kann die Anzahl der erzeugbaren Sätze bestimmen: | |
| − | <eval id="4b8bd388a505a">findall(X,parse(X),Ys),length(Ys,Z),write(Z).</eval> |
| + | <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: | |
| − | <eval id="4b8bd388a5b5c">abcsatz1([a,a,a,a,a,a,b,b,b,b,b,c,c,c,c,c]).</eval> |
| + | <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. | |
| − | <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> |
| + | <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. |