DM131 - 3. semester

Ugeplan for Softwarearkitektur og Distribuerede Programmer

Tema: Træer og Grafer (datastrukturer og algoritmer) samt sprogteori
  - Gå til uge: 17, 18, 19, 20, 21, 22

Sidst ændret: 2014.05.19

 

Uge 17
Dag Tidspunkt Emne Litteratur / Opgaver
Mandag PÅSKE DAG INGEN UNDERVISNING  
     
Onsdag 08:30 - Vi tager fat på nyt tema med datastrukturer og algoritmer,
hvor hoved temaet vil være træer og grafer.

Da vi allerede har set på en del datastrukturer, herunder binære træer på 1. studieår (uge 43-44) vil denne uge være tale om delvis gentagelse af stof fra 1. år.

Denne uge vil vi fokusere på binære træer, som der også vil kunne komme opgaver i til eksamen.

Øvrige vi lige kort vil samle op på:
- Array og Lister baseret på Array (C# List) (ved Jan og Anton)
- Linkede lister (ved Jan)
- Hashtabeller (ved Anton)
- Stack
- Queue

Binære træer (ved Anders)

Visualisering af Binær træ

Nyt:
Visitor pattern i forbindelse med traversering af datastruktur
Om datastrukturer gennerelt:
- Skim for et overblik: http://en.wikipedia.org/wiki/List_of_data_structures
Om generisk template:
- læses: Generiske datastrukturer (template baserede) - her en dårlig stak 173_StackTemplate  

Om algoritme kompleksitet
- Læs hele artiklen: http://en.wikipedia.org/wiki/Best,_worst_and_average_case
- skim afsnit 1til 3 incl: http://en.wikipedia.org/wiki/Algorithmic_complexity#Complexity_classes

Læses - Induktionsbeviser - bevis for korrekt virkemåde at algoritmer

Læses: intens: Noter til binære træer koncentrat om begreber

Fordybelse - Binær søgetræ (du kan vælge den du bedst forstår):
    -  http://en.wikipedia.org/wiki/Binary_search_tree (Engelsk - lidt mere dybde)
    -  http://da.wikipedia.org/wiki/Binært_søgetræ (dansk)
    -  Microsoft: om træer: http://msdn.microsoft.com/en-us/library/ms379572.aspx  

Suplement:
- C# eksempel på dele af binært træ
- IComparable og IComparer interfaces:- Eksempel med brug af IComperable og Collections.Comparer til sortering af varer i list på forskellige kriterier (varenr, betegnelse og pris)

Læs om visitor pattern - i forbindelse med traversering
- Binære søgetræer i med visitor pattern i CSharp
 
- 11:50 Opgaver med binære træer ( repetition - løs opgave BT01,BT02,BT03 og BT04 - laves inden onsdag)
 
12:30

- 14:00

Opgaveløsning uden lærerstøtte
Opgaver med binære træer
 - repetition - løs opgave BT01,BT02,BT03 og BT04 - laves inden onsdag)
 - opgave BT05 - blev også stillet på 1. studieår, hvis den blev løst er det repetition, hvor du så kan udvide med test.

 

  
Fredag 08:30 - Opgaveløsning uden lærerstøtte
Opgaver med binære træer (løs opgave BT05)		  
- 10:00
12:30 - 14:00 Opgaveløsning uden lærerstøtte
Opgaver med binære træer (løs opgave BT05)
Afleveringsopgaver (obligatoriske) denne uge: opgave BT05 - (BT01-04 skal laves til onsdag dag, men ikke afleveres)
 
 

 

Uge 18
Dag Tidspunkt Emne Litteratur / Opgaver
Mandag 08:30 - Evt. opsamling på binære træer

Introduktion til grafer 

Graf - implementering / datastrukturer

Note om grafer af Niels Otto Knudsen  - side 1-4 - læs før undervisningen
 http://msdn.microsoft.com/en-us/library/ms379574.aspx - skim før undervisningen
 

