DM1302DK - 3. semester

Ugeplan for Softwarearkitektur og Distribuerede Programmer


Tema: Træer og Grafer (datastrukturer og algoritmer) samt sprogteori
- Gå til uge: 46, 47, 48, 49, 50, 51,
- Gå til tidligere uger: 34-38  (socket og tråd), 46-51 (Webservice (WCF) og Web programmer)

Sidst ændret: 2014.12.02

 

Uge 46
Dag Tidspunkt Emne Materialer
Tirsdag 08:30 - Vi tager fat på nyt tema med datastrukturer og algoritmer,
hvor hoved temaet vil være træer og grafer.

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

Du forventes at have forberedt dig godt jvf. vejledningen i dybden ---------->


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å (flere af dem skal vi flittigt bruge i forbindelse med algoritmer på træer og grafer):
- Array og Lister baseret på Array (C# List)
- Linkede lister
- Hashtabeller
- Stack
- Queue

Binære træer

 		 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

Graf-kurver for funktioner (kompleksitet): (NY!! - manglede på ugeplanen)
 - BigO_Complexity.pdf

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  

 
10:30 - 12:00 Grupperne, der har arbejdet projekter for Leisner, præsenterer løsningerne for Sune Leisner, Bjørk og hinanden

FynBus grupperne løser opgaver uden støtte fra underviser i loungen?
Opgaver med binære træer ( løs opgave BT01,BT02,BT03 og BT04 - laves inden onsdag)
Opgaverne løses manuelt "på papir"
Diskuter løsningerne og prøv herefter at kontrollere fremgangsmåde og resultatet med programmet Visualisering af Binær træ
 
12:30- 14:00 Opgaveløsning uden støtte fra underviser
Opgaver med binære træer ( løs opgave BT01,BT02,BT03 og BT04 - laves inden onsdag)
Opgaverne løses manuelt "på papir"
Diskuter løsningerne og prøv herefter at kontrollere fremgangsmåde og resultatet med programmet Visualisering af Binær træ
 

Onsdag 08:30 -

Opsamling på datastrukturer og algoritmer på Array, Lister, Linkede Lister, Hashtabeller, Stack og Queue

Opsamling på opgaverne BT01,BT02,BT03 og BT04 - diskussion af hvad der kan udledes

Binære søgetræer fortsat.
- datastrukturen - implementering i C#
- indsættelse, sletning, søgning
- traversering - herunder vil vi se på recursion, brug af queue og stack til løsning.
- generalisering af løsninger med brug af  interrfaces og delegater, herunder visitor pattern
  (vi vil her også se på dette i forhold til List og sortering - da det dels er illustrativ på forskellige løsninger og dels er nyttigt)
- generalisering med brug at template  

  

Video fra tidligere forløb om datastruktur, indsættelse og traversering af binær træ

Lidt om visitor pattern - fokuser på formålet / ideen - vi laver en meget enklere implementering i C# på det binære træ.
http://en.wikipedia.org/wiki/Visitor_pattern

Suplement:
- C# eksempel på dele af binært søgetræ med vistor pattern
- 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)
Om generisk template (fra tirsdagen):
-Generiske datastrukturer (template baserede) - her en dårlig stak 173_StackTemplate  

Gennemgang af datastruktur, indsættelse og traversering af binær træ fra tidligere forløb. Video  
 
   
12:30- 14:00 Opgaveløsning uden støtte fra underviser
Opgaver med binære træer ( løs opgave BT05)
 
Torsdag 08:30 - Binære søgetræer fortsat - opsamling og det vi evt. ikke nåede onsdag
En del tid vil blive brugt på opgaveløsning, hvor man kan få hjælp
 		 se onsdag
   
12:30- 14:00 Opgaveløsning uden støtte fra underviser
 
Afleveringsopgaver denne uge: opgave BT05 - (BT01-04 skal laves til onsdag, men ikke afleveres)
 
 

 

