Útravaló

Nagyházi szépségverseny

• Beküldés: infoc@eet.bme.hu, NEPTUN kóddal
• Screenshot a nagyháziról (egy jellegzetes jelenetről)
• Min. 3, max. 5 soros leírás

Programozási verseny

• Boros László kezdeményezése
• Vizsgaidőszak vége felé (?)
• Nevezés egy otthon elkészített programmal
• Részletek később!

A←B m↓T T↑B

1. Írd be a számokat A-ba és B-be.
2. Nézd meg, világít-e a lámpa.
    Ha igen, ugorj a 7. pontra.
3. Nyomd meg az m↓T gombot.
4. Nyomd meg az A←B gombot.
5. Nyomd meg a T↑B gombot.
6. Ugorj a 2. pontra.
7. Kész, az eredmény A-ban.

while (b != 0) {
   t = a%b;
   a = b;
   b = t;
}

Gépeket terveztünk, amelyek adott feladatot megoldanak. Ezen gépek szöveges leírását adtuk C nyelven.

A mai órán: írjunk egy egyszerű táblázatkezelő programot!

Kihívások:

1. A képletek értelmezése.
2. A keretszhivatkozások feloldása.

Kifejezések értelmezése (parsing)

Matematikai kifejezések

• Postfix alak: 4 5 7 + *
• Prefix alak: * 4 + 5 7
• Infix alak: 4 * (5 + 7)

Ezek mind ugyanazt jelentik.

Infixes alak: 4 * (5 + 7)

Ezt összetett feladat értelmezni: zárójelek, precedenciaszabályok, …

A nyelvi elemzés (parse, parsing) „Helló világ”-ja a négy alapműveletet és a zárójeleket ismerő matematikai kifejezések értelmezése.

(3+4)*(5+6) = 3 4 + 5 6 + *

(+ 4 5 6)

4+5+6 = (+ 4 (+ 5 6))

Kezdetnek próbáljuk megfogalmazni, hogy néz ki egy egész szám:

Decimális egész szám

• Egy szám legalább egy számjegyből áll.
• Egy számjegy a '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' szimbólumok valamelyike.
• Ha a szám több számjegyű, akkor a legelső számjegy nem lehet nulla.

A fenti, szabad nyelvi leírás nehezen áttekinthető és nem formális, ami nehezíti az algoritmizálást.

Az egész szám formális leírása EBNF alakban:

szám              ::= számjegy | (számjegy_nemnulla számjegy+)
számjegy_nemnulla ::= '1'|'2'|'3'|'4'|'5'|'6'|'7'|'8'|'9'
számjegy          ::= '0'|számjegy_nemnulla

ahol

• ::= egy nyelvtani szabály definíciója
• 'c' egy tényleges karakter a szövegben
• | opció (vagy az egyik elem van ott, vagy a másik)
• + egy, vagy több ugyanolyan elem
• () egy együtt kezelt egység (ua. mint algebrában)
• egymás után írt szimbólumok pedig egymást kell kövessék a szövegben.

Többféle EBNF alak létezik, mi most a W3C konzorcium szabványát használjuk.

összeg ::= szám (('+' | '-') szám)*

A * tetszőleges számú (akár 0) ismétlést jelent.

A minta illeszkedik (match) ezekre a példákra:

2
234 + 14
1278 - 897
788 + 567 - 34

Fontos a precedencia: hogyan tudjuk bevezetni a szorzást/osztást?!

Nem vezethetjük be a '+' és '-' alternatívájaként:

kifejezés ::= szám (('+' | '-' | '*' | '/') szám)*

Így nem érvényesül az, hogy pl. a

2 + 3 * 6

Ötlet: legyen a szorzás és osztás egy különálló egység, így azokat egyben kezeli az értelmező.

Ez azt jelenti, hogy egy új szabályt vezetünk be a szorzás és osztás számára.

kifejezés ::= összeg
összeg    ::= szorzat (('+' | '-') szorzat)*
szorzat   ::= szám    (('*' | '/') szám)*

Nézzük meg, hogy hogyan értékelődik ki a 2+3*6:

   2        +     3   *    6
 szám           szám     szám
                \___________/
szorzat            szorzat
\________________________/
          összeg

Figyeljük meg, hogy a fenti nyelvtan továbbra is leírja az összes esetet, amit az összeadás/kivonás vizsgálatakor megnéztünk, hiszen a szorzat bármikor leegyszerűsödhet egy egyszerű számmá, amivel visszakapjuk az eredeti, egy szabályból álló nyelvtant.

Ami egy kifejezés értelmezését bonyolulttá teszi, az a zárójel!