Gennemgang af datastrukturen graf ift. implementering   se video før undervisningen
- 10:00 Oplæg til bredere obligatorisk opgave i sproglære og grafer - opgaven vil blive opdelt i delopgaver over de næste uger, så der til sidst gerne skulle kunne ses en samlet løsning.

delopgave 1) Med udgangspunkt i oplæggets bilag med ruteplan skal du finde frem til hvilke knuder og kanter og tegne en graf, der svarer til ruteplanen. Når du får lavet et grafprogram, kan du bruge ruteplan-grafen som testdata.
 
10:20 - Opsamling på Obligatorisk køreplansopgave - delopgave 1)
 		 Gennemgang af datastrukturen graf ift. implementering   se evt. video igen i forbindelse med opgaveløsningen.
12:30

- 14:00

Delopgave 2a: (datastruktur, metoder til at indsætte elementer, test), se under afleveringsopgaver denne uge

Ekstra opgaver for dem der har løst ruteplansopgaverne - GrafOpgaver - programmering 

  
Onsdag 08:30 -

Graf algoritmer
- opsamling på datastrukturer for graf
- bredde- og dybde-traversering

 Note om grafer af Niels Otto Knudsen  - side 5-6- læs før undervisningen
 http://msdn.microsoft.com/en-us/library/ms379574.aspx - læs samme enme her

Se evt. start på: Gennemgang af Dijkstra's "Shoretst Path" algoritme i en graf, herunder opsamling på dybde og bredde gennemløb samt Prims minimum spanning tree - gennemgået at Bjørk Boye Busch 2010-11-18    
- 11:50 Opgaveløsning med lærerstøtte
 
Løsningseksempel på grafalgoritmerne kan findes her:
- http://bjoerks.net/CSharp/Modeller/Graf_Matrix.zip
Du skal selvfølgelig selv prøve at løse opgaverne, men kan bruge løsningen som inspiration, hvis du går helt i stå eller vil tjekke din løsning af selv.
 
12:30

- 14:00

Opgaveløsning uden lærerstøtte

Delopgave 2b: metode for brede-først traversering, se under afleveringsopgaver denne uge

Evt. ekstraopgave for ruteplan:
- Lav også en metode for dybde først med brug af recursion
- Lav en metode for dybde først uden brug af recursion

Ekstra opgaver for dem der har løst ruteplansopgaverne - GrafOpgaver - programmering 

  

Løsningseksempel på grafalgoritmerne kan findes her:
- http://bjoerks.net/CSharp/Modeller/Graf_Matrix.zip
Du skal selvfølgelig selv prøve at løse opgaverne, men kan bruge løsningen som inspiration, hvis du går helt i stå eller vil tjekke din løsning af selv.
Fredag 08:30 - Opsamling og opgaveløsning med støtte  
- 10:00
12:30 - 14:00

Opgaveløsning uden lærerstøtte

Delopgave 2b: metode for brede-først traversering, se under afleveringsopgaver denne uge

Evt. ekstraopgave for ruteplan:
- Lav også en metode for dybde først med brug af recursion
- Lav en metode for dybde først uden brug af recursion

Ekstra opgaver for dem der har løst ruteplansopgaverne - GrafOpgaver - programmering 
Afleveringsopgaver (obligatoriske) denne uge: Ruteplansopgave - frem til delopgave 2b - Bredde først traversering
 
Oplæg til bredere obligatorisk opgave i sproglære og grafer - opgaven vil blive opdelt i delopgaver over de næste uger, så der til sidst gerne skulle kunne ses en samlet løsning.
delopgave 1) Med udgangspunkt i oplæggets bilag med ruteplan skal du finde frem til hvilke knuder og kanter og tegne en graf (papir og blyant), der svarer til ruteplanen.
delopgave 2) Du skal have lavet en grafklasse og et program, der med brug af denne kan løse grafspørgsmålene med brug af ruteplan-grafen som testdata (behøver ikke at kunne udskrive i formatet som beskrevet i projekt-oplæg)
  -  2a) grafklassen skal kunne indeholde en graf.
              - Der skal være metoder så man skal kunne indsætte elementer i grafen
              - Du skal evt. have en metode, der for alle knuder kan udskrive kanterne som kontrol
  -  2b) metode for brede-først traversering.
  -  2c) metode for minimum spanning tree
  -  2d) du er velkommen til at udvide med ekstra metoder for fx shortest path (Dijkstra)
 

 

