Prolog i DCG

Gramatyki bezkontekstowe

Gramatyka bezkontekstowa to skończony zbiór reguł, mówiących, czy dane wyrażenia są poprawne gramatycznie (poprawne składniowo) oraz jaka jest ich struktura gramatyczna. Poniżej przedstawiony został prosty przykład gramatyki dla fragmentu języka angielskiego.

s -> np vp

np -> det n

vp -> v np
vp -> v

det -> a
det -> the

n -> womaneasy
n -> man

v -> shoots
  • n - rzeczownik (noun)
  • v - czasownik (verb)
  • det - (determiner)

Symbole terminalne i nieterminalne

Składniki reguł gramatyk bezkontekstowych można podzielić na 2 grupy:

  • symbole terminalne (woman, man, schoots, the, a), stanowiące alfabet języka reprezentowanego przez gramatykę
  • symbole nieterminalne (s,np,vp,det, n, p), będące pewnymi uogólnieniami, grupującymi symbole terminalne (oraz nieterminalne) według przyjętych zasad; np. symbol nieterminalny n grupuje wszystkie symbole terminalne będące rzeczownikami.

Każda reguła gramatyki bezkontekstowej składa sie z symbolu nieterminalnego (będącego lewą częścią reguły) i z symbolu terminalnego, lub nieterminalnego (lub kombinacji dwóch typów symboli), który stanowi prawą stronę reguły.

Drzewo parsowania (parse tree)

Rozważając przypadek z powyższego listingu i zasady budowania reguł z sekcji Symbole terminalne i nieterminalne można wysnuć wniosek, że reguły tworzą pewnego rodzaju drzewo, którego liśćmi są symbole terminalne, a poszczególnymi węzłami symbole nieterminalne.

Takie drzewo dla zdania a woman shoots a man, bazujące na gramatyce z powyższego listingu miałoby następującą postać.

DCG (Definite clause Grammars)

DCG jest zapisem pozwalającym tworzyć pasery bazujące na CFG; innymi słowy jest to zapis będący prologową reprezentacją formalnej notacji CFG. Przykład z sekcji Gramatyki bezkontekstowe zapisany za pomocą DCG wyglądałby następująco:

s --> np,vp.

np --> det,n.

vp --> v,np.
vp --> v.

det --> [the].
det --> [a].

n --> [woman].
n --> [man].

v --> [shoots].

Zakładając, że chcemy sprawdzić czy zdanie a man shoots a woman jest zgodne z gramatyką, wywołujemy następujący predykat:

 s([a,woman,shoots,a,man],[]).
  • Nazwa predykatu jest nazwą dowolnego symbolu nieterminalnego będącego elementem gramatyki. W tym przypadku jets to symbol nieterminalny reprezentujący całe zdanie, ale równie dobrze mógłby być to dowolny inny symbol.
  • Pierwszym parametrem jest lista składająca sie z symboli terminalnych, dla których będzie budowane drzewo parsowania.
  • Drugim parametrem jest lista symboli nieterminalnych, które chcemy wykluczyć przy budowaniu drzewa parsowania. Dla przykładu wywołanie predykatu postaci
    s([a,woman,shoots,a,man],[shoots]).

    zakończy sie niepowodzeniem (ponieważ zdanie bez czasownika nie jest poprawne według gramatyki przedstawionej w DCG (Definite clause Grammars)), ale wywołanie s([a,man,shoots,a,woman],[a,woman]).</code> da pozytywny wynik, ponieważ zdanie a man shoots jest zgodne z gramatyką.

Symbole terminalne i nieterminalne

  • Symbole nieterminalne mogą być dowolnym termem w języku prolog; stosuje się do nich zatem taką samą notację jak w przypadku zwyczajnego termu.
  • Symbole terminalne zapisujemy jako listy termów. Zazwyczaj są to listy jednoelementowe.

Jak to działa

DCG to tak naprawdę syntactic sugar dla list różnicowych. Zapis podany w listingu z sekcji DCG (Definite clause Grammars) jest interpretowany przez Prolog identycznie jak ten poniżej:

s(X,Z) :- np(X,Y), vp(Y,Z).

np(X,Z) :- det(X,Y), n(Y,Z).

vp(X,Z) :-  v(X,Y), np(Y,Z).
vp(X,Z) :-  v(X,Z).

det([the|W],W).
det([a|W],W).

n([woman|W],W).
n([man|W],W).

v([shoots|W],W).

Parametryzowanie reguł

W celu budowania bardziej skomplikowanych gramatyk, bardzo przydatne jest parametryzowanie niektórych reguł. Przykładowo, chcąc rozbudować gramatykę z podrozdziału (XXX) tak aby zamiast rzeczowników woman oraz man można było stosować również zaimki, należy określić w którym miejscu zdania jaki zaimek może zostać użyty. Można to osiągnąć albo poprzez dodanie nowych reguł, lub poprzez sprarametryzowanie istniejących.

W przykładzie poniżej określamy, że zaimki he oraz she mogą stać na początku zdania pełniąc rolę podmiotu, natomiast zaimki her oraz him mogą występować w zdaniu jedynie jako dopełnienie.

s --> np(subject),vp.
 
np(_) --> det,n.
np(X) --> pro(X).
 
vp --> v,np(object).
vp --> v.
 
det --> [the].
det --> [a].
 
n --> [woman].
n --> [man].
 
pro(subject) --> [he].
pro(subject) --> [she].
pro(object) --> [him].
pro(object) --> [her].
 
v --> [shoots].

Prolog w DCG

Ponieważ każdy składnik reguły DCG traktowany jest w sposób przedstawiony w (Jak to działa), nie jest możliwe bezpośrednie wykorzystywanie predykatów prologowych w ciele reguły. Aby dodać kod Prolog do reguły DCG należy umieścić go w nawiasach klamrowych.

 s --> np,vp, {write('Zdanie poprawne')}.

Przykład użycia wstawki prologowej do sprawdzenia, czy podstawowy składnik wyrażenia matematycznego jest liczbą.

expr --> term, addterm.
addterm --> [].
addterm --> [+], expr.
term --> factor, multfactor.
multfactor --> [].
multfactor --> [*], term.
factor --> [I], {integer(I)}.
factor --> ['('], expr, [')'].

Ćwiczenia

  • Wykorzystując przykład z sekcji DCG (Definite clause Grammars) napisz predykat wypisujący wszystkie poprawne gramatycznie zdania
  • Wykorzystując przykład z sekcji DCG (Definite clause Grammars) wypisz wszystkie symbole terminalne „do których można strzelać” ;)
  • Rozbuduj gramatykę z przykładu Parametryzowanie reguł tak aby zdanie typu a man hates a woman and shoots her było poprawne. Wykorzystaj parametryzowanie reguł.
  • Napisz gramatykę języka poleceń dla robota. Przykład podlecenia: [speed, 10, prosto, prosto, obrot, 90, tyl, speed, 5, tyl]. Znaczenie: Ustaw prędkość na 10 jednostek, przesuń sie do przodu o ustaloną ilość jednostek, przesuń sie do przodu o ustaloną ilość jednostek, obróć się o 90 stopni, przesuń sie w tył o ustaloną ilość jednostek, zmień prędkość na 5 jednostek, przesuń się w tył o ustaloną ilość jednostek.
  • Za pomocą wstawek prologowych dodaj funkcjonalność obliczania położenia robota w przestrzeni.
  • Rozbuduj parser wyrażeń matematycznych z podrozdziału Prolog w DCG Dodaj inne operatory, oraz obsługę minusa unarnego.
  • Wykorzystując ten program, służący do rozbijania pliku na tokeny, napisz gramatykę weryfikującą poprawność pliku passwd.

Przydatne Materiały

pl/prolog/prolog_lab/prolog_lab_dcg.txt · ostatnio zmienione: 2017/07/17 08:08 (edycja zewnętrzna)
www.chimeric.de Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0