Grammatica's en ontleden

Vakcode:

WIGONT

Studiepunten:

5.72 ECTS (=4 oude studiepunten)

Periode:

periode 2 (week 44 t/m 51, dwz 28-10-2002 t/m 20-12-2002; herkansing week 10)

Deelnemers:

tot nu toe 128 inschrijvingen

Rooster:

Dit is een oud rooster!

vorm	groep	tijd	week	zaal	docent
college		ma 09-11	44-50	Rup-rood	Johan Jeuring
college		do 11-13	44-50	Lang-F125	Johan Jeuring
practicum	groep 1	ma 11-13	44-50	BBL-408	Atze Dijkstra Reinier Meerwaldt
	groep 1	vr 09-11	44-50	BBL-408	Atze Dijkstra Reinier Meerwaldt
	groep 2	ma 11-13	44-50	BBL-412	Gerard Tel Patrick Camphuijsen
	groep 2	vr 09-11	44-50	BBL-412	Gerard Tel Patrick Camphuijsen
	groep 3	do 09-11	44-50	BBL-408	Martijn Schrage Lukas Spee
	groep 3	vr 13-15	44-50	BBL-408	Martijn Schrage Lukas Spee
	groep 4	do 09-11	44-50	BBL-412	Karina Olmos Joffre Niels van der Velden
	groep 4	vr 13-15	44-50	BBL-412	Karina Olmos Joffre Niels van der Velden
tentamen		di 14-17	51	EDUC-theta

Inhoud:

Veel programma's hebben als input een rij symbolen. Deze rij symbolen heeft vrijwel altijd een structuur. Voorbeelden van zulke rijen symbolen zijn programma's in een of andere programmeertaal, over het internet in pakketvorm verstuurde informatie, of informatie die door een programma in een file is weggeschreven met de bedoeling door een ander programma weer ingelezen te worden.

Dergelijke structuren worden beschreven met behulp van grammatica's. Vanuit deze beschrijving kunnen automatisch programma's gegenereerd worden die deze structuur herkennen. Dit herkennisproces is een belangrijk component van veel programma's (bijvoorbeeld vertalers), en ook de beschrijving van het vertaalproces maakt gebruik van dergelijke grammaticale formalismen.

Door speciale klassen van grammatica's te gebruiken kun je al dan niet meer van de structuur uitdrukken, of tevoren garanderen dat je de structuur gemakkelijk (bijvoorbeeld in lineaire tijd) kunt herkennen.

In dit vak leer je zelf grammatica's te ontwerpen, hoe hiervoor ontleders te construeren en hoe de resultaten van deze ontleders verder te gebruiken.

Literatuur:

Collegediktaat: Grammatica's en ontleden.

Werkvorm:

Het vak heeft een practicum. Dit vak leent zich voor een leervorm waarin aspecten van werkcollege en practicum worden gecombineerd.

Toetsvorm:

De toetsing bestaat uit een tentamen en een practicum.

Inspanningsverplichting voor aanvullende toets:

Om aan de aanvullende toets te mogen meedoen is ontbreken van ten hoogte 1 toetsactiviteit toegestaan.

Beschrijving:

Allereerst worden context-vrije grammatica's (BNF) behandeld, tesamen met het schijven van eenvoudige niet-deterministische top-down ontleders (recursive descent ontleden) hiervoor. Het BNF-formalisme wordt daarna uitgebreid met de reguliere afkortingen, zoals we die uit de Extended-BNF kennen, en ook hiervoor worden weer ontleders aangeleverd.

In een aparte sectie worden reguliere talen en hun bijbehorende automaten beschreven. Een belangrijk aspect hierbij is het verschil tussen deterministisch en niet-deterministich ontleden die hierbij samen vallen. Ook laten we zien hoe een voorbeeld dat we eerder hebben geintroduceerd m.b.v. de reguliere subtaal kan worden herschreven, en wel zo dat het nu efficient is te ontleden. Ook het begrip syntax directed translation wordt hierbij geintroduceerd.

Voortbouwend wordt tenslotte de klasse der LL(1) talen behandeld, waarbij begrippen als grammatica-analyse gedemonstreerd worden. Dit biedt tevens een inleiding tot een begrip als abstracte interpretatie.

Tenslotte worden enige belangrijke stellingen behandeld die betrekking hebben op de uitdrukkingskracht van de verschillende klassen van talen.

Leerdoel van dit vak is ook een eerste kennismaking te bieden met enige technieken uit de programmeermethodologie, die slechts voor een beperkt aantal studenten bij latere vakken uitgebreider aan de orde komen. Veel van de technieken worden concreet gemaakt door ook programma-code aan te bieden in de vorm van Haskell programma's.

Kennisdoelen: grammatica's, top-down ontleders, (niet)determinisme, combinator parsers, compositionaliteit (via o.a. initiele algebra's), reguliere structuren, finite state machines, LL(1), partiële evaluatie, XML/DTD, Chomsky hierarchie, pomp-stellingen.

Vaardigheden-doelen: Het ontwerpen van context-vrije grammatica's, het construeren van ontleders hiervoor, en het op systematische wijze aanpakken van het vertaalproces.

Inzicht-doelen: Met de behandeling van het begrip compositionaliteit (d.w.z. homomorfisme) trachten we een verband met de semantiek van talen te leggen. Mogelijkheden en onmogelijkheden van abstracte interpretatie (in dit geval grammatica analyse), inzicht in de algemene structuur van vertalers, en een verder ontwikkelde programmeervaardigeheid en de mogelijkheid te abstraheren van concrete instanties van een probleem. Ook wordt (hopelijk) enig inzicht verkregen in de relatie met automatische stelling bewijzers, en een basis opgebouwd van waaruit logische programmeertalen (o.a. definite clause grammars) beter begrepen kunnen worden.

Indeling:

Context Vrije Grammatica's
Combinator Parsers I
Reguliere uitbreidingen, Finite State Machines
Combinator Parsers II
Compositionaliteit (zeer eenvoudig vertalertje)
LL(1)
Uitdrukkingskracht van talen, Chomsky Hierarchie

wijzigen?