Uge 19
Dag Tidspunkt Emne Litteratur / Opgaver
Mandag 08:30 - Graf algoritmer
- bredde- og dybde-traversering (opsamling)
- minimum spanning tree - Prims algoritme
- minimum spanning tree - Kruskals		 http://msdn.microsoft.com/en-us/library/ms379574.aspx - læs forud om minumum spanning tree
 Note om grafer af Niels Otto Knudsen  - side 10-17- suppler læsning her

Prims algoritme på graf - minimum spanning tree
Prims algoritme: applet for simulering af algoritme 

Kruskals algoritme på graf - minimum spanning tree
Kruskals algoritme: applet for simulering af algoritme
- 11:50 Opgaveløsning med lærerstøtte

Delopgave 2c: metode for minimum spanning tree, se under afleveringsopgaver denne uge

Evt. ekstraopgave for ruteplan:
- du kan prøve at lave 2 udgaver for minimum spanning tree med - Prims og Kruskals
- du kan udvide med ekstra metoder for fx shortest path (Dijkstra)

Gennemgang af Dijkstra's "Shoretst Path" algoritme i en graf, herunder opsamling på dybde og bredde gennemløb samt Prims minimum spanning tree - gennemgået at Bjørk Boye Busch 2010-11-18    

Løsningseksempel på grafalgoritmerne kan findes her:
- http://bjoerks.net/CSharp/Modeller/Graf_Matrix.zip
Du skal selvfølgelig selv prøve at løse opgaverne, men kan bruge løsningen som inspiration, hvis du går helt i stå eller vil tjekke din løsning af selv.
     
12:30

- 14:00

 Opgaveløsning uden lærerstøtte

Ekstra opgaver for dem der har løst ruteplansopgaverne - GrafOpgaver - programmering 
 		  
Onsdag 08:30 - Graf algoritmer, opsamling til nu

evt. Dijkstras shortest path		 Gennemgang af Dijkstra's "Shoretst Path" algoritme i en graf   se video før undervisningen
Simulerings af Dijkstra's algoritme
Note om grafer af Niels Otto Knudsen  - side 11-13- suppler læsning her

Gennemgang af Dijkstra's "Shoretst Path" algoritme i en graf, herunder opsamling på dybde og bredde gennemløb samt Prims minimum spanning tree - gennemgået at Bjørk Boye Busch 2010-11-18   
- 11:50
12:30
- 14:00		 Opgaveløsning uden lærerstøtte - se sidst i ugens plan  
Fredag 08:30 - Graf algoritmer, opsamling til nu

Dijkstras shortest path - evt. taget onsdag 

Evt. domain-model med data for ruteplan og fra denne til graf

 Gennemgang af Dijkstra's "Shoretst Path" algoritme i en graf   se video før undervisningen
Simulerings af Dijkstra's algoritme
Note om grafer af Niels Otto Knudsen  - side 11-13- suppler læsning her

Gennemgang af Dijkstra's "Shoretst Path" algoritme i en graf, herunder opsamling på dybde og bredde gennemløb samt Prims minimum spanning tree - gennemgået at Bjørk Boye Busch 2010-11-18   
- 10:00
12:30 - 14:00 Opgaveløsning uden lærerstøtte - se sidst i ugens plan
Afleveringsopgaver (obligatoriske) denne uge: Ruteplansopgave - frem til delopgave 2c - Minimum spanning tree
 
