Projekt 6 — Syntaktický analyzátor (Parser)

Napiš AI, která syntakticky rozebírá věty a extrahuje jmenné fráze.

$ python parser.py
Sentence: Holmes sat.
        S
   _____|___
  NP        VP
  |         |
  N         V
  |         |
holmes     sat

Noun Phrase Chunks
holmes

Kdy úlohu dokončit

Do 2027-06-30T23:59:00+00:00.

Jak získat pomoc

1. Ptej se prostřednictvím Ed!
2. Ptej se v kterékoli komunitě CS50!

Východiska

Běžnou úlohou zpracování přirozeného jazyka je parsing, určování struktury věty. Je užitečné z více důvodů: znalost struktury pomáhá počítači porozumět významu a získávat z věty informace. Zejména extrakce jmenných frází často pomůže určit, o čem věta je.

Pro strukturu anglických vět použijeme formalismus bezkontextové gramatiky. Přepisovacími pravidly opakovaně měníme symboly na jiné. Začínáme neterminálním symbolem S, větou, a pravidla používáme až do vytvoření celé věty terminálních symbolů, tedy slov. S -> N V například přepisuje S na N V, podstatné jméno následované slovesem. S pravidly N -> "Holmes" a V -> "sat" vytvoříme větu "Holmes sat.".

Jmenná fráze nemusí být jediné slovo jako "Holmes". Fráze "my companion", "a country walk" či "the day before Thursday" vyžadují složitější pravidla. Pro "my companion" můžeme například uvažovat:

NP -> N | Det N

Pravidlo říká, že NP, jmenná fráze, může být samotné podstatné jméno N nebo determinátor Det následovaný podstatným jménem. Determinátory zahrnují například "a", "the" a "my". Svislá čára | odděluje více přípustných přepisů NP.

Chceme-li toto pravidlo použít při rozboru věty S, musíme také změnit S -> N V, aby podmětem mohla být jmenná fráze NP. Vidíš jak? Pro složitější jmenné fráze bude možná potřeba gramatiku dále rozšířit.

Začínáme

• Stáhni dodaný kód z https://cdn.cs50.net/ai/2023/x/projects/6/parser.zip a rozbal jej.
• Ve složce parser spusť pip3 install -r requirements.txt, kterým nainstaluješ závislost nltk pro zpracování přirozeného jazyka.

Porozumění zadání

Nejprve se podívej na textové soubory ve složce sentences. Každý obsahuje anglickou větu. Cílem je napsat parser, který rozebere všechny tyto věty.

V parser.py si prohlédni pravidla bezkontextové gramatiky na začátku souboru. Pravidla terminálních symbolů už jsme připravili v globální proměnné TERMINALS. Neterminální symbol Adj generuje přídavná jména, Adv příslovce, Conj spojky, Det determinátory, N podstatná jména, rozepsaná pro čitelnost na více řádků, P předložky a V slovesa.

Dále je NONTERMINALS pro všechna pravidla generující neterminální symboly. Zatím obsahuje pouze S -> N V. To vytvoří věty jako "Holmes arrived." či "He chuckled.", ale složitější ne. Pravidla NONTERMINALS musíš upravit tak, aby rozebrala všechny věty.

Funkce main přijme větu ze souboru nebo od uživatele. preprocess ji předzpracuje a pak se rozebere podle gramatiky v souboru. Vypíší se výsledné stromy i „noun phrase chunks“, úseky jmenných frází definované ve specifikaci, pomocí np_chunk.

Kromě gramatických pravidel pro tyto věty musíš implementovat také preprocess a np_chunk.

Specifikace

Dokonči preprocess a np_chunk i pravidla bezkontextové gramatiky v NONTERMINALS.

• preprocess přijme sentence a vrátí seznam slov převedených na malá písmena.
  • Můžeš předpokládat, že sentence je řetězec.
  • K tokenizaci použij funkci word_tokenize z nltk.
  • Vrať seznam slov; každé bude řetězec malých písmen.
  • Slovo bez alespoň jednoho písmene, například . či 28, z výsledku vyřaď.
