Tlmočník 5

Nový tlmočník spracováva štruktúry namiesto inštrukcií. Každá štruktúra začína číslom, ktoré určuje jej typ. Typ štruktúry určí ako ju tlmočník interpretuje.

Dátové štruktúry

Existuje niekoľko základných typov štruktúr. Typ 1 predstavuje pole čísiel. Druhý základný typ, typ 2 je pole indexov (smerníkov). Šablóna oboch štruktúr je v tabuľke 1.

Tabuľka 1 Šablóna štruktúr typu 1 a typu 2. Ak typ je 1, tak ide o pole čísiel. Ak typ je 2, tak ide o pole indexov.
pozícia	0	1	…	…
pole	typ	dĺžka	hodnoty	0

Pole typ je buď 1 alebo 2. Pole dĺžka určuje počet hodnôt (čísiel alebo smerníkov).

Napríklad nasledujúca štruktúra

1 2 1 1 0

reprezentuje pole [1, 1], alebo pár (1, 1). Nasledujúca štruktúra reprezentuje dvojicu dvojíc

2 2       // Dva smerníky
 5 6      // na indexe 5 a 10
0
1 2 1 1 0 // 5: prvý pár (1, 1)
1 2 3 2 0 // 10: druhý par (3, 2)

Typ 1 slúži na uchovávanie dát. Typ 2 slúži na kompozíciu dát. Ak tlmočník narazí na takéto štruktúry v pamäti, tak ich preskočí (neinterpretuje), pretože reprezentujú dáta a nie vykonateľný program.

Zo súboru definície.h, ktorého obsah je na obrázku 1, som odstránil niekoľko definícií. Napríklad veľkosť blokov, pretože koncept blokov v tejto verzii tlmočníka už nevyužívam.

Program 1 Súbor definície.h obsahuje definície niekoľkých konštánt.

/* V tomto súbore sú definované
   konštanty. */
#ifndef _DEFINÍCIE_H
#define _DEFINÍCIE_H

#define ZÁKLADNÝ_TYP int64_t
#define ZT ZÁKLADNÝ_TYP

#define VEĽKOSŤ_PAMÄTE 1000
#define VP VEĽKOSŤ_PAMÄTE
#endif

Obsah súboru rozpoznanie.h sa nezmení. Tieto funkcie využívam aj v novej verzii tlmočníka. Obsah súboru je na obrázkoch 2.

Program 2 Obsah súboru rozpoznanie.h. Obsahuje funkcie na rozpoznanie celých čísiel.

#ifndef _ROZPOZNANIE_H_
#define _ROZPOZNANIE_H_
/* V tomto súbore sú funkcie na
   rozpoznávanie zadaných znakov
   a blokov. */
#include "definície.h"

ZT načítaj_kladné_číslo(){
  // Kladné číslo je konečná
  // postupnost číslic.
  ZT číslo = 0;
  // Max 18 číslic.
  for (ZT i = 0;
       i < 18; ++i) {
    int c = getchar() - '0';
    if (c > -1 && c < 10) {
      číslo *= 10;
      číslo += c;
    } else {
      break;
    }
  }
  return číslo;
} // súbor pokračuje

Na obrázku 3 je zostatok súboru rozpoznanie.h. Táto časť súboru obsahuje funkciu na načítanie celých čísiel.

Program 3 Druhá časť súboru rozpoznanie.h.

ZT načítaj_číslo() {
  // Pozri prvý znak. Ak je to '-',
  // tak ide o záporné číslo.
  int c = getchar();
  ZT číslo = 0;
  if (c == '-') {
    číslo = načítaj_kladné_číslo();
    číslo = -číslo;
  } else {
    ungetc(c, stdin);
    číslo = načítaj_kladné_číslo();
  }
  return číslo;
}
#endif

Tlmočník preskočí dátové štruktúry (typu 1 a 2). Po vykonaní operácie skočí na ďalšiu operáciu. Súbor preskoč.h obsahuje funkcie, ktoré vykonajú dané skoky. Tento súbor je na obrázku 4.