Minden zárójelen belül egy új kifejezés van: úgy kell értelmezni, mint az egészet, és önálló egységként kell kezelni. Ezen felül: tetszőleges mélységben egymásba ágyazható kifejezéseket kell értelmeznünk.

Megoldás: új szabályt kell bevezetni a zárójel lekezélésére – ezzel megoldjuk, hogy egy egységként legyen lekezelve (precedencia). Mi lehet egy zárójelpáron belül? Egy új matematikai kifejezés, vagyis a legalacsonyabb szabályunk! Ez egy rekurzió.

kifejezés ::= összeg
összeg    ::= szorzat (('+' | '-') szorzat)*
szorzat   ::= tényező (('*' | '/') tényező)*
tényező   ::= szám | zárójeles
zárójeles ::= '(' kifejezés ')'

Így értelmezhetővé válnak az alábbi alakok is:

2 + 3 * (4 - 8 * 2)
12 * ((3 - 4) * 14)

Már csak ki kéne találni, hogy hogyan tudunk olyan programot írni, amit egy ilyen nyelvtan szerint kiértékel!

int szabaly(char **szoveg, ……… *eredmeny);

Az illesztő függvény általában így néz ki (ez most számjegyet illeszt):

int szamjegy(char **szoveg, char *szamjegy) {
   char *ptxt = *szoveg;               // munkaváltozat

   if (ptxt[0]>='0' && ptxt[0]<='9') { // számjegy?
      *szamjegy = ptxt[0];

      *szoveg = ptxt+1;
      return 1;                        // illeszkedik :)
   }
   else
      return 0;                        // nem illik rá :(
}

A leírt függvényalak könnyűvé teszi a nyelvtanok algoritmizálását.

 ?  Opcionalitás

'-'? szám

char *szoveg = "-223";

if (szabaly_minusz(&szoveg, ………)) {
  /* sikeres illeszkedés feldolgozása */
}

/* további részek feldolgozása */

 *  Tetszőleges számú előfordulás

szám ::= nemnullaszámjegy bármilyenszámjegy*

char *szoveg = "223";

/* előző részek feldolgozása */

while (szabaly_barmilyenszamjegy(&szoveg, ………)) {
  /* első és további illeszkedések feldolgozása */
}

/* további részek feldolgozása */

A működése hasonló a fentihez, csak a szabály illesztése többször is megtörténik. Minden egyes sikeres illesztésnél a szoveg pointer módosul, így a különböző hívások eltérő szövegrészeken dolgoznak.

 +  Legalább egyszeri előfordulás

név ::= vezetéknév keresztnév+

char *szoveg = "Kiss István Pista";

/* előző részek feldolgozása */

if (szabaly_keresztnev(&szoveg, ………)) {
  /* első illeszkedés feldolgozása */

  while (szabaly_keresztnev(&szoveg, ………)) {
    /* további illeszkedések feldolgozása */
  }
}
else
  return 0;  /* nincs illeszkedés! */

 |  Opciók

megszólítás ::= 'Tisztelt' ('Hölgyem'|'Uram')

char *szoveg = "Tisztelt Uram!";

/* előző részek feldolgozása */

if (szabaly_holgyem(&szoveg, ………)
    || szabaly_uram(&szoveg, ………)) {

   /* bármelyik opció teljesül, itt értékeljük ki */

}
else
   return 0;    /* nem illeszkedett! */

/* további részek feldolgozása */

     Egymásra következés

megszólítás ::= 'Tisztelt' címzett

char *szoveg = "Tisztelt Uram!";
char *ptxt = szoveg;

if (szabaly_tisztelt(&ptxt, ………)
    && szabaly_cimzett(&ptxt, ………)) {

   /* illeszkedés feldolgozása */

}
else
   return 0;    /* nem illeszkedett! */

/* további részek feldolgozása */

Buktató: vegyes logikai kifejezések?

if ((tisztelt(&szoveg, ………) && nev(&szoveg, ………))
    || hello(&szoveg, ………)) {
  /* illeszkedés feldolgozása */
}

Ha tisztelt() illeszkedik, de nev() nem, akkor megpróbálja hello()-t illeszteni, de tisztelt() elállította a mutatót! Ilyenkor vissza kell állítani a mutatót a szöveg elejére az ÉS kapcsolat sikertelensége esetén, és utána lehet megpróbálni hello()-t illeszteni.

Buktató: ciklusban egymásra következés?

