DM565: Formelle sprog og dataprocessering
Indgangskrav
Faglige forudsætninger
Studerende, der følger kurset, forventes at have kendskab til centrale elementer i kurser om algoritmer og datastrukturer, samt diskret matematik, herunder viden om træer, rekursive definitioner, basale bevisteknikker, søgetræer og hashtabeller, samt at have en vis programmeringserfaring, herunder kendskab til assemblerprogrammering.
Kurset kan ikke følges af studerende, der har taget DM546.
Formål
Kurset har til formål at sætte de studerende i stand til at udtrykke formelle sprog i forskellige formalismer, herunder at vælge den rette udtryksform for et givent problem under hensyntagen til effektivitet.
Der findes tusindvis af dataformater, og realistiske projekter vil ofte trække på mange forskellige på samme tid. Kurset skal sætte de studerende i stand til at processere dataformater automatisk, herunder at transformere et dataformat til et andet.
En af de mest avancerede former for datatransformation er den, en oversætter realiserer ved oversættelse fra et højniveausprog til et lavniveausprog. Kurset vil udstyre de studerende med viden om de essentielle teknikker i den proces.
Endelig vil de studerende blive introduceret til innovative processer, konkretiseret gennem et eget projekt.
Kurset bygger oven på den viden, der er erhvervet i kurser om algoritmer og datastrukturer, diskret matematik og computerarkitektur, og giver et fagligt grundlag for at studere komplekistet og beregnelighed, der er placeret senere i uddannelsen.
I forhold til uddannelsens kompetenceprofil har kurset eksplicit fokus på at give den studerende kompetencen til at udtrykke sig gennem formalismer til specifikation af formelle sprog, genkende essentielle elementer af dataformater, samt at kunne transformere både simple og komplekse formater til andre, herunder at kunne vælge den bedste teknik til det forhåndenværende problem. Desuden skal den studerende opnå kompetencer i værdiskabelse gennem innovative processer under anvendelse af bl.a. centrale elementer fra kurset.
Målbeskrivelse
For at opnå kursets formål er det læringsmålet for kurset, at den studerende demonstrerer evnen til at:
- kunne konstruere endelige automater og regulære udtryk for simple sprog og konvertere mellem disse.
- formulere kontekstfri grammatikker for kontekstfri sprog.
- kunne transformere mellem et udvalg af dataformater.
- formulere sig ved hjælp af regulære udtryk og anvende disse til at konstruere scannere til leksikal analyse.
- afgøre om en grammatik er LL(1) eller LR(1) og justere den, hvis den ikke er, og at kunne konstruere parsere til syntaksanalyse baseret på disse klasser.
- kunne designe abstrakte syntakstræer og opbygge disse under parsning.
- kunne anvende astrakte syntakstræer til forskellige formål som f.eks. typecheck af programmeringssprog under anvendelse af symboltabeller.
- kunne håndtere processen omkring at transformere et abstrakt syntakstræ for et højniveau sprog til et lavniveau sprog.
- udføre en process indeholdende innovativ informationsprocessering gennem et projekt, hvor eksisterende data ekstraheres, transformeres og kombineres med henblik på værdiskabelse med udgangspunkt i en forretningsmodel.
Indhold
Kurset indeholder følgende faglige hovedområder:
- regulære udtryk
- endelige automater
- kontekstfri grammatikker
- dataformater og datatransformation
- LL(1) og LR(1) sprog og grammatikker
- top-down og bottom-up parsningsteknikker
- intern repræsentation
- typecheck
- oversættelse
- innovation
Litteratur
Eksamensbestemmelser
Eksamenselement a)
Tidsmæssig placering
Udprøvninger
Skriftlig eksamen og projekt med mundtligt forsvar
EKA
Censur
Bedømmelse
Identifikation
Sprog
Varighed
Hjælpemidler
ECTS-point
Uddybende information
Eksamensformen ved reeksamen er mundtlig med ekstern censur og 7-trinsskala.
Vejledende antal undervisningstimer
Undervisningsform
På naturvidenskab er undervisningen tilrettelagt efter trefasemodellen dvs. intro, trænings- og studiefasen.
- Introfase (forelæsning, holdtimer) - Antal timer: 34 timer
- træningsfase: Antal timer: 28, heraf eksaminatorie: 28 timer
I introfasen benyttes en modificeret udgave af klassisk forelæsning, hvor fagets grundbegreber og metoder præsenteres, med såvel teori som eksempler baseret på konkrete data. I disse timer er der mulighed for spørgsmål og diskussion.
I træningsfasen arbejdes der med opgaver og diskussionsemner, som relaterer sig til indholdet i de forudgående introfasetimer. I disse timer er der mulighed for at arbejde specifikt med særligt vanskelige emner. I studiefasen arbejder de studerende selvstændigt med projekt og relationen til fagets termer. Der er efterfølgende mulighed for at bringe spørgsmål op.
Studiefaseaktiviteter: I studiefasen arbejder de studerende selvstændigt med projekt og relationen til fagets termer. Der er efterfølgende mulighed for at bringe spørgsmål op.