Różnice między wybraną wersją a wersją aktualną.
| Nowa wersja | Poprzednia wersja | ||
|
pl:prolog:prolog_lab:prolog_lab_dcg [2009/11/04 18:40] gjn utworzono |
pl:prolog:prolog_lab:prolog_lab_dcg [2019/06/27 15:50] (aktualna) |
||
|---|---|---|---|
| Linia 1: | Linia 1: | ||
| - | http://cs.union.edu/~striegnk/courses/nlp-with-prolog/html/node31.html#lecture5 | + | ===== 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. | ||
| - | http://cs.union.edu/~striegnk/learn-prolog-now/html/node54.html#lecture7 | + | <code> |
| + | s -> np vp | ||
| - | http://www.amzi.com/AdventureInProlog/a15nlang.htm#DefiniteClauseGrammar | + | np -> det n |
| - | http://www.dai.ed.ac.uk/groups/ssp/bookpages/quickprolog/node27.html#SECTION000120000000000000000 | + | vp -> v np |
| + | vp -> v | ||
| + | |||
| + | det -> a | ||
| + | det -> the | ||
| + | |||
| + | n -> womaneasy | ||
| + | n -> man | ||
| + | |||
| + | v -> shoots | ||
| + | </code> | ||
| + | |||
| + | * 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ć. | ||
| + | |||
| + | {{:pl:prolog:prolog_lab:cfg.gif|}} | ||
| + | |||
| + | ==== 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: | ||
| + | <code> | ||
| + | s --> np,vp. | ||
| + | |||
| + | np --> det,n. | ||
| + | |||
| + | vp --> v,np. | ||
| + | vp --> v. | ||
| + | |||
| + | det --> [the]. | ||
| + | det --> [a]. | ||
| + | |||
| + | n --> [woman]. | ||
| + | n --> [man]. | ||
| + | |||
| + | v --> [shoots]. | ||
| + | </code> | ||
| + | |||
| + | Zakładając, że chcemy sprawdzić czy zdanie //a man shoots a woman// jest zgodne z gramatyką, wywołujemy następujący predykat: <code> s([a,woman,shoots,a,man],[]).</code> | ||
| + | |||
| + | * **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 <code>s([a,woman,shoots,a,man],[shoots]).</code> 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: | ||
| + | |||
| + | <code> | ||
| + | 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). | ||
| + | </code> | ||
| + | |||
| + | ===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. | ||
| + | <code> | ||
| + | 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]. | ||
| + | </code> | ||
| + | |||
| + | ===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.<code> s --> np,vp, {write('Zdanie poprawne')}.</code> | ||
| + | |||
| + | Przykład użycia wstawki prologowej do sprawdzenia, czy podstawowy składnik wyrażenia matematycznego jest liczbą. | ||
| + | <code> | ||
| + | expr --> term, addterm. | ||
| + | addterm --> []. | ||
| + | addterm --> [+], expr. | ||
| + | term --> factor, multfactor. | ||
| + | multfactor --> []. | ||
| + | multfactor --> [*], term. | ||
| + | factor --> [I], {integer(I)}. | ||
| + | factor --> ['('], expr, [')']. | ||
| + | </code> | ||
| + | |||
| + | ====Ć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 {{:pl:prolog:prolog_lab:tokenizer.pl|ten}} program, służący do rozbijania pliku na tokeny, napisz gramatykę weryfikującą poprawność pliku //passwd//. | ||
| + | |||
| + | ====Przydatne Materiały==== | ||
| + | * http://cs.union.edu/~striegnk/courses/nlp-with-prolog/html/node31.html#lecture5 | ||
| + | * http://cs.union.edu/~striegnk/learn-prolog-now/html/node54.html#lecture7 | ||
| + | * http://www.amzi.com/AdventureInProlog/a15nlang.htm#DefiniteClauseGrammar | ||
| + | * http://www.dai.ed.ac.uk/groups/ssp/bookpages/quickprolog/node27.html#SECTION000120000000000000000 | ||
