Supplerende opgaver til Modul 2, RUC, Logik og sprog, forår 2000

Opgave 1

Diskutér og formulér nogle forslag til definitioner af følgende begreber:

oversætter	udsagn
fortolker	bevis
virtuel maskine	database
formelt sprog	databasesystem
operativsystem	forespørgsel
kommandofortolker	svar

Tanken er her, at I skal danne nogle grupper og heri vende og dreje mulige definitioner. Det er ikke meningen at I skal bruge en masse tid på litteratursøgning!

Opgave 2

K.N.Ips er en ihærdig amatørfotograf, som overvejer at gå over til digitale medier, men han er indædt modstander af at komprimere billeder vha. diverse kendte komprimeringsalgoritmer. Han mener, at det informationstab, som finder sted vil være dybt destruktiv for hans kunstneriske værker. Ips har tænkt sig at opbevare sine billeder på CD-ROM og han overvejer at indkøbe en ROM-brænder. Som inputmedium tænker han sig at scanne sine gode gammeldags 24x36 negativer vha. en fotoscanner. Han han netop set en Minolta Dîmage scanner på udsalg og skal lige regne lidt på, om det nu er noget for ham. Kan du hjælpe ham med at finde ud af følgende:

hvor mange billeder kan han lagre i fuld opløsning på en CD-ROM?
hvis han køber en CD-ROM brænder til omkring 4000kr, hvor lang tid tager det at få lagret ét billede.
Er der en fornuftig sammenhæng mellem den opløsning, han tænker sig at benytte, og det han kan skrive ud på en god farveprinter, han regner med at finde på et godt tilbud til ca. 3000kr?

De nødvendige oplysningerne kan findes i Tanenbaums bog og ved søgning på www.

Opgave 3

Eksamensopgave fra sommer 98 (15% af 4 timer)
Opgaven handler om tilstandsmaskiner anvendt til strengsøgning og kan besvares på baggrund af Sprog og abstrakte maskiner kapitel 12. Vi benytter et alfabet bestående af de to bogstaver a, og b, og opgaven lyder i al sin enkelhed: Tegn en deterministisk tilstandsmaskine, som accepterer netop de strenge, hvori delstrengen »abba« indgår, jvf. principperne beskrevet i afsnit 12.4 i Sprog og abstrakte maskiner.

Opgave 4

Eksamensopgave fra vinter 96/97 (20% af 4 timer)
Denne opgave handler om syntaks og syntaksgenkendelse og knytter sig til Sprog og abstrakte maskiner, kapitel 13. Vi forestiller os, at programmør Nørd Nørdsen forsøger sig som sprogdesigner, hvor han ønsker at opnå en syntaks, som gør det nemt at indtaste sit program. For eksempel, så ønsker han at skulle skrive semikolon efter hver eneste simpel sætning, og 'begin'-'end' skrives med parenteser. Samtidig ønsker han at have 'if-then' sætninger med og uden 'else' og dertil 'if-then-else' udtryk, som de f.eks. kendes fra Simula. Nu kommer det store spørgsmål, om disse krav kan forenes i en grammatik, som kan forenes med den parsemetode, som Nørd har tænkt sig at benytte, nemlig den rekursivt nedstigende. Som et eksperiment har han udarbejdet følgende grammatik, hvor, som vi kan se, udtryk er meget forenklede, og der, hvor vi vil forvente logiske betingelser, bruges der blot almindelige udtryk.

Grammatikkens nonterminaler er 'program', 'sætning', 'Ssætning' (for simpel sætning), 'udtryk', 'Sudtryk' (for simpelt udtryk), 'variabel' og 'tal'. Terminalsymboler er følgende {'.', '1', '+', 'if', 'then', 'else', ':=', '*', '(', ')'}.

NYT Spørgsmål 0: indtegn kasser og pile i nedenstående tegning:

program

             sætning               .


sætning

                    Ssætning

        if    udtryk    then    Ssætning

                                               else    Ssætning



Ssætning

        variabel        :=       udtryk

        (    sætning    )