while (szabaly1(&szoveg, ………) && szabaly2(&szoveg, ………) {
    /* illeszkedés feldolgozása */
}

int osszeg(char **szoveg, int *ertek) {
   char *ptxt = *szoveg;
   int val;

   if (szorzat(&ptxt, &val)) {
      int val2; char c;

      while (pluszminusz_szorzat(&ptxt, &c, &val2)) {
         if (c == '+') val += val2;
         else val -= val2;
      }
      *ertek = val;
      *szoveg = ptxt;
      return 1;
   }
   return 0;
}

Példa bemenet:

3+4*5

A cellák kiértékelése

Kiértékelés menete pl. B2-re:

B2 → B1
   → B5 → B4

kiszamol(cellacím) {
    HA (van cella hivatkozás) {
        kiszamol(hivatkozott cella);
    }

    cella érték beállítása;
}

	A	B
1
2

A1→B1→C2→A1

Javított bejárás

logikai kiszamol(cellacím) {
    HA (jártunk itt) VISSZA HAMIS;

    cella megjelölése;    +jel

    HA (van cella hivatkozás) {
        HA (!kiszamol(hivatkozott cella)) VISSZA HAMIS;
    }
    cellaérték beállítása;

    cellajelölés törlése; -jel

    VISSZA IGAZ;
}

Maga a táblázat egy kétdimenziós tömb:

typedef struct tablazat {
    cella **adat;           /* 2D din. tömb */
    int szelesseg;
    int magassag;
} tablazat;

A táblázat egy cellája:

typedef struct cella {
    char *tartalom;         /* din. sztring */

    double cachelt_ertek;   /* ne kelljen többször */
    int kiszamolva;

    int mar_jartunk_itt;    /* bejáráshoz */
} cella;

int cella_kiszamol(tablazat *a_tablazat, int sor, int oszlop) {
    cella *a_cella = &a_tablazat->adat[sor][oszlop];

    if (a_cella->mar_jartunk_itt) return 0;             // körkörös!
    if (a_cella->kiszamolva) return 1;     // már kész

    a_cella->mar_jartunk_itt = 1;

    double ertek;
    if (kiertekel(a_cella->tartalom, &ertek, a_tablazat)) { // ok?
        a_cella->cachelt_ertek = ertek;
        a_cella->kiszamolva = 1;
        a_cella->mar_jartunk_itt = 0;
        return 1;                                           // ok!
    }

    a_cella->mar_jartunk_itt = 0;
    return 0;                                               // hiba
}

Escher

A cella_kiszamol() hívja a kiertekel()-t:

… és a kiertekel() hívja a cella_kiszamol()-t. Kölcsönös rekurzió!

Csak akkor írhatunk bele, ha nem viszünk be körkörös hivatkozást:

void cella_modosit(tablazat *a_tablazat, int sor, int oszlop,
                   char *tartalom) {
   char *regi = a_tablazat->adat[sor][oszlop].tartalom;
   char *uj = (char *) malloc(strlen(tartalom) + 1);
   strcpy(uj, tartalom);

   /* megpróbáljuk betenni az újat */
   a_tablazat->adat[sor][oszlop].tartalom = uj;
   /* sikerült? */
   if (cella_kiszamol(a_tablazat, sor, oszlop)) {
      free(regi);
   } else {
      free(uj); // hiba!
      a_tablazat->adat[sor][oszlop].tartalom = regi;
   }
}

Minden modul mutassa a lehető legkisebb felület!

#include "tablazat.h"

int kiertekel(char *szoveg, double *ertek,
              tablazat *a_tablazat);

Az elemző többi függvénye statikus – tehát a modulra nézve lokális.

#include "elemzo.h"

static int szokoz(char **txt) {...}
static int karakter(char **txt, char const *vals, char *talalat) {...}
static int szam(char **txt, double *val) {...}
static int cellacim(char **txt, char *oszl, int *sor) {...}
static int osszeg(char **txt, double *val, tablazat *tabla) {...}
static int szorzat(char **txt, double *val, tablazat *tabla) {...}
static int tenyezo(char **txt, double *val, tablazat *tabla) {...}
static int zarojeles(char **txt, double *val, tablazat *tabla) {...}

Miért jó, ha így csináljuk? Két okból. Egyrészt, aki használja az elemzőt, nem kell gondolkodjon, hogy a sok számára érthetetlen függvény közül melyiket kell hívja. Egy függvény érhető el, a kiertekel(). Másrészt a fejlécfájlt más forrásba is beillesztjük, ezért ha változik, azokat a forrásokat is újra kell fordítani. Ha a kifelé nem mutatott részeket nem írjuk bele, akkor az ottani változtatások miatt nem kell feleslegesen sok mindent újrafordítani a programban.

Utasítás: kiir
---+-----------+-----------+-----------+-----------+-----------+
   |     A     |     B     |     C     |     D     |     E     |
---+-----------+-----------+-----------+-----------+-----------+
 0 | Osszetevo | Rum       |        12 | Ft/ml     |           |
 1 |           | Cola      |         2 | Ft/ml     |           |
 2 | CubaLibre |           |       800 | Ft        |           |
 3 |           |           |           |           |           |
 4 |           |           |           |           |           |
---+-----------+-----------+-----------+-----------+-----------+

Utasítás: vizsgal c2

C2:  =C0*50+C1*100

Utasítás: _

Epilógus

Egy C99 függvény belsejében elhelyezhetünk egy Web címet:

#include <stdio.h>

int main() {
    int i;

    i = 0;

    http://infoc.eet.bme.hu/
    printf("Helló, InfoC!\n");
    i++;

    if (i<10) goto http;

    return 0;
}

Ez azért van, mivel a kettősponttal egy címkét jelölhetünk meg a kódban, ahova a goto utasítással lehet ugrani. A címke neve itt http lesz – így az if()-fel és a goto http-vel egy hátultesztelő ciklust valósítunk meg. Természetsen a címkék neve egyedi kell legyen, tehát egy függvényben csak egy http:// kezdetű címünk lehet.

A void typedef-elhető:

typedef void Ize, Semmi;

Semmi foreach(Ize *ettol, Ize *eddig, Semmi (*fv)(Ize *),
              Semmi (*kov)(Ize **)) {
    for (Ize *iter = ettol; iter != eddig; kov(&iter))
        fv(iter);
}

Semmi intkiir(Ize *pi) {
    printf("%d ", *(int *)pi);
}

Semmi intptrnovel(Ize **pi) {
    ++ *(int **)pi;   /* here be dragons */
}

foreach(tomb, tomb+5, intkiir, intptrnovel);

int main() {
    int a[] = { 0, 10, 20, 30, 40, 50 };

    /* drunk, fix later */
    printf("%d", 3[a]);

    return 0;
}

Tipp: az összeadás kommutatív: tagjai felcserélhetőek.

int main() {
    int c;

    c = 1["Hello"];
    printf("%c", c);

    return 0;
}

A sztring C-ben: csak egy karaktertömb, semmi más.

#include <stdio.h>
main(t,_,a) char *a; {
return!0<t?t<3?main(-79,-13,a+main(-87,1-_,main(-86,0,a+1)+a)):
1,t<_?main(t+1,_,a):3,main(-94,-27+t,a)&&t==2?_<13?
main(2,_+1,"%s %d %d\n"):9:16:t<0?t<-72?main(_,t,
"@n'+,#'/*{}w+/w#cdnr/+,{}r/*de}+,/*{*+,/w{%+,/w#q#n+,/#{l+,/n{n+,/+#n+,/#\
;#q#n+,/+k#;*+,/'r :'d*'3,}{w+K w'K:'+}e#';dq#'l \
q#'+d'K#!/+k#;q#'r}eKK#}w'r}eKK{nl]'/#;#q#n'){)#}w'){){nl]'/+#n';d}rw' i;#\
){nl]!/n{n#'; r{#w'r nc{nl]'/#{l,+'K {rw' iK{;[{nl]'/w#q#n'wk nw' \
iwk{KK{nl]!/w{%'l##w#' i; :{nl]'/*{q#'ld;r'}{nlwb!/*de}'c \
;;{nl'-{}rw]'/+,}##'*}#nc,',#nw]'/+kd'+e}+;#'rdq#w! nr'/ ') }+}{rl#'{n' ')# \
}'+}##(!!/")
:t<-50?_==*a?putchar(31[a]):main(-65,_,a+1):main((*a=='/')+t,_,a+1)
:0<t?main(2,2,"%s"):*a=='/'||main(0,main(-61,*a,
"!ek;dc i@bK'(q)-[w]*%n+r3#l,{}:\nuwloca-O;m .vpbks,fxntdCeghiry"),a+1);
}

Hogy működik? Reverse Engineering the Twelve Days of Christmas.

Ehhez hasonló C kódokat a The International Obfuscated C Code Contest oldalon lehet találni. Ők minden évben megrendeznek egy versenyt, hogy ki tud olvashatatlanabb C kódot írni.

#define ever (;;)

for ever {
    printf("I ♥ U\n");
}

A struct és a union szintaktikája „vészesen” hasonlít egymásra:

struct szamok {
    int i;
    double d;
};

union szamok {
    int i;
    double d;
};

Tehát a teendők:

• Bekapcsolni a szobatárs gépét
• Megkeresni a fejlesztőkörnyezet stdio.h-ját
• Beírni az elejére: #define struct union
• Várni a hatást :D