Program 4 Obsah súboru preskoč.h.

#ifndef _PRESKOČ_H_
#define _PRESKOČ_H_
#include "definície.h"
extern ZT pamäť[VP]; // Pamäť.
extern ZT pp; // Počítadlo programu.
void preskoč_štruktúru(){
  // Tlmočník je na prvom elemente, teda type
  // štruktúry.
  // Druhý element štruktúry je jeho dĺžka n.
  // Potom je n čísiel.
  // Na konci štruktúry je ešte 0, takže
  // celkový pp je nutné inkrementovať o
  // n + 3.
  pp += pamäť[pp+1] + 3;
}
void preskoč_operáciu(){
  // Tlmočník je na prvom elemente, teda na type
  // operácie. Za typom nasleduje index argumentovej štruktúry
  // a potom 0. Volanie operácie zaberá 3 miesta v
  // pamati, takže je pp navýšiť o 3.
  pp += 3;
}
#endif

Operácie

Každá operácia má práve jeden argument, pole smerníkov. Toto pole obsahuje smerníky na argumenty funkcie. Všetky operácie vyzerajú v pamäti ako šablóna v tabuľke 2.

Tabuľka 2 Šablóna operácií. Každá operácia spracuje jeden argument, pole smerníkov.
pozícia:	0	1	2
pole:	typ	štruktúra (argument)	koniec:0

Typ operácie určuje operáciu. Napríklad operácia typu 4 vypisuje hodnoty do konzoly a operácia typu 10 vykoná podmienený skok.

Prvá operácia (typu 3) je operácia načítaj_pamäťovú_oblasť, ktorá načíta na vybrané pamäťové miesto dáta zo štandardného vstupu (konzoly). Jej argumenty sú opísané v tabuľke 3.

Tabuľka 3 Štruktúra argumentov inštrukcie `načítaj_pamäťovú_oblasť`.
pozícia:	0	1	2
pole:	počet	prvá adresa	nové pp

Pole počet určuje koľko čísiel sa má do pamäte načítať zo štandardného vstupu. Hodnota prvá adresa je adresa, na ktorú je načítané prvé číslo. Ďalšie načítané čísla sa zaradia za to prvé vtom poradí, v ktorom boli načítané. Pole nové pp určuje hodnotu počítadla programu po načítaní čísiel. Teda určuje kde začne tlmočník vykonávať inštrukcie.

Napríklad program

3 3 0 // 0: Volanie načítaj_pamäťovú_oblasť
      // argumenty sú na indexe 3.
2 3 9 12 15 0 // 3: 3 smerníky
1 1 10 0 // 9: hodnota 10
1 1 0 0 // 12: hodnota 0
1 1 0 0 // 15: hodnota 0

načíta 10 čísiel na pozície 0 1 2 … 9 a po načítaní nastaví počítadlo programu na 0.

Implementácia operácie načítaj_pamäťovú_oblasť je v súbore načítaj.h a je zobrazená na obrázku 5.

Program 5 Obsah súboru načítaj.h, ktorý obsahuje implementáciu operácie načítaj_pamäťovú_oblasť.

#ifndef _NAČÍTAJ_H
#define _NAČÍTAJ_H
#include "definície.h"
#include "rozpoznanie.h"
#include "zjedz.h"

extern ZT pamäť[VP]; // Pamäť.
extern ZT pp; // Počítadlo programu.