• Globální NONTERMINALS nahraď pravidly bezkontextové gramatiky, která spolu s TERMINALS umožní rozbor všech vět ve složce sentences/.
  • Každé pravidlo musí být na vlastním řádku a obsahovat -> pro přepis symbolu. Pokud je přepisů více, může obsahovat |.
  • Pravidlo S -> N V nemusíš zachovat, ale první pravidlo musí začínat S ->, protože S, věta, je počáteční symbol.
  • Můžeš přidat libovolný počet neterminálních symbolů.
  • Neterminální NP použij pro jmennou frázi, například podmět věty.
• np_chunk přijme syntaktický strom tree a vrátí seznam všech úseků jmenných frází věty.
  • Zde je „noun phrase chunk“ jmenná fráze, která už žádnou další jmennou frázi neobsahuje. Formálně jde o podstrom původního stromu se štítkem NP, který nemá jiné jmenné fráze jako podstromy.
    • Pokud je například "the home" takovým úsekem, "the armchair in the home" jím není, protože obsahuje první frázi jako podstrom.
  • Můžeš předpokládat vstup typu nltk.tree se štítkem S, tedy strom věty.
  • Vrať seznam objektů nltk.tree, každý se štítkem NP.
  • Pro práci s objektem nltk.tree může pomoci dokumentace nltk.tree.

V parser.py neupravuj nic kromě funkcí určených zadáním. Můžeš přidat pomocné funkce a importy standardní knihovny Pythonu. Musíš změnit definici NONTERMINALS, ale definici TERMINALS neměň.

Tipy

• Parser může generovat věty, které podle tebe nejsou syntakticky nebo významově správné. Nemusíš se tedy obávat, pokud umožní rozbor nesmyslné věty jako "His Thursday chuckled in a paint.".
  • Přesto se podle možností vyhýbej nadměrnému generování. Parser rozhodně nemá přijmout například "Armchair on the sat Holmes.".
  • Vyhýbej se také příliš omezenému generování. Pravidlo S -> N V Det Adj Adj Adj N P Det N P Det N by sice vytvořilo větu 10, ale nepříliš užitečným a zobecnitelným způsobem.
  • Pravidla ve zdrojovém kódu přednášky jsou záměrně velmi jednoduchá a mohou generovat příliš mnoho vět. Můžeš a měla bys je upravit tak, aby byla co nejobecnější bez nadměrného generování. Zvaž zejména, jak přijmout „Holmes sat in the armchair.“, „Holmes sat in the red armchair.“ a „Holmes sat in the little red armchair.“, ale nepřijmout „Holmes sat in the the armchair.“.
• Parser může vytvořit několik různých rozborů jedné věty. Anglická gramatika je ze své podstaty nejednoznačná!
• V dokumentaci nltk.tree mohou být zvlášť užitečné funkce label a subtrees.
• Chceš-li nejprve testovat parser bez extrakce jmenných frází, může np_chunk dočasně vracet prázdný seznam []. Program tak poběží bez této extrakce, zatímco zkoušíš ostatní části.

Testování

Chceš-li vyhodnotit správnost kódu, můžeš po nastavení check50 spustit následující příkaz. Není to povinné: při odevzdání podle kroků na konci zadání proběhnou stejné testy na našem serveru. V každém případě kód také sama zkompiluj a otestuj!

check50 ai50/projects/2024/x/parser

Následujícím příkazem vyhodnotíš styl kódu pomocí style50.

style50 parser.py

Jak odevzdat

1. Otevři tento odkaz, přihlas se účtem GitHub a klikni na Authorize cs50. Pak zaškrtni souhlas s přístupem učitelů k odevzdaným pracím a klikni na Join course.
2. Nainstaluj Git a případně nainstaluj submit50.
3. Pokud máš nainstalované submit50, spusť

   submit50 ai50/projects/2024/x/parser
   

   Jinak pomocí Gitu odešli práci do https://github.com/me50/USERNAME.git, kde USERNAME je tvoje jméno na GitHubu, na větev ai50/projects/2024/x/parser.

Práce by měla být ohodnocena do pěti minut. Svůj postup pak můžeš sledovat na https://cs50.me/cs50ai!