Oplæg til bredere obligatorisk opgave i sproglære og grafer - opgaven vil blive opdelt i delopgaver over de næste uger, så der til sidst gerne skulle kunne ses en samlet løsning.
delopgave 1) Med udgangspunkt i oplæggets bilag med ruteplan skal du finde frem til hvilke knuder og kanter og tegne en graf (papir og blyant), der svarer til ruteplanen.
delopgave 2) Du skal have lavet en grafklasse og et program, der med brug af denne kan løse grafspørgsmålene med brug af ruteplan-grafen som testdata (behøver ikke at kunne udskrive i formatet som beskrevet i projekt-oplæg)
  -  2a) grafklassen skal kunne indeholde en graf.
              - Der skal være metoder så man skal kunne indsætte elementer i grafen
              - Du skal evt. have en metode, der for alle knuder kan udskrive kanterne som kontrol
  -  2b) metode for brede-først traversering.
  -  2c) metode for minimum spanning tree
  -  2d) du er velkommen til at udvide med ekstra metoder for fx shortest path (Dijkstra)
delopgave 3) Der skal laves en datastruktur/domaine-model, der kan indeholde informationen fra den beskrevne ruteplan (oplæg/idé gennemgås næste mandag, men spørg hvis du er klar denne uge)
delopgave 4) Der skal laves en rutine, der ud fra data i ruteplan-modellen(domain-modellen) kan danne grafen. 
 

 

Uge 20
Dag Tidspunkt Emne Litteratur / Opgaver
Mandag 08:30 - Opsamling på grafer og algoritmer på disse

Fra domain-model med data til graf
 

  
  Introduktion til sprogteori
- Grammatikker og sprog
- Compiler
- regulære udtryk
- BNF + EBNF

- en lille smule om Assembler (symbolsk maskinsprog), maskinsprog og afvikling på cpu (udskudt til onsdag)

 Noter/litteratur se tidligere udleverede kopier:
 1. Hvordan virker en Compiler (læs forud for undervisningen)
 2.  Compiler design  (læs forud for undervisningen)
 3. Note om EBNF grammatik(kbh. uni)) (læs efter behov undervejs)
De første 2 vil være primære for denne dag - den sidste inddrages undervejs i forløbet efter behov som supplement, idet der vil være eksempler og gennemgang ud fra C# i selve undervisningen.
Supplerende / alternativ litteratur for de der måtte ønske at anskaffet sig dette - kan man bruge #Comp - primært kap. 1 og 4.

Slides om Sprog og compiler (vigtige pointer og overblik)

Om Context frie grammatikker (wikipedia) - se specielt på eksemplerne:
- http://en.wikipedia.org/wiki/Context-free_grammar