void načítaj_pamäťovú_oblasť() {
  ZT smerníky = pamäť[pp + 1];
  ZT počet_argumentov = pamäť[smerníky + 1];
  ZT počet_pole = pamäť[smerníky + 2]; // Prvý smerník.
  ZT počet = pamäť[počet_pole + 2];
  ZT prvá_adresa_pole = pamäť[smerníky + 3]; // Druhý smerník.
  ZT prvá_adresa = pamäť[prvá_adresa_pole + 2];
  ZT nové_pp_pole = pamäť[smerníky + 4]; // Tretí smerník.
  ZT nové_pp = pamäť[nové_pp_pole + 2];

  // printf("smerníky %d, počet argumentov: %d, počet: %d, prvá_adresa: %d, nové_pp: %d\n",
         // smerníky, počet_argumentov, počet, prvá_adresa, nové_pp);

  // Iteratuj počet načítaných čisiel.
  pp = prvá_adresa;
  for (ZT i = 0; i < počet; ++i) {
    zjedz_po_číslo();

    // Prepíš pamäť.
    pamäť[pp] = načítaj_číslo();
    // printf("načítané číslo [%d]: %d\n", i, pamäť[pp]);
    pp++;
  }
  pp = nové_pp;
}
#endif

Nasledujúce operácie sú operácie výpisu. Vypisujú jednu hodnotu typu 1 na definovanom mieste v pamäti.

Program 6 Obsah súboru vypíš.h. Súbor obsahuje definíciu funkcie vypíš, vypíš_nr a vypíš_m.

#ifndef _VYPÍŠ_H
#define _VYPÍŠ_H
#include "definície.h"

extern ZT pamäť[VP]; // Pamäť.
extern ZT pp; // Počítadlo programu.

// Vypíš hodnotu typu 1 na mieste i.
void vypíš() {
  ZT smerníky = pamäť[pp + 1];
  ZT i_pole = pamäť[smerníky + 2];
  ZT i = pamäť[i_pole + 2];

  printf("%ld", pamäť[i]);
}

// Vypíš hodnotu typu 1 na mieste i a ukonči riadok.
void vypíš_nr() {
  ZT smerníky = pamäť[pp + 1];
  ZT i_pole = pamäť[smerníky + 2];
  ZT v = pamäť[i_pole + 2];
  // printf("vypíš_nr\n");
  // printf("smerníky: %d, i_pole: %d, i: %d\n", smerníky, i_pole, v);

  printf("%ld\n", v);
}

// Vypíš hodnotu typu 1 na mieste i s medzerou na konci.
void vypíš_m() {
  ZT smerníky = pamäť[pp + 1];
  ZT i_pole = pamäť[smerníky + 2];
  ZT i = pamäť[i_pole + 2];

  printf("%ld ", pamäť[i]);
}
#endif

Definujem aj operáciu na výpis polí čísiel a smerníkov (teda štruktúr typu 1 a 2).

Program 7 Obsah súboru vypíš-štruktúru.h. Súbor obsahuje definíciu funkcie vypíš_pole a vypíš_pole_nr.

#ifndef _VYPÍŠ_ŠTRUKTÚRU_H
#define _VYPÍŠ_ŠTRUKTÚRU_H
#include "definície.h"

extern ZT pamäť[VP]; // Pamäť.
extern ZT pp; // Počítadlo programu.

// Vypíš štruktúru na mieste i.
void vypíš_štruktúru() {
  ZT smerníky = pamäť[pp + 1];
  ZT i_pole = pamäť[smerníky + 2];
  ZT i = pamäť[i_pole + 2];

  ZT typ = pamäť[i];
  ZT počet = pamäť[i+1];

  if (typ == 1)  {
    printf("Pole ");
  } else if (typ == 2) {
    printf("Smerníky ");
  } else {
    printf("Chybný typ pri vypisovaní štruktúry.\n");
    return;
  }
  printf("[%d]: ", počet);
  for (int j=0; j<počet; ++j){
    printf("%d\n", pamäť[i+2+j]);
  }
}

// Vypíš štruktúru na mieste i a ukonči riadok.
void vypíš_štruktúru_nr() {
  vypíš_štruktúru();
  printf("\n");
}
#endif

Definujem aj inštrukcie na odpočítavanie čísiel. Operácia na vstupe očakáva index poľa smerníkov, ktoré obsahujú 3 indexy a, b, c. Ide o indexy troch číselných polí v pamäti p. Argumenty a, b a c sú indexy štruktúr typu 1. Operácia odčítania je opísaná rovnicou \( p[c+1] = p[a+1] - p[b+1], \) kde p je pamäť. Implementácia tejto operácie je na obrázku 8.