udtryk

                               Sudtryk

        if     udtryk  then    Sudtryk    else    Sudtryk

                                 +


Sudtryk

                              variabel

                                 tal

                         (     udtryk      )


variabel

                                 X

Opgave 5

Eksamensopgave fra sommer 1999 (15% af 4 timer)
I denne opgave betragtes den simple heltals Java maskine (IJVM), som Mic-1 microprogrammet i Tanenbaum implementerer.

Antag at vi har følgende programstump i Java:

   j=3; k=4; r=1;
   for (i=0; i<j; i++)
      r = r+k;
   r = r-2;

Der er flere måder at oversætte dette til IJMV. Man kunne vælge at anvende variablene direkte:

    BIPUSH 3
    ISTORE j    // j=3;
    BIPUSH 4
    ISTORE k    // k=4;
    BIPUSH 1
    ISTORE r    // r=1;
    BIPUSH 0
    ISTORE i    // i=0;
L1: ILOAD i
    ILOAD j
    ISUB
    IFLT L2     // if ( (i-j) < 0 )
    GOTO L3
L2: ILOAD r
    ILOAD k
    IADD
    ISTORE r    // r=r+k;
    ILOAD i
    BIPUSH 1
    IADD
    ISTORE i    // i=i+1;
    GOTO L1
L3: ILOAD r
    BIPUSH 2
    ISUB
    ISTORE r    // r=r-2;

Spørgsmål 1

Hvor mange gange udføres ILOAD og ISTORE under udførslen af det ovenstående assemblerprogram?

Spørgsmål 1

I Java har man af og til behov for at fjerne to værdier fra stakken. Umiddelbart kan det løses ved at kalde POP to gange, men derved skal der læses i lageret to gange (for at opdatere TOS). Udvid Mic-1 med en instruktion POP2, der fjerner de to øverste værdier fra stakken, men kun opdaterer TOS en enkelt gang.

Hvor mange mikroinstruktioner (cykler) spares ved at udføre POP2 i stedet for POP to gange?

Opgave 6

Eksamensopgave fra vinter 1999/2000 (15% af 4 timer)
I denne opgave betragtes den simple heltals Java maskine (IJVM), som Mic-1 microprogrammet i Tannenbaum implementerer.

Antag at vi har følgende programstump i Java:

   j=4; k=3; r=1;
   for (i=0; i<j; i++)
     r = r+k;
   r = r-2;

Der er flere måder at oversætte dette til IJMV, for eksempel ved at oprette variable, og gemme alle mellemresultater ved brug af ISTORE, eller ved at anvende stakken til at opbevare alle mellemberegninger.

I det følgende antages at en oversætter ved oversættelse af programstumpen producerer følgende IJVM kode:

    BIPUSH 4
    ISTORE j // j=4;
    BIPUSH 3
    ISTORE k // k=3;
    BIPUSH 1 // r=1;
    BIPUSH 0 // i=0;
L1: DUP
    ILOAD j
    ISUB<
    IFLT L2  // if ( (i-j) < 0 )
    POP
    BIPUSH 2
    ISUB     // r=r-2;
    GOTO L3
L2: SWAP
    ILOAD k
    IADD
    SWAP     // r=r+k;
    BIPUSH 1
    IADD     // i=i+1;
    GOTO L1
L3: ISTORE r

Spørgsmål 1

Vil en udførsel af denne kodestump resultere i det samme resultat, som man ville forvente af en udførsel af Java programstumpen?

Svaret skal begrundes, eventuelt ved at redegøre for hvilke værdier de fire variable i, j, k og r har efter udførelsen i de to tilfælde.

Hvis der er forskel, hvilken betydning har en sådan så?

Spørgsmål 2

Udvid Mic-1 microprogrammet med operationen "INEG", der negerer værdien øverst på stakken.

Eksempel:

Hvis stakken til at begynde med indeholder:

[4 2 ...]

vil stakken efter udførsel af INEG indeholde:

[-4 2 ...]