EBNF eksempler
Download EBNF Visualizer (fra http://dotnet.jku.at/applications/Visualizer/)
Ebnf-Visualizer_bjbu.exe.zip - udgave kører under windows7

Leksikalsk analyse ( scanner til tokens ):
- http://en.wikipedia.org/wiki/Lexical_analysis

Om programmeringssprog, parsertree og tokenization (wikipedia):
- http://en.wikipedia.org/wiki/Parsing#Programming_languages
- vigtigste er: http://en.wikipedia.org/wiki/File:Python_add5_parse.png
Om state pattern:
- http://en.wikipedia.org/wiki/File:State_Design_Pattern_UML_Class_Diagram.png

For dem der gerne vil lidt dybere i emnet
Om hvad er en compiler er og forskellige typer (wikipedia):
- http://en.wikipedia.org/wiki/Compiler

  Opgaver med EBNF (løs opgave 1-5)
Ruteplansopgave - delopgave 3, 5 og 6		  
12:30

- 14:00
Opgaveløsning uden lærerstøtte
 - EBNF 1-5
- Ruteplansopgave - delopgave 3,  5 og 6		  
Onsdag 08:30 - Sproglære fortsat

- en lille smule om Assembler (symbolsk maskinsprog), maskinsprog og afvikling på cpu (flyttet fra mandag)

Opsamling på BNF, EBNF og regulære udtryk og EBNF opgaver

introduktion til Scanner / Leksikalsk analyse - vi skal "bygge" første del af inputbehandlingen

  • beskrivelse  med regulære udtryk
  • design med DFA (tilstandsdiagram med overgang og effekt)

Compilering_af_symbolsk_maskinsprog med brug af  Symboltabel
Bjarnes modelmaskine til VirtualBox med dokomentation og tilhørende eksempler
Oracles VirtualBox software: https://www.virtualbox.org/ (For de der gerne vil afprøve selv)
Denne del er ikke noget vi bruge ret meget tid på, men er med for at forstå en smule om hvad maskinsprog er for noget, samt simple sprog som assembler sprog er.

 

Note om EBNF grammatik og syntakstyret indlæsning (se tidligere udleverede kopier)

Scanner / Leksikalsk analyse:
- eksempel på simpel scanner / leksikalsk analyse
  
- 11:50 Opgaveløsning med støtte
     
12:30

- 14:00
Opgaveløsning uden lærerstøtte - ruteplanopgaver - se sidst i ugens plan 		  
Fredag   Store bededag - ingen undervisning  
 
Afleveringsopgaver (obligatoriske) denne uge: ingen obligatoriske afleveringer denne uge

Ruteplansopgave - delopgave 3 (den er vigtig, da struktur skal bruges i sproglære- / indlæsnings delen og indgår i opgave senere)

Ruteplansopgave - delopgave 4 kan binde indlæsning sammen med graf til samlet løsning (hvis du er bagud så drop delopgave 4 frem for andre opgaver)

Ruteplansopgave - delopgave 5 og 6 skal ikke afleveres denne uge men laves og indgår næste uge
Oplæg til bredere obligatorisk opgave i sproglære og grafer - opgaven vil blive opdelt i delopgaver over de næste uger, så der til sidst gerne skulle kunne ses en samlet løsning.
delopgave 3) Der skal laves en datastruktur/domaine-model, der kan indeholde informationen fra den beskrevne ruteplan (oplæg/idé gennemgås denne uge)
 - følgende kunne bruges som struktur (EBNF_Ruteplan_Datamodel_for_Regionskoereplan.ppt) 
- du kan evt. vælge at bruge denne model, hvis du har problemer med at definere din egen (EBNF_Ruteplan_Model_Syntakstræ_Projekt.zip) 

delopgave 4) Der skal laves en rutine, der ud fra data i ruteplan-modellen(domain-modellen) kan danne grafen. 

delopgave 5) Med udgangspunkt i grammatikken for Ruteplansinputtet skal du fastsætte passende brikker/tokens og herefter omskrive grammatikken med disse som terminaler, du skal endvidere beskrive hvert af disse tokens som regulære udtryk.

delopgave 6) Der skal laves en Token klasse, der kan bruges til scanner (leksikalske analysator) og parser. Du kan evt. også også lave en klasse til udveksle Tokens som i løsningen med medlemssystemet.
du kan tage udgangspunkt i ét af følgende eksempler - Det er ikke meningen du i denne uge skal lave hele scanneren, men i denne uge blot en Token klasse, der passer med det du er kommet frem til i delopgave 5- klassen skal bruges i næste del5
- eksempel på simpel scanner / leksikalsk analyse
- eksempel på scanner / leksikalsk analyse baseret på statepattern
 
#comp: Programming Language Processors In Java - compilers and interpreters, David A Watt & Derick F Brown, Printice Hall, ISBN: 0-130-25786-9

 

Uge 21
Dag Tidspunkt Emne Litteratur / Opgaver
Mandag 08:30 - Sproglære fortsat

Scanner / Leksikalsk analyse - vi skal "bygge" første del af inputbehandlingen

  • opsamling på design med DFA (tilstandsdiagram med overgang og effekt)
     
  • kode med brug af state-pattern
    state pattern
 