Program 8 Obsah súboru aritmetika.h. Súbor obsahuje definíciu operácie odčítania.

#ifndef _ARITMETIKA_H
#define _ARITMETIKA_H
#include "definície.h"

extern ZT pamäť[VP]; // Pamäť.
extern ZT pp; // Počítadlo programu.

// Odpočítaj dve čísla a ulož výsledok.
void odčítaj() {
  // printf("Odpočítaj.\n");
  ZT smerníky = pamäť[pp + 1];

  ZT a_pole = pamäť[smerníky + 2];
  ZT a = pamäť[a_pole + 2];

  ZT b_pole = pamäť[smerníky + 3];
  ZT b = pamäť[b_pole + 2];

  ZT c_pole = pamäť[smerníky + 4];

  // printf("smerníky: %d, a: %d, b: %d, c_pole: %d\n", smerníky, a, b, c_pole);

  pamäť[c_pole + 2] = a - b;
}
#endif

Operácia podmieneného skoku očakáva 2 argumenty. Prvým je index testovanej hodnoty a druhým je nová hodnota počítadla programu po skoku.

Program 9 Obsah súboru skoky.h. Súbor obsahuje definíciu operácie skok_ak_nula.

#ifndef _SKOKY_H
#define _SKOKY_H
#include "definície.h"

extern ZT pamäť[VP]; // Pamäť.
extern ZT pp; // Počítadlo programu.

ZT skok_ak_nula() {
  // printf("skok_ak_nula\n");
  ZT smerníky = pamäť[pp + 1];

  ZT testh_pole = pamäť[smerníky + 2];
  ZT test_hodnota = pamäť[testh_pole + 2];

  // printf("smerníky: %d, testh_pole %d, test_hodnota: %d\n", smerníky, testh_pole, test_hodnota);
  if (test_hodnota == 0) {
    ZT nové_pp_pole = pamäť[smerníky + 3];
    ZT nové_pp = pamäť[nové_pp_pole + 2];
    // printf("nové_pp: %d\n", nové_pp);
    pp = nové_pp;
    // Signalizuj hotový skok.
    return 1;
  }
  // Signalizuj nevykonaný skok.
  return 0;
}
#endif

Priradenie operácií k typom je v tabuľke

Tabuľka 4 Priradenie typov operáciám výpisu.
typ	operácia
vypíš	4
vypíš_nr	5
vypíš_m	6
vypíš_štruktúru	7
vypíš_štruktúru_nr	8
odčítaj	9
skok_ak_nula	10

Tlmočník využíva pomocné funkcie, pomocou ktorých sú nepoužité znaky vo vstupnom toku ignorované.

#ifndef ZJEDZ_H_
#define ZJEDZ_H_

/* V tomto súbore sú funkcie na
   zjedenie (zahadzovanie)
   vstupných znakov. */

ZT zjedz_biele_znaky() {
  ZT zjedené = 0;
  int c = getchar();
  while (c == ' ' || c == '\r' || c == '\n') {
    zjedené++;
    c = getchar();
  }
  ungetc(c, stdin);
  return zjedené;
}

ZT zjedz_riadok(){
  ZT zjedené = 0;
  int c = getchar();
  while (c != '\n') {
    zjedené++;
    c = getchar();
  }
  return zjedené;
}

ZT zjedz_komentár(){
  ZT zjedené = 0;
  int c = getchar();
  if (c == '/') {
    zjedené++;
    zjedz_riadok();
  } else {
    ungetc(c, stdin);
  }
  return zjedené;
}

// Táto funkcia zje všetky znaky po
// prvý znak - alebo číslicu, ktoré nie
// sú súčasťou komentáru.
void zjedz_po_číslo(){
  ZT zjedené = 1;
  while (zjedené != 0) {
    zjedené = 0;
    zjedené += zjedz_biele_znaky();
    zjedené += zjedz_komentár();
  }
}
#endif

Tlmočníka upravíme do tvaru na obrázku 10.

