Context-vrije grammatica — het idee

Bronvermelding — deze track is een afgeleide bewerking van CS50 AI Project 6: Parser van Harvard University, gelicenseerd onder CC BY-NC-SA 4.0. Wij hebben het vertaald naar het Nederlands, opgeknipt in PRIMM-stappen en de NLTK-parser vervangen door een eigen browser-parser. De grammatica ontwerp je zélf; een antwoord om na te kijken staat alleen achter een uitklapbaar blok bij de opdrachten, en je docent heeft een antwoordblad bij de hand-out. Deze hele track wordt onder dezelfde licentie verspreid.

Leerdoel: je begrijpt wat een context-vrije grammatica (CFG) is, en het verschil tussen een terminal en een non-terminal. Nog geen opdracht, eerst snappen.

Het probleem

Een computer ziet een zin als een rij losse woorden:

Holmes lit a pipe

Hoe "weet" een programma dat dit een correcte zin is, terwijl

pipe a Holmes lit

dat niet is? De woorden zijn precies hetzelfde. Het verschil zit in de volgorde en in de structuur: welke woorden horen bij elkaar, en welke rol spelen ze? Daar is een grammatica voor: een verzameling regels die beschrijven hoe je een geldige zin opbouwt.

De bouwsteen-analogie

Denk aan LEGO. De losse blokjes zijn de woorden zelf: holmes, lit, a, pipe. Je kunt ze niet verder uit elkaar halen, en daarom heten ze terminals, eindpunten. Daarnaast heb je bouwplaten waar je blokjes op vastklikt tot een groter geheel, en die gehelen bestaan weer uit andere bouwstenen: dat zijn de non-terminals. Een grammatica zegt hoe je blokjes en platen aan elkaar klikt.

De notatie: regels met een pijl

De notatie oefen je eerst met een mini-voorbeeld dat niets met de opdracht te maken heeft, een grammaticaatje voor begroetingen:

Zin   -> Groet Naam
Groet -> "hallo" | "hoi"
Naam  -> "sam" | "kim"

Lees de eerste regel als "een Zin bestaat uit een Groet gevolgd door een Naam". Links staat één non-terminal, rechts staat waaruit hij mag bestaan. De pijl -> betekent "bestaat uit", en het streepje | betekent "of": Groet -> "hallo" | "hoi" zegt dat een groet hallo of hoi is. Een terminal, een echt woord, staat tussen aanhalingstekens: "hallo", "sam".

Een zin als boom

Met dit grammaticaatje kun je de zin hallo sam helemaal ontleden. Dat ziet eruit als een boom:

Zin
├─ Groet: hallo
└─ Naam: sam

Bovenaan het geheel Zin, dat uiteenvalt in een Groet en een Naam, die eindigen bij de echte woorden (de terminals).

Zin, Groet en Naam zijn non-terminals (groepen). "hallo", "hoi", "sam" en "kim" zijn terminals (woorden). Het bovenste non-terminal heet het startsymbool — daar begint elke geldige zin.

Waarom "context-vrij"?

Een regel zoals Naam -> "sam" mag je toepassen overal waar een Naam nodig is. Het maakt niet uit wat er omheen staat, de context; de regel staat op zichzelf. Daardoor kun je er zo makkelijk mee rekenen.

Een grammatica controleert alleen de structuur, niet de betekenis. hoi kim is grammaticaal prima, ook al ken je geen Kim.

Waar grammatica's het werk doen

Grammatica's zijn niet alleen iets voor Engelse zinnen. Overal waar een computer tekst met een vaste vorm moet begrijpen, staat er een.

Python zelf. Druk je op Voer uit, dan ontleedt Python eerst je code met een grammatica in bijna dezelfde notatie als hierboven (de pijl heet daar een dubbele punt). Hij staat in de taalbeschrijving van Python, honderden regels lang. Hieronder zie je de boom die Python van een som maakt.
JSON. Het formaat waarin een server data terugstuurt, zoals in je eerste endpoint, past in een handvol regels. Op json.org staan ze getekend als spoordiagrammen: een andere manier om dezelfde regels op te schrijven.
Mensentaal. Het CS50-project waar deze track van afstamt gebruikte NLTK, een Python-bibliotheek voor taal. Hoofdstuk 8 van het NLTK-boek (Engels) doet met S -> NP VP precies wat jij straks doet.
Meer. Programmeertalen, rekenmachines, zoekopdrachten in een database: Wikipedia noemt de rest.

Zo laat Python zijn eigen boom zien. Kijk of 2 * 3 bij elkaar staat:

Python

Code-omgeving wordt voorbereid…

Wat zie je?

Expression(
  body=BinOp(
    left=Constant(value=1),
    op=Add(),
    right=BinOp(
      left=Constant(value=2),
      op=Mult(),
      right=Constant(value=3))))

2 * 3 zit als één tak (BinOp met Mult) rechts van de Add. De grammatica van Python legt zo de rekenvolgorde vast, nog voor hij iets uitrekent.

Wat je gaat doen

In deze track ontwerp je zelf, zin voor zin, een grammatica die tien Engelse zinnen uit een Sherlock Holmes-verhaal kan ontleden. Je krijgt het lexicon, dat zegt welk woord welke woordsoort is (N, V, Det, Adj, Adv, P, Conj), en een kant-en-klare parser-motor die het ontleden doet.

Wat je zelf bedenkt zijn de regels: welke woordgroepen je nodig hebt, zoals een zelfstandig-naamwoordgroep of een werkwoordgroep, en hoe die samen een zin S vormen. Bij elke nieuwe zin breid je je grammatica uit, en alle eerdere zinnen moeten geldig blijven. Alles draait in de browser, zonder iets te installeren.

info

Liever eerst op papier? Print Een grammatica op papier: dezelfde tien zinnen, met achter elk woord zijn woordsoort, zin 1 voorgedaan, en na elke zin ruimte om je regels tot dan toe te schrijven. Wat je daar bedenkt, typ je in de bouwstenen over.

Zo bouw je het op

De code bouw je in kleine stappen, elk op een eigen pagina in de map "Bouwen, stap voor stap":

Daarna zet je alles samen in Alles samen — test je complete grammatica, en ga je het aanpassen en zelf bouwen.

Door naar stellingen →.

Het probleem​

De bouwsteen-analogie​

De notatie: regels met een pijl​

Een zin als boom​

Waarom "context-vrij"?​

Waar grammatica's het werk doen​

Wat je gaat doen​

Zo bouw je het op​