Date post: | 30-Dec-2015 |
Category: |
Documents |
Upload: | kuame-chapman |
View: | 52 times |
Download: | 2 times |
Morfologická analýzaBezkontextové gramatiky
Daniel Zeman
http://ufal.mff.cuni.cz/course/popj1/
Počítačové zpracování přirozeného jazyka
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 2
Bezkontextové gramatiky
• Zkratka CFG (context-free grammar)
• Čtveřice (T, N, S, P)– T … abeceda terminálních (koncových) symbolů, obvykle se
používají malá písmena
– N … abeceda neterminálních symbolů, obvykle se používají velká písmena
– S N … startovní neterminální symbol
– P … množina přepisovacích pravidel tvaru X ,kde X N a (TN)*
• Řetězec lze v CFG odvodit, jestliže může vzniknout opakovanou aplikací pravidel na startovní symbol.
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 3
Bezkontextové gramatiky: příklad
• Neterminály začínají velkým písmenem, terminály malým.– Slovo Stupeň Zápor Kmen Koncovka | Kmen Koncovka
– Stupeň nej
– Zápor ne
– Kmen abatyš | abbé | abdikac | abdikov | …
– Koncovka λ | a | ovi | e | em | y | u | o | ou | …
• Odlišit kmeny, které dovolují konkrétní skupiny afixů.
• Vyřešit nepravidelnosti, změny kmenových souhlásek…
• Problém: gramatika by byla příliš veliká!
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 4
Bezkontextové gramatiky:příklad derivačního stromu
abatyš e
Kmen Koncovka
Slovo neterminály
terminály
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 5
Bezkontextové gramatiky: změny kmenových souhlásek
• Změny kmenových souhlásek — možné řešení:– KmenNF1 m a t K | ž e N | …
– K k | c
– N n | ň
– KoncovkaNF1 a | y | e | …
• Přijme matka, matky, matce, ale i *matca, *matcy, *matke. Buď doplňková pravidla mimo gramatiku (např. před „e“ měkká souhláska, všude jinde tvrdá), nebo zesložitění gramatiky.
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 6
Bezkontextové gramatiky: změny kmenových souhlásek
• Přesnější gramatika pro změnu kmenových souhlásek:– Slovo KmenNF1Normální KoncovkaNF1Normální |
KmenNF1Měkký KoncovkaNF1Měkká
– KmenNF1Normální m a t k | ž e n
– KmenNF1Měkký m a t c | ž e ň
– KoncovkaNF1Normální a | y | u | o | ou | | ám | ách | ami
– KoncovkaNF1Měkká e
• Nebezpečí, aby se velikost gramatiky nepřiblížila velikosti výčtu všech tvarů. Zbytečně opakujeme části „m a t“, „ž e“.
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 7
Bezkontextové gramatiky: vkládání / mazání e
• Navíc ještě vkládání e: matek– Slovo KmenNF1Normální KoncovkaNF1Normální |
KmenNF1Měkký KoncovkaNF1Měkká | KmenNF1VklE
– KmenNF1Normální m a t k | ž e n
– KmenNF1Měkký m a t c | ž e ň
– KmenNF1VklE m a t e k | ž e n
– KoncovkaNF1Normální a | y | u | o | ou | ám | ách | ami
– KoncovkaNF1Měkká e
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 8
Bezkontextové gramatiky: analýza a syntéza
• Syntéza– Vyjdeme ze startovního symbolu.– V řetězci, který máme, vybereme nějaký neterminální symbol a
přepíšeme ho na základě přepisovacího pravidla. Někdy (často!) si musíme pravidlo vybrat z několika, která přicházejí v úvahu.
– Jakmile se řetězec skládá pouze z terminálních symbolů, je hotov.
• Analýza– Máme řetězec, v případě morfologické analýzy slovo.– Hledáme části, které lze nahradit neterminály. Nedeterministické!– Cíl: startovní symbol S.
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 9
Morfologická syntéza pomocí bezkontextové gramatiky
• Vstup:<l>matka<t>NNFS6-----A----
• Očekávaný výstup:<f>matce
• Gramatika:TvarMatka KmenMatka KoncMatkaKmenMatka mat | bab | vlaj | …KoncMatka MatS1 | MatS2 | …MatS1 ka ; MatS2 ky ; MatS3 ceMatP1 ky ; MatP2 ek ; MatP3 kám
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 10
Morfologická syntéza pomocí bezkontextové gramatiky
• Doplňková dohoda:– Názvy některých neterminálů nesou informaci
z morfologických značek.
– Zde konkrétně: poslední dva znaky v neterminálech těsně pod neterminálem, jehož jméno začíná „Konc“.
• Teoreticky možný postup:– Nejdřív analýza lemmatu matka. Zjistíme, že se skládá
z mat + MatS1.
– Nahradíme za požadované MatS6.
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 11
Morfologie a CFG: mnohem více vzorů, než jsme zvyklí
• žena– žen | vlád | mát | láv | …+ a | y | ě | u | o | ě | ou |
y | λ | ám | y | y | ách | ami
• matka– mat | bab | vlaj | …+ ka | ky | ce | ku | ko | ce | kou |
ky | ek | kám | ky | ky | kách | kami
• banka– ban+ ka | ky | ce | ku | ko | ce | kou |
ky | k | kám | ky | ky | kách | kami
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 12
Morfologie a CFG: mnohem více vzorů, než jsme zvyklí
• barva– bar | lar | kur | … | bit | pit | …+ va | vy | vě | vu | vo | vě | vou |
vy | ev | vám | vy | vy | vách | vami
• tráva– tr | kr | šť | … (ale ne už třeba k!)+ áva | ávy | ávě | ávu | ávo | ávě | ávou |
ávy | av | ávám | ávy | ávy | ávách | ávami
• louka– l | m (ale ne už třeba prv, mrav!)+ ouka | ouky | ouce | ouku | ouko | ouce | oukou |
ouky | uk | oukám | ouky | ouky | oukách | oukami
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 13
Všeho moc škodí
• Exploze vzorů
• Dva nezávislé problémy:– Měkčení kmenové souhlásky
• ha/ze, ga/ze, cha/še, ka/ce, ra/ře, da/dě, ta/tě, na/ně, ba/bě, fa/fě, ma/mě, pa/pě, va/vě … 13
– Krácení kmenové samohlásky• láva/láv, tráva/trav, louka/luk, síla/sil, díra/děr … 5
– Pro původně 1 vzor žena dostáváme• 13 + 5 = 18
• 13 × 5 = 65
• Nějak oddělit řešení obou problémů!
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 14
Měkčení a krácení
KoncV NFVS1 | NFVS2 | NFVS3 | NFVS4 | NFVS5 | NFVS6 | NFVS7 | NFVP1 | NFVP3 | NFVP4 | NFVP5 | NFVP6 | NFVP7
KoncKrV NFVP2KmenV láv | sův | tráv | smlouv | …KmenKrV láv | sův | trav | smluv | …TvarV KmenV KoncV KmenKrV KoncKrV
Nevýhoda: Po analýze se nedozvíme, že kmeny smlouv a smluv odpovídají stejnému lemmatu!
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 15
Opakování doplňkové dohody
• Dosavadní doplňková dohoda:– Neterminály bezprostředně pod neterminálem
začínajícím na Konc kódují morfologické značky.• Např. neterminál začínající na NFV odpovídá značceNNF??-----A----.
• Součástí dohody je tabulka korespondencí značek a neterminálů. Jedné značce odpovídá několik neterminálů od různých skloňovacích vzorů!
– Poslední dva znaky neterminálů pod Konc kódují číslo a pád.
• Např. NFVP2 odpovídá číslo P a pád 2, celá značka je pak NNFP2-----A----.
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 16
Rozšíření doplňkové dohody
• Přidat do dohody:– Neterminály začínající na X obsahují znaky, které by na
daném místě byly v kmeni u lemmatu.• Např. neterminál Xá nám řekne, že v lemmatu by na tomto
místě bylo dlouhé á, přestože pro tvar, který právě analyzujeme, se Xá přepíše na krátké a.
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 17
Měkčení a krácení
KoncV NFVS1 | NFVS2 | NFVS3 | NFVS4 | NFVS5 | NFVS6 | NFVS7 | NFVP1 | NFVP3 | NFVP4 | NFVP5 | NFVP6 | NFVP7
KoncKrV NFVP2Xá aXou uKmenV láv | sův | …KmenK0V tráv | smlouv | …KmenK1V tr Xá v | sml Xou v | …TvarV KmenV KoncV | KmenV KoncKrV KmenK0V KoncV | KmenK1V KoncKrV
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 18
Výsledek analýzy
• Na konci analýzy podle doplňkové dohody přečíst kmen lemmatu a morfologickou značku.
sml u v λ
Xou
KmenK1V
NFVP2
KoncKrV
TvarV
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 19
Výsledek analýzy
• Po analýze ještě syntéza základního tvaru (dle dohody je to S1). TvarV nám řekne správný vzor.
sml u v λ
Xou
KmenK1V
NFVP2
KoncKrV
TvarV
smlouv a
KmenK0V
NFVS1
KoncV
TvarV
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 20
Nedeterminismus
TvarV13 KmenV13 KoncV13KoncV13 V13PS1 | V13PS2 | V13PS3 | V13PP1 | V13PP2 | V13PP3
KmenV13 nes | ber | maž | jd | …V13PS1 uV13PS2 ešV13PS3 eV13PP1 eme | emV13PP2 eteV13PP3 ou
nesoucímiV13PS1V13PP3
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 21
Homonymie
smlouv y
KmenK0V
NFVS2
KoncV
TvarV
smlouv y
NFVP1
smlouv y
NFVP4
smlouv y
NFVP5
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 22
Algoritmus analýzy podle bezkontextové gramatiky
• Shora dolů– Na začátku máme jeden neterminál – počáteční symbol.– Rozbalit jeden neterminál: najít pravidlo, kde tvoří
levou stranu, nahradit ho pravou stranou.– Opakovat, dokud nemáme samé terminály.– Pokud jsme nedostali analyzované slovo, vrátit se a pro
některý neterminál vybrat jiné pravidlo.– Pokud jsme analyzované slovo dostali, vrátit se také,
může existovat i jiná analýza.– Pokud jsme prošli všechny kombinace, známe množinu
analýz. Je prázdná? Pak slovo není ve slovníku.
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 23
Algoritmus analýzy podle bezkontextové gramatiky
• Zdola nahoru– Na začátku máme posl. terminálů – analyzované slovo.– Sbalit jeden neterminál: najít v analyzovaném řetězci
pravou stranu některého jeho pravidla, nahradit jím.– Opakovat, dokud lze něco najít.– Pokud jsme nedostali počáteční symbol, vrátit se a pro
některý neterminál vybrat jiné pravidlo.– Pokud jsme počáteční symbol dostali, vrátit se také,
může existovat i jiná analýza.– Pokud jsme prošli všechny kombinace, známe množinu
analýz. Je prázdná? Pak slovo není ve slovníku.
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 24
Analýza shora dolů
• Musíme zajistit směřování k terminálnímu řetězci, který analyzujeme.
• Řešení: průběžně kontrolovat, zda terminály ve stavu odpovídají počátku věty.
• Stav analýzy: řetězec terminálů a neterminálů, tečka označuje zkontrolovanou (přečtenou) část.
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 25
Příklad analýzy shora dolů
Analyzujeme slovo matce
. Tvar
. TvarNFeka
. KmenNFeka KoncNFeka
. bár KoncNFeka !!! ZPĚT
. bud KoncNFeka !!! ZPĚT
…
. mat KoncNFeka
mat . KoncNFeka
mat . NFekaS1
mat . ka !!! ZPĚT
mat . NFekaS2
mat . ky !!! ZPĚT
mat . NFekaS3
mat . ce
matce .
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 26
Pozorování o slovníku
• V praxi by se měl slovník oddělit a implementovat efektivněji.
• Poslední neterminál nad slovníkem je tzv. preterminál.
• Ten zná seznam řetězců, které pod něj patří, a umí ho prohledávat rychle.
• Implementace: hashovací tabulka, vyhledávací strom, trie…
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 27
Pozorování o (levé) rekurzi
dělat – dělávat – dělávávat – dělávávávat – dělávávávávat …
Tvar → TvarV5TvarV5 → KmenV5 KoncV5
| KmenV5 Iter KoncV5KoncV5 → V5INF | V5PS1
| V5PS2 | …KmenV5 → děl | lét | …Iter → Iter áv | ávV5INF → at | atiV5PS1 → ám…
. Tvar
. TvarV5
…
děl . Iter KoncV5
děl . Iter áv KoncV5
děl . Iter áv áv KoncV5
děl . Iter áv áv áv KoncV5
děl . Iter áv áv áv áv KoncV5
…
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 28
Rekurze a obrana proti zacyklení
• Zajistit, aby se rekurentní pravidla použila, až když to jinak nejde.
• Je-li více rekurentních pravidel, zajistit, aby se vyzkoušely všechny kombinace.
• Kombinací je konečně mnoho — rekurze každého pravidla se dá zastavit, jakmile počet symbolů překročí počet terminálů na vstupu.
• Zakázat levou rekurzi, povolit jen pravou(Iter → áv | áv Iter).
• Použít analýzu zdola nahoru.
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 29
Příklad analýzy zdola nahoru
Analyzujeme slovo matce
. matce
. NNíS7 atce
. KoncNNí atce !!! ZPĚT
. NFaD7 tce
. KoncNFa tce !!! ZPĚT
. KmenNFeka ce
KmenNFeka . ce
KmenNFeka . NFekaS3
KmenNFeka . KoncNFeka
KmenNFeka KoncNFeka .
TvarNFeka .
Tvar .
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 30
Jak si zapamatovat možné odbočky
• V případě krachu se máme vrátit na poslední křižovatku, kde jsme vybírali z více pravidel.
• Musíme si tedy křižovatky pamatovat.
• Možnost: zásobník záložních stavů.
• Na křižovatce nevybírat jeden nový stav, vygenerovat všechny. Uložit je do zásobníku.
• Potom vybrat jeden stav ze zásobníku a s ním pokračovat.
• Při krachu ho zahodit a zkusit další ze zásobníku.
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 31
Bezkontextová analýza jako problém hledání cesty
• Analýza odpovídá obecnému problému hledání cesty stromem možností od kořene k listu (umělá inteligence).
• Prohledávání do hloubky: seznam možností je zásobník (LIFO).
• Prohledávání do šířky: seznam možností je fronta (FIFO).
• Prohledávání do šířky potřebuje více paměti na záložní stavy, ale má méně problémů při rekurzi. Ovšem na negramatických řetězcích se zacyklí také.
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 32
Analýza zdola nahoru:popis algoritmu
• Vzít stav, který je na řadě v zásobníku (frontě), a prohlásit ho za aktuální.
• Projít všechny podřetězce aktuálního stavu začínající nalevo od tečky a končící u tečky. Porovnat je s pravými stranami všech pravidel. Pro každý podřetězec, který se s nějakou pravou stranou shoduje, vygenerovat nový stav, v němž bude nalezená pravá strana nahrazena levou stranou příslušného pravidla; zbytek stavu se bude shodovat s aktuálním stavem. Uložit nově vygenerovaný stav do zásobníku.
• Nakonec ještě vygenerovat stav, který se od aktuálního stavu liší tím, že tečka je posunuta o 1 symbol doprava. Uložit ho do zásobníku.
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 33
Příklad analýzy zdola nahoru včetně zásobníku
Gramatika
S C D
C c | B C
D d | d C
B b | ab
ZásobníkAktuální stav
. a b c d b c
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 34
Příklad analýzy zdola nahoru včetně zásobníku
Gramatika
S C D
C c | B C
D d | d C
B b | ab
Zásobník
a . b c d b c
Aktuální stav
. a b c d b c
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 35
Příklad analýzy zdola nahoru včetně zásobníku
Gramatika
S C D
C c | B C
D d | d C
B b | ab
ZásobníkAktuální stav
a . b c d b c
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 36
Příklad analýzy zdola nahoru včetně zásobníku
Gramatika
S C D
C c | B C
D d | d C
B b | ab
Zásobník
a b . c d b c
Aktuální stav
a . b c d b c
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 37
Příklad analýzy zdola nahoru včetně zásobníku
Gramatika
S C D
C c | B C
D d | d C
B b | ab
ZásobníkAktuální stav
a b . c d b c
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 38
Příklad analýzy zdola nahoru včetně zásobníku
Gramatika
S C D
C c | B C
D d | d C
B b | ab
Zásobník
a b c . d b c
B . c d b c
a B . c d b c
Aktuální stav
a b . c d b c
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 39
Příklad analýzy zdola nahoru včetně zásobníku
Gramatika
S C D
C c | B C
D d | d C
B b | ab
Zásobník
B . c d b c
a B . c d b c
Aktuální stav
a b c . d b c
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 40
Příklad analýzy zdola nahoru včetně zásobníku
Gramatika
S C D
C c | B C
D d | d C
B b | ab
Zásobník
a b c d . b c
a b C . d b c
B . c d b c
a B . c d b c
Aktuální stav
a b c . d b c
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 41
Příklad analýzy zdola nahoru včetně zásobníku
Gramatika
S C D
C c | B C
D d | d C
B b | ab
Zásobník
a b C . d b c
B . c d b c
a B . c d b c
Aktuální stav
a b c d . b c
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 42
Příklad analýzy zdola nahoru včetně zásobníku
Gramatika
S C D
C c | B C
D d | d C
B b | ab
Zásobník
a b c d b . c
a b c D . b c
a b C . d b c
B . c d b c
a B . c d b c
Aktuální stav
a b c d . b c
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 43
Příklad analýzy zdola nahoru včetně zásobníku
Gramatika
S C D
C c | B C
D d | d C
B b | ab
Zásobník
a b c D . b c
a b C . d b c
B . c d b c
a B . c d b c
Aktuální stav
a b c d b . c
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 44
Příklad analýzy zdola nahoru včetně zásobníku
Gramatika
S C D
C c | B C
D d | d C
B b | ab
Zásobník
a b c d b c .
a b c d B . c
a b c D . b c
a b C . d b c
B . c d b c
a B . c d b c
Aktuální stav
a b c d b . c
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 45
Příklad analýzy zdola nahoru včetně zásobníku
Gramatika
S C D
C c | B C
D d | d C
B b | ab
Zásobník
a b c d B . c
a b c D . b c
a b C . d b c
B . c d b c
a B . c d b c
Aktuální stav
a b c d b c .
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 46
Příklad analýzy zdola nahoru včetně zásobníku
Gramatika
S C D
C c | B C
D d | d C
B b | ab
Zásobník
a b c d b C .
a b c d B . c
a b c D . b c
a b C . d b c
B . c d b c
a B . c d b c
Aktuální stav
a b c d b c .
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 47
Příklad analýzy zdola nahoru včetně zásobníku
Gramatika
S C D
C c | B C
D d | d C
B b | ab
Zásobník
a b c d B . c
a b c D . b c
a b C . d b c
B . c d b c
a B . c d b c
Aktuální stav
a b c d b C .
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 48
Příklad analýzy zdola nahoru včetně zásobníku
Gramatika
S C D
C c | B C
D d | d C
B b | ab
Zásobník
a b c d B . c
a b c D . b c
a b C . d b c
B . c d b c
a B . c d b c
Aktuální stav
a b c d b C .
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 49
Příklad analýzy zdola nahoru včetně zásobníku
Gramatika
S C D
C c | B C
D d | d C
B b | ab
Zásobník
a b c D . b c
a b C . d b c
B . c d b c
a B . c d b c
Aktuální stav
a b c d B . c
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 50
Příklad analýzy zdola nahoru včetně zásobníku
Gramatika
S C D
C c | B C
D d | d C
B b | ab
Zásobník
a b c d B c .
a b c D . b c
a b C . d b c
B . c d b c
a B . c d b c
Aktuální stav
a b c d B . c
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 51
Příklad analýzy zdola nahoru včetně zásobníku
Gramatika
S C D
C c | B C
D d | d C
B b | ab
Zásobník
a b c D . b c
a b C . d b c
B . c d b c
a B . c d b c
Aktuální stav
a b c d B c .
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 52
Příklad analýzy zdola nahoru včetně zásobníku
Gramatika
S C D
C c | B C
D d | d C
B b | ab
Zásobník
a b c d B C .
a b c D . b c
a b C . d b c
B . c d b c
a B . c d b c
Aktuální stav
a b c d B c .
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 53
Příklad analýzy zdola nahoru včetně zásobníku
Gramatika
S C D
C c | B C
D d | d C
B b | ab
Zásobník
a b c D . b c
a b C . d b c
B . c d b c
a B . c d b c
Aktuální stav
a b c d B C .
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 54
Příklad analýzy zdola nahoru včetně zásobníku
Gramatika
S C D
C c | B C
D d | d C
B b | ab
Zásobník
a b c d C .
a b c D . b c
a b C . d b c
B . c d b c
a B . c d b c
Aktuální stav
a b c d B C .
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 55
Příklad analýzy zdola nahoru včetně zásobníku
Gramatika
S C D
C c | B C
D d | d C
B b | ab
Zásobník
a b c D . b c
a b C . d b c
B . c d b c
a B . c d b c
Aktuální stav
a b c d C .
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 56
Příklad analýzy zdola nahoru včetně zásobníku
Gramatika
S C D
C c | B C
D d | d C
B b | ab
Zásobník
a b c D .
a b c D . b c
a b C . d b c
B . c d b c
a B . c d b c
Aktuální stav
a b c d C .
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 57
Příklad analýzy zdola nahoru včetně zásobníku
Gramatika
S C D
C c | B C
D d | d C
B b | ab
Zásobník
a b c D . b c
a b C . d b c
B . c d b c
a B . c d b c
Aktuální stav
a b c D .
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 58
Příklad analýzy zdola nahoru včetně zásobníku
Gramatika
S C D
C c | B C
D d | d C
B b | ab
Zásobník
a b c D . b c
a b C . d b c
B . c d b c
a B . c d b c
Aktuální stav
a b c D .
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 59
Příklad analýzy zdola nahoru včetně zásobníku
Gramatika
S C D
C c | B C
D d | d C
B b | ab
Zásobník
a b C . d b c
B . c d b c
a B . c d b c
Aktuální stav
a b c D . b c
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 60
Příklad analýzy zdola nahoru včetně zásobníku
Gramatika
S C D
C c | B C
D d | d C
B b | ab
Zásobník
a b c D b . c
a b C . d b c
B . c d b c
a B . c d b c
Aktuální stav
a b c D . b c
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 61
Příklad analýzy zdola nahoru včetně zásobníku
Gramatika
S C D
C c | B C
D d | d C
B b | ab
Zásobník
a b C . d b c
B . c d b c
a B . c d b c
Aktuální stav
a b c D b . c
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 62
Příklad analýzy zdola nahoru včetně zásobníku
Gramatika
S C D
C c | B C
D d | d C
B b | ab
Zásobník
a b c D b c .
a b c D B . c
a b C . d b c
B . c d b c
a B . c d b c
Aktuální stav
a b c D b . c
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 63
Tutéž pravou stranu hledáme na stejném místě stále znova!
Gramatika
S C D
C c | B C
D d | d C
B b | ab
Zásobník
a b c D b c .
a b c D B . c
a b C . d b c
B . c d b c
a B . c d b c
Aktuální stav
a b c d b . c
a b c D b . c…
a b C d b . c
B c d b . c
a B c d b . c
…
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 64
Složitost analýzy
• Popsaný algoritmus má exponenciální složitost (musíme projít všechny cesty ve stromu).– Problém: opakovaně hledáme stejnou pravou
stranu na stejném místě.
• Existuje polynomiální algoritmus:CYK, chart parser.
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 65
Chart parser
• Chart [ča:t] = „přehled“, „diagram“– Hlavní datová struktura v chart parseru.
– Pamatuje si, které pravé strany už byly rozpoznány a kde.
• Poznámka: Česky by se tedy chart parser dal přeložit jako analýza s přehledem, ale tento název se nepoužívá. I v češtině je tato metoda známa pod anglickým názvem.
• Chart parsing je speciální případ tzv. dynamického programování.
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 66
Nehledat všechny kombinace. Evidovat každou složku zvlášť!
Gramatika
S C D
C c | B C
D d | d C
B b | ab
Chart (Přehled)
B 0 2
B 1 2
C 2 3
C 1 3
…
S 0 6
Řetězec
0a1b2c3d4b5c6
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 67
Stádium rozpracovanosti
• Vstup se čte po jednotlivých terminálech, protože za každým z nich může být rozpoznána pravá strana nějakého pravidla.
• V přehledu je navíc seznam pravidel, jejichž pravé strany jsou rozečteny:– Tečka označuje, která část pravé strany byla už
rozpoznána a která ještě ne.– Opět známe pozice ve vstupním řetězci, kde pravá
strana začala a kde zatím končí (kde je tečka).– Příklad: (B -> a . b) (0;1)
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 68
Přehled (chart)
• Agenda. Seznam složek, které už byly ve vstupu rozpoznány a čekají na zpracování. U každé je uveden rozsah (počáteční a koncová pozice ve vstupu).
• Přehled „aktivních přechodů“, tj. pravých stran, jejichž část už byla ve vstupu rozpoznána. U každé je rozsah (počáteční a koncová pozice pravé strany) a pozice, ke které už byla pravá strana rozpoznána (tečka).
• Přehled zpracovaných složek. U každé je uveden rozsah. Sem se přesouvají složky z agendy po zpracování.
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 69
Algoritmus chart parseru
1. Na začátku je agenda, přehled aktivních přechodů i zpracovaných složek prázdný.
2. Je-li agenda prázdná, přečíst další terminál ze vstupu a přidat ho do agendy.
3. Pokud je agenda prázdná a vstup přečten, skočit na 10.
4. Vybrat z agendy novou aktuální složku (C,i,j). Složka ve vstupním řetězci sahá od pozice i do pozice j.
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 70
Algoritmus chart parseru
5. Projít pravidla gramatiky. Pro každé pravidlo tvaru X C X1 … Xn přidat do přehledu nový aktivní přechod z i do i tvaru X • C X1 … Xn. (Nová pravidla, která zde začínají.)
6. Pro každý aktivní přechod z k do i tvaru X X1 … • C … Xn přidat do přehledu nový aktivní přechod z k do j tvaru X X1 … C • … Xn. (Pravidla, která zde pokračují.)
7. Pro každý aktivní přechod z k do j tvaru X X1 … Xn C • přidat do agendy novou složku X s rozsahem od k do j, pokud tato již není v agendě nebo v seznamu zpracovaných frází. (Pravidla, která zde končí.)
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 71
Algoritmus chart parseru
8. Přesunout (C,i,j) z agendy do seznamu zpracovaných složek. Pokud C=S a i,j pokrývá celý vstup, byla nalezena analýza vstupu. Mohou však existovat i jiné analýzy.
9. Vrátit se na krok 2.
10. Jestliže seznam zpracovaných složek obsahuje složku (S,0,n), kde n je počet terminálů na vstupu, analýza byla úspěšná.
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 72
Složitost chart parsingu
• Polynomiální (O(gn3), n je počet terminálů na vstupu, g je počet pravidel v gramatice).
• Rozsahů složek (od i do j) je (n+1)2.• V jednom rozsahu lze nalézt nejvýše tolik složek,
kolik pravidel má gramatika.• Každé pravidlo můžeme mít rozečtené v nejvýše
n+1 stavech (počet možných umístění tečky).
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 73
Zachovat všechny fáze rozpracovanosti pravidel!
6.Pro každý aktivní přechod z k do i tvaru X X1 … • C … Xn přidat do přehledu nový aktivní přechod z k do j tvaru X X1 … C • … Xn. (Pravidla, která zde pokračují.)
• Po posunutí tečky v pravidle ponechat v přehledu i dosavadní fázi pravidla!
• Co když bude později rozpoznána stejná složka začínající na stejném místě, ale delší?
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 74
Příklad
A a | a AB b A…
baac
B b • A (0,1)A a • (1,2)B b A • (0,2)A a • (2,3)A a A • (1,3)B b A • (0,3)…
Aplikujeme tohle pravidlo
na tenhle vstup
Poznáme (A,1,2), ale tento aktivní přechod
nezahodíme!
Později poznáme ještě (A,1,3) a budeme chtít
vytvořit tohle!
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 75
Jak si zapamatovat analýzu?
• Zatím pouze umíme zjistit, zda analýza existuje, tj. zda řetězec patří do jazyka popsaného gramatikou.
• Potřebujeme znát i hierarchii složek („derivační strom“). Z ní přečteme to, co má být výstupem analýzy:
– Tvar ( TvarNFeka ( KmenNFeka ( m a t ) KoncNFeka ( NFekaS1 ( k a ) ) ) )
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 76
Jak si zapamatovat analýzu?
7.Pro každý aktivní přechod z k do j tvaru X X1 … Xn C • přidat do agendy novou složku X s rozsahem od k do j, pokud tato již není v agendě nebo v seznamu zpracovaných frází.
• S každou složkou vláčet i informaci o tom, jak vznikla. Totéž u každého rozpracovaného pravidla.
• Pozor, stejná složka se stejným rozsahem mohla vzniknout několika alternativními způsoby!
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 77
Jak si zapamatovat analýzu?
• S A | Ab• A a | ab• řetězec „ab“
– S ( A ( a b ) )– S ( A ( a ) b )
$agenda[0][2]{"S"}{popis} = "S:0:2";push(@slozeni, [$agenda[0][1]{"A"}, $agenda[1][2]
{"b"}]);push(@slozeni, [$agenda[0][2]{"A"}]);push(@{$agenda[0][2]{"S"}{slozeni}}, \@slozeni);# Vypsat j-tou složku i-tého složení složky S:0:2.print $agenda[0][2]{"S"}{slozeni}[$i][$j]{popis};
$agenda[$i][$j]{$N}{slozeni}[$k][$l]• složka začíná na pozici $i• složka končí na pozici $j• složka má neterminál $N• ke každé složce máme tyto údaje:
• složení• popis
• ze všech způsobů, jak složku složit, chceme ten $k-tý• složení je seznam odkazů na podsložky, z nich nás zajímá $l-tá podsložka
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 78
Příklad chart parsingu
Gramatika
S C D
C c | B C
D d | d C
B b | ab
a b c d b c
c 6
b 5
d 4
c 3
b 2
a 1
0 1 2 3 4 5
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 79
Příklad chart parsingu
Gramatika
S C D
C c | B C
D d | d C
B b | ab
a b c d b c
c C 6
b B 5
d D 4
c C 3
b B 2
a 1
0 1 2 3 4 5
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 80
Příklad chart parsingu
Gramatika
S C D
C c | B C
D d | d C
B b | ab
a b c d b c
C c C 6
b B 5
S d D 4
C c C 3
B b B 2
a 1
0 1 2 3 4 5
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 81
Příklad chart parsingu
Gramatika
S C D
C c | B C
D d | d C
B b | ab
a b c d b c
D C c C 6
b B 5
S S d D 4
C C c C 3
B b B 2
a 1
0 1 2 3 4 5
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 82
Příklad chart parsingu
Gramatika
S C D
C c | B C
D d | d C
B b | ab
a b c d b c
S D C c C 6
b B 5
S S S d D 4
C C c C 3
B b B 2
a 1
0 1 2 3 4 5
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 83
Příklad chart parsingu
Gramatika
S C D
C c | B C
D d | d C
B b | ab
a b c d b c
S S D C c C 6
b B 5
S S S d D 4
C C c C 3
B b B 2
a 1
0 1 2 3 4 5
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 84
Příklad chart parsingu
Gramatika
S C D
C c | B C
D d | d C
B b | ab
a b c d b c
S S S D C c C 6
b B 5
S S S d D 4
C C c C 3
B b B 2
a 1
0 1 2 3 4 5
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 85
Bezkontextové gramatiky pro morfologickou analýzu: shrnutí
Hezky popisují opravdu pravidelné jevy. Pro „pravidelné nepravidelnosti“ někdy potřeba operace,
které CFG přímo nepodporují, nutno simulovat. Neúnosně roste velikost gramatiky. Vysoký počet vzorů potřebujeme rozumné nástroje pro
údržbu. Má-li uživatel přiřadit nové slovo ke vzoru, nemůžeme chtít, aby procházel 30 velmi podobných vzorů, které se liší třeba jen jedním drobným rysem.
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 86
Domácí úkol CHRT
• Vstup:– Bezkontextová gramatika v dohodnutém formátu.– Text (slovo, věta) v dohodnutém formátu.
• Výstup:– Analýza textu (odvozovací strom).
• Napište v Perlu chart parser, který na základě gramatiky rozebere vstupní text a na výstup vypíše buď derivační strom, nebo informaci, že text nelze danou gramatikou analyzovat.
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 87
CHRT – formát vstupu
• Text i gramatika jsou v UTF-8.
• Text na STDIN, gramatika v $ARGV[0].– Text je jediné slovo. Každý znak je
samostatným terminálem. Mezerový znak nebo EOF ukončuje vstup.
• Alternativně rozšířená verze: text je delší, rozsekaný na slova, samostatně analyzovat vše od <f(>| .*?>) do <.
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 88
CHRT – formát gramatiky
• Jedno pravidlo na jednom řádku.• Pravé strany ke stejné levé straně se neshlukují, vždy
samostatné pravidlo.• Neterminál se pozná tak, že se v některém pravidle
vyskytuje na levé straně.– Neterminál na levé straně prvního pravidla je počáteční symbol.
• Jednotlivé symboly (terminály i neterminály) na pravé straně jsou odděleny jedním nebo více mezerovými znaky.
• Zvláštní znaky: -> (přesně takhle za sebou). Pokud by se měly vyskytnout na pravé straně nějakého pravidla (jako terminály), bude mezi nimi mezera.
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 89
CHRT – příklad gramatiky
S -> C D
S -> Ab1 B C D
C -> m a t
D -> k a
D -> k y
D -> c e
D -> k u
…
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 90
CHRT – formát výstupu
• Seznam všech nalezených složek, které jsou součástí alespoň jedné z analýz.
• U každé složky uvést rozsah.
• U každé složky uvést odkazy na bezprostřední podsložky, ze kterých se může skládat. Potenciálně obrovská množina derivačních stromů je tedy sbalena do relativně malého seznamu složek.
• Jestliže vstupní řetězec neodpovídá gramatice, vrátit jedinou složku s vyznačením této chyby.
12.11.2009 http://ufal.mff.cuni.cz/course/popj1 91
CHRT – formát výstupu
<slozka id=“S02” nazev=“S” od=“0” do=“2”> <sloz><podsl ref=“A01”><podsl ref=“B12”></sloz> <sloz><podsl ref=“Hugo”></sloz> (id může být libovol)</slozka><slozka id=“A01” nazev=“A” od=“0” do=“1”> <sloz>a</sloz> (terminál)</slozka><slozka id=“Hugo” nazev=“A” od=“0” do=“2”> <sloz>ab</sloz> <sloz>a<podsl ref=“B12”></sloz></slozka><slozka typ=“negram” od=“0” do=“8”> <sloz>
bflmpsvz</sloz></slozka> (negramatický vstup)