Program 10 Obsah súboru tlmočník5.c, ktorý obsahuje hlavnú rutinu main.

#include<stdio.h>
#include<stdint.h>
#include "rozpoznanie.h"
#include "definície.h"
#include "aritmetika.h"
#include "skoky.h"
#include "vypíš-štruktúru.h"
#include "vypíš.h"
#include "preskoč.h"
#include "načítaj.h"

// Úvodný program načíta
// druhý program zo štandardného vstupu.
ZT pamäť[VEĽKOSŤ_PAMÄTE] = {
  3, 3, 0, // 0: Volanie načítaj_pamäťovú_oblasť, argument na indexe 3
  2, 3, 9, 13, 17, 0, // 3:  3 smerníky
  1, 1, 21, 0, // 9: hodnota 18 (načítaj 18 čísiel)
  1, 1, 0, 0, // 13: hodnota 0 (na adresu 0)
  1, 1, 0, 0, // 17: hodnota 0 (nová hodnota pp je 0)
};
// Počítadlo programu.
ZT pp = 0;

ZT main() {
  int i = 0;
  while (i < 2) {
    ZT hlavička = pamäť[pp];
    switch(hlavička) {
    case 1:
    case 2:
      preskoč_štruktúru();
      break;
    case 3:
      načítaj_pamäťovú_oblasť();
      break;
    case 4:
      vypíš(); preskoč_operáciu();
      break;
    case 5:
      vypíš_nr(); preskoč_operáciu();
      break;
    case 6:
      vypíš_m(); preskoč_operáciu();
      break;
    case 7:
      vypíš_štruktúru(); preskoč_operáciu();
      break;
    case 8:
      vypíš_štruktúru_nr(); preskoč_operáciu();
      break;
    case 9:
      odčítaj(); preskoč_operáciu();
      break;
    case 10:
      if (!skok_ak_nula()) preskoč_operáciu();
      break;
    default:
      return 1;
      break;
    }
  }
}

Nový obsah programového súboru je:

// Prvá časť programu načíta druhú časť programu.

3 3 0 // 0: Volanie načítaj_pamäťovú_oblasť, argument na indexe 3
2 3 9 13 17 0 // 3:  3 smerníky

// Argumenty.
1 1 53 0 // 9: hodnota 53 (načítaj 53 čísiel, od indexu 0 po 52)
1 1 0 0 // 13: hodnota 0 (na adresu 0)
1 1 0 0 // 17: hodnota 0 (nová hodnota pp je 0)

// Inicializačný program načíta čísla potiaľto.
// Po načítaní ďalšej časti sa vynulujú indexy.

// Druhá časť programu. Vypíše číslice od 1 po 10.
1 1 0 0 // 0: 0 pre porovnanie.
1 1 10 0 // 4: počítadlo.
1 1 1 0 // 8: krok odčítania.

5 15 0 // 12: vypíš hodnotu typu 1 (počítadlo)
2 1 4 0 // 15: argumentová štruktúra výpisu

10 22 0 // 19: Ak počítadlo je 0, tak skok na koniec programu.
2 2 4 27 0 // 22: argumentová štruktúra (testovaná hodnota, nové pp)
1 1 52 0 // 27: index konca programu

9 34 0 // 31: Odpočítaj krok od počítadla.
2 3 4 8 4 0 // 34: Argumenty operácie odčítaj (a,b,c) c = a - b.
10 43 0 // 40: Skok na výpis.
2 2 0 48 0 // 43: Testovaná hodnota je 0 na miestie 0.
1 1 12 0 // 48: Adresa výpisu.

11 // 52: koniec

#+end_src Program skompilujeme pomocou skriptu na obrázku 11.

Program 11 Skript na kompilovanie tlmočníka.

#!/bin/sh
gcc tlmočník5.c -o tlmočník5

Skript nastavíme spustiteľným pomocou príkazom chmod +x skompiluj.sh. Potom kompiláciu spustíme príkazom ./skompiluj.sh.

Program spustím pomocou príkazu

cat program.txt | ./tlmočník5