A paraméteres kifejezések ismételt kiértékelése a számológépben

A szintaxis fákkal foglalkozó korábbi írásokban (Szintaxis fák, Változók használata) felépítettünk egy számológép programot, ami a beolvasott matematikai kifejezéseket egy szintaxisfává alakítja, majd kiértékeli.

A program a második írás végére már képessé vált változók kezelésére és ehhez kapcsolódóan belekerült az értékadó operátor, amely nagyon hasonlóan működött a C nyelvben megtalálhatóhoz. Az egyetlen különbség az volt, hogy nem volt láncolható, tehát az a = b = c = 5 alakú kifejezéseket nem tudta kiértékelni.

Egy másik hiányossága volt a bemutatott számológépnek, hogy nem tudta visszahívni a beírt paraméteres kifejezéseket. Pedig nagyon hasznos lehet egy összetett kifejezés újraszámolása megváltozott változóértékekkel. Ehhez mindössze annyit kell tenni, hogy el kell menteni a szintaxisfa gyökerének a címét egy tárolóba.

Jelen írásban a fenti két problémára keresünk megoldást és közben áttekintünk egy-két újabb nyelvészeti érdekességet.

A számológépünk legutóbbi verziója által felismert nyelvtan a következőképpen néz ki:

értékadó_kifejezés ::= ( változónév '=' )? összeg
összeg    ::= szorzat (('+' | '-') szorzat)*
szorzat   ::= tényező (('*' | '/') tényező)*
tényező   ::= szám | változónév | zárójeles 
zárójeles ::= '(' értékadó_kifejezés ')'

A láncolás itt azért nem tud működni, mert az értékadás (változónév '=') egy opcionális elem, tehát vagy egyszer, vagy egyszer sem fordul elő, utána pedig egy összeg következik. Az összeg leegyszerűsödhet a szorzaton és tényezőn keresztül egy zárójeles kifejezéssé, ami pedig lehet egy újabb értékadás, de ekkor már zárójelek között.

Tehát a fenti nyelvtan az értékadó operátor láncolását az következő alakban tudta értelmezni: a = (b = (c = 5)).

Először tehát azt kell kitalálnunk, hogy miként tudnánk a nyelvtanunkban megfogalmazni azt, hogy tetszőleges számú értékadás állhat egymás után.

Erre két megoldás is létezik. Az első – a nyelvtan szintjén egyszerűbb – az, hogy az értékadás opcionalitását lecseréljük tetszőleges számú ismétlődésre. Ez azt jelenti, hogy a kérdőjelet csillagra cseréljük:

értékadó_kifejezés ::= ( változónév '=' )* összeg
összeg    ::= szorzat (('+' | '-') szorzat)*
szorzat   ::= tényező (('*' | '/') tényező)*
tényező   ::= szám | változónév | zárójeles 
zárójeles ::= '(' értékadó_kifejezés ')'

Így továbbra is meg lehet értékadás nélküli kifejezéseket adni, hiszen a * operátor megengedi a 0-szor való előfordulást is – ahogy ez az összeg és a szorzat esetén is történik.

Van ettől elvben is különböző megoldás erre a problémára: azt mondjuk, hogy az értékadó_kifejezés egy opcionális értékadásból és egy összegből áll, az összeg pedig egy értékadó kifejezés VAGY két szorzat összege:

értékadó_kifejezés ::= ( változónév '=' )? összeg
összeg    ::= értékadó_kifejezés | ( szorzat (('+' | '-') szorzat)* )
szorzat   ::= tényező (('*' | '/') tényező)*
tényező   ::= szám | változónév | zárójeles 
zárójeles ::= '(' értékadó_kifejezés ')'

Így tehát az értékadó kifejezés tartalmazhat egy értkadást, majd egy összeg következik, amely újból lehet egy értékadás plusz egy összeg. Így tulajdonképpen rekurzív módon tetszőleges számú ismétlődést tudtunk megadni.

Amikor végeszakad a láncolásnak, tehát mondjuk az a = b = c = 5 kifejezésben eljutunk az 5-ig, ott az összeg szabályban az értékadó_kifejezés már nem fog illeszkedni és ekkor megpróbálja a szorzatot illeszteni, ami sikerül is, hiszen az a tényezőn keresztül le tud számmá egyszerűsödni.