Note om EBNF grammatik og syntakstyret indlæsning (se tidligere udleverede kopier)

Scanner / Leksikalsk analyse:
- eksempel på simpel scanner / leksikalsk analyse - simple ord
- eksempel på simpel scanner / leksikalsk analyse - fuld antal state - NY
- eksempel på scanner / leksikalsk analyse baseret på statepattern
 Om state pattern: http://en.wikipedia.org/wiki/State_pattern

- 10:00
10:20 - Opgaveløsning med lærerstøtte
- Ruteplansopgave - delopgave 7a		  
12:30

- 14:00

 Opgaveløsning uden lærerstøtte
- Ruteplansopgave - delopgave 7a		  
Onsdag 08:30 -    
- 10:00 Scanner / Leksikalsk analyse  fortsat
  • Opsamling på scanner med brug af state pattern
     
  • brug af Lex/Flex værktæj (C# udgave tilpasset brug med Visual Studio)

Om state pattern: http://en.wikipedia.org/wiki/State_pattern

Scanner / Leksikalsk analyse:
- eksempel på simpel scanner / leksikalsk analyse - fuld antal state - NY
- eksempel på scanner / leksikalsk analyse baseret på statepattern

Medlemsliste LexAnalyser med Lex værktøj:  CsLexSolutionMedlemsliste_v1.zip
- i forhold til programmeringsopgave skal værktøjsløsning ikke anvendes i primære løsning, men vise hvordan man kan bruge regulære udtryk næsten direkte til at lave en Leksikalsk analyse
     
12:30

- 14:00

 Opgaveløsning uden lærerstøtte
- Ruteplansopgave - delopgave 7a og 7b		  
Fredag 08:30 - Introduktion til parseren

 

 



 

Se følgende videoer inden mandag

 

 

Bottom-up parsing:
- http://en.wikipedia.org/wiki/Bottom-up_parsing
Recursive descent parser (top-down):
- http://en.wikipedia.org/wiki/Recursive_descent_parser
Parse tree (resultat fra parser):
- http://en.wikipedia.org/wiki/Parse_tree
Eliminering af vestre-recursion i grammatikken (se tidligere udleverede kopier)
- (man skal kun kende til problematikken ikke kunne omskrive) 


Parser - kode svarende til videoer:

- eksempel på recursive decent parser (medlemsliste)

- eksempel på parser baseret på startepattern (medlemsliste)
- 10:00
12:30 - 14:00

Opgaveløsning uden lærerstøtte
- Ruteplansopgave - delopgave 7a og 7b

 



 
Afleveringsopgaver (obligatoriske) denne uge: Ruteplansopgave - leksikalsk analyse / scanner: delopgave 5, 6 og 7a

Oplæg til bredere obligatorisk opgave i sproglære og grafer - opgaven vil blive opdelt i delopgaver over de næste uger, så der til sidst gerne skulle kunne ses en samlet løsning.

delopgave 5) Med udgangspunkt i grammatikken for Ruteplansinputtet skal du fastsætte passende brikker/tokens og herefter omskrive grammatikken med disse som terminaler, du skal endvidere beskrive hvert af disse tokens som regulære udtryk.

delopgave 6) Der skal laves en Token klasse, der kan bruges til scanner (leksikalske analysator) og parser. Du kan evt. også også lave en klasse til udveksle Tokens som i løsningen med medlemssystemet.
du kan tage udgangspunkt i ét af følgende eksempler:
- eksempel på simpel scanner / leksikalsk analyse
- eksempel på scanner / leksikalsk analyse baseret på statepattern

