Þessi grein er hugsuð sem viðbót við greinina „Forrita reiknivél með binary tree (C/C++)“ eftir wolfy (birt 7. október 2008). Þar sem sú grein er orðin frekar gömul ákvað ég frekar að skrifa nýja grein í staðin fyrir að senda inn svar/álit við þeirri grein.
Beinn hlekkur á greinina er hér: http://www.hugi.is/forritun/articles.php?page=view&contentId=6183347


Ég útfærði reiknivél sem hefur sömu virkni og reiknivélin í hinni greininni (og er útskýrð þar), nema ég notaði aðra aðferð sem byggir á endurkvæmni (e. recursion).
Ég notfærði mér fræði um samhengisóháð mál (e. context free languages hér eftir CFL) og samhengisóháða málfræði (context free grammar hér eftir CFG).
Ef þú þekkir ekki hugtakið CFG mæli ég með að lesa greinina http://en.wikipedia.org/wiki/Context_free_grammar.
Þar er sérstaklega dæmi 3 (example 3) sem er mjög svipað reiknivélinni sem er hér til umfjöllunar, fyrir utan að málfræðin í því dæmi gefur ekki margföldun og deilingu hærri forgang heldur en samlagningu og frádrætti.
CFG og CFL eru yfirleitt fjallað um í námskeiðum um formleg mál og/eða námskeiðum um þýðendur sem eru kennd víða á tölvutengdum námsbrautum.

