Programmeermethoden 2009
Tweede programmeeropgave
42-compiler
De tweede programmeeropgave van het vak
Programmeermethoden
in het najaar van 2009
heet 42-compiler;
zie ook het
vierde werkcollege,
vijfde werkcollege
(de betreffende WWW-bladzijde bevat handige
tips evenals enkele testfiles — te zijner tijd!)
en
zesde werkcollege,
en lees geregeld deze pagina op WWW.
Spreekuur in zalen 302 ... 309:
dinsdag 29, woensdag 30 september, donderdag 1, dinsdag 6, woensdag 7, donderdag 8
en vrijdag 9 oktober 2009, van circa
15.30 tot 17.00 uur.
De bedoeling is om een compiler te schrijven die
programma's in de programmeertaal 42 compileert.
Eigenlijk is het zelfs een interpreter, want
de waardes van de "expresssies"
uit het programma wordt ter plekke uitgerekend.
Dit is eigenlijk een veredelde rekenmachine.
We doen helaas maar een paar aspecten van het hele proces ...
Lees de opgave goed, het lijkt misschien nogal ingewikkeld.
De opgave
Programma's in 42 bestaan uit allerlei symbolen, maar
eigenlijk zijn alleen de cijfers en operatoren als +
(in de vorm van een drielettercode als PLU)
van belang voor de werking.
Een 42-programma rekent de waarde uit van de "expressies"
die in het programma voorkomen. Wat is een expressie?
Hiertoe wordt allereerst een getal gedefinieerd
als een direct aaneengesloten serie cijfers. Een term
is een serie getallen gescheiden door de operatoren
MUL en DIV,
voor vermenigvuldigen en delen;
een enkel getal is ook een term. Een expressie is een serie termen gescheiden
door de operatoren PLU en MIN, voor optellen
en aftrekken; een enkele term (en dus ook een enkel getal)
is ook een expressie.
Helaas (?) staan tussen de getallen en operatoren allerlei
andere symbolen.
Een voorbeeld:
100abc PLUdef gh 3MULkl(mn4 MINop5q)rMULs6t
staat voor 100+3*4-5*6 = 100+12-30 = 82.
Het programma moet de invoerfile
helemaal doorlezen, en de waardes van de voorkomende expressies opleveren.
Tegelijkertijd moeten de expressies, één per regel,
netjes op het scherm worden afgedrukt
(in het voorbeeld als 100+3*4-5*6; eindresultaat 82).
Verder moeten in een uitvoerfile alle karakters uit de tekst
die niet voor de expressies gebruikt zijn netjes worden afgedrukt,
inclusief de regelovergangen. Uit de voorbeeldregel:
abc def gh kl(mn opq)rst
We maken de volgende afspraken:
- Een expressie staat op één regel.
Tussen elk tweetal opeenvolgende getallen van een expressie
staat precies één
operator uit PLU, MIN, MUL en DIV.
Als (zodra) er een cijfer op een regel staat, staat er
precies één geldige expressie
op die regel.
Voor het eerste en na het laatste getal van een expressie staat geen operator.
Sommige regels bevatten geen expressie.
-
De operatoren vermenigvuldigen en delen (MUL en DIV)
worden van links naar rechts afgewerkt, en hebben hogere prioriteit
dan optellen en aftrekken (PLU en MIN).
Ook deze worden van links naar rechts afgewerkt.
-
Als ergens in een expressie door 0 gedeeld wordt,
moet het eindresultaat van de gehele expressie 0 worden.
Daarnaast moet de mededeling 0-deling worden afgedrukt.
-
Neem aan dat de afzonderlijke getallen en alle (tussen)resultaten
niet te groot of te klein zijn.
Wel tussentijds steeds breuken vereenvoudigen, svp.
-
De gebruiker kan kiezen of de berekeningen als breuk (met
een teller en een noemer) plaats hebben, of als geheel getal.
In dat laatste geval wordt een deling uitgevoerd zoals gebruikelijk is
bij gehele getallen in C++.
In het geval van breuken: deze worden steeds zoveel mogelijk
vereenvoudigd. Ze moeten worden afgedrukt als (bijvoorbeeld) 3/4.
Zo wordt 18/4 afgedrukt als 9/2.
En een breuk als 7/1 moet als 7 worden afgedrukt.
Aan de gebruiker wordt gevraagd
hoe de invoerfile en de uitvoerfile heten,
en op welke regels de speciale acties
moeten beginnen en eindigen.
De gebruiker geeft daartoe twee getallen op, zeg a
en b,
het eerste minstens 1, het tweede minstens het eerste.
De regels a tot en met b worden nu
"behandeld".
Buiten de hierdoor aangegeven grenzen moet er verder niets worden gedaan,
en niets naar de uitvoerfile
worden geschreven.
Let erop dat het ook goed moet werken als a en/of b
groter is dan het aantal regels van de file.
Stel eenvoudige vragen om gegevens, zoals filenamen, van de gebruiker te
weten te komen.
Het programma leest dan eenmalig de opgegeven invoerfile,
en schrijft de uitvoer symbool voor symbool weg naar de uitvoerfile.
Tevens beeldt het de expressies netjes op
het beeldscherm af, en berekent het de eindwaardes van de expressies.
Elk symbool uit de invoerfile mag en moet maximaal
één maal (met invoer.get (...)) gelezen worden.
Na afloop moeten enkele eenvoudige "statistieken"
op het beeldscherm afgedrukt worden,
namelijk
het totaal aantal ingelezen karakters uit de invoerfile
(inclusief regelovergangen, spaties en dergelijke),
het aantal uitgevoerde karakters naar de uitvoerfile
en het aantal expressies.
Het aantal ingelezen karakters kan wat schelen tussen verschillende interpretaties!
Opmerkingen
-
We nemen aan dat de gebruiker zo vriendelijk is verder geen
fouten te maken bij het invoeren van gegevens.
De invoerfiles mogen maar één maal gelezen worden.
-
Gebruik de regelstructuur: elke regelovergang in een bestand bestaat
uit een LineFeed
(\n) (in UNIX) of een CarriageReturn gevolgd door een LineFeed
(\r\n) (in DOS/Windows).
Normaal gesproken gaat dit "vanzelf" goed.
We nemen aan dat er voor het EndOfFile-symbool (wat dat ook moge zijn)
een regelovergang staat.
-
Alleen voor de namen van de files
mag een array (of string) gebruikt worden;
voor het lezen
en verwerken van de tekst is slechts het huidige karakter en enige
kennis over enkele vorige nodig.
Alleen de headerfiles iostream en fstream
mogen gebruikt worden (en string
voor de filenamen; denk in dat geval aan het gebruik
van c_str).
Uit een file mag alleen met invoer.get (...) gelezen
worden, vergelijk Hoofdstuk 3.7 uit het dictaat,
gedeelte "aantekeningen bij de hoorcolleges".
Binnen de hoofdloop van het programma staat bij voorkeur maar
één keer een get-opdracht,
vergelijk het voorbeeldprogramma uit dit hoofdstuk
(daar staat twee keer get, één maal
vóór de loop).
Karakters mogen niet worden teruggezet in de
oorspronkelijke file.
-
Denk aan het infoblokje dat aan begin
op het scherm verschijnt. Gebruik enkele geschikte functies,
bijvoorbeeld voor de grootste gemeenschappelijke deler,
voor het vereenvoudigen van een breuk,
voor het verwerken van de berekening
(zie de tips bij het vijfde werkcollege),
en om een file te bewerken.
Globale variabelen zijn verboden.
Ruwe indicatie voor de lengte van het C++-programma: circa 250 regels.
Uiterste inleverdatum: vrijdag 9 oktober 2009, 17.00 uur.
Manier van inleveren:
- Digitaal de C++-code
inleveren: stuur een email naar
pm@liacs.nl.
Stuur geen executable's,
lever alleen de C++-file digitaal in! Noem deze bij voorkeur zoiets als
balkkok2.cc, dit voor de tweede opdracht van het duo Balk-Kok.
De laatst voor de deadline ingeleverde versie wordt nagekeken.
- En ook een papieren versie van het verslag
(inclusief de C++-code) deponeren
in de speciaal daarvoor bestemde doos "Programmeermethoden" in de postkamer
van Informatica, kamer 156 van het Snellius-gebouw.
Overal duidelijk datum en namen van de (maximaal twee) makers vermelden,
in het bijzonder als commentaar in de eerste regels van de C++-code.
Lees bij het
zesde werkcollege hoe het verslag
eruit moet zien.
Te gebruiken compiler: als hij maar C++ vertaalt;
het programma moet in principe zowel op een Linux-machine
(met g++) als onder Visual C++ of DevC++ draaien.
Test dus in principe op beide systemen!
Normering: layout 2; commentaar 2;
overzichtelijkheid/modulariteit 2;
werking 4.
Eventuele aanvullingen en verbeteringen: lees deze WWW-bladzijde.
Vragen en/of opmerkingen kunnen worden gestuurd
naar: kosters@liacs.nl.
16 september 2009 — http://www.liacs.nl/home/kosters/pm/op2pm09.html