delopgave 7a) Der skal laves en Scanner / Leksikalsk analysator, der kan lave Tokens ud fra en tekstfil og aflevere disse i en passende datastruktur Parseren senere kan bruge som input. Du skal teste med en udskrift af de tokens du finder. Du skal lave passende fejludskrift, hvis der er fejl i den leksikalske analyse (input ikke passer til tokens), hvis du prøve om du kan scanne videre og "komme på sporet igen".
Du kan tage udgangspunkt i ét af følgende eksempler:
- eksempel på simpel scanner / leksikalsk analyse
- eksempel på scanner / leksikalsk analyse baseret på statepattern

delopgave 7b) Der skal laves en Scanner / Leksikalsk analysator med brug af Lex/Flex værktøjet - du tilretter medlemsliste syntaksen til ruteplanssyntaksen  
Du kan tage udgangspunkt i en af følgende eksempler
- Medlemsliste LexAnalyser med Lex værktøj:  CsLexSolutionMedlemsliste_v1.zip 
 

 

Uge 22
Dag Tidspunkt Emne Litteratur / Opgaver
Mandag 08:30 -

Sprogteori / parser - se videoer før undervisningen

 

Parser:
- eksempel på recursive decent parser (medlemsliste)
- eksempel på parser baseret på startepattern (medlemsliste)

Evt. supplement hvis nogen føler særlig trang. Løsning med tabel-styret parser tættere på beskrivelser i KBH note)
- EBNF_Syntaksstyret_Medlemsliste_nokn_bjbu 
  Opgaveløsning med lærerstøtte
- Ruteplansopgave - delopgave 8a
     
12:30

- 14:00

 Opgaveløsning uden lærerstøtte
- Ruteplansopgave - delopgave 8a		  
Onsdag 08:30 - Sprogteori / parser Lekikalsk analyse og parsing med brug af værktøj (LALR(1) - Flex+Bisson)

Video om brug af Lex/Flex værktæj (C# udgave tilpasset brug med Visual Studio)   
- 10:00 Sprogteori / parser Medlemsliste med brug af "Flex" - "Bisson" lignende værktøj til C# for Leksikalsk analyse og parsing - Se hvor nemt det bliver når man "bare" kan beskrive grammatikken med regulære udtryk til leksikalske analysator og BNF til parseren
  Opgaveløsning med lærerstøtte
- Ruteplansopgave - delopgave 8a og 8b
 		  
12:30

- 14:00

 Opgaveløsning uden lærerstøtte
- Ruteplansopgave - delopgave 8a og 8b 		  
Fredag   dagen efter Kr. himmelfart - ingen undervisning  
 
Afleveringsopgaver (obligatoriske) denne uge: Ruteplansopgave - parser - delopgave 8a

Oplæg til bredere obligatorisk opgave i sproglære og grafer - opgaven vil blive opdelt i delopgaver over de næste uger, så der til sidst gerne skulle kunne ses en samlet løsning.

delopgave 8a) Der skal nu laves en Parser, der som input kan tage en samling "færdige" tokens og opbygge en regionskøreplan svarende til tidligere definerede struktur (EBNF_Ruteplan_Datamodel_for_Regionskoereplan.ppt)
- du kan evt. vælge at bruge denne model, hvis du har problemer med at definere din egen (EBNF_Ruteplan_Model_Syntakstræ_Projekt.zip)
Du kan tage udgangspunkt i ét af følgende eksempler:
- eksempel på recursive decent parser
- eksempel på parser baseret på startepattern

delopgave 8b) Der skal laves en Parser analysator med brug af Lex/Flex værktøjet - du tilretter medlemsliste syntaksen til ruteplanssyntaksen
Du kan tage udgangspunkt i følgende eksempel
- Lekikalsk analyse og parsing med brug af værktøj (LALR(1) - Flex+Bisson)  eller hvis du vil prøve den mere avancerede hvor der opbygges model direkte i forbindelse med parsingen  CsLexParserSolutionMedlemsliste_Model.zip

delopgave 9) Delene du tidligere har programmeret skal nu sammenkobles, så der kommer en samlet løsning på ruteplansopgaven - scanner+parser til ruteplan-model og fra ruteplan-model til graf med løsning af graf-opgaver.