Różnice między wybraną wersją a wersją aktualną.
| Both sides previous revision Poprzednia wersja Nowa wersja | Poprzednia wersja | ||
|
pl:prolog:prolog_lab:prolog_lab_dcg [2009/12/14 13:42] esimon dcg-draft |
pl:prolog:prolog_lab:prolog_lab_dcg [2019/06/27 15:50] (aktualna) |
||
|---|---|---|---|
| Linia 2: | Linia 2: | ||
| ==== Gramatyki bezkontekstowe ==== | ==== 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. | 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. | ||
| - | |||
| <code> | <code> | ||
| Linia 33: | Linia 32: | ||
| ===Drzewo parsowania (parse tree)=== | ===Drzewo parsowania (parse tree)=== | ||
| - | Rozważając przypadek z listingu (XXX) i zasady budowania reguł z sekcji (XXX) 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. | + | 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 litingu (XXX) miałoby następującą postać. | + | Takie drzewo dla zdania //a woman shoots a man//, bazujące na gramatyce z powyższego listingu miałoby następującą postać. |
| - | **Rysunek** | + | {{:pl:prolog:prolog_lab:cfg.gif|}} |
| ==== DCG (Definite clause Grammars) ==== | ==== 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. | 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 (XXX) zapisany za pomocą DCG wyglądałby następująco: | + | Przykład z sekcji [[#Gramatyki bezkontekstowe]] zapisany za pomocą DCG wyglądałby następująco: |
| <code> | <code> | ||
| s --> np,vp. | s --> np,vp. | ||
| Linia 63: | Linia 62: | ||
| * **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. | * **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. | * **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 przedstwaionej w [[XXX]]), ale wywołanie s([a,man,shoots,a,woman],[a,woman]).</code> da pozytywny wynik, ponieważ zdanie //a man shoots// jest zgodne z gramatyką. | + | * **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ą. |
| - | Czy wywołanie predykatu //s([a,woman,shoots,a,man,but,she,is,immortal],[but she is immortal])// Zakończy się fałszem? Jaki wynik da wywołanie predykatu s([a,woman,a,woman,shoots,a,man],[a,woman])? | ||
| ===Symbole terminalne i nieterminalne=== | ===Symbole terminalne i nieterminalne=== | ||
| Linia 72: | Linia 70: | ||
| ===Jak to działa=== | ===Jak to działa=== | ||
| - | DCG to tak naprawdę //syntactic sugar// dla list różnicowych. Zapis podany w listingu (XXX) jest interpretowany przez Prolog identycznie jak ten poniżej: | + | 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> | <code> | ||
| Linia 134: | Linia 132: | ||
| ====Ćwiczenia==== | ====Ćwiczenia==== | ||
| - | * Wykorzystując przykład [[XXX]] napisz predykat wypisujący wszystkie poprawne gramatycznie zdania | + | * Wykorzystując przykład z sekcji [[#DCG (Definite clause Grammars)]] napisz predykat wypisujący wszystkie poprawne gramatycznie zdania |
| - | * Wykorzystując przykład [[XXX]] wypisz wszystkie symbole terminalne "do których można strzelać" ;) | + | * 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 [[XXX]] tak aby zdanie typu //a man hates a woman and shoots her// było poprawne. Wykorzystaj parametryzowanie reguł. | + | * 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ł. |
| - | * Rozbuduj parser wyrażeń matematycznych z podrozdziału [[XXX]] Dodaj inne operatory, oraz obsługę minusa unarnego. | + | * 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. |
| - | * Wykorzystując [[ten]] program, służący do rozbijania pliku na tokeny, napisz gramatykę weryfikującą poprawność pliku [???] | + | * 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 Matriały==== | + | ====Przydatne Materiały==== |
| * http://cs.union.edu/~striegnk/courses/nlp-with-prolog/html/node31.html#lecture5 | * 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://cs.union.edu/~striegnk/learn-prolog-now/html/node54.html#lecture7 | ||
