DM091 - 3. semester

Ugeplan for Softwarearkitektur og Distribuerede Programmer

Tema: Sproglære - Gå til uge: 47, 48, 49

Sidst ændret: 2010.12.10

Uge 47
Dag	Tidspunkt	Emne	Litteratur / Opgaver

Mandag	08:30 - 11:50	Grafer fortsat Oplæg til datastruktur / objektmodel for ruteplanen i den stillede opgave. - modellen skal kunne indeholde informationer fra ruteplanen, men i denne del sættes den konkrete plan direkte ind i strukturen uden indlæsning og tolkning fra tekstfilen.	EBNF_Ruteplan_Datamodel_for_Regionskoereplan.ppt

	- 14:00	Opgaveløsning uden lærerstøtte
Tirsdag	08:30 - 10:00	Grafer fortsat
Tirsdag
Torsdag	08:30 - 11:50	Introduktion til sproglære - Grammatikker og sprog - Compiler - regulære udtryk - BNF + EBNF	Noter/litteratur se tidligere udleverede kopier (Hvordan virker en Compiler, Compiler design og Note om EBNF grammatik) De første 2 vil være primære for mandagen - den sidste inddrages undervejs i forløbet. Slides om Sprog og compiler Compilering_af_symbolsk_maskinsprog med brug af Symboltabel Bjarnes modelmaskine - virual floppy for Virtual PC 2007 Selve modelmaskine til dos-box med dokomentation - tilhørende eksempler 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/) 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
		Opgave med EBNF - EBNFOpgave01
	- 14:00	Fortsættelse af formiddagens emner / opgave

Afleveringsopgaver (obligatoriske) denne uge: Ruteplansopgave - frem til delopgave 4

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.
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.
delopgave 3) Der skal laves en datastruktur, der kan indeholde informationen fra den beskrevne ruteplan (oplæg/idé gennemgås denne uge)
delopgave 4) Der skal laves en rutine, der ud fra data i ruteplan-modellen kan danne grafen.

Uge 48
Dag	Tidspunkt	Emne	Litteratur / Opgaver

Mandag	08:30 - 11:50	Sproglære fortsat Scanner / Leksikalsk analyse - vi skal "bygge" første del af inputbehandlingen beskrivelse med regulære udtryk design med DFA (tilstandsdiagram med overgang og effekt) kode med brug af state-pattern (ikke nået udskudt til tirsdag	Note om EBNF grammatik og syntakstyret indlæsning (se tidligere udleverede kopier) Scanner / Leksikalsk analyse: EBNF_Syntaksstyret_Medlemsliste_bjbu (vælg LexAnalyse_.... solution - 2 forskellige løsninger på LexAnalyzer - Simpel og med State Pattern)
		Delopgave 5) og 6) færdiggøres til tirsdag morgen	Se Token klassen i TokenLibrary (se ovenfor)
	- 14:00	Opgaveløsning uden lærerstøtte
Tirsdag	08:30 - 10:00	Scanner / Leksikalsk analyse fortsat state pattern brug af Lex/Flex værktæj (C# udgave tilpasset brug med Visual Studio) (udskudt til torsdag)	Om state pattern: http://en.wikipedia.org/wiki/State_pattern 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
Tirsdag
Torsdag	08:30 - 11:50	Afrunding om scanner / leksikalsk analyse brug af Lex/Flex værktæj (C# udgave tilpasset brug med Visual Studio) (udskudt fra tirsdag) Introduktion til parseren	vedr. værktøj se tirsdag 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)
		- for dem der var færdige med scanneren blev gennemgået en regelstyret parser
	- 14:00	Parser fortsat samt opgaveløsning / opsamling på scanner / leksikalsk analyse

Afleveringsopgaver (obligatoriske) denne uge: Ruteplansopgave - frem til delopgave 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.

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

delopgave 7b) Der skal laves en Scanner / Leksikalsk analysator med brug af Lex/Flex værktøjet - du tilretter medlemsliste syntaksen til ruteplanssyntaksen

Uge 49
Dag	Tidspunkt	Emne	Litteratur / Opgaver

Mandag	08:30 - 11:50	Sproglære / parser regelstyret (recursive decent) state pattern	Parser: EBNF_Syntaksstyret_Medlemsliste_bjbu (vælg Parser solution - 2 forskellige løsninger på Parser) 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

	- 14:00	Opgaveløsning uden lærerstøtte
Tirsdag	08:30 - 10:00	Sproglære / parser parser lavet med med "yacc"/bisson" værktøj	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)
Tirsdag
Torsdag	08:30 - 11:50	Sproglære / parser parser lavet med med "yacc"/bisson" værktøj - med opbygning af medlemliste-model opsaming - Kodning helt fra starten af det centrale i scanner / leksikalske analyse til ruteplan - Kodning helt fra starten af det centrale i parser til ruteplan	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

	- 14:00	Sproglære / parser (fortsat)

Afleveringsopgaver (obligatoriske) denne uge: Ruteplansopgave - frem til delopgave 8b

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)

delopgave 8b) Der skal laves en Parser analysator med brug af Lex/Flex værktøjet - du tilretter medlemsliste syntaksen til ruteplanssyntaksen

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.