Ga naar hoofdinhoud

Cheatsheet — context-vrije grammatica

Snelle referentie. Klap open wat je nodig hebt. De voorbeelden gebruiken een neutraal mini-grammaticaatje, geen oplossing van de opdracht.

Notatie​

Wat betekent een regel?
Zin -> Groet Naam

Lees als "een Zin mag bestaan uit een Groet gevolgd door een Naam". Links altijd één groep (non-terminal), rechts de onderdelen op een rij.

  • Meerdere mogelijkheden voor dezelfde groep schrijf je als aparte regels, óf op één regel met |:

    Groet -> "hallo"
    Groet -> "hoi"

    is hetzelfde als

    Groet -> "hallo" | "hoi"

  • Een terminal (echt woord) staat tussen aanhalingstekens: Naam -> "sam".

Terminal vs. non-terminal​

Het verschil
  • Terminal = een echt woord, een eindpunt. Staat tussen aanhalingstekens: "hallo", "sam". Wordt niet verder ontleed.
  • Non-terminal = een groep die uit andere bouwstenen bestaat: het startsymbool en alle groepen die jij verzint, plus de woordsoorten uit het lexicon (N, V, Det, Adj, Adv, P, Conj). Heeft altijd minstens één regel die zegt waaruit hij bestaat.
  • Het startsymbool is het bovenste non-terminal; in deze opdracht is dat S. Elke geldige zin moet daaruit voortkomen.

Recursie: "één of meer"​

Hoe laat je onbeperkt veel van iets toe?

Wil je willekeurig veel van iets achter elkaar, dan verwijst een groep naar zichzelf:

Reeks -> "ja" Reeks
Reeks -> "ja"

Dit dekt "ja", "ja ja", "ja ja ja", en zo verder. De ketting eindigt altijd via de tweede regel. Hetzelfde idee gebruik je als je een groep wilt laten herhalen of een staart wilt laten aangroeien. De parser-motor kan dit veilig aan, omdat elk recursief stuk een korter stuk van de zin beslaat.

Een zin testen​

Hoe ontleed je een zin?
  1. Combineer je grammatica (de regels) met het lexicon (woorden).
  2. Maak van de zin een lijst kleine-letter-woorden: zin.lower().split(). Géén leestekens.
  3. Vraag de parser naar alle bomen voor het startsymbool S.
  4. Geen bomen: de zin is afgekeurd. Eén of meer bomen: geaccepteerd, en het aantal bomen is het aantal interpretaties.

Goed om te weten​

Vorm versus betekenis

Een CFG controleert alleen de vorm van een zin, niet of hij klopt qua betekenis. Een zin met de juiste vorm komt erdoor, ook als hij nergens op slaat. Dat een grammatica de betekenis negeert, is precies wat hem zo simpel en algemeen maakt.

"Echte" tools gebruiken hetzelfde idee

De parser-motor in deze track is met opzet klein, zodat hij in je browser draait zonder installatie. Professionele tools zoals de Python-bibliotheek NLTK gebruiken dezelfde bouwstenen, terminals, non-terminals en regels met ->, met meer mogelijkheden eromheen.

Licentie en bronvermelding​

Deze track is een afgeleide bewerking van CS50 AI Project 6: Parser van Harvard University. Het origineel is gelicenseerd onder CC BY-NC-SA 4.0.

Wijzigingen ten opzichte van het origineel:

  • Volledig vertaald naar het Nederlands.
  • Opgeknipt in PRIMM-stappen (concept → stellingen → zin-voor-zin bouwen → compleet → aanpassen → zelf-bouwen → fouten → cheatsheet).
  • De NLTK-parser is vervangen door een eigen, compacte pure-Python parser-motor die zonder installatie in de browser draait (Pyodide).
  • De regels ontwerp je zelf. Een antwoord om na te kijken staat alleen achter een uitklapbaar blok bij de opdrachten, zoals overal op deze site; je docent heeft een antwoordblad bij de hand-out.

Conform de share-alike-eis wordt deze track onder dezelfde licentie verspreid: CC BY-NC-SA 4.0.

De rest van de Coderius Algoritmes-site staat onder CC BY-NC 4.0.