Uge 47
Dag Tidspunkt Emne Materialer
Tirsdag 08:30 -

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 
  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 (manuelt med hånden på papir), der svarer til ruteplanen. Når du får lavet et grafprogram, kan du bruge ruteplan-grafen som testdata.
 
10:20 - Opsamling på køreplansopgave - delopgave 1)
 		 Gennemgang af datastrukturen graf ift. implementering   se evt. video igen i forbindelse med opgaveløsningen.
 
12:30- 14:00

Opgaveløsning uden lærerstøtte
Delopgave 2a: (datastruktur, metoder til at indsætte elementer, udskrift for test...), se under afleveringsopgaver denne uge
 
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. Grafalgoritmer Define og Bredde først - C# med matrix  

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     
10:30-12:30 Grupperne, der har arbejdet projekter for FynBus, præsenterer løsningerne for Michael Dydensborg, Bjørk og hinanden.
Dette foregår hos FynBus (Tolderlundsvej 9, 5100 Odense C)

Leisner grupperne løser opgaver uden støtte fra underviser
 
12:30- 14:00

Opgaveløsning uden lærerstøtte

Delopgave 2b: metode for bredde-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

 

 Se evt. Grafalgoritmer Define og Bredde først - C# med matrix  
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.
 
Torsdag 08:30 - Opsamling og opgaveløsning med støtte  
 

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 
12:30- 14:00 Opgaveløsning uden støtte fra underviser (se oven for)
 
Afleveringsopgaver denne uge: Ruteplansopgave - frem til delopgave 2b - Bredde først traversering
NB: Bemærk krav om deltagelsespligter i  overordnet semesterplan - 2 afleveringer inden for emnet grafer og sprogteori - for at kunne gå til eksamen
Oplæg til bredere 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 48
Dag Tidspunkt Emne Materialer
Tirsdag 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 se video før undervisningen
Prims algoritme: applet for simulering af algoritme 

Kruskals algoritme på graf - minimum spanning tree se video før undervisningen
Kruskals algoritme: applet for simulering af algoritme

 
  Opgaveløsning med lærerstøtte - se sidst i ugens plan
 		 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 - se sidst i ugens plan
 
 
Onsdag 08:30 - Graf algoritmer, opsamling til nu

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    
  Opgaveløsning med lærerstøtte - se sidst i ugens plan
 		 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 - se sidst i ugens plan
 
Torsdag 08:30 - Graf algoritmer, opsamling og afrunding

Fra domain-model med data til graf
- vi ser på en mulig domain model, der svarer data fra input til ruteplanen og hvordan man ud fra den kan danne en graf.

Vi skal senere bruge denne model - da vi i næste runde skal kunne lave indlæsning ud fra sprog regler og compiler-principper og ende med at få et abstrakt syntakstræ (hvor det konkret så er vores domain model vi ender med at få dannet).
Du skal altså ikke nu tænke på at få data fra en fil, men blot "hardcode" data i en test-domain-model, som der så kan bruges til at lave grafen ud fra.
 

 - mulig model (EBNF_Ruteplan_Datamodel_for_Regionskoereplan.ppt) 
  Opgaveløsning med lærerstøtte - se sidst i ugens plan
 
12:30- 14:00 Opgaveløsning uden lærerstøtte - se sidst i ugens plan
 
Afleveringsopgaver denne uge: Ruteplansopgave - frem til delopgave 2c - Minimum spanning tree
NB: Bemærk krav om deltagelsespligter i  overordnet semesterplan - 2 afleveringer inden for emnet grafer og sprogteori - for at kunne gå til eksamen
Oplæg til bredere 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)
 - 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. 
 

 

Uge 49
Dag Tidspunkt Emne Materialer
Tirsdag 08:30 - Introduktion til sprogteori
- Grammatikker og sprog
- Compiler
- regulære udtryk
- BNF + EBNF

 

 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

 
  En lille smule om Assembler (symbolsk maskinsprog), maskinsprog og afvikling på cpu

Vi kommer her også ind på faserne i en oversættelse (illustreret ved manuelle løsninger)

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. 
  Opgaver med EBNF (løs opgave 1-5)
Ruteplansopgave - delopgave 3, 5 og 6 


Tokenklasse for medlemsliste syntaksen
12:30- 14:00 Opgaver med EBNF (løs opgave 1-5)
Ruteplansopgave - delopgave 3, 5 og 6


  
Onsdag 08:30 - Sproglære fortsat

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)

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
  Opgaveløsning med lærerstøtte - ruteplanopgaver - se sidst i ugens plan
 
12:30- 14:00 Opgaveløsning uden lærerstøtte - ruteplanopgaver - se sidst i ugens plan
 
Torsdag 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
- eksempel på scanner / leksikalsk analyse baseret på statepattern
 Om state pattern: http://en.wikipedia.org/wiki/State_pattern

   
12:30- 14:00 Opgaveløsning uden lærerstøtte - ruteplanopgaver - se sidst i ugens plan
 
Afleveringsopgaver denne uge: ingen, bemærk at der allerede er næste tirsdag (Ruteplansopgave - leksikalsk analyse / scanner: delopgave 5, 6 og 7a)
NB: Bemærk krav om deltagelsespligter i  overordnet semesterplan - 2 afleveringer inden for emnet grafer og sprogteori - for at kunne gå til eksamen
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

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 

Supplerende / alternativ litteratur for de der måtte ønske at anskaffet sig dette - primært kap. 1 og 4.
#comp: Programming Language Processors In Java - compilers and interpreters, David A Watt & Derick F Brown, Printice Hall, ISBN: 0-130-25786-9

 

Uge 50
Dag Tidspunkt Emne Materialer
Tirsdag 08:30 - 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
- 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 
  Opgaveløsning med lærerstøtte - ruteplanopgaver - se sidst i ugens plan
 
12:30- 14:00 Opgaveløsning unden lærerstøtte - ruteplanopgaver - se sidst i ugens plan
 
13:30-15:00 FynBus fremlæggelser - runde 2 - tirsdag den 9. december kl. 13:30-15:00
hos FynBus
 
Onsdag 08:30 - Introduktion til parseren

 

 



 

Se følgende videoer som forberedelse før undervisningen

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) 
  Opgaveløsning med lærerstøtte - ruteplanopgaver - se sidst i ugens plan
 
12:30- 14:00

Opgaveløsning uden lærerstøtte
- Ruteplansopgave - delopgave 7a og 7b
 
Torsdag 08:30 -

Sprogteori / parser - opsamling på onsdagen

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  
   
12:30- 14:00 Opgaveløsning uden støtte fra underviser
 
Afleveringsopgaver tirsdag denne uge: Ruteplansopgave - leksikalsk analyse / scanner: delopgave 5, 6 og 7a
NB: Bemærk krav om deltagelsespligter i  overordnet semesterplan - 2 afleveringer inden for emnet grafer og sprogteori - for at kunne gå til eksamen

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 - 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

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 


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.  
 

 

Uge 51
Dag Tidspunkt Emne Materialer
Tirsdag 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)    
  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 unden lærerstøtte
- Ruteplansopgave - delopgave 8a og 8b
 
Onsdag 08:30 - Sprogteori  - opsamling - løsning af opgaven  
  Opsamling / repetition af semesterets pensum og opgaver
 
12:30- 14:00 Opgaveløsning uden støtte fra underviser
 
Torsdag 08:30 - Opsamling / repetition af semesterets pensum og opgaver
 		  
   
12:30- 14:00 Opgaveløsning uden støtte fra underviser
 
Afleveringsopgaver tirsdag denne uge: Ruteplansopgave - parser - delopgave 8a
NB: Bemærk krav om deltagelsespligter i  overordnet semesterplan - 2 afleveringer inden for emnet grafer og sprogteori - for at kunne gå til eksamen

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.