Allir stengir sem reiknivélin samþykir og getur reiknað út úr tilheyra ákveðnu CFL. Ég get lýst því á eftirfarandi hátt með með CFG (nota BNF):
( http://en.wikipedia.org/wiki/Backus%E2%80%93Naur_Form )

<expr>   ::= <term> | <term>"+"<expr> | <term>"-"<expr>
<term>   ::= <factor> | <factor>"*"<term> | <factor>"/"<term>
<factor> ::= <num>  | "("<expr>")" | "(-"<expr>")"
<num>    ::= <digit> | <digit><num>
<digit>  ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

(expr er segð, term er liður, factor er þáttur og num er strengur sem inniheldur eitt eða fleiri tölutákn og digit er stakt tölutákn).

Þar sem mig grunar að mörgum gæti þótt tormelt að skilja þetta CFG þá ætla ég að sýna CFG fyrir einfaldari útgáfu af reiknivél sem er vonandi auðveldara að átta sig á og auðveldar síðan að skilja flóknari reiknivélina í framhaldinu.

Einfaldari reiknivélin leggur bara saman tvo liði (getur s.s. lagt saman 1+2 en ekki 1+2+3), og margfaldar bara tvo þætti (og styður ekki sviga).
Hér er CFG fyrir einfaldari reiknivélina:
<expr>   ::= <term>  | <term>"+"<term> 
<term>   ::= <factor> | <factor>"*"<factor>
<factor> ::= <num>
<num> og <digit> eru eins og í fyrra dæiminu


Eins og kemur fram í wikipediugreininni um CFG (ef hún hefur ekki breyst mikið milli þess sem þetta er skrifað og þess sem þetta er lesið), þá er hægt að búa til svo kölluð parse tree þegar maður les strengi og kannar hvort þau séu í viðkomandi CFL.
Tvíundartrén (e. binary trees) sem var fjallað um í greininni eftir wolfy voru í raun dæmi um parse tree.

Aðferðin sem ég nota byggir hinsvegar á endurkvæmni (hún kallast recursive decent parser) þannig að ég þarf ekki að búa til gagnagrind (data structure) fyrir tré eða hnúta heldur mynda endurkvæmnuköllinn sjálfkrafa tré sem er í rauninni parse tréð (sjá dæmi og útskýringu á um trjá endurkvæmni á http://mitpress.mit.edu/sicp/full-text/sicp/book/node16.html ).

(Ég sá í athugasemdunum við fyrri greinina að menn minntust á að það væri hægt að nota stafla (stack) til að parsa “matched parenthesis”, en það má þess geta að CFL (sem hafa tilheyrandi CFG) eru mjög oft pörsuð með pörsurum (er til íslenskt orð yfir parser?) sem byggja á svokölluðum staflavélum (e. push down automata eða PDA) sem eru stöðuvélar (e. statemachines eða automata) sem hafa stafla (e. stack). Ég ætla þó ekki að fara nánar út í það hér.)

Það sem er svolítið sérstakt við aðferðina sem ég nota er að einungis einn stafur er lesinn í einu úr inntaks strengnum (eins og LL(1) parser gerir) og strengurinn er bara lesinn einu sinni í gegn. Það er aldrei leitað í gegnum strenginn eða neitt þannig.

Recursive decent parser virkar þannig að það er eitt fall, fyrir hvert non-terminal tákn í málfræðinni. Hvert slíkt fall kallar á önnur slík föll ef production-in innihalda önnur non-terminal tákn.
Ég setti upp málfræðina þannig að það er alltaf sama non-terminal táknið eða eitthvert terminal tákn lengst til vinstri í hverju production-i og því er alltaf hægt að vita hvaða fall á að kalla á, hverju sinni með því a. (það þarf sem sagt aldrei að kalla á tvö föll (eða fleiri) og sjá hvort annað þeirri skili réttri niðurstöðu og nota hana svo þá niðurstöðu og henda hinni).
Það sem ég gerði að auki var að láta föllin reikna endurkvæmt gildið, þannig að skilagildið á factor() fallinu er gildið (talan) á þættinum og skilagildi term() er gildið á liðnum (og þá er kannski búið að margfalda saman þætti í liðinum).

Hér er kóðinn:
#include <stdio.h>
int term(char *c); // defined later
int num(char *c);
int isnum(char c) // checks if char is a number
{
   if (c >= '0' && c <= '9' )
      return 1;
   return 0;
}
int ctoi(char c) // converts char to number
{	
   return c-'0';
}
int expr(char *next, char sign)
{
   int res = term(next); 
   if (sign == '-') // make sure only one term gets negative value for every symbol
   res = -res;
   if ( *next == '+' )
   {
      scanf("%c", next);
      return res + expr(next,'+'); // reduce	 <expr> ::= <term>'+'<expr>
   }
   else if (*next == '-')
   {
      scanf("%c", next);
      return res + expr(next,'-');	 // reduce	<expr> ::= <term>'-'<expr>
   }
   else if (*next == '\n' || *next == ')')
      return res;	// reduce expr ::= <term>
   else
   {
      perror("Error parsing expr, illegal character after term nonterminal");
   }
   return 0;	
}
int factor(char *next)
{
   int res;
   if (*next == '(')	// <factor> ::= '('<expr>')'
   {
      scanf("%c",next);
      if (*next == '-') // unary minus
      { 
         scanf("%c",next);
         res = expr(next,'-');
      }
      else			
         res = expr(next,'+');
	 
      if ( *next == ')')
      {
         scanf("%c",next);
      }
      else
         perror("Error parsing factor, unmached parenthesis");
   }
   else if (isnum(*next)) // <factor> ::= <num
   {
      res = num(next);
   }
   else
      perror("Error parsing factor");
   return res;
}
int term(char *next)
{
   int res;
   res = factor(next);
   if (*next == '*')
   {
      scanf("%c",next);
      res = res * term(next); // <term> ::= <factor>'*'<term>
   }
   else if (*next == '/')
   {
      scanf("%c",next);
      res = res / term(next); //	 <term> ::= <factor>'*'<term>
   }
   else if (*next == '\n' || *next == '+' || *next == '-' || *next == ')' )
   {
      res = res; // <term> ::= <factor>
   }
   else
      perror("Error: found in term ");
   return res;
}
int num(char *next) // parse a number
{
   int res = 0;
   while (isnum(*next))
   {
      res = res*10 + ctoi(*next);
      scanf("%c",next);
   }
   return res;
}
int main()
{
   char next;
   int res;
   printf ("write an expression to be evaluated or \"q\" to quit\n"); 
   while (1)
   {
      scanf("%c", &next);
      if (next == 'q' || next == EOF)
         break;
      if (next == '-') // check if unary minus
      {
         scanf("%c", &next);
         res = expr(&next,'-');
      }
      else
         res = expr(&next,'+');
      printf("result: %d\n",res);
   }
}


Mæling á hraða:
Vegna þess að í athugasemdum við hina greinina voru menn að nefna hve hratt reiknivél gat reiknað út úr strengnum “(2+2)*2” því ákvað ég að hafa það með hér hraða mælingu á nokkrum strengjum:
Þar sem ég notaði scanf() til að lesa úr stdin þá bjó ég til skrá sem innihélt sama strenginn endurtekinn milljón sinnum og notaði posix skipunina “time” til að mæla tíman.

Strengurinn “1” tók 0,24 sek. (ca 5 milljón sinnum á sek).
Strengurinn “(2+2)*2” tók 0,94 sek (ca milljón sinnum á sek)
Strengurinn “((2+32)*3)-92*(2+(54+(17*(8/4+2))))” tók 4,54 sek (ca 200 þúsund sinnum á sek).
Strengurinn “1+2*(3+4)-6*(7-8)*9*(10-11)+((((((((((12-13)*14)-15)*18)-19)*20)+21)*22+23)-25)*26)” tók 10,7 sek. (tæplega 100 þúsund sinnum á sek).

Prófanir voru gerðar tölvu með intel core duo 2GHz örgjörva. (meira en 3 ára)

Það er hægt að sjá að reiknivélin hefur flækjustigið O(n) (ég get rökstutt það ef einhver biður um það) og þessar hraða mælingar passa vel við það.


Vankantar
- a/b/c reiknast sem a/(b/c) (venjan er held ég að reinkivélar reikni a/b/c sem (a/b)/c en það er held ég bara skilgreiningar atriði).
- Hún styður heldur ekki veldi eins og reiknivélin sem Polarina minntist á í athugasemdum við hinni greininni.
- Ég eyddi ekkert miklum tíma í að villuprófa forritið og reyna að hugsa út allar mögulegar villur (ég pældi samt aðeins í því). Ég læt nægja að prenta bara út villuskilaboð (með perror) þegar villur koma fyrir.
-Reiknivélin reiknar bara með heiltölur, markmiðið mitt var aðalega áskorunin að nota þessi fræði til að búa til reiknivél, frekar en að búa til tól er þægilegt að nota (usability). Það er ekkert svo mikið mál að betrumbæta reiknivélina og láta hana ráða við fleytitölur líka.


Lokaorð
Það kæmi mér ekki á óvart að mörgum þyki þessi grein tormelt, sérstaklega þeim sem hafa ekki lært mikið (eða jafnvel ekkert) um formleg mál.
Ég vona þó að einhverjum hafi þótt þessi grein gagnleg, fróðleg eða jafnvel skemmtileg.