Az eredeti jelölésrendszerben, amit formális nyelvtanok leírására használtak (BNF) nem szerepeltek a ?, * és + operátorok. Mindent a fent látott, rekurzív módon adtak meg.

Vegyük észre, hogy a kétféle módszer tulajdonképpen ugyannak a problémának az iteratív (cikluson alapuló) illetve rekurziv megoldása. Általánosságban is azt mondtuk, hogy a problémáinkra léteznek iteratív és rekurzív megoldások és mindig az aktuális problémához jobban illő, arra hatékonyabb megoldást adó változatot érdemes használnunk.

Mi most az utóbbit fogjuk választani, mert a programkódunk egyszerűbb lesz, ugyanakkor szembetaláljuk magunkat egy problémával, ami pedig gyakorta előkerül komplexebb nyelvtanokban, ezért érdemes néhány szót szólni róla.

A megvalósítandó nyelvtanunkban csak az összeg szabály módosult, tehát csak a neki megfelelő kódot kell megváltoztatnunk.

A kódolás előtt még bele kell gondolni abba, hogy a szintaxisfa hogyan fog felépülni. Ha egy pillantást vetünk az értékadó_kifejezés kódjára, láthatjuk, hogy az értékadó szimbólum "gyermeke" az a kifejezésfa, amit az összeg szabály épít fel és ad át az értékadó_kifejezésnek:

	...

	if (valtozonev(&munka, nev) && karakter(&munka, "=", &kar)) {
		van_ertekadas = 1;
	}
	else munka = *szoveg;


	if (osszeg(&munka, &kifejezes)) {
		if (van_ertekadas) {
			*ast = uj_ertekadas(nev, kifejezes);
		}

	...

Ha tehát az összeg szabály egy értékadó_kifejezés által alkotott fával is vissza tud majd térni, akkor az a = b = 5 alak úgy fog kiértékelődni, hogy az értékadó_kifejezés feldolgozza az a = szövegrészletet, majd a további részeket átadja az összegnek, ami ismét megpróbálja értékadásként értelmezni. A másodjára meghívott ertekado_kifejezes előállítja a b = 5 kifejezésnek megfelelő részfát, amit az elsőnek meghívott ertekado_kifejezes el fog menteni, mint a létrehozott ertekadas szimbólum kifejezése. Így jön létre az ábrán látható szintaxisfa.

A kiértékelés helyesen fog működni, hiszen az a = szimbólum lekérdezi az általa tárolt kifejezés értékét. Ez a kifejezés a b = 5, ami a kiértékelés során egyfelől eltárolja a b változóban az 5-ös értéket, másfelől vissza is adja ezt, tehát az a = kifejezés is 5-öt kap értékül.

Valósítsuk meg a nyelvtanunk által előírt működést az osszeg függvényben! Tulajdonképpen mindössze annyit kell tennünk, hogy megpróbáljuk a szöveget értékadó kifejezésként értelmezni. Ha sikerült, akkor a visszaadott részfa lesz a visszatérési értékünk, hiszen a kapott értékadó kifejezést így tudjuk hozzáláncolni a korábbihoz. Ha pedig nem sikerült, akkor két szorzat összegét próbáljuk illeszteni – ahogy azt tettük eddig is:

static int osszeg(char **szoveg, szimbolum **ast) {
  ...

  szokoz(&munka);
  
  if (ertekado_kifejezes(&munka, ast)) {
    *szoveg = munka;
    return 1;
  }

  if (szorzat(&munka, &op1)) {
    while (karakter(&munka, "+-", &kar)) {
      if (szorzat(&munka, &op2)) {
        uj = uj_muvelet(kar);
        uj->op1 = op1;
        uj->op2 = op2;

        op1 = uj;
      }
      else return 0;
    }

    if (uj == NULL) *ast = op1;
    else *ast = uj;
    
    *szoveg = munka;
    return 1;
  }
  else {
    return 0;
  }
}

Ha megpróbáljuk így futtatni a programunkat, akkor végtelen rekurzióba kerül és a stack beteltekor az operációs rendszer leállítja. Próbáljuk meg megfejteni a hiba okát!

Ehhez a nyelvtanhoz kell visszanyúlnunk.

értékadó_kifejezés ::= ( változónév '=' )? összeg
összeg    ::= értékadó_kifejezés | ( szorzat (('+' | '-') szorzat)* )
szorzat   ::= tényező (('*' | '/') tényező)*
tényező   ::= szám | változónév | zárójeles 
zárójeles ::= '(' értékadó_kifejezés ')'

Próbáljuk meg végigkövetni, hogy mi történik az „a = b = 5” szövegrészlet elemzésekor! Az elemző meghívja az ertekado_kifejezes() függvényt, ami ráilleszt az „a =” szövegrészletre, majd meghívja az osszeg() függvényt. Ő ismét meghívja az ertekado függvényt, ami megtalálja az újabb értékadást – a „b =” részletet és a maradékra meghívja az osszeg()-et, ami természetesen azzal kezd, hogy meghívja az ertekado_kifejezes()-t. Ez utóbbi már nem talál tovább értékadást, így rögtön meghívja az osszeg()-et, ami az ertekado_kifejezes()-t és így tovább, amíg csak be nem telik a függvényhívási stack.

A problémát a programkód szintjén tulajdonképpen az okozza, hogy nincs báziskritériuma a rekurziónak, tehát nincs olyan feltétel, ami leállítaná a két függvény kölcsönös hívását.

A megoldást az jelentené, ha az osszeg csak akkor hívná meg az ertekado_kifejezes()-t, ha tényleg szükség van rá, tehát tényleg egy következő értékadás szerepel a kifejezésünkben és nem egy összeg.

Az első ötletünk az lehet, hogy cseréljük fel a két vizsgálatot, először próbáljunk összeget találni és ha az nem sikerült, akkor nézzük meg, hogy nem egy értékadással van-e dolgunk. Itt észrevehetjük azt, hogy bár a VAGY-kapcsolatban elvben felcserélhetőek az operandusai, hiszen a kifejezés értéke a sorrendtől teljesen független, de a nyelvtanok esetében (és a C nyelvben a logikai rövidzár miatt) ez mégsincs így.

Az elgondolásunk azonban nem jó eredményre vezet, az „a = b = 5” kifejezésünk „a = b”-ként lesz értelmezve a végén lévő „= 5”-tel pedig nem tud mit kezdeni az értelmező. Ennek az az oka, hogy ebben az esetben a ertekado_kifejezes() az „a =”-ig jut el, majd a további részt az osszeg()-re bízza, ami pedig először szorzatként próbálja meg értelmezni a fennmaradó szöveget. A szorzat a tényezőn keresztül le tud egyszerűsödni változónévvé, ami sikeresen illeszkedik a „b”-re és ezen a ponton félrecsúszik az értelmezik, hiszen az értelmező a fennmaradó részben először *-ot vagy /-t, majd +-t vagy --t keres és amikor egyiket sem találja, akkor úgy dönt, hogy egy egytagú összeggel volt dolga és itt befejeződik a kifejezés.

A nyelvtanunk tehát helyes, az értelmezőnk azonban nem tudja feldolgozni a kifejezést. Más irányban kell elindulnunk. Azt mondtuk, hogy csak akkor szabadna meghívni az osszeg()-ből a ertekado_kifejezes()-t, ha biztosak vagyunk benne, hogy egy értékadás következik. Tegyünk így!

Tipikus technika az értelmezők írásakor, hogy "csalunk" és előreolvasunk a szövegben. Ha biztosan értékadás következik, akkor megpróbálhatunk értékadást értelmezni!

Azt már láttuk, hogy az értelmező függvényeket, amik rekurzív hívásokat hajtanak végre és módosítják a szintaxisfát, csak óvatosan szabad meghívni, hiszen olyan módosításokat vihetnek végbe, amik vakvágányra vihetik az elemzést.

Ugyanakkor vannak egyszerű szövegelemző függvényeink is, amelyek nem hívnak további elemző függvényeket, tulajdonképpen nem a szimbólumok szintjén dolgoznak, hanem egy adott szimbólumot próbálnak felismerni a karakterek szintjén. Az ilyen funkcionalitást szoktuk átfogóan lexernek hívni szemben az értelmező, parser függvényekkel.

Lexer függvényeket tehát bátran hívhatunk, hiszen azok csupán a munka pointert állítják el, ami könnyedén vissza tudunk állítani, ha nem volt illeszkedés.

Az egy értékadás (változónév és '=' karakter) előreolvasó osszeg() tehát a következőképpen néz ki:

static int osszeg(char **szoveg, szimbolum **ast) {
  char *munka = *szoveg, *eloreolvaso;
  char kar, vnev[51];
  szimbolum *op1, *op2, *uj = NULL;

  szokoz(&munka);
  
  eloreolvaso = munka;
  if (valtozonev(&eloreolvaso, vnev) && karakter(&eloreolvaso, "=", &kar)) {
    if (ertekado_kifejezes(&munka, ast)) {
      *szoveg = munka;
      return 1;
    }
  }

  if (szorzat(&munka, &op1)) {
    while (karakter(&munka, "+-", &kar)) {
      if (szorzat(&munka, &op2)) {
        uj = uj_muvelet(kar);
        uj->op1 = op1;
        uj->op2 = op2;

        op1 = uj;
      }
      else return 0;
    }

    if (uj == NULL) *ast = op1;
    else *ast = uj;
    
    *szoveg = munka;
    return 1;
  }
  else {
    return 0;
  }
}

Látható, hogy mivel az előreolvasás során elállított pointer értéke minket nem érdekel, ezért látrehozunk egy ideiglenes változót (eloreolvaso), amit a két lexer függvénynek (valtozonev és karakter) adunk át, de az értékét sehol másutt nem használjuk fel. Ez azért lehetséges, mert ha sikeres volt az előreolvasás, akkor a stringet a kezdeti pozíciótól kezdve adjuk át az ertekado_kifejezes()-nek, ha pedig nem akkor a szorzat() kapja meg, szintén az eredeti pozíciótól.

Gyakori számítási feladatokban, hogy ugyanazt a kifejezést (pl. másodfokú egyenlet megoldóképlete) szeretnénk kiértékeli különböző változóértékekkel. Hasznos lenne tehát, ha erre képes lenne a programunk.

Igazából programozói szempontból ez a feladat nem jelent kihívást. Minden kiértékelés során előáll a szintaxisfa, ami változóhivatkozásokat tárol és nem konkrét változóértékeket, így ha egy későbbi időpontban meghívjuk a fát kiértékelő függvényt (ast_kiertekel()), akkor az a változók aktuális értékét fogja használni.

Mindössze annyit kell tehát tennünk, hogy eltároljuk a szintaxisfákat és visszahívhatóvá tesszük őket.

Ehhez két dolgot kell még biztosítanunk. Az első, hogy valahogyan hivatkozhatóvá kell tennünk a paraméteres kifejezéseket. Ennek a legegyszerűbb módja az, hogy megszámozzuk őket. Itt csak arra kell vigyáznunk, hogy egy kifejezést csak akkor tároljunk el és ezzel együtt a számlálót csak akkor növeljük, ha sikeres volt a kiértékelés. Tehát csak helyes fákat mentünk el, így az újbóli kiértékeléskor hibakezeléssel már nem kell törődnünk.

A másik dolog egy kényelmi szolgáltatás. A visszahívott kifejezés szövegét illik kiírni, hogy könnyebb legyen a számításokat áttekinteni. Ez nem triviális feladat, ugyanis a fában a felépítés tárolja a kiértékelési sorrendet, tehát a zárójelek egészen absztrakt és nehezen visszafejthető módon vannak jelen. Az eredetileg beírt szöveget tehát meglehetősen nehéz lenne visszanyerni a szintaxifából. Éppen ezért ezzel meg sem próbálkozunk. Ehelyett, vállalva, hogy egy kicsit terheljük a memóriát, eltároljuk a kifejezéseink szövegét is, bár azokat többé nem értékeljük ki, mindössze arra használjuk őket, hogy megjelenítsük az kifejezést, amikor a hozzá tartozó szintaxisfát újból kiértékeljük.

Így az adatszerkezetünk a következképpen néz ki:

typedef struct kifejezesek {
  char szoveg[255];
  szimbolum *ast; 
  struct kifejezesek *kovetkezo;
} kifejezesek;

A tárolás pedig egy láncolt listában történik. A visszahíváskor a ismetel utasítás után beírt sorszámnak megfelelő listaelemet keressük meg.

A teljes